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}+\dots +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+\dots +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

$\mathrm{var}[T_n]=\sum _{k=0}^{n-1}\frac{nk}{(n-k{)}^2}⩽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{\mathrm{var}[T_n]}}{E[T_n]}=O\left(\frac{1}{\ln (n)}\right),$

zatem asymptotycznie zmienna $T_n$ jest mocno skoncentrowana.

Bibliografia

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę
• Szablon:Cytuj książkę