Kromo biltzailearen ebazkizuna

Probabilitate teorian, kromo biltzailearen ebazkizunak aldi ezberdinetan kromo bana hartzen duen pertsona batek kromo guztien bilduma izateko, aldi ezberdinetan kromo berdina jaso daitekeela eta kromoak zoriz jasotzen direla kontuan hartuz, zenbat aldiz itxaron behar duen aztertzen duen ebazkizuna da. Zehatzago, t alditan n kromo guztiak biltzeko probabilitatea eta n kromo guztiak bildu arte batez bestez itxaron beharreko aldi kopurua kalkulatu behar dira. Lehenengo aldian ziur edo 1eko probabilitateaz izango da kromo ezberdin bat. Lehenengo kromoak biltzeko, aldi gutxi itxaron beharko da, baina edukitako kromo ezberdinen kopurua handitu ahala, gero eta aldi gehiago itxaron behar da beste kromo ezberdin bat lortzeko. Esaterako, n=50 kromo ezberdin biltzeko, guztira batez bestez 225 aldi itxaron behar da.

Ebazpena

n bildu beharreko kromo kopurua, T kromo guztiak biltzeko itxaron beharreko aldi kopurua eta t_i i-garren kromo ezberdina, aurretik i-1 kromo ezberdin bildu direla, lortu arte itxaron beharreko aldi kopurua izanik, T eta t_i zorizko aldagaiak izanik:

$T=t_{1}+t_{2}+\cdots +t_{n}$

Itxaropenak kalkulatuz:

$\operatorname {E} (T)=\operatorname {E} (t_{1})+\operatorname {E} (t_{2})+\cdots +\operatorname {E} (t_{n})$

Edozein alditan, i-garren kromo berri bat lortzeko probabilitatea honela adierazi eta kalkulatzen da:

$p_{i}={\frac {n-i+1}{n}}$

Beraz, t_i zorizko aldagai bakoitzak banaketa geometrikoari jarraitzen dio, bakoitzari itxaropena 1/p_i izanik.

Eta ondorioz hau izango da guztira itxaron beharreko aldi kopuruaren itxaropena:

${\begin{aligned}\operatorname {E} (T)&=\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{aligned}}$

H_n zenbaki harmonikoa izanik. Zenbaki harmonikorako hurbilketa bat erabiliz:

$\operatorname {E} (T)=n\cdot H_{n}\approx n\ln n+\gamma n+{\frac {1}{2}},\ \ \ \ n\to \infty ,$

$\gamma \approx 0.5772156649$ Euler–Mascheroniren konstantea izanik.

Ondorengo taulan n kromo kopuru ezberdinetarako kromo guztiak bildu arte batez bestez itxaron beharreko aldi kopuruak azaltzen dira, aurreko hurbilketa erabiliz:

n	E(T)
10	29.30
20	71.95
50	224.95
100	518.72
200	1175.56
500	3398.30
1000	7485.26

Kromo guztiak bildu arte itxaron beharreko T aldi kopuruaren bariantza ematen da jarraian, t_i zorizko aldagai bakoitzak banaketa geometrikoari jarraitzen diola kontuan hartuz betiere:

${\begin{aligned}\operatorname {Var} (T)&=\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}}}\\&\leq {\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}\\&\leq n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots \right)={\frac {\pi ^{2}}{6}}n^{2}\leq 2n^{2},\end{aligned}}$

Karratuen alderantzizkoen baturari buruzko arestiko azken berdinketa Riemannen zeta funtzioaren balio bati buruzkoa da (Baselen ebazkizuna).

Itxaropen matematikoa eta bariantza ezaguturik, Txebixeven desberdintza erabil daiteke T zorizko aldagairi buruzko probabilitateak bornatzeko:

$\operatorname {P} \left(|T-nH_{n}|\geq c\,n\right)\leq {\frac {2}{c^{2}}}.$

Adibidez, 50 kromo bilduma osoa lortzeko, 1000 kromo edo gehiago behar izateko probabilitatea honela bornatzen da, jakinda itxaron beharreko T aldi kopuruaren itxaropen matematikoa 224.95 dela:

$\operatorname {P} \left(T\geq 1000\right)=\operatorname {P} \left(|T-224.95|\geq 775.05\right)=\operatorname {P} \left(|T-224.95|\geq 50\times 15.5\right)\leq {\frac {2}{15.5^{2}}}=0.00832.$

Bilatzen den probabilitatea 0.00832 baino txikiagoa da.

Kanpo estekak

• Datuak: Q1148012
• Multimedia: Coupon collector's problem / Q1148012

• (Ingelesez) Adler, Ilan; Oren, Shmuel; Ross, Sheldon M., The coupon-collector's problem revisited, Journal of Applied Probability, Volume 40, Number 2 (2003), 513-518.