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 {\displaystyle 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 , {\displaystyle T_{n},} po której w każdej urnie znajdzie się co najmniej jedna kula. Liczba rzutów T n {\displaystyle 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 {\displaystyle k} urn i niech T n , k {\displaystyle T_{n,k}} oznacza liczbę rzutów potrzebnych do zapełnienia k + 1 {\displaystyle k+1} urn (czyli do dorzucenia jednej kuli do pustych urn). Wtedy

  1. T n , k {\displaystyle T_{n,k}} jest zmienną losową o rozkładzie geometrycznym z parametrem ( n − k ) / n , {\displaystyle (n-k)/n,}
  2. T n = T n , 0 + T n , 1 + … + T n , n − 1 , {\displaystyle T_{n}=T_{n,0}+T_{n,1}+\ldots +T_{n,n-1},}
  3. zmienne T n , 0 , T n , 1 , … , T n , n − 1 {\displaystyle 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 {\displaystyle p} wynosi 1 / p {\displaystyle 1/p} oraz z tego, że wartość oczekiwana sumy zmiennych losowych jest równa sumie wartości oczekiwanych tych zmiennych otrzymujemy

E [ T n ] = ∑ k = 0 n − 1 n n − k = n ∑ k = 0 n − 1 1 n − k = n ∑ k = 1 n 1 k . {\displaystyle 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 + … + 1 / n {\displaystyle 1/1+1/2+\ldots +1/n} nazywana jest n {\displaystyle n} -tą liczbą harmoniczną i oznaczana symbolem H n . {\displaystyle H_{n}.}

Ponadto

H n = ln ⁡ ( n ) + γ + 1 2 n − 1 12 n 2 + O ( 1 n 4 ) , {\displaystyle H_{n}=\ln(n)+\gamma +{\frac {1}{2n}}-{\frac {1}{12n^{2}}}+O\left({\frac {1}{n^{4}}}\right),}

gdzie γ = 0,577 21... {\displaystyle \gamma =0{,}57721...} jest stałą Eulera-Mascheroniego.

W konsekwencji

T n = n ln ⁡ ( n ) + γ n + 1 2 − 1 12 n + O ( 1 n 3 ) . {\displaystyle 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 {\displaystyle T_{n}} można wyznaczyć w podobny sposób jak wyznacza się wartość oczekiwaną. Zmienna losowa o rozkładzie geometrycznym z parametrem p {\displaystyle p} ma wariancję równą ( 1 − p ) / p 2 {\displaystyle (1-p)/p^{2}} oraz z wariancja sumy niezależnych zmiennych losowych jest równa sumie wariancji tych zmiennych, skąd wynika że

var ⁡ [ T n ] = ∑ k = 0 n − 1 n k ( n − k ) 2 ≤ n 2 ∑ k = 0 n − 1 1 ( n − k ) 2 = n 2 ∑ k = 1 n 1 k 2 < n 2 π 2 6 < 2 n 2 . {\displaystyle \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

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

zatem asymptotycznie zmienna T n {\displaystyle T_{n}} jest mocno skoncentrowana.

Bibliografia

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