Problem kolekcjonera kuponów

Wykres liczby kuponów, n vs oczekiwana liczba prób (tj. czas) potrzebnych do zebrania ich wszystkich, E ( T )

W teorii prawdopodobieństwa problem kolekcjonera kuponów opisuje konkursy „zbierz wszystkie kupony i wygraj”. Zadaje następujące pytanie: Jeśli każde pudełko płatków zbożowych zawiera kupon, a istnieje n różnych rodzajów kuponów, jakie jest prawdopodobieństwo, że trzeba będzie kupić więcej niż t pudełek, aby zebrać wszystkie n kuponów? Alternatywne stwierdzenie brzmi: biorąc pod uwagę n kuponów, ile kuponów należy wylosować z zamianą , zanim co najmniej raz wylosuje się każdy kupon? Analiza matematyczna problemu pokazuje, że oczekiwana liczba potrzebnych prób rośnie wraz z ${\ Displaystyle \ Theta (n \ log (n))}$ . Na przykład, gdy n = 50, zebranie wszystkich 50 kuponów zajmuje średnio około 225 prób.

Rozwiązanie

Obliczanie oczekiwań

Niech czas T będzie liczbą losowań potrzebnych do zebrania wszystkich n kuponów, a t _i będzie czasem zebrania i -tego kuponu po zebraniu i − 1 kuponów. T ${\ Displaystyle T = t_ {1} + \ cdots + t_ {n}$ . Pomyśl o T i t _i jak o zmiennych losowych . Zauważ, że prawdopodobieństwo zebrania nowego kuponu wynosi ${\ Displaystyle p_ {i} = {\ Frac {n- (i-1)}} }}={\frac {n-i+1}{n}}}$ . Dlatego ${\ Displaystyle t_ {i}}$ ma rozkład geometryczny z oczekiwaniem ${\ Displaystyle {\ Frac {1} {p_ {i}}} = {\ Frac {n} {n-i+1}}}$ . Z liniowości oczekiwań mamy:

${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {E} (T) & {} = \ nazwa operatora {E} (t_ {1} + t_ {2} + \ cdots + t_ {n}) \\ & {} =\nazwa_operatora {E} (t_{1})+\nazwa_operatora {E} (t_{2})+\cdots +\nazwa_operatora {E} (t_{n})\\&{}={\frac {1 }{p_{1}}}+{\frac {1}{p_{2}}}+\cdots +{\frac {1}{p_{n}}}\\&{}={\frac {n }{n}}+{\frac {n}{n-1}}+\cdots +{\frac {n}{1}}\\&{}=n\cdot \left({\frac {1} {1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)\\&{}=n\cdot H_{n}.\end{wyrównane }}}$

Tutaj Hn _- jest n tą liczbą harmoniczną . Korzystając z asymptotyki liczb harmonicznych, otrzymujemy:

${\ Displaystyle \ nazwa operatora {E} (T) = n \ cdot H_ {n} = n \log n+\gamma n+{\frac {1}{2}}+O(1/n),}$

gdzie jest stałą Eulera – Mascheroniego ${\ Displaystyle \ gamma \ około 0,5772156649}$ .

Używając nierówności Markowa do ograniczenia pożądanego prawdopodobieństwa:

${\ Displaystyle \ nazwa operatora {P} (T \ geq cnH_ {n}) \ równoważnik {\ Frac {1} {c}}.}$

Powyższe można nieco zmodyfikować, aby obsłużyć przypadek, gdy uzbieraliśmy już część kuponów. Niech k będzie liczbą zebranych już kuponów, wtedy:

${ \ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {E} (T_ {k}) & {} = \ nazwa operatora {E} (t_ {k + 1} + t_ {k + 2} + \ cdots + t_ {n} )\\&{}=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{nk}}\right )\\&{}=n\cdot H_{nk}\end{wyrównane}}}$

A kiedy ${\ displaystyle k = 0}$ wtedy otrzymujemy oryginalny wynik.

Obliczanie wariancji

Korzystając z niezależności zmiennych losowych t _i , otrzymujemy:

${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {Var} (T) i {} = \ nazwa operatora {Var} (t_ {1} + \ cdots + t_ {n})\\&{}=\nazwa_operatora {Var} (t_{1})+\nazwa_operatora {Var} (t_{2})+\cdots +\nazwa_operatora {Var} (t_{n})\\ &{}={\frac {1-p_{1}}{p_{1}^{2}}}+{\frac {1-p_{2}}{p_{2}^{2}}}+ \cdots +{\frac {1-p_{n}}{p_{n}^{2}}}\\&{}<\left({\frac {n^{2}}{n^{2} }}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}\right) \\&{}=n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{ \frac {1}{n^{2}}}\right)\\&{}<{\frac {\pi ^{2}}{6}}n^{2}\end{aligned}}}$

od ${\ Displaystyle {\ Frac {\ pi ^ {2}} {6}} = {\ Frac {1} {1 ^ {2} }}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}+\cdots }$ (patrz problem z Bazylei ).

Ogranicz żądane prawdopodobieństwo za pomocą nierówności Czebyszewa :

${\ Displaystyle \ nazwa operatora {P} \ lewo (| T-nH_ {n} | \ geq cn \ po prawej) \ równoważnik {\ Frac {\ pi ^ {2}} {6c ^ {2}}}.}$

Szacunki ogona

Silniejsze oszacowanie ogona dla górnego ogona można uzyskać w następujący sposób. Niech ${\ displaystyle {Z} _ {i} ^ {r}}$$kupon$ zdarzenie, że $nie$ został wybrany w pierwszych próbach. Następnie

${\ Displaystyle {\ rozpocząć {wyrównane} P \ lewo [{Z} _ {i} ^ {r} \ prawej] = \ lewo (1- {\ Frac {1} {n}} \ prawo) ^ {r} \leq e^{-r/n}.\end{wyrównane}}}$

Zatem dla ${\ Displaystyle r = \ beta n \ log n}$ , mamy ${\ Displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }}$ . Otrzymujemy za pośrednictwem związku związanego $z$

${\ Displaystyle {\ rozpocząć {wyrównane} P \ lewo [T> \ beta n \ log n \ prawo] = P \ lewo [\ bigcup _ {i} {Z} _ {i} ^ {\ beta n \ log n }\right]\leq n\cdot P[{Z}_{1}^{\beta n\log n}]\leq n^{-\beta +1}.\end{aligned}}}$

Rozszerzenia i uogólnienia

• - Simon Laplace , ale także Paul Erdős i Alfréd Rényi udowodnili twierdzenie graniczne dla rozkładu T. Wynik ten jest dalszym rozszerzeniem poprzednich granic. Dowód znajduje się w.

${\ Displaystyle \ nazwa operatora {P} (T <n \ log n + cn) \ do e ^ {-e ^ {-c}}, {\ tekst {jak}} n \ do \ infty.} Donald J.$

• Newman a Lawrence Shepp uogólnił problem kolekcjonera kuponów, gdy trzeba zebrać m kopii każdego kuponu. Niech T _m będzie pierwszym razem, gdy zbiera się m kopii każdego kuponu. Pokazali, że oczekiwanie w tym przypadku spełnia:

${\ Displaystyle \ nazwa operatora {E} (T_ {m}) = n \ log n + (m-1) n \ log \ log n + O (n), {\ tekst {jako}} n \ do \ infty.}$

Tutaj m jest stałe. Gdy m = 1 otrzymujemy wcześniejszy wzór na oczekiwanie.

• Powszechne uogólnienie, również ze względu na Erdősa i Rényiego:

${\ Displaystyle \ nazwa operatora {P} \ lewo (T_ {m}<n \ log n + (m-1) n \ log \ log n + cn \ prawo) \ do e ^ {-e ^ {-c} / ( m-1)!},{\text{ as }}n\to \infty .}$

• W ogólnym przypadku niejednorodnego rozkładu prawdopodobieństwa, według Philippe Flajolet et al.

${\ Displaystyle \ nazwa operatora {E} (T) = \ int _ {0} ^ {\ infty} \ lewo (1- \ prod _ {i = 1} ^ {m} \ lewo (1-e ^ {- p_ {i}t}\right)\right)dt.}$

To jest równe

${\ Displaystyle \ nazwa operatora {E} (T) = \ suma _ {q = 0} ^ {m-1} (-1) ^ {m-1-q} \ suma _ { |J|=q}{\frac {1}{1-P_{J}}},}$

gdzie m oznacza liczbę kuponów do zebrania, a P _J oznacza prawdopodobieństwo otrzymania dowolnego kuponu ze zbioru kuponów J .

Zobacz też

• McDonald's Monopoly - przykład problemu kolekcjonera kuponów, który dodatkowo zwiększa wyzwanie, czyniąc niektóre kupony z zestawu rzadszymi
• Estymator Wattersona
• Kwestia urodzin
• Twierdzenie o liczbach pierwszych

Notatki

•    Blom, Gunnar; Holst, Lars; Sandell, Dennis (1994), „7,5 Kupon zbierający I, 7,6 Kupon zbierający II i 15,4 Kupon zbierający III”, Problems and Snapshots from the World of Probability , Nowy Jork: Springer-Verlag, s. 85–87, 191, ISBN 0-387-94161-4 , MR 1265713 .
•   Dawkins, Brian (1991), „Problem Siobhan: powrót kolekcjonera kuponów”, The American Statistician , 45 (1): 76–82, doi : 10.2307/2685247 , JSTOR 2685247 .
•   Erdős, Paweł ; Rényi, Alfréd (1961), „O klasycznym problemie teorii prawdopodobieństwa” (PDF) , Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei , 6 : 215–220, MR 0150807 .
• Laplace, Pierre-Simon (1812), Théorie analytique des probabilités , s. 194–195 .
•    Newman, Donald J .; Shepp, Lawrence (1960), „The double dixie cup problem”, American Mathematical Monthly , 67 (1): 58–61, doi : 10.2307/2308930 , JSTOR 2308930 , MR 0120672
•   Flajolet Filip ; Gardy, Daniele; Thimonier, Loÿs (1992), „Urodzinowy paradoks, kolekcjonerzy kuponów, algorytmy buforowania i samoorganizujące się wyszukiwanie” , Discrete Applied Mathematics , 39 (3): 207–229, doi : 10.1016/0166-218X (92) 90177-C , MR 1189469 .
•    Isaac, Richard (1995), „8.4 Problem kolekcjonera kuponów rozwiązany”, The Pleasures of Probability , Undergraduate Texts in Mathematics , New York: Springer-Verlag, s. 80–82, ISBN 0-387-94415-X , MR 1329545 .
•    Motwani, Rajeev ; Raghavan, Prabhakar (1995), „3.6. Problem kolekcjonera kuponów”, Randomizowane algorytmy , Cambridge: Cambridge University Press, s. 57–63, ISBN 9780521474658 , MR 1344451 .

Linki zewnętrzne

• „ Problem kolekcjonera kuponów ” autorstwa Eda Pegga, Jr. , projekt Wolfram Demonstrations . Pakiet Mathematica.
• Ile pojedynczych, podwójnych, potrójnych itp. powinien spodziewać się kolekcjoner kuponów? , krótka notatka Dorona Zeilbergera .