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:
- mamy urn,
- do urn tych wrzucamy kolejno kule,
- 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 urn i niech oznacza liczbę rzutów potrzebnych do zapełnienia urn (czyli do dorzucenia jednej kuli do pustych urn). Wtedy
- jest zmienną losową o rozkładzie geometrycznym z parametrem
- zmienne są niezależne.
Wartość oczekiwana
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 -tą liczbą harmoniczną i oznaczana symbolem
Ponadto
gdzie jest stałą Eulera-Mascheroniego.
W konsekwencji
Wariancja
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ą 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
- 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.