Problemi i grumbulluesit të kuponave

[[Skeda:Coupon_collector_problem.svg|parapamje|400x400px| 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{align}
\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{align}

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

### Llogaritja e variancës 
Duke përdorur pavarësinë e ndryshoreve të rastit t_i, marrim:

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

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- n H_n| \geq cn\right) \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{align}
P\left [ {Z}_i^r \right ] = \left(1-\frac{1}{n}\right)^r \le e^{-r / n}.
\end{align}

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{align}
P\left [ T > \beta n \log n \right ] = 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{align}