期待値の計算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/05 15:18 UTC 版)
「クーポンコレクター問題」の記事における「期待値の計算」の解説
T を全 n 種のクーポンを収集する時間とし、 ti を i - 1種のクーポンを収集した後に i 種類目のクーポンを収集する時間とする。T と ti を確率変数と考える。新しいクーポンを集める確率は pi = (n − (i − 1))/n である。従って、 ti は期待値を1/pi とする幾何分布となる。期待値の線形性により、以下が得られる。 E ( T ) = E ( t 1 ) + E ( t 2 ) + ⋯ + E ( t n ) = 1 p 1 + 1 p 2 + ⋯ + 1 p n = n n + n n − 1 + ⋯ + n 1 = n ⋅ ( 1 1 + 1 2 + ⋯ + 1 n ) = n ⋅ H n {\displaystyle {\begin{aligned}\operatorname {E} (T)&=\operatorname {E} (t_{1})+\operatorname {E} (t_{2})+\cdots +\operatorname {E} (t_{n})={\frac {1}{p_{1}}}+{\frac {1}{p_{2}}}+\cdots +{\frac {1}{p_{n}}}\\&={\frac {n}{n}}+{\frac {n}{n-1}}+\cdots +{\frac {n}{1}}\\&=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)\\&=n\cdot H_{n}\end{aligned}}} ここで、 Hn は n 番目の調和数である。 調和数の漸近解析（英語版）を使用して、以下が得られる。 E ( T ) = n ⋅ H n = n log n + γ n + 1 2 + O ( 1 / n ) {\displaystyle \operatorname {E} (T)=n\cdot H_{n}=n\log n+\gamma n+{\frac {1}{2}}+O(1/n)} ここで、 γ ≈ 0.5772156649 {\displaystyle \gamma \approx 0.5772156649} はオイラーの定数である。 マルコフの不等式を使用して、所望の確率の上限を与えることができる。 P ( T ≥ c n H n ) ≤ 1 c {\displaystyle \operatorname {P} (T\geq cnH_{n})\leq {\frac {1}{c}}}
※この「期待値の計算」の解説は、「クーポンコレクター問題」の解説の一部です。
「期待値の計算」を含む「クーポンコレクター問題」の記事については、「クーポンコレクター問題」の概要を参照ください。
- 期待値の計算のページへのリンク
