مقدار تكرارات الحلقة المتوقعة عند البحث في مصفوفة باستخدام فهرس عشوائي
سؤال
لنفترض أن لدينا مصفوفة A بحجم n.يحتوي على 1 كفهرسه الأول وn كفهرسه الأخير.أنه يحتوي على قيمة x، مع حدوث x k مرات في A حيث 1<=k<=n
إذا كان لدينا خوارزمية بحث مثل ذلك:
while true:
i := random(1, n)
if A[i] == x
break
عشوائي (أ، ب) يختار رقما موحدا من أ إلى ب
من هذا نعلم أن فرص العثور على x وإنهاء البرنامج هي k/n مع كل تكرار.لكن ما أود معرفته هو ما هي القيمة المتوقعة لعدد التكرارات أو بشكل أكثر تحديدًا مقدار المرات التي تم فيها الوصول إلى المصفوفة في هذا البرنامج بالنظر إلى المصفوفة A كما هو موضح أعلاه.
المحلول
يترك $ن$ يكون هندسيًا R.V.الذي يُرجع عدد مرات الوصول إلى المصفوفة للبحث عن العنصر، $أ[x]$ حتى نجده بنجاح.نريد أن نعرف $\mathbb{E[N]$.
يمكننا أن ننظر إلى تكرارات حلقة while كسلسلة من تجارب IID Bernoulli، ولكل منها احتمالية $p$ من النجاح، و $س = 1 - ص$ من الفشل.بالنظر إلى السؤال، نريد أن نعرف عدد المحاولات اللازمة للحصول على "النجاح" الذي يتمثل في العثور على العنصر $أ[x]$ وهكذا while
تنتهي الحلقة.
منذ $\Pr\{N = k\} = q^{k-1}p$, ، لدينا هذا $\mathbb{E}[N] = \sum\limits_{k = 1}^\infty k \:ف^{ك-1}ص$.
هكذا، $\mathbb{E}[N] = \dfrac 1p$ أين $p = \dfrac kn$ لذا $\mathbb{E}[N] = \dfrac nk$.
لذلك في المتوسط، يستغرق الأمر $\dfrac nk$ يصل قبل أن نجد العنصر، $أ[x]$.