Kolekcionāra problēma

Kolekcionāra problēmas sagaidāmo pirkumu skaits līdz visa kolekcija ir savākta pie kolekcijas lieluma n.

Kolekcionāra problēma ir varbūtības teorijas uzdevums, kas analizē kolekcionēšanu. Tā uzdod šādu jautājumu: "Ja katram pirkumam nāk līdzi viens kupons un kopumā ir n dažādi kuponi, cik vidēji jāveic pirkumi, lai savāktu visus kuponus?". Pastāv arī alternatīvi formulējumi uzdevumam, piemēram, kāda ir varbūtība, ka visa kolekcija būs savākta pēc t pirkumiem? Pēc matemātiskās analīzes sagaidāmā vērtība pirkumu skaitam pie lieliem n aug kā $\Theta (n\cdot \ln(n))$ funkcija. Piemēram, kad kolekcijā ir n = 50 elementi, tad nepieciešami apmēram 225 pirkumi lai savāktu visus 50 kuponus.

Atrisinājums

Grafikā pārādīts kā aug nepieciešamo kuponu skaits, norādīta arī viena standartnovirze.

Apzīmēsim $T$ kā nepeiciešamo skaitu pirkumu, lai savāktu visus n kuponus, kā arī $t_{i}$kā pirkumu skaitu, lai iegūtu i-to kuponu, kad i-1 kuponi jau ir savākti. Tad izpildās $T=t_{1}+t_{2}+...+t_{n}$. Var uzskatīt $T$ un $t_{i}$ kā gadījuma lielumus. Var novērot, ka varbūtība iegūt jaunu kuponu ir $p_{i}={\frac {n-(i-1)}{n}}={\frac {n-i+1}{n}}$. Katram i-tajam jaunajam kuponam ir atšķirīga varbūtība, ka nākamais pirkums būs nebijis kupons, taču šī varbūtība nopirkt jaunu kuponu nemainās kamēr nav atrasts jauns kupons. Šis ir nosacījums binomiālajam sadalījuma gadījuma lielumam, līdz ar to šo uzdevumu var interpretēt kā summēt sagaidāmās vērtības mainīgo vērtībām, kuras nāk no binomiālā sadalījuma. Priekš binomiālā sadalījuma sagaidāmā vērtība līdz vienam vēlamam gadījumam ir ${\frac {1}{p_{i}}}$ un šī vērtība mums ir zināma: ${\frac {1}{p_{i}}}={\frac {n}{n-i+1}}$, tad var izmantot sagaidāmās vērtības linearitāti un aprēķināt uzdevumu:

$E(T)=E(t_{1}+t_{2}+...+t_{n})$,: $E(t_{1}+t_{2}+...+t_{n})=E(t_{1})+E(t_{2})+...+E(t_{n})$

${\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{aligned}}$

kur $H_{n}$ ir n-tais harmoniskais skaitlis. Izmantojot asimptošu analīzi var iegūt, ka:

$E(T)=n\cdot H_{n}=n\cdot \ln {n}+\gamma \cdot n+{\frac {1}{2}}+O(1/n)$, kur $\gamma \approx 0.5772156649$ ir Eilera-Maščeroni konstane.