クーポンコレクター問題
したがって、 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}}}