Problemi i grumbulluesit të kuponave

Grafiku i numrit të kuponëve, $n$ kundrejt numrit të pritshëm të provave (d.m.th., koha) e nevojshme për t'i mbledhur të gjitha, $\operatorname {E} [T]$

Në teorinë e probabilitetit, problemi i grumbulluesit të kuponëve përshkruan konkurset "mblidhni të gjithë kuponët dhe fitoni". Ai shtron pyetjen e mëposhtme: Nëse çdo kuti e një marke drithërash përmban një kupon dhe ka $n$ lloje të ndryshme kuponësh, sa është probabiliteti që duhet të blihen më shumë se $t$ kuti për të mbledhur të gjithë $n$ kuponët? Një deklaratë alternative është: Duke pasur parasysh $n$ kuponët, sa kuponë prisni që ju duhet të tërhiqni (me zëvendësim) përpara se të keni tërhequr çdo kupon të paktën një herë? Analiza matematikore e problemit zbulon se numri i pritshëm i provave të nevojshme rritet si $\Theta (n\log(n))$ . Për shembull, kur $n=50$ duhen mesatarisht rreth 225 prova për të mbledhur të gjithë 50 kuponët.

Zgjidhje

Llogaritja e pritjes matematike

Le të jetë koha $T$ numri i tërheqjeve të nevojshme për të mbledhur të gjithë $n$ kuponët dhe le jetë $t_{i}$ koha për të mbledhur kuponin i -të pas janë mbledhur $i-1$ kupona. Pastaj $T=t_{1}+\cdots +t_{n}$ . Mendoni për $T$ dhe $t_{i}$ si ndryshore të rastësishme . Vini re se probabiliteti për të mbledhur një kupon të ri është $p_{i}={\frac {n-(i-1)}{n}}={\frac {n-i+1}{n}}$ . Prandaj, $t_{i}$ ka shpërndarje gjeometrike me pritje matematike ${\frac {1}{p_{i}}}={\frac {n}{n-i+1}}$ . Nga lineariteti i pritjeve kemi:

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

Këtu $H_{n}$ është numri harmonik n -të. Duke përdorur asimptotikën e numrave harmonikë, marrim:

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

ku $\gamma \approx 0.5772156649$ është konstantja Euler-Mascheroni .

Përdorimi i mosbarazimit të Markovit për të kufizuar probabilitetin e dëshiruar:

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

Sa më sipër mund të modifikohet pak për të trajtuar rastin kur ne kemi mbledhur tashmë disa nga kuponët. Le të jetë k numri i kuponëve të mbledhur tashmë, atëherë:

${\begin{aligned}\operatorname {E} (T_{k})&{}=\operatorname {E} (t_{k+1}+t_{k+2}+\cdots +t_{n})\\&{}=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n-k}}\right)\\&{}=n\cdot H_{n-k}\end{aligned}}$

Llogaritja e variancës

Duke përdorur pavarësinë e ndryshoreve të rastit $t_{i}$, marrim:

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

nga relacioni ${\frac {\pi ^{2}}{6}}={\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}+\cdots$ (shih problemin e Bazelit ).

Kufizoni probabilitetin e dëshiruar duke përdorur mosbarazimin e Çebishevit :

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

Vlerësimet e bishtit

Një vlerësim më i fortë i bishtit për bishtin e sipërm merret si më poshtë. Le të jenë ${Z}_{i}^{r}$ që tregojnë ngjarjen që kupini $i$-të nuk është zgjedhur në $r$ provat e para. Atëherë

${\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}.\end{aligned}}$

Kështu, për $r=\beta n\log n$, ne kemi $P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }$ . Ne marrim

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