Kupon toplayıcısının problemi

Tum n kuponu toplamak icin gerekli zaman T olarak ve t_i i - 1 kupon toplandıktan sonra iinci kuponu toplamak için gerekli zaman olduğu kabul edilsin. T ve t_i rassal değişkenler olarak görülebilir. i - 1 kupon elde bulunduğu verilmiş ise bir yeni kuponu toplama olasılığı
'p_i = (n - i + 1)/n
olduğu gözümlenebilir. Bundan dolayı t_i beklenen değeri 1/p_i olan bir geometrik dağılım gösterir. beklenen değerlerin doğrusallığı dolayısıyla şu yazılabilir:

${\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}}}$

Burada H_n bir harmonik sayı olur ve harmonik sayıların "asimptotik" özelliğini kullanarak, şu ifade bulunur:

${\displaystyle \operatorname {E} (T)=n\cdot H_{n}=n\ln n+\gamma n+{\frac {1}{2}}+o(1),\ \ {\text{as}}\ n\to \infty ,}$

Burada ${\displaystyle \gamma \approx 0.5772156649}$ Euler–Mascheroni sabiti olur.

Şimdi Markov eşitsizliği kullanarak istenilen olasılık sayısı için sınırlar konulur:

${\displaystyle \operatorname {P} (T\geq c\,nH_{n})\leq {\frac {1}{c}}.}$

t_i rassal degişkenlerinin bağımsızlığı özelliği kullanılarak şu elde edilir:

${\displaystyle {\begin{aligned}\operatorname {Var} (T)&=\operatorname {Var} (t_{1})+\operatorname {Var} (t_{2})+\cdots +\operatorname {Var} (t_{n})\\&={\frac {1-p_{1}}{p_{1}^{2}}}+{\frac {1-p_{2}}{p_{2}^{2}}}+\cdots +{\frac {1-p_{n}}{p_{n}^{2}}}\\&\leq {\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}\\&\leq n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots \right)={\frac {\pi ^{2}}{6}}n^{2}\leq 2n^{2},\end{aligned}}}$

Burada son eşitlilik baz problem olarak anılan Riemann zeta fonksiyonunun değeridir.

Şimdi istenilen olasılık değerine sınırlar koymak için Çebişev eşitsizliği kullanılır:

${\displaystyle \operatorname {P} \left(|T-nH_{n}|\geq c\,n\right)\leq {\frac {2}{c^{2}}}.}$

Diğer bir yaklaşım kullanılarak başka bir yukarı sınır ifadesi de elde etmek mümkündür: İlk ${\displaystyle r}$ sayıda deneysel seçimde ${\displaystyle i}$-inci kuponun ele geçmeme olayı ${\displaystyle {Z}_{i}^{r}}$ ile ifade edilsin. O zaman

${\displaystyle {\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}\end{aligned}}}$

Böylece, ${\displaystyle r=\beta n\log n}$, için şu elde edilir ${\displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }}$.

${\displaystyle {\begin{aligned}P\left[T>\beta n\log n\right]\leq P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}]\leq n^{-\beta +1}\end{aligned}}}$

Kupon toplayıcısının problemini çözmek için üretici fonksiyon yaklaşımı da kullanılabilir.