Problem kolekcjonera kuponów

Problem kolekcjonera kuponów opisuje klasę konkursów, w którym gracz otrzymuje wygraną po zebraniu wszystkich kuponów z określonej puli. Problem polega na przewidzeniu jak długo należy zbierać kupony, aby otrzymać wygraną. Problem ten jest interesujący z matematycznego punktu widzenia, jak i ma wiele zastosowań w informatyce.

Analiza problemu

Oto doprecyzowanie podstawowego wariantu problemu kolekcjonera kuponów:

1. mamy $n$ urn,
2. do urn tych wrzucamy kolejno kule,
3. wybór każdej urny jest równo prawdopodobny oraz kolejne wybory są wykonywane niezależnie.

Interesuje nas liczba rzutów $T_{n},$ po której w każdej urnie znajdzie się co najmniej jedna kula. Liczba rzutów $T_{n}$ jest zmienną losową.

Problem ten można stosunkowo łatwo zanalizować, rozbijając proces wypełniania urn na etapy. Załóżmy, że w pewnej chwili wypełnionych jest $k$ urn i niech $T_{n,k}$ oznacza liczbę rzutów potrzebnych do zapełnienia $k+1$ urn (czyli do dorzucenia jednej kuli do pustych urn). Wtedy

1. $T_{n,k}$ jest zmienną losową o rozkładzie geometrycznym z parametrem $(n-k)/n,$
2. $T_{n}=T_{n,0}+T_{n,1}+\ldots +T_{n,n-1},$
3. zmienne $T_{n,0},T_{n,1},\dots ,T_{n,n-1}$ są niezależne.

Wartość oczekiwana

Korzystając z tego, że wartość oczekiwana zmiennej o rozkładzie geometrycznym z parametrem $p$ wynosi $1/p$ oraz z tego, że wartość oczekiwana sumy zmiennych losowych jest równa sumie wartości oczekiwanych tych zmiennych otrzymujemy

$E[T_{n}]=\sum _{k=0}^{n-1}{\frac {n}{n-k}}=n\sum _{k=0}^{n-1}{\frac {1}{n-k}}=n\sum _{k=1}^{n}{\frac {1}{k}}.$

Suma $1/1+1/2+\ldots +1/n$ nazywana jest $n$-tą liczbą harmoniczną i oznaczana symbolem $H_{n}.$

Ponadto

$H_{n}=\ln(n)+\gamma +{\frac {1}{2n}}-{\frac {1}{12n^{2}}}+O\left({\frac {1}{n^{4}}}\right),$

gdzie $\gamma =0{,}57721...$ jest stałą Eulera-Mascheroniego.

W konsekwencji

$T_{n}=n\ln(n)+\gamma n+{\frac {1}{2}}-{\frac {1}{12n}}+O\left({\frac {1}{n^{3}}}\right).$

Wariancja

Wariancję zmiennej losowej $T_{n}$ można wyznaczyć w podobny sposób jak wyznacza się wartość oczekiwaną. Zmienna losowa o rozkładzie geometrycznym z parametrem $p$ ma wariancję równą $(1-p)/p^{2}$ oraz z wariancja sumy niezależnych zmiennych losowych jest równa sumie wariancji tych zmiennych, skąd wynika że

$\operatorname {var} [T_{n}]=\sum _{k=0}^{n-1}{\frac {nk}{(n-k)^{2}}}\leq n^{2}\sum _{k=0}^{n-1}{\frac {1}{(n-k)^{2}}}=n^{2}\sum _{k=1}^{n}{\frac {1}{k^{2}}}<n^{2}{\frac {\pi ^{2}}{6}}<2n^{2}.$

Ponadto

${\frac {\sqrt {\operatorname {var} [T_{n}]}}{E[T_{n}]}}=O\left({\frac {1}{\ln(n)}}\right),$

zatem asymptotycznie zmienna $T_{n}$ jest mocno skoncentrowana.

Bibliografia

• D.E. Knuth, R.L. Graham, O. Patashnik: Matematyka Konkretna. Wydawnictwo Naukowe PWN, 2002. Brak numerów stron w książce
• William Feller: Wstęp do rachunku prawdopodobieństwa. Wydawnictwo Naukowe PWN, 2009. Brak numerów stron w książce
• M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. Brak numerów stron w książce