 A feladat a kupongyűjtő probléma azon esete, amikor a valószínűségek nem egyenlők.
A cinkelt dobókockával való dobás megfeleltethető egy kupon megvásárlásának. Tegyük fel, hogy \(\displaystyle n\) különböző ,,kupon'' létezik, amelyek \(\displaystyle p_1\), \(\displaystyle p_2\), ..., \(\displaystyle p_n\) valószínűséggel fordulnak elő (ahol \(\displaystyle p_1+\ldots+p_n=1\)). Célunk, hogy egy teljes kupon-gyűjteményt állítsunk össze, és kérdésünk, hogy várhatóan hány kupont kell ehhez megvennünk.
A konkrét feladatban \(\displaystyle n=5\), a valószínűségek pedig \(\displaystyle \frac{1}{6}\), \(\displaystyle \frac{1}{6}\), \(\displaystyle \frac{1}{6}\), \(\displaystyle \frac{1}{3}\), \(\displaystyle \frac{1}{6}\).
Az általános feladat megoldása megtalálható például Marco Ferrante és Monica Saltalamacchia The Coupon Collector’s Problem című írásában.
(Vázlatosan.) Jelentse az \(\displaystyle X_i\) valószínűségi változó azt, hogy hányadik húzásnál kaptuk meg először az \(\displaystyle i\) értéket. (Az egyszerűség kedvéért mostantól feltételezzük, hogy az 1,2,...,\(\displaystyle n\) értékek jöhetnek ki. Ez a feltételezés olvashatóbbá teszi az indexeket, és nem változat a feladat lényegén.)
A fenti jelöléssel a teljes gyűjteményt \(\displaystyle \max_{i\in \{1,\ldots,n\}} X_i\) lépésben állítjuk össze. Keressük \(\displaystyle \max X_i\) várható értékét.
Felhasználjuk a skatulya-elvhez analóg alábbi azonosságot:
\(\displaystyle
\max_{i}\{x_i\}
=\sum_{i=1}^n x_i - \sum_{i<j}\min\{x_i,x_j\} +\sum_{i<j<k}\min\{x_i,x_j,x_k\} - \cdots + \left(-1\right)^{n+1}\min\{x_1,\ldots,x_n\},
\)
továbbá a várható érték linearitását.
\(\displaystyle
E[\max X_i]
= \sum E[X_i] - \sum_{i<j} E[\min\{X_i, X_j\}] + \sum_{i<j<k} E[\min\{X_i,X_j,X_k\}] - \ldots
\)
Vegyük még észre, hogy az \(\displaystyle X_i\), \(\displaystyle \min\{X_i,X_j\}\), \(\displaystyle \min\{X_i,X_j,X_k\}\), ...valószínűségi változók mind geometriai eloszlásúak, rendre \(\displaystyle p_i\), \(\displaystyle p_i+p_j\), \(\displaystyle p_i+p_j+p_k\), ...paraméterrel.
Például \(\displaystyle \min\{X_1, X_2\}\) azt jelenti, hogy mikor jött ki először egy kupon az \(\displaystyle \{1,2\}\) halmazból, vagyis mikor következett be először egy \(\displaystyle p_1+p_2\) valószínűségű esemény.
Mivel a \(\displaystyle p\) valószínűségű esemény első bekövetkezésének várható értéke \(\displaystyle \frac{1}{p}\), ezért a kupongyűjtő probléma megoldása:
\(\displaystyle
E[\max X_i] = \sum_{i}\frac{1}{p_i}- \sum_{i<j}\frac{1}{p_i+p_j} + \sum_{i<j<k}\frac{1}{p_i+p_j+p_k}-\ldots+(-1)^{n+1}\frac{1}{p_1+\ldots+p_n}
\)
A cinkelt kockára mondjuk \(\displaystyle p_1=p_2=p_3=p_4=\frac{1}{6}\) és \(\displaystyle p_5=\frac{1}{3}\). Alkalmazva a fenti formulát a keresett várható lépésszámra \(\displaystyle \frac{127}{10}\) jön ki.
| 
