Problem kolekcjonera kuponów

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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}, \ldots ,T_{n,n-1}niezależne

Wartość oczekiwana[edytuj | edytuj kod]

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}{2 n}- \frac{1}{12 n^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}{12 n} + O\left(\frac{1}{n^3}\right).

Wariancja[edytuj | edytuj kod]

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)/p2 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{n k}{(n-k)^2} \leq n^2 \sum_{k=0}^{n-1} \frac{1}{(n-k)^2} =
n^2 \sum_{k=1}^{n} \frac{1}{n^2} < n^2  \frac{\pi^2}{6} < 2 n^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[edytuj | edytuj kod]

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