Safnaraþrautin

Safnaraþrautin (eða safnaravandamálið, e. coupon collector's problem) er stærðfræðilegt viðfangsefni á sviði líkindafræðinnar. Þar er eftirfarandi spurning sett fram: Setjum svo að tiltekin aðgerð hafi n ólíkar útkomur, allar jafnlíklegar. Hversu oft ætli þurfi að framkvæma aðgerðina til að allar ólíkar útkomur hafi komið fyrir a.m.k. einu sinni.

Þrautin degur nafn sitt af þekktu dæmi, um aðstæður úr raunveruleikanum. Safnari hyggst safna N ólíkum safngripum, segjum t.d. ólíkum leikfangaböngsum sem fylgja með morgunkornspökkum. Í hverjum morgunkornspakka er nákvæmlega einn bangsi og allir bangsarnir eru jafnlíklegar til að leynast í hverjum paka. Hversu marga pakka ætti safnarinn að þurfa að kaupa til að safna a.m.k. einu eintaki af hverjum bangsa? Við þessu er vitanlega ekkert svar. Ef safnarinn er einstaklega heppinn þarf hann einungis N pakka til að ná markmiði sínu, en það þýðir að í hverjum pakka fái hann bangsa sem hann á ekki fyrir. Ekkert hámark er þó á því hversu marga pakka safnarinn gæti þurft að kaupa til að komast yfir alla bangsana. Þar sem líkurnar á hverjum bangsa fyrir sig eru alltaf þær sömu (1/n) gæti hann fræðilega séð safnað pökkum út í hið óendanlega ef hann er svo óheppinn að lenda aldrei á tilteknum bangsa sem vantar í safnið.

Hér er markmiðið því, rétt eins og í líkindafræði almennt, að reikna út fræðilegan fjölda, $E_{f}$, þeirra pakka sem kaupa þyrfti. Eftir því sem sama tilraunin væri endurtekin oftar ætti fjöldi þeirra pakka sem kaupa þyrfti að nálgast æ meir hið fræðilega gildi.

Lausn

Látum N vera fjölda ólíkra bangsa sem safnari hyggst safna með kaupum á morgunkornspökkum, en sem fyrr segir fylgir einn bangsi í hverjum pakka og er hver þeirra jafnlíklegur.

Látum P(x) tákna líkurnar á því að safnarinn nái x-ta nýja bangsanum þegar x-1 bangsa hefur verið náð.

(þannig táknar t.d. P(5) líkurnar á því að safnari sem hefur þegar náð sér í fjóra ólíkar bangsa og opnar nýjan pakka fái fimmta ólíka bangsann (en ekki ein af þeim sem hann hafði þegar náð)).

Látum ennfremur E(x) tákna þann fræðilega fjölda pakka sem þarf að kaupa til að ná x-ta nýju fígúrunni þegar x-1 bangsa hefur verið náð.

Athugum að $E(x)={1 \over P(x)}$ (*).

(Ef líkur á tiltekinni útkomu atburðar eru t.d. P(x)=1/2, þá má vænta þess að þurfa að endurtaka hann tvisvar til að fá umrædda útkomu. $E(x)={1 \over {1 \over 2}}=2$.)

Hugsum okkur nú að safnarinn okkar hyggist hefja söfnunina. Hann gengur inn í verslun, grípur fyrsta morgunkornspakkann og opnar hann. Sama hvaða bangsa hann fær á hann þann bangsa ekki til.Líkurnar á að hann fái bangsa sem hann á ekki eru því 100%, þ.e. $E(1)=1$ og þá $P(1)=1$.

Hann fer með bangsann heim til sín og heldur svo aftur út í búð. Nú eru eftir sem áður N ólíkir bangsar í morgunkornspökkum verslunarinnar, en þar sem hann safnaranum hefur nú þegar áskotnast einn þeirra eru N-1 þeirra sem uppfylla skilyrðið að verða nýr bangsi í safnið (bangsi nr. 2). Líkurnar á að fá nýjan bangsa eru því $P(2)={N-1 \over N}$ og þá $E(2)={1 \over {N-1 \over N}}={N \over N-1}$.

Þegar honum hafa áskotnast tvær ólíkar tegundir bangsa eru N-2 nýjar tegundir sem hann vantar, af þeim N sem til eru í búðinni. Líkurnar á að fá nýja tegund eru því $P(3)={N-2 \over N}$

$E(3)={1 \over {N-2 \over N}}={N \over N-2}$.

Almennt gildir því fyrir x-ta nýja bangsann að fræðilegt gildi þeirra pakka sem kaupa þarf til að ná honum er $N \over N-(x+1)$.

Þegar öllum böngsum nema einum hefur verið safnað má t.d. vænta þess að kaupa þurfi ${N \over N-(N+1)}={N \over 1}=N$ morgunkornspakka til að ná þeim síðasta.

Fræðilegt gildi þeirra pakka sem kaupa þarf til að safna öllum N böngsunum er því

$E_{f}=$$\sum _{i=1}^{N}E(i)=E(1)+E(2)+E(3)+...+E(N)$

$=1+{N \over N-1}+{N \over N-2}+{N \over N-3}+...+{N \over 3}+{N \over 2}+N$

$=N(1+{1 \over 2}+{1 \over 3}+...+{1 \over N-3}+{1 \over N-2}+{1 \over N-1}+{1 \over N})$

$=N*\sum _{i=1}^{N}{1 \over i}$.

Nokkur dæmi, og námundun

Ef bangsategundirnar sem safnarinn leitaði að reynast t.d. vera N=10 má þá gera ráð fyrir að hann þyrfti að kaupa um

$10*\sum _{i=1}^{10}{1 \over i}=10(1+{1 \over 2}+{1 \over 3}+...+{1 \over 9}+{1 \over 10})\approx 29$ morgunkornspakka til að safna öllum böngsunum.

Sem fyrr segir má nota safnaraaðferðina til að reikna ýmiss konar hluti sem gerast á handahófskenndan hátt.

Setjum sem svo að þrír samskonar boltar, gulur, rauður og blár, séu í skál. Bolti er dreginn upp úr af handahófi, litur hans skráður og honum síðan skilað aftur. Fræðilegt gildi þeirra drátta sem þarf til að allir litirnir komi fram er þá $E_{f}=$ $3*\sum _{i=1}^{3}{1 \over i}=3(1+{1 \over 2}+{1 \over 3})={11 \over 2}=5,5.$

Eftir því sem N stækkar veður því sífellt betri nálgun að skrifa fræðilegan fjölda drátta sem þarf til að safna öllum N böngsunum sem $E_{f}=$ $N*ln(N)$.

Þessi nálgun er ekki góð fyrir lágar tölur. Séu bangsarnir t.d. bara tveir fæst með þessari nálgun $E_{f}=2*ln(2)\approx 1,39$ en eðli málsins samkvæmt er ekki hægt að safna tveimur böngsum með færri en tveimur tilraunum.