7 Mart 2012 Çarşamba

Rastgelenin gücü: Monte Carlo



Pi sayısını hesaplamanın değişik ve sıradışı bir yöntemi vardır:

İçerisine çeyrek çember çizilmiş bir karenin içinde RASTGELE noktalar seçelim. Eğer seçimleriniz gerçekten rastgele(!) ise çeyrek çemberin içinde kalan noktaların sayısının tüm noktaların sayısına oranının çeyrek çemberin alanının karenin alanına oranına yakın bir sayı olmasını bekleriz. Bu alanların oranı da kolayca görülebileceği gibi 'e eşittir. Dolayısı ile sadece bir rastgele sayı üreteci ve bir koşul belirleyerek insanlığın bu en eski problemlerinden biri nispeten "zahmetsizce" çözülebilir. 

Bu tipteki yaklaşımlara Monte Carlo Yöntemi ismi verilir. 20. yy'nın büyük hezarfeni John von Neumann tarafından Los Alamos'da atom bombası üzerinde çalışırken keşfedildiği rivayet edilir ve olasılığa (kabaca "şansa") dayalı yapısı nedeni ile meşhur kumarhanenin ismi ile isimlendirilmiştir. 

Günümüzde Monte Carlo yöntemi fizikten mühendisliğe, hesaplamalı biyolojiden uygulamalı istatistiğe, oyunlardan dizayna ve görsel uygulamalara, finans ve iş dünyası modellerinden telekominikasyona kadar geniş bir yelpazede kendisine uygulama alanı bulur. 

Sadece yukarıdaki pi sayısı örneğini düşünürsek üstteki paragraf biraz abartılı gelebilir zira bu problem az değişkenli bir problemdir ve geleneksel yollardan rahatça çözülebilir. Monte Carlo'nun gücü kendisini çok değişkenli fonksiyonlarda gösterir çünkü bu fonskiyonların integral hesaplamalarının klasik yollarla alacağı zaman fonksiyonun değişken sayısına ÜSTEL bağımlılık gösterir.  Oysa Monte Carlo algoritması "boyutsallık laneti" diye isimlendirilen bu durumdan bu kadar ağır etkilenmez ve yüksek boyutlu problemlerde avantaj sağlamaya başlar.

Yukarıda animasyonu verilen pi sayısı hesaplama problemi için python dilinde yazdığım kısacık bir bilgisayar kodu ile bitirelim. Deneyip kendiniz de görebilirsiniz.

import random        # Python'da rastgele sayi üreten protokolun yer aldigi modul
nokta_sayisi = 100000      # Toplam nokta sayisi
icinde = 0                          # cemberin icinde kalan nokta sayisi
for m in range(nokta_sayisi):
    x = random.random()       # bir noktanin x koordinati
    y = random.random()       # ayni noktanin y koordinati
    if y < (1-x**2)**0.5:    # Cember denkleminden cemberin icinde kalma kosulu
       icinde += 1          # eger kosul dogruysa icindeki nokta sayisini 1 arttirir
pi_sayisi = 4*float(icinde)/float(nokta_sayisi)
print 'Pi sayisi yaklasik olarak:', pi_sayisi

Programı yürüttüğümde aldığım bazi sonuclar:
3.14096
3.14396
3.14684
3.13652
3.1386
3.13224  vs. vs. vs....

5 yorum:

  1. Burda anlamadigim sey, python kodlarinda kurdugunuz dongu, range(100000) icerisindeki tum sayilari m degiskenine atiyoruz ama m degiskenini hic kullanmiyoruz, for yerine while kullansak daha dogru olur gibi geldi bana yada bir yero kacirdim sanirim hocam.

    YanıtlaSil
  2. yüz bin defa bu işlemi yaptırmaktan başka bir anlamı yok orada m'nin. Yani "nokta_sayisi" kadar nokta "atıyor" kafadan ve içeride mi dışarıda mı ona bakıyor.

    YanıtlaSil
  3. Bu yorum yazar tarafından silindi.

    YanıtlaSil
  4. Random metodu yerel saati formulize ederek byte turune donusturur yani rasgele degildir

    YanıtlaSil
    Yanıtlar
    1. Güzel bir nokta bu. Ne var ki rastgelelik, tanımı zor olan bir kavram. Ben şahsen felsefi yaklaşımlardan ziyade ölçülebilirlik ararım. Bunun için de bir metot var. İstatistikte merkezi limit teoremi (central limit theorem) diye bir önerme var. Bu teorem çok sayıda "rastgele" sayının ortalamasını alırsanız ve bu işlemi çok fazla sayıda yaparsanız ortalamaların dağılımının normal (gaussian) olacağını öngörüyor. Dolayısı ile 1000 defa 1000 tane rastgele sayı oluşturup ortalamalarının dağılımına bakıp gaussian şeklini andırıyorsa sayılar rastgeledir denebilir. Arzu ederseniz örnek bir kod yollayabilirim. Yukarıdaki örnekte ise pi'ye yakın sonuç vermesi random metodunun "rastgelelik açısından" fena çalışmadığını söylüyor bana.

      Sil