Ein einfaches Problem mit geometrischen Verteilungswörtern

Question

Ich bin mit einem einfachen Wahrscheinlichkeitsproblem festgefahren.

Es gibt einen Algorithmus zur Auswahl von Werbung aus $m$Seiten. Das$i$th Seite hat $n(i)$ Werbung, mit $n(i)$ weniger als eine Zahl $n$.

So funktioniert der Algorithmus:

• Wählen Sie eine zufällige Seite aus $m$ Seiten
• Akzeptiere diese Seite mit Wahrscheinlichkeit $n(i)/n$
• Wenn akzeptiert, wählen Sie eine Anzeige aus den auf der Seite
• Andernfalls wiederholen Sie die Schleife

Die Frage: Wie viele Iterationen erwartet der Algorithmus voraussichtlich?

Dies reduziert sich (glaube ich) auf eine geometrische Verteilung mit Mittelwert $1/p$ wo $p$ ist die Wahrscheinlichkeit, eine Anzeige für eine bestimmte Iteration zu akzeptieren.

Ich habe überprüft, dass die Wahrscheinlichkeit, eine der zu akzeptieren $m$ Seiten (und damit eine Werbung annehmen) ist $p = \bar{n}/n$, wo $ \bar{n} = \sum_{i=1}^{m}n(i)/m$.

Wenn das oben Gesagte korrekt ist, sollte die erwartete Anzahl von Iterationen sein $n/\bar{n}$.

Mein Buch (Ross) sagt mir jedoch, dass die Lösung ist $n\sqrt{n}$.

Wo ist mein Fehler?

Answer 1

Du hast keinen Fehler gemacht; Die Antwort des Buches ist falsch (Antwortschlüssel können Fehler enthalten).

Angenommen, jede Seite hat dieselbe Nummer. $k\;$sagen wir, von Werbung, wo $0 < k \le n$.

Dann wenn $e$ ist die erwartete Anzahl von Iterationen, die wir erhalten $$ e = \left(\frac{k}{n}\right) {\cdot\,} 1 + \left(\frac{n-k}{n}\right) {\cdot\,} (1+e) $$ was ergibt $e={\large{\frac{n}{k}}}$nicht $e=n\sqrt{n}$.

Hinweis:$\;$Die Antwort des Buches $n\sqrt{n}$ typografisch ähnelt $n/\bar{n}$Es handelt sich also möglicherweise um einen Fehler des Herausgebers, nicht des Autors.