Algorithms/Randomized Algorithms

الخوارزمية العشوائية هي الخوارزمية التي تستخدم عددًا عشوائيًا لتقرّر الخطوة التالية في سير عملها، فعلى سبيل المثال خوارزمية الترتيب السريع العشوائية Randomized Quick Sort، تستخدم الخوارزمية عددًا عشوائيًا لاختيار المحور التالي (أو لتغيير مواقع العناصر في المصفوفة عشوائيًا). يُستفاد من العشوائية عادةً في التقليل من التعقيد الزمني والتعقيد المكاني في الخوارزميات العادية.

مقدمة رياضية

الاحتمالية المشروطة P(A | B)‎ هي احتمالية وقوع الحدث 'A' على افتراض وقوع الحدث 'B' قبله.

P(A|B) = \frac{P(A\cup B)}{P(B)} 

يمكن الاستعانة بالشكل التالية لفهم الصيغة السابقة، إذ لمّا كان الحدث 'B' قد وقع بالفعل، فإنّ فضاء العينة سيتقلّص إلى 'B' فقط؛ ولهذا فإنّ احتمالية وقوع الحدث 'A' ستصبح P(A ∩ B)‎ مقسومًا على P(B)‎.

تربط علاقة بايس Bayes’s forumla بين الاحتماليتين المشروطتين P(A|B)‎ و P(B|A)‎.

 P(A|B) = \frac{P(B|A)P(A)}{P(B)}

المتغيرات العشوائية

المتغير العشوائي هو دالة تربط نتائج حدث عشوائي (مثل رمي العملة المعدنية) بقيمة حقيقية.

مثال:

لعبة رمي القطعة النقدية:

في هذه اللعبة يحصل اللاعب على 50 نقطة إن كانت نتيجة رمي القطعة النقدية (النقش) ويخسر 50 نقطة إن كانت النتيجة (الكتابة).

يمكن تعريف المتغير العشوائي لعدد النقاط النهائي الذي سيحصل عليه اللاعب كما يلي:

Points = +50 if Head
         -50 if Tail

القيمة المتوقعة للمتغير العشوائي

يمكن تعريف القيمة المتوقعة للمتغير العشوائي R بأنّها:

    E[R] = r1*p1 + r2*p2 + ... rk*pk

تمثل ri قيمة R مع الاحتمالية pi.
ويمكن القول بأنّ القيمة المتوقعة هي مجموع حاصل ضرب الطرفين التاليين (لجميع الأحداث الممكنة):

1. احتمالية الحدث
2. قيمة R في ذلك الحدث.

أمثلة:

• القيمة المتوقعة للنقاط في المثال السابق = 50 * (1/2) + (-50) * (1/2) = 0
• والقيمة المتوقعة لرمي زهر سداسي الوجوه = = 1(1/6) + 2(1/6) + .... + 6*(1/6) = 3.5

خطية التوقع Linearity of Expectations

لنفترض أن R1 و R2 متغيران عشوائيان مجرّدان في فضاء احتمالية معين، فإنّ:

     E[R1 + R2] = E[R1] + E[R2]

القيمة المتوقعة لمجموع الأرقام الناتجة من رمي الزهر ثلاث مرات = ‎3 * 7/2 = 10.5‎

عدد المحاولات المتوقع قبل تحقيق النجاح

إذا كانت احتمالية النجاح في كل محاولة هي p فإن العدد المتوقع للمحاولات قبل تحقيق النجاح هو ‎1/p‎.

لنفترض أنّ سنرمي زهرًا سداسي الوجوه إلى حين الحصول على الرقم 5، فإنّ عدد الرميات المتوقعة قبل الحصول على الرقم 5 هو 6 رميات. لاحظ بأنّ احتمالية الحصول على الرقم 5 هي 1/6 في كل رمية، وبهذا يكون عدد المحاولة ‎1/(1/6)‎ = 6‎.

وفي خوارزمية الترتيب السريع والتي تبحث فيها الخوارزمية عن العناصر المحورية إلى أن تختار العنصر الوسطي n/2 فإنّ عدد المحاولات المتوقعة للعثور لاختيار العنصر الوسطي سيكون 2 وذلك لأنّ احتمالية اختيار أحد العناصر الوسطية هو 1/2.

مصادر

• صفحة Randomized Algorithms | Set 0 (Mathematical Background) في توثيق الخوارزميات في موقع GeeksforGeeks.