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.
Bir Lunaparkta Birbirini Kaybeden İki Arkadaşın Buluşabilmesi İçin En Verimli Yol Nedir?
