متوسط ​​عدد عمليات التفتيش

Question

خذ بعين الاعتبار مجموعة من العناصر n التي تكون قيمها الأساسية هي $$0, 1, ..., n−1.$$ يترك $p(i) (0 ≥ i ≥ n−1) $ يكون احتمال البحث عن العنصر الذي يحتوي على المفتاح i.افترض التوزيع التالي لـ $p(i)’s$:

$$p(i) = \begin{cases} 1/2^{n−1}, & \text{if i = 0} \\ 1/2^i, & \text{otherwise} \end{cases}$$

افترض أنه تم استخدام البحث الخطي وأن كل بحث ناجح - فكل عنصر نبحث عنه موجود.

ما هو متوسط ​​عدد العقد التي تم فحصها للبحث ضمن مؤسسة عشوائية (يتم تخزين العناصر الموجودة في القائمة المرتبطة بترتيب عشوائي) وما هو متوسط ​​عدد العقد إذا تم فرزها بناءً على احتماليتها المتناقصة (أي أنها تبدأ بالعنصر) '1'، متبوعًا بالعنصر '2'، ثم '3'، وهكذا، بحيث تحتوي العقدة الأخيرة على العنصر '0'.) بالنسبة لقيم n الكبيرة؟

أعلم أن إجابة الجزء الأول هي بالتأكيد لا $ن/2$(نظرًا لأن الاحتمال ليس هو نفسه بالنسبة لجميع العناصر) لكنني لا أعرف حقًا أكثر من ذلك بكثير ...ولكن عندما فرزها، وأظن أنه ينبغي أن يكون شيئا قريب من ذلك $$\sum_{i=1}^{n-1} i*{1/2^{i}} + n * 1/2^{n-1}$$ لأنه يتطلب مقارنة واحدة للوصول إلى العنصر الأول، واثنين إلى العنصر الثاني، وما إلى ذلك.والأخير يأخذ n مقارنات مضروبة في احتمال 0.لقد وجدت أيضا $$\sum_{i=o}^{∞} أ*ب^أ = ب/(1-ب)^2$$ والتي في هذه الحالة ستكون مساوية لـ 2 (b = 1/2) ولكن ليس لدي أدنى فكرة عن كيفية التعامل مع حالة الحافة - "0".:(

أنا أيضا على علم بذلك هذا الموضوع ولكن هناك كل رقم له نفس الاحتمال ولكنه ليس هو نفسه تمامًا.

آمل أن أجد إجابة لهذا السؤال لأنه كان يزعجني لفترة طويلة وأنا مهتم حقًا بالنتيجة.
أي تلميح سيكون موضع تقدير كبير!

Answer 1

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

لنفترض أن لدينا $ن = 5$ عناصر.لنفترض أنه تم فرزها في الطريق $s = [1، 3، 4، 0، 2]$.ثم باستخدام البحث الخطي سننتقل إلى الاحتمالية $(1/2)^3$ لدينا خطوتين في بحثنا ومع الاحتمال $(1/2)^4$ لدينا 4 خطوات في بحثنا.

إذًا، ما هو متوسط ​​عدد الخطوات التي نحتاجها للعثور على عنصر يعطي فرزًا عشوائيًا $س$؟دعنا نقول $X$ - عدد الخطوات اللازمة في بحثنا.احتمال الحصول على $س=أنا$ الخطوات تعادل طلب البحث عن عنصر $k \في \{0,1,2,..,n-1\}$ إعطاء لدينا في $i$المركز العاشر.إنه $$P(X = i) = \sum_{k=0}^{n-1} P(search\ for\ k\ |\ the\ element\ k\ is\ في \ ith\ Position)P(the\ العنصر\ k\ is\ at\ ith\ Position)$$ ثم نلاحظ ذلك $P(the\ element\ k\ is\ at \ ith\ Position) = \frac{(n-1)!}{n!} = \frac{1}{n}$ لأن لدينا عنصر في موضع ثابت و $(ن-1)!$ التباديل الممكنة للعناصر الأخرى من المجموع $ن!$ التباديل المحتملة لدينا $ن$ عناصر.ثم نلاحظ ذلك $\sum_{k=0}^{n-1} P(search\ for\ k\ |\ the\ element\ k\ is\ at \ ith\ Position) = 1$.هذا يعني انه $P(X=i) = \frac{1}{n}$.لذلك، التوقع هو مجرد $\sum_{k=1}^{n} \frac{k}{n} = \frac{n+1}{2}$.

بالطبع، الجزء الثاني أسهل بكثير في الاشتقاق، إنه مجرد $$E(X|مرتبة\ في\ متناقصة\ الاحتمالية) = \sum_{k=1}^{n-1} \frac{k}{2^{k}} + \frac{n}{2^{ ن-1}}$$ (فقط لاحظ أن العناصر ستكون من $1$ ل $ن-1$ ومن ثم العنصر $0$, ، لكن $0$ يمكن أن يكون العنصر قبل الأخير لأنه له نفس الاحتمال $ن-1$).لذلك، نحن فقط نحسب توقع التوزيع الاحتمالي، على الرغم من أنه هذه المرة ليس للاحتمال المشترك بل المشروط.