Erwarteter Wert beim Durchblättern eines Buches
Angenommen, ein Buch hat $N$Seiten, und wir lesen das Buch wie folgt durch. Wir beginnen auf Seite 0 und wenn wir auf Seite sind$i$Wir blättern zufällig zu einer Seite $i + 1, i + 2, ..., N$ mit gleicher Wahrscheinlichkeit.
- Was ist der erwartete Wert für die Anzahl der Flips, die wir benötigen, um das Buch fertigzustellen?
Die Intuition sagt mir, dass wir im Durchschnitt damit rechnen können, die Anzahl der verbleibenden Seiten zu halbieren. Dies ergibt$\log_2(N)$, aber ich habe Probleme, es zu formalisieren.
- Wenn $N = 26$Wie hoch ist die Wahrscheinlichkeit, dass wir irgendwann auf Seite 13 blättern? Angenommen, wir beginnen auf Seite 0.
ich lasse $P_i$ Seien Sie die Wahrscheinlichkeit, dass wir ab Seite auf Seite 13 landen $i$. Dann,$P_{13} = 1$, und allgemein, $$P_{i} = \frac{1}{26 - i}\sum_{k = i + 1}^{13}P_k$$
Begriffe wie bewerten $P_{12}, P_{11}, P_{10}$Ich sehe, dass all diese Werte sind $\frac{1}{14}$, einschließlich $P_0$. Gibt es einen intuitiveren Grund für eine so einfache Antwort?
Antworten
Betrachten wir das äquivalente Problem, bei dem wir auf Seite beginnen $n$ und blättern Sie rückwärts durch das Buch und gehen Sie zu jeder der Seiten $0, 1, ..., n - 1$mit gleicher Wahrscheinlichkeit. Lassen$E_n$die erwartete Anzahl von Flips sein. Dann haben wir$E_0 = 0$ und
$E_n = 1 + \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i$
Dann haben wir insbesondere
\ begin {Gleichung} \ begin {split} E_ {n + 1} & = 1 + \ frac {1} {n + 1} \ sum \ limit_ {i = 0} ^ {n} E_i \\ & = 1 + \ frac {E_n} {n + 1} + \ frac {n} {n + 1} \ frac {1} {n} \ sum \ limit_ {i = 0} ^ {n - 1} E_i \\ & = 1 + \ frac {E_n} {n + 1} + \ frac {n} {n + 1} (1 + \ frac {1} {n} \ sum \ limit_ {i = 0} ^ {n - 1} E_i) - \ frac {n} {n + 1} \\ & = 1 - \ frac {n} {n + 1} + \ frac {1} {n + 1} E_n + \ frac {n} {n + 1} E_n \\ & = \ frac {1} {n + 1} + E_n \ end {split} \ end {Gleichung}
wann immer $n \geq 1$ (und die Identität ist leicht zu überprüfen, wenn $n = 0$ auch).
Dann haben wir durch Induktion $E_n = \sum\limits_{j = 1}^n \frac{1}{j}$, das $n$th harmonische Zahl. Dies wird asymptotisch sehr nahe sein$\log_e(n)$.
Lassen $P_n$ sei die erwartete Anzahl von Flips in einem Buch mit $n$Seiten. Dann$P_0=0,\ P_1=1$ und $$P_n=1+\frac1n\sum_{k=0}^{n-1}P_k,\tag1$$ weil wir einen Flip machen müssen, und dann haben wir gleich wahrscheinlich eine beliebige Anzahl von Seiten von $0$ zu $n-1$ links durchblättern.
Wir bekommen $$\begin{align} P_1&=1\\ P_2&=\frac32\\ P_3&=\frac{11}6\\ P_4&=\frac{50}{24}\\ P_5&=\frac{174}{120} \end{align}$$
Die Nenner sind offensichtlich $n!$Also suchen wir in OEIS nach den Zählern und finden A000254 , die vorzeichenlosen Stirling-Zahlen der ersten Art.
OESI gibt die Wiederholung $$a_{n+1}=(n+1)a_n+n!$$ für die vorzeichenlosen Stirling-Zahlen der ersten Art, die durch geteilt werden $(n+1)!$ wir bekommen $$P_{n+1}=P_n+\frac1{n+1}$$ was klar gibt $$P_n=\sum_{k=1}^n\frac1k=H_n,$$ das $n$th harmonische Zahl. Um das Problem zu lösen, müssen wir zeigen, dass die harmonischen Zahlen die Wiederholung erfüllen$(1)$.
Du bist dran.
So näherte ich mich dem ersten Teil des Problems. Betrachten Sie ein Buch mit genau$n$Seiten. Lassen$P_1$ Bezeichnen Sie die erste Seite, zu der Sie gewechselt haben, und lassen Sie sie $X_n$Stellen Sie die Anzahl der Seiten dar, die Sie umgedreht haben, bis Sie zur letzten Seite gelangen. Hinweis$P_1$ ist gleichmäßig am Set verteilt $\{1,...,n\}$ und $E(X_1)=1$. Unter Verwendung des gesamten Erwartungsgesetzes, für das wir sorgen$n\geq2$ Das $$E(X_n)=\sum_{k=1}^{n}E(X_n|P_1=k)P(P_1=k)=\frac{1}{n}\sum_{k=1}^{n}E(X_n|P_1=k)$$
Beachten $E(X_n|P_1=k)=1+E(X_{n-k})$ und so $$E(X_n)=\frac{1}{n}\sum_{k=1}^{n}\Big[1+E(X_{n-k})\Big]=1+\frac{E(X_0)+\dots+E(X_{n-1})}{n}$$ Ersetzen $n$ mit $n+1$ bekommen $$E(X_{n+1})=1+\frac{E(X_0)+\dots+E(X_{n})}{n+1}$$ Die Kombination der beiden vorhergehenden Gleichungen enthüllt die Beziehung $$(n+1)(E(X_{n+1})-1)=(n+1)E(X_n)-n$$ das ist gleichbedeutend mit sagen $$E(X_{n+1})=E(X_n)+\frac{1}{n+1}$$ So endlich $$E(X_n)=\sum_{k=1}^{n}\frac{1}{k}$$