Problém sběratelů kupónů - Coupon collectors problem - Wikipedia

Graf počtu kupónů, n vs očekávaný počet pokusů (tj. čas) potřebných k jejich shromáždění, E (T )

v teorie pravděpodobnosti, problém sběratelů kupónů popisuje soutěže „nasbírejte všechny kupóny a vyhrajte“. Ptá se na následující otázku: Pokud každá krabička značky obilovin obsahuje kupón a jsou n různé typy kupónů, jaká je pravděpodobnost, že více než t K vyzvednutí všech je třeba zakoupit krabice n kupony? Alternativní prohlášení je: Dáno n kupónů, kolik kupónů očekáváte, že musíte čerpat s náhradou, než alespoň jednou vylosujete každý kupón? Matematická analýza problému ukazuje, že očekávané číslo potřebných zkoušek roste ${ displaystyle Theta (n log (n))}$.^[A] Například když n = 50 to trvá asi 225^[b] v průměru vyzkoušíte všech 50 kupónů.

Řešení

Výpočet očekávání

Nechat T být čas shromáždit vše n kupóny, a nechat t_i být čas sbírat i-tý kupón po i - Byly shromážděny 1 kupóny. Pak ${ displaystyle T = t_ {1} + cdots + t_ {n}}$. Myslet na T a t_i tak jako náhodné proměnné. Všimněte si, že pravděpodobnost sběru a Nový kupón je ${ displaystyle p_ {i} = { frac {n- (i-1)} {n}} = { frac {n-i + 1} {n}}}$. Proto, ${ displaystyle t_ {i}}$ má geometrické rozdělení s očekáváním ${ displaystyle { frac {1} {p_ {i}}} = { frac {n} {n-i + 1}}}$. Podle linearita očekávání my máme:

${ displaystyle { begin {aligned} operatorname {E} (T) & {} = operatorname {E} (t_ {1} + t_ {2} + cdots + t_ {n}) & {} = operatorname {E} (t_ {1}) + operatorname {E} (t_ {2}) + cdots + operatorname {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 {zarovnáno }}}$

Tady H_n je n-th harmonické číslo. Za použití asymptotika z harmonických čísel získáme:

${ displaystyle operatorname {E} (T) = n cdot H_ {n} = n log n + gamma n + { frac {1} {2}} + O (1 / n),}$

kde ${ displaystyle gamma přibližně 0,5772156649}$ je Euler – Mascheroniho konstanta.

Nyní lze použít Markovova nerovnost k vázání požadované pravděpodobnosti:

${ displaystyle operatorname {P} (T geq cnH_ {n}) leq { frac {1} {c}}.}$

Výpočet rozptylu

Využití nezávislosti náhodných proměnných t_i, získáváme:

${ displaystyle { begin {aligned} operatorname {Var} (T) & {} = operatorname {Var} (t_ {1} + cdots + t_ {n}) & {} = operatorname {Var } (t_ {1}) + operatorname {Var} (t_ {2}) + cdots + operatorname {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}}} vpravo) & {} = n ^ {2} cdot vlevo ({ frac {1} {1 ^ {2}}} + { frac {1} {2 ^ {2}}} + cdots + { frac {1} {n ^ {2}}} vpravo) & {} <{ frac { pi ^ {2}} {6}} n ^ {2} end {zarovnáno}}}$

od té doby ${ displaystyle { frac { pi ^ {2}} {6}} = { frac {1} {1 ^ {2}}} + { frac {1} {2 ^ {2}}} + cdots + { frac {1} {n ^ {2}}} + cdots}$ (vidět Basilejský problém ).

Nyní lze použít Čebyševova nerovnost k vázání požadované pravděpodobnosti:

${ displaystyle operatorname {P} left (| T-nH_ {n} | geq cn right) leq { frac { pi ^ {2}} {6c ^ {2}}}.}$

Odhady ocasu

Z následujícího pozorování lze odvodit jinou horní mez. Nechat ${ displaystyle {Z} _ {i} ^ {r}}$ označují událost, kterou ${ displaystyle i}$-tý kupón nebyl vybrán v prvním ${ displaystyle r}$ pokusy. Pak:

${ displaystyle { begin {aligned} P left [{Z} _ {i} ^ {r} right] leq left (1 - { frac {1} {n}} right) ^ {r } leq e ^ {- r / n} end {zarovnáno}}}$

Tedy pro ${ displaystyle r = beta n log n}$, my máme ${ displaystyle P left [{Z} _ {i} ^ {r} right] leq e ^ {(- beta n log n) / n} = n ^ {- beta}}$.

${ displaystyle { begin {zarovnáno} P left [T> beta n log n right] = P left [ bigcup _ {i} {Z} _ {i} ^ { beta n log n } right] leq n cdot P [{Z} _ {1} ^ { beta n log n}] leq n ^ {- beta +1} end {zarovnáno}}}$

Rozšíření a zobecnění

• Pierre-Simon Laplace, ale také Paul Erdős a Alfréd Rényi, prokázal limitní větu pro distribuci T. Tento výsledek je dalším rozšířením předchozích hranic.

${ displaystyle operatorname {P} (T$

• Donald J. Newman a Lawrence Shepp dal zevšeobecnění problému sběratelů kupónů, když m je třeba sbírat kopie každého kupónu. Nechat T_m být poprvé m kopie každého kupónu jsou shromažďovány. Ukázali, že očekávání v tomto případě splňuje:

${ displaystyle operatorname {E} (T_ {m}) = n log n + (m-1) n log log n + O (n), { text {as}} n na infty.}$

Tady m je opraveno. Když m = 1 dostaneme dřívější vzorec pro očekávání.

• Společné zevšeobecňování, také kvůli Erdősovi a Rényimu:

${ displaystyle operatorname {P} vlevo (T_ {m}$

• V obecném případě nerovnoměrného rozdělení pravděpodobnosti podle Philippe Flajolet,^[1]

${ displaystyle operatorname {E} (T) = int _ {0} ^ { infty} left (1- prod _ {i = 1} ^ {n} left (1-e ^ {- p_ {i} t} right) right) dt.}$

Viz také

• Wattersonův odhad
• Problém s narozeninami

Poznámky

Reference

externí odkazy

• "Problém sběratelů kupónů "od Ed Pegg, Jr., Demonstrační projekt Wolfram. Balíček Mathematica.
• Kolik singlů, čtyřhry, trojic atd. By měl sběratel kupónů očekávat?, krátká poznámka od Doron Zeilberger.