[S. 5] Rastgele sayı üretmek ve kâhinlik

Blogun bir sonraki yazısının müzikle ilgili olacağına söz vermiştim ancak geçen haftalarda Twitter’da bahsettiğim hoş bir problem hakkında [S] serisine kısa bir yazı eklemeden duramadım.

Bir sayı tahmin oyunu

Can rastgele iki farklı gerçel sayı seçsin ve bu sayıları iki kağıda yazsın. Numan, kağıtlarda yazan sayılara bakmadan, kağıtların birini rastgele seçsin. Can, Numan’a bu kağıtta yazan sayıyı söylesin. Numan’ın amacı, seçtiği kağıttaki sayının Can’ın yazdığı sayıların büyüğü mü küçüğü mü olduğunu tahmin etmek. Bizim amacımız Numan için bir tahmin stratejisi geliştirmek. Aşikar bir gözlemle başlayalım.

Önerme: Numan’ın doğru tahmin etme olasılığını 1/2 yapan bir strateji vardır.
Kanıt: Numan seçtiği sayının büyük sayı olduğunu söylesin. \blacksquare

Numan seçtiği kağıdı rastgele seçtiği için ve Can’ın sayıları nasıl seçtiğini bilmediği için 1/2 olasılıktan daha iyisinin yapılamayacağını düşünüyor olabilirsiniz. Ben de soruyu ilk duyduğumda böyle düşünmüştüm. Her şey çok “simetrik” gözüküyor. Ancak gerçekler böyle değilmiş.

Rastgele sayı üreterek kâhinlik yapmak

Numan verilen bir sürekli olasılık dağılımına göre rastgele sayı üretebiliyorsa, kendisinin bunu kullanarak doğru tahmin etme olasılığını artırması mümkün.

Teorem: Numan’ın doğru tahmin etme olasılığını 1/2’den daha büyük yapan bir strateji vardır.
Kanıt: Numan önce standart normal dağılıma göre rastgele bir x sayısı üretsin. (Aslında burada dağılımın normal olması çok önemli değil. Numan’ın gerçel sayıların her noktasında pozitif sürekli bir olasılık dağılımına göre rastgele sayı üretmesi yeterli.)

Eğer seçtiği kağıttaki sayı x’den büyükse, seçtiği kağıttaki sayının büyük sayı olduğunu söylesin. Eğer seçtiği kağıttaki sayı x’den küçükse, seçtiği kağıttaki sayının küçük sayı olduğunu söylesin. Eğer seçtiği kağıttaki sayı x’e eşitse, canı ne isterse onu yapsın; mesela seçtiği kağıttaki sayının büyük sayı olduğunu söylesin.

Can’ın kağıtlara yazdığı sayılar a<b olsun. Elimizdeki durumlar şunlar:

  • (x<a<b): Bu durumda Numan seçtiği kağıttaki sayının büyük sayı olduğunu söyleyecek. Dolayısıyla 1/2 olasılıkla doğru tahminde bulunacak.
  • (a<b<x): Bu durumda Numan seçtiği kağıttaki sayının küçük sayı olduğunu söyleyecek. Dolayısıyla 1/2 olasılıkla doğru tahminde bulunacak.
  • (a<x<b): Bu durumda Numan kesinlikle doğru tahminde bulunacak.
  • (a=x veya b=x): Numan’ın kullandığı dağılım noktalara sıfır olasılık atadığı için bu durumun gerçekleşme olasılığı sıfır ve az sonra yapacağımız hesaba bir etkisi olmayacak.

Demek ki Numan’ın bu stratejiyle doğru tahminde bulunma olasılığı

\frac{Pr(x<a)}{2}+\frac{Pr(b<x)}{2}+Pr(a<x<b)=

\frac{Pr(x<a)+Pr(b<x)+Pr(a<x<b)}{2}+\frac{Pr(a<x<b)}{2}=\frac{1}{2}+\frac{Pr(a<x<b)}{2}

Numan’ın rastgele sayı ürettiği dağılım her noktada pozitif olduğuna göre \frac{Pr(a<x<b)}{2} pozitif bir sayı. Demek ki Numan’ın bu stratejiyle doğru tahminde bulunma olasığı 1/2’den daha büyük. \blacksquare

Bu hoş probleme şu sayfada denk geldim. Mevzubahis strateji “Pick the largest number” isimli bir sayfalık şu yazıdan. Problemin Wikipedia sayfasına şuradan ve ilgili bir MathOverflow sorusuna şuradan erişilebilir.

C.N.

Reklamlar

[S. 5] Rastgele sayı üretmek ve kâhinlik” üzerine 12 düşünce

  1. atlanılan bir nokta var ki arkadaş “x sayısı” için bir değer belirlediğinde bu da tahmin olasılığına eklenmelidir. yani bir önermeye sentetik bir şart atayıp sonra da olasılık arttı demek mantıken yanlıştır, oluşturulan sentetik yapı da olasılığa dahil edilmelidir.

    Beğen

    • x sayısı belirlenmiyor. Can ve Numan’ın oynadığı deneyi tekrarlasak, yani Can bir olasılık dağılımına göre sürekli iki sayı üretse, Numan bu sayıların birini rastgele seçse ve normal dağılıma göre bir x sayısı üretip yukarıdaki stratejiyi uygulasa, her deneyde Numan (muhtemelen) başka bir x sayısına göre cevap verecek. Hesapta bir hata yok; belki stratejiyi iyi ifade edememiş olabilirim.

      Stratejinin “statik” halini görmek için şu örneği düşünebilirsiniz. Diyelim ki Can’ın seçtiği sayıların [0,10] aralığında olduğunu biliyoruz ve sayıları uniformly random bir şekilde seçsin bu aralıktan.. Bu durumda Numan rastgele sayı üretmek yerine x=5 seçerek yukarıdaki stratejiyi uygularsa 0.75 olasılıkla doğru tahmin edecektir. (0.5 olasılıkla Can’ın seçtiği sayıların ikisi de ya (0,5) ya da (5,10) aralığında, ki bu durumda Numan 0.5 olasılıkla doğru tahminde bulunuyor. 0.5 olasılıkla Can’ın seçtiği sayıların biri (0,5) aralığında diğeri (5,10) aralığında, ki bu durumda Numan kesinlikle doğru tahminde bulunuyor. Dolayısıyla 0.5*0.5+0.5=0.75)

      Aslında bu “statik” stratejiyi genel duruma da uygulayabiliriz. Diyelim ki Can sayılarını standart normal dağılıma göre seçiyor. Numan da kendisine gösterilen sayı pozitifse bu sayının büyük sayı olduğunu, negatifse bu sayının küçük sayı olduğunu söylesin (yani x=0 durumunda yukarıdaki stratejiyi uygulasın). Bu durumunda Numan’ın doğru bilme olasılığı gene 0.75 olacaktır. Tabii asıl problemde Can’ın sayıları nasıl seçtiğini bilmiyoruz, sadece ilgili olasılığın 0.5’den büyük olabileceğini göstermek adına örneklemek istedim.

      Beğen

  2. Şöyle daha güzel bir soru var:

    100 tane kağıda uniform dağılıma göre (her sayı eşit olasılıkta) rastgele bir sayı yazılsın.
    Kağıtlara sırayla bakma hakkımız var. Herhangi bir anda son baktığımız kağıdı seçebiliyoruz.
    – En büyük rakamı seçmemiz için izlenecek en iyi strateji nedir?
    – Bu stratejiye göre en büyük rakamı seçme ihtimalimiz nedir?

    Beğen

    • Arkadaşlar (genel olarak bloga yorum yapanlar),

      Yazan şeylerin saçma olduğunu iddia ediyorsanız bir zahmet saçmalığın da nerede olduğunu açıklayın.

      Bakın diğer yorumda yukarıdaki deneyin belirli bir aralıkta olan versiyonunu da verdim:

      Birisi uniformly random iki sayı seçsin [0,1] aralığından. Sonra sayılardan rastgele birini seçip size göstersin. Eğer bu sayı 1/2’den büyükse o sayının büyük sayı olduğunu 1/2’den küçükse küçük sayı olduğunu tahmin edin. (Ortada rastgele sayı üretme falan yok dikkatinizi çekerim.)

      Bu durumda doğru bilme olasılığınız %75. Önce problemin bu basitleştirilmiş versiyonunu anlamaya çalışın. Bunu becerdikten sonra yukarıdaki çözümü tekrar okuyun.

      Beğen

    • Problemin discrete durumunu denemeniz için, aşağıdaki basit C kodu 0 ile 1000 arasında iki rastgele (tam)sayı üretiyor (s1 ve s2), daha sonra bunlardan rastgele birini seçiyor (Numan’a gösterilen sayı r), Numan için rastgele bir sayı üretiyor (s) ve bunları ilgili stratejiye göre karşılaştırıp Numan her doğru bildiğinde hanesini (j) bir artırıyor. Deneyi 1 milyon kere yaptığınızda karşınıza çıkan sonuç (olması gerektiği gibi) %66.

      http://pastebin.com/DFt6U4dL

      Numan rastgele sayı üretmek yerine 0-1000 aralığının ortasını referans sayısı olarak kullanırsa (yani s=500), bu durumda da 1 milyon denemeden sonra ilgili sonuç (olması gerektiği gibi) %75.

      http://pastebin.com/0DecDviZ

      Beğen

  3. http://pastebin.com/iiAhP3nW
    şurdaki kod basitçe 3 farklı 1-1000 aralığında sayı üretip (a b x), a’nın büyük sayı mı küçük sayı mı olduğunu tahmin etmeye çalışıyor. Birinde x’i kullanarak birinde tamamen rastgele.
    100bin denemede şu şekilde doğru tahmin sayıları:
    [66509,49460] (ilk sayı yazıda anlatılan yöntemle yapılan tahminler, diğeri direkt rastgele)

    Bilgisayarda normal dağılımla rastgele sayı üretmeyi bilmediğim için bi sayı aralığı kullandım. Yani %100 facebook onaylı çalışıyor 😀

    Beğen

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Connecting to %s