Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: senior - Ağustos 14, 2011, 12:40:54 öö
-
6 yüzlü bir zarı kaç kez attığımızda bütün sayıların gelmesini bekleriz. (N'in beklenen değeri nedir?)
-
Uzun bir süre geçmiş, çözümü paylaşalım :)
İlk olarak zar oyunundan bağımsız şu alt problemi çözelim:
Elimizde hileli bir para var, yazı gelme olasılığı p olsun. Tura gelme olasılığı 1-p. Ortalama kaç el ardarda para atmalıyız ki, yazı gelsin?
1 el olasılığı --> p
2 el olasılığı --> (1-p)p
3 el olasılığı --> (1-p)2p
...
ve bu sonsuza kadar gider. Her el sayısını olasılığıyla çarparsak
Ortalama X = p + 2(1-p)p + 3(1-p)2p + ... elde başarıya ulaşırız.
Tabi bu sonsuz bir toplam, kısaltılması lazım, o zaman toplamı biraz daha inceleyelim:
X = p( 1 + 2(1-p) + 3(1-p)2 + ... ) = -p( 1 + (1-p) + (1-p)2 + (1-p)3 ... )'
()' : Türev anlamında. Devam edelim,
X = -p( 1/(1-(1-p)) )' = -p(1/p)' = p/p2 = 1/p
Yani X = 1/p çıktı. Gayet mantıklı, mesela, yazı gelme olasılığı 1/10 ise, ortalama 10 el atıp yazı gelmesini bekleriz değil mi?
Bunu şöyle kısaca özetleyebiliriz: Başarı olasılığı p olan bir olayın gerçekleşmesi için ortalama 1/p deneme yapmalıyız.
Şimdi orjinal soruya geçelim:
Problemde zar ile uğraşırken, önümüzde altı adet adım var. Birincisi ilk sayının gelmesi. 2.si ikinci farklı sayının gelmesi, ... 6.farklı sayının gelmesi.
İlk farklı sayının gelmesi için zaten zarı 1 kez atmamız yeterli. Gelen sayı önceden hiç zar atmadığımız için kaydedilecektir.
İkinci farklı sayının gelme olasılığı 5/6, o zaman ortalama 6/5 zarda 2. yeni sayı gelecek.
İki yeni sayı geldi, üçüncü yeni sayı için olasılığımız 4/6, yani 6/4 el lazım ortalama.
Böyle devam ederse, 6.sayı için olasılık 1/6 yani, ortalama 6/1 = 6 el demektir.
Bunları toplarsak, zardaki bütün sayıların gelmesi için gereken ortalama atış sayısını buluruz yani:
1 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 147/10 çıkar.
-
çok güzel, tebrikler :)
-
N sayısı için bu sorunun neredeyse aynısını yıllar önce çözmüştüm. Siz de p demişsiniz.
p için genel hali hesapladıysanız, sonucun yaklaşık değerini hatırlıyorum. Karşılaştırabiliriz.
Soru şuydu:
1,2,...,N sayılarının bir permütasyonunu elde etmeye çalışıyoruz.
[1-N] arasında rastgele sayı üreten bir makinemiz var.
Makine ilk sayıyı üretiyor.
Sonra ikinci sayıyı üretiyor. İlk sayının aynısı ise bir daha çalıştırıyoruz. Ta ki, farklı sayı çıkana kadar.
Diğer sayılar için de aynı işlem devam ediyor.
Makine en iyi ihtimalle N kez çalışacak. En kötü ihtimalle sonsuz kez çalışacak.
Peki, ortalama kaç kez çalışacak?
Ben, yaklaşık olarak (N'nin büyük değerleri için) N2.ln(n) (ya da N ln n, tam hatırlayamadım) tarzında (baskın fonksiyon bu şekilde, yanında altında başka şeyler vardı) bir şey bulmuştum. Zamanında bir harddisk yanmasına kurban gitti.
Yanlış yorumlamadıysam, sizin sorduğunuz soru ile bu soru aynı şeyi soruyor.
Uğraşmak isteyenlere duyurulur.
Soruyu iki türlü düşünün:
1) Beklenen değeri tam olarak bulmaya çalışın?
2) N'nin çok büyük değerleri için beklenen değerin tahmini değerini bulun. Burada tahmini değerden kasıt şu: Diyelim beklenen f(N) = 4+3N + 5(log N)3 + N2 + 3N3 çıkıyor. Bunun tahmini değerine N3 diyebilirsiniz. (Aslında sizden tam değeri bulmadan, daha kısa bir cevap bekleniyor. Sandwich Teoremi gibi, beklenen değer f(N) ken, N'nin büyük değerleri için 2N2 - N<f(N)<3N2+lnN ise f(N) nin yaklaşık değerine N2 diyebiliyoruz.)
-
N'nin büyük değerleri için 2N2 - N<f(N)<3N2+lnN ise f(N) nin yaklaşık değerine N2 diyebiliyoruz.
Selamlar hocam, neden yaklaşık değeri f(N) = 3N2/2 ya da 3N2 seçmiyoruz da sadece N2 seçiyoruz? hem N2 ifadesi verilen eşitsizliği sağlamıyor. Bu kısmı anlamadım. N pozitif tamsayıları için 2N2 - N < N2 olmaz. N3 lü örneğinizde de neden yaklaşık değeri 3N3 almadık?
-
Lokman Hocam arkadaşın bahsettiği konu complexity theory diye geçer. Big-O Notation diye de bahsedilir. Buna göre,
f(N) = O(g(N)) ise bütün n > n0 için f(N) < b*g(N) eşitsizliğini sağlayacak a sayısını bulabiliriz.
Örneğin, f(N) = 3N2/2 = O( N2 ) olduğunu kanıtlayalım.
< 3N2/2 < a*N2 der ve a = 2 seçersek bütün N > 0 için eşitsizliği doğrulamış oluruz. O zaman
f(N) = O(N2)'dir. Buna üst limit de denilir. Yani bir işi yapmak için gereken üst limit fonksiyonu.
Bir de boşbeleş'n dediği gibi Sandwich Theorem'e benzer bir şey var, ona da Tight Bound, yani dar limit denir. Ama bu O ile değil de Theta ile gösterilir.
Tanımı da şu
f(N) = Theta( g(N) ) ise bu sefer g(N)'in bir katı ile hem alttan hem de üstten sınırlıdır.
ag(N) <= f(N) <= bg(N), ve bu her N > N0 içindir. N0'ı, a ve b'yi istediğimiz gibi seçmekte özgürüz. Maksat seçebilmek.
Mesela bir önceki fonksiyon için a = 1, b = 2 seçilebilir. N0 = 0 seçilebilir.
Boşbeleş arkadaşımızın bulduğu yaklaşık limite gelelim:
Benim bulduğum sonuç zaten şöyle:
N * (1/N + 1/(N-1) + 1/(N-2) + ... 1/2 + 1/1)
Parantez içinin toplamı yaklaşık lnN'dir. Çünkü 1/x'in integrali lnx'tir. Yani, Toplam yapılması gereken hamle sayısı yaklaşık olarak N * lnN olur.
-
şöyle bir şey buldum:
http://en.wikipedia.org/wiki/Coupon_collector's_problem
-
Aynı problem :)