Kromo biltzailearen ebazkizuna

Wikipedia(e)tik
Hona jo: nabigazioa, Bilatu

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[aldatu | aldatu iturburu kodea]

n bildu beharreko kromo kopurua, T kromo guztiak biltzeko itxaron beharreko aldi kopurua eta ti i-garren kromo ezberdina, aurretik i-1 kromo ezberdin bildu direla, lortu arte itxaron beharreko aldi kopurua izanik, T eta ti 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, ti zorizko aldagai bakoitzak banaketa geometrikoari jarraitzen dio, bakoitzari itxaropena 1/pi izanik.

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


\begin{align}
\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{align}

Hn zenbaki harmonikoa izanik. Zenbaki harmonikorako hurbilketa bat erabiliz:


\operatorname{E}(T)= n \cdot H_n \approx n \ln n + \gamma n + \frac1{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, ti zorizko aldagai bakoitzak banaketa geometrikoari jarraitzen diola kontuan hartuz betiere:


\begin{align}
\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 2 n^2,
\end{align}

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- n H_n| \geq c\, n\right) \le \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) \le \frac{2}{15.5^2}=0.00832.

Bilatzen den probabilitatea 0.00832 baino txikiagoa da.

Bibliografia[aldatu | aldatu iturburu kodea]

  • (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.