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, $\mathrm{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 $\mathrm{\Theta }(n\log (n))$ . Stampa:Efn 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{array}{cc}\mathrm{E}(T)& =\mathrm{E}(t_1+t_2+\cdots +t_n)\\ & =\mathrm{E}(t_1)+\mathrm{E}(t_2)+\cdots +\mathrm{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 (\frac{1}{1}+\frac{1}{2}+\cdots +\frac{1}{n})\\ & =n\cdot H_n.\end{array}$

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

$\mathrm{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:

$\mathrm{P}(T\ge cn{H}_n)\le \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{array}{cc}\mathrm{E}(T_k)& =\mathrm{E}(t_{k+1}+t_{k+2}+\cdots +t_n)\\ & =n\cdot (\frac{1}{1}+\frac{1}{2}+\cdots +\frac{1}{n-k})\\ & =n\cdot H_{n-k}\end{array}$

Llogaritja e variancës

Duke përdorur pavarësinë e ndryshoreve të rastit $t_i$, marrim:

$\begin{array}{cc}\mathrm{Var}(T)& =\mathrm{Var}(t_1+\cdots +t_n)\\ & =\mathrm{Var}(t_1)+\mathrm{Var}(t_2)+\cdots +\mathrm{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}\\ & <(\frac{n^2}{n^2}+\frac{n^2}{(n-1{)}^2}+\cdots +\frac{n^2}{1^2})\\ & =n^2\cdot (\frac{1}{1^2}+\frac{1}{2^2}+\cdots +\frac{1}{n^2})\\ & <\frac{{\pi }^2}{6}{n}^2\end{array}$

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 :

$\mathrm{P}(|T-n{H}_n|\ge cn)\le \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{array}{c}P\left[Z_i^r\right]={(1-\frac{1}{n})}^r\le e^{-r/n}.\end{array}$

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

$\begin{array}{c}P[T>\beta n\log n]=P\left[\bigcup _i{Z}_i^{\beta n\log n}\right]\le n\cdot P[Z_1^{\beta n\log n}]\le n^{-\beta +1}.\end{array}$