Kupongyűjtő probléma

1. Sablon:Humatek A kupongyűjtő probléma (Coupon Collector’s Problem) egy klasszikus valószínűségszámítási probléma, amely azt vizsgálja, hogy egy adott számú kupont (vagy tárgyat) véletlenszerűen kiválasztva mennyi időbe telik összegyűjteni mindet.

Probléma Leírása Tegyük fel, hogy van $n$ különböző típusú kupon, és minden egyes vásárlás alkalmával egy véletlenszerűen kiválasztott kupont kapunk, amely egyenletes valószínűséggel bármelyik $n$ típus lehet. A kérdés az, hogy hány kupont kell összesen megszerezni ahhoz, hogy biztosan legyen mindegyik típusból legalább egy.

Megoldás Legyen $T_n$ a várható értéke annak a kuponszámnak, amelyet meg kell szerezni ahhoz, hogy mind a $n$ különböző típusból legyen legalább egy. Ekkor $T_n$ várható értéke:

$$T_n=n(1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n})=n{H}_n$$

ahol $H_n$ az $n$-edik harmonikus szám, amely a következőképpen írható fel:

$$H_n=\sum _{k=1}^n\frac{1}{k}$$

A harmonikus szám $H_n$ aszimptotikusan $\ln (n)+\gamma$-hoz konvergál, ahol $\gamma$ az Euler-féle állandó (kb. 0,577).

Példa Ha $n=5$ különböző típusú kupon van, akkor a várható értéke annak, hogy mind az ötöt megszerezzük:

$$T_5=5(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5})\approx 5\times 2,283=11,415$$

Ez azt jelenti, hogy átlagosan körülbelül 11,415 kupont kell gyűjteni ahhoz, hogy mind az öt típusból legyen legalább egy.

Értelmezés és Alkalmazások A kupongyűjtő probléma jól modellezi azokat a helyzeteket, amikor valakinek egy sor véletlenszerűen elérhető tárgyat kell összegyűjtenie. Tipikus alkalmazásai közé tartozik például a gyűjthető kártyák megszerzése, DNS-minták véletlenszerű összegyűjtése genetikai kutatásban, vagy akár a hálózati csomagok teljes lefedettségének biztosítása a hálózati protokollokban.

A probléma egyik fontos tanulsága, hogy az utolsó néhány kupon megszerzése a legnehezebb, és exponenciálisan több kísérlet szükséges hozzá, mint az első néhányhoz. Sablon:Hunl