مقدار تكرارات الحلقة المتوقعة عند البحث في مصفوفة باستخدام فهرس عشوائي

Question

لنفترض أن لدينا مصفوفة 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 كما هو موضح أعلاه.

Answer 1

يترك $ن$ يكون هندسيًا 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]$.