本をめくるの期待値
本が持っていると仮定します $N$ページ、そして私達は次のように本を読み通しました。私たちは0ページから始めます、そして私たちがページにいるなら$i$、ランダムにページをめくります $i + 1, i + 2, ..., N$ 等しい確率で。
- 本を完成させるために必要なフリップ数の期待値はどれくらいですか?
直感的に言うと、平均して残りのページ数は半分になると予想できます。これにより、$\log_2(N)$、しかし私はそれを形式化するのに苦労しています。
- 場合 $N = 26$、ある時点で13ページにめくる確率はどれくらいですか?0ページから始めると仮定します。
させて $P_i$ ページから始めて、最終的に13ページに到達する確率になります。 $i$。次に、$P_{13} = 1$、そして一般的に、 $$P_{i} = \frac{1}{26 - i}\sum_{k = i + 1}^{13}P_k$$
次のような用語の評価 $P_{12}, P_{11}, P_{10}$、これらの値はすべて $\frac{1}{14}$を含む $P_0$。そのような単純な答えのより直感的な理由はありますか?
回答
ページから始める同等の問題を考えてみましょう $n$ 本をさかのぼって、各ページに移動します $0, 1, ..., n - 1$等しい確率で。しましょう$E_n$予想されるフリップ数になります。次に、$E_0 = 0$ そして
$E_n = 1 + \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i$
それから特に私達は持っています
\ begin {equation} \ begin {split} E_ {n + 1}&= 1 + \ frac {1} {n + 1} \ sum \ limits_ {i = 0} ^ {n} E_i \\&= 1 + \ frac {E_n} {n + 1} + \ frac {n} {n + 1} \ frac {1} {n} \ sum \ limits_ {i = 0} ^ {n-1} E_i \\&= 1 + \ frac {E_n} {n + 1} + \ frac {n} {n + 1}(1 + \ frac {1} {n} \ sum \ limits_ {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 {equation}
いつでも $n \geq 1$ (そして、身元は次の場合に簡単に確認されます $n = 0$ 同様に)。
次に、誘導によって、 $E_n = \sum\limits_{j = 1}^n \frac{1}{j}$、 $n$調和数。これは漸近的に非常に近くなります$\log_e(n)$。
しましょう $P_n$ で本のフリップの予想数である $n$ページ。次に$P_0=0,\ P_1=1$ そして $$P_n=1+\frac1n\sum_{k=0}^{n-1}P_k,\tag1$$ 1回めくる必要があるので、同じように任意の数のページが表示される可能性があります。 $0$ に $n-1$ 左にめくります。
我々が得る $$\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}$$
分母は明らかに $n!$、したがって、OEISで分子を探し、A000254を見つけます。これは、第1種の符号なしスターリング数です。
OESIは再発を与えます $$a_{n+1}=(n+1)a_n+n!$$ 第1種の符号なしスターリング数の場合、 $(n+1)!$ 我々が得る $$P_{n+1}=P_n+\frac1{n+1}$$ これは明らかに $$P_n=\sum_{k=1}^n\frac1k=H_n,$$ インクルード $n$調和数。問題を完了するには、調和数が漸化式を満たすことを示す必要があります$(1)$。
あなたの番。
これが私が問題の最初の部分にどのようにアプローチしたかです。正確に本を考えてみましょう$n$ページ。しましょう$P_1$ めくった最初のページを示し、 $X_n$最後のページに到達するまでにめくったページ数を表します。注意$P_1$ セットに均一に分布している $\{1,...,n\}$ そして $E(X_1)=1$。私たちが得る期待の総法則を使用して$n\geq2$ それ $$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)$$
通知 $E(X_n|P_1=k)=1+E(X_{n-k})$ など $$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}$$ 交換 $n$ と $n+1$ 取得するため $$E(X_{n+1})=1+\frac{E(X_0)+\dots+E(X_{n})}{n+1}$$ 前の2つの方程式を組み合わせると、関係が明らかになります $$(n+1)(E(X_{n+1})-1)=(n+1)E(X_n)-n$$ これは言うのと同じです $$E(X_{n+1})=E(X_n)+\frac{1}{n+1}$$ だからついに $$E(X_n)=\sum_{k=1}^{n}\frac{1}{k}$$