Basit bir geometrik dağılım kelime problemi

Question

Basit bir olasılık problemi olması gereken şeyle sıkışıp kaldım.

Reklamları seçmek için bir algoritma var $m$sayfalar. $i$Sayfada $n(i)$ reklamlar ile $n(i)$ bir sayıdan az $n$.

Algoritma şu şekilde çalışır:

• İçinden rastgele bir sayfa seçin $m$ sayfaları
• O sayfayı olasılıkla kabul edin $n(i)/n$
• Kabul edilirse, sayfadakilerden bir reklam seçin
• Aksi takdirde döngüyü tekrarlayın

Soru: Algoritma tarafından alınan beklenen yineleme sayısı nedir?

Bu (sanırım) ortalama ile geometrik bir dağılıma indirgenir $1/p$ nerede $p$ belirli bir yinelemede bir reklamı kabul etme olasılığıdır.

Herhangi birini kabul etme olasılığını doğruladım $m$ sayfalar (ve dolayısıyla bir reklamı kabul eden) $p = \bar{n}/n$, nerede $ \bar{n} = \sum_{i=1}^{m}n(i)/m$.

Yukarıdakiler doğruysa, beklenen yineleme sayısı olmalıdır $n/\bar{n}$.

Ancak kitabım (Ross) bana çözümün $n\sqrt{n}$.

Hatam nerede

Answer 1

Hiç hata yapmadınız; kitabın cevabı yanlış (cevap anahtarlarında hatalar olabilir).

Örneğin, her sayfanın aynı numaraya sahip olduğunu varsayalım, $k\;$diyelim ki reklamlar, nerede $0 < k \le n$.

O zaman eğer $e$ beklenen yineleme sayısıdır, $$ e = \left(\frac{k}{n}\right) {\cdot\,} 1 + \left(\frac{n-k}{n}\right) {\cdot\,} (1+e) $$ hangi sonuç verir $e={\large{\frac{n}{k}}}$, değil $e=n\sqrt{n}$.

Not:$\;$Kitabın cevabı $n\sqrt{n}$ tipografik olarak benzer $n/\bar{n}$, bu nedenle muhtemelen yazar tarafından değil, yayıncının bir hatasıdır.