Sürpriz Yumurtadan Çıkan Bütün Oyuncakları Toplamak İsteyen Biri, Tahminen Kaç Yumurta Almalı?
coupon collector’s problem'den bahsetmek istiyorum
Coupon collector’s problem: Kupon toplayıcısı problemi.
kupon örneğini biraz değiştirelim, sıkıntı değil pek. mesela sürpriz yumurta'dan çıkan bütün oyuncakları (birbirinden farklı, toplamda n adet sayıda oyuncak olsun) toplamak istediğinizi düşünelim. her bir oyuncağın çıkma ihtimali de eşit olsun. şimdi soru şu: böyle bir durumda, tüm oyuncakları toplamak için (1'den n'e kadar hepsi) satın almanız gereken (beklenen*) yumurta sayısı kaç tanedir?
* herhangi bir hile olmadığı sürece, bütün oyuncakların teorik olarak elde edilmesini garantileyen sayı. (not: pratikte daha fazla gerekebilir).
problemin çözümü ise şöyle
1. oyuncağın çıkma ihtimali: p(1)=1
k. oyuncağın çıkma ihtimali: p(k)=n-(k+1)/n ---> (herhangi k-1 oyuncak topladıktan sonra geriye kalan n-(k+1) oyuncaktan herhangi birinin çekilme ihtimali)
n. oyuncağın çıkma ihtimali: p(n)=1/n'dir.
bu durumda, beklenen değerin doğrusallığı ilkesinden yararlanarak, n sayıda oyuncak için gereken sayı:
s(n)=1/p(1)+...+1/p(k)+...+1/p(n)
s(n)=n/1+...+n/(n-k+1)+...+n/n
s(n)=n*(1/1+1/2+1/3+...+1/n)
olarak bulunur.
söz gelimi 20 oyuncak için,
s(20)=20*(1/1+1/2+1/3+...+1/20)
s(20)=~72.
yaklaşık 72 sürpriz yumurtadan sonra teorik olarak 20 oyuncağın hepsinin çıkmış olması beklenebilir. pratikte ise sürpriz yumurta size gerçekten sürpriz yapabilir ve sonuçta da daha fazla sayıda yumurta almanız gerekebilir.