テールの推定とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/05 15:18 UTC 版)

「クーポンコレクター問題」の記事における「テールの推定」の解説

異なる上限は、以下の計算から導き出すことができる。 Z i r {\displaystyle {Z}_{i}^{r}} を最初の r {\displaystyle r} 回の試行で i {\displaystyle i} 番目のクーポンが引けない事象を表すとする。 P [ Z i r ] = ( 1 − 1 n ) r ≤ e − r / n {\displaystyle {\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}\end{aligned}}} したがって、 r = β n log ⁡ n {\displaystyle r=\beta n\log n} については P [ Z i r ] ≤ e ( − β n log ⁡ n ) / n = n − β {\displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }} となる。 P [ T > β n log ⁡ n ] = P [ ⋃ i Z i β n log ⁡ n ] ≤ n ⋅ P [ Z 1 β n log ⁡ n ] ≤ n − β + 1 {\displaystyle {\begin{aligned}P\left[T>\beta n\log n\right]=P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}^{\beta n\log n}]\leq n^{-\beta +1}\end{aligned}}}

※この「テールの推定」の解説は、「クーポンコレクター問題」の解説の一部です。
「テールの推定」を含む「クーポンコレクター問題」の記事については、「クーポンコレクター問題」の概要を参照ください。