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]

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

  1. jest zmienną losową o rozkładzie geometrycznym z parametrem
  2. zmienne niezależne

Wartość oczekiwana[edytuj]

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

Suma nazywana jest n-tą liczbą harmoniczną i oznaczana symbolem . Ponadto

gdzie jest stałą Eulera–Mascheroniego. W konsekwencji,

Wariancja[edytuj]

Wariancję zmiennej losowej można wyznaczyć w podobny sposób jak wyznacza się wartość oczekiwaną. Zmienna losowa o rozkładzie geometrycznym z parametrem 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

.

Ponadto

,

zatem asymptotycznie zmienna jest mocno skoncentrowana.

Bibliografia[edytuj]

  • 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, Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.