rastgele yürüyüş

Question

$N\times N$ bir satranç tahtamız olsun. Karelerin renkleri önemli değil. Bu tahtaya bir beyaz ve bir siyah taşı rastgele yerleştirelim. Sonra adım adım bunları rastgele hareket ettirelim, Her adımda her taş ya yerinde kalacak, ya da komşu bir kareye gidecek. Her bir kareye gitme olasılığı eşit. Daha açık yazmak gerekirse:

eğer bir taş tahtanın köşesindeyse, 3 komşusu vardır. 1/4 olasılıkla yerinde kalacak, 1/4'er olasılıkla bu komşulardan birine gidecek.

eğer bir taş tahtanın kenarındaysa, 5 komşusu vardır. 1/6 olasılıkla yerinde kalacak, 1/6'şar olasılıkla bu komşulardan birine gidecek.

eğer ne köşede ne kenardaysa, 8 komşusu vardır. 1/9 olasılıkla yerinde kalacak, 1/9'ar olasılıkla bu komşulardan birine gidecek.

Her adımda hem beyaz hem siyah taş bu rastgele strateji ile hareket edecek.

Bunlar bir ara aynı kareye gelirler. Aynı kareye geldikleri adım sayısı $T$ olsun. $T$'nin beklentisi nedir?

Bilgisayarda simulasyon yapınca $T$'nin beklentisi ile standart sapması çok yakın çıkıyor. Baya bir $N$ için denedim, her zaman çok yakın çıktı. Eşit bunlar galiba. Bunun kanıtı da ikinci soru olsun.

Comments

Senelerdir çözemediğim bir soruydu, buraya yazarken yanıtı buldum. Sayfayı hazırlayanlara teşekkür ediyorum bu nedenle:)

---

Paylasacak misin peki :)

---

Yanılmışım galiba. Emin olmadan birşey yazmayayım.

---

Evet yanılmışım. Kesin olarak anladım. Yanıt bekliyorum yani soruya:)

---

Taşlar nedense kenarlarda bulunmayı sevmiyorlar. Hele köşelerde bulunmayı hiç sevmiyorlar. Tek bir taşı $5\times 5$ lik tahtada 10000 adım hareket ettirdim. Kenarlara pek uğramadı, köşelere hele neredeyse hiç uğramadı. Halbuki köşedeyken bir adım sonra yerinde kalma olasılığı çok daha yüksek. İlginç değil mi?

---

Fizikle bağlantılı olarak düşünülecek olursak -ki rastgele yürüyüş istatistik fizikte çok önemli yeri olan bir problem-modeldir, köşeleri sevmeme durumu entropi (düzensizliğin bir ölçüsü diyebiliriz) niceğilinin dâima artan davranışta (denge durumlarında, yâni dış etki olmaması durumunda ise maksimum) olmasıyla anlaşılabilir. 

Yâni parçacıklar düzensizliği dâimâ maksimum yapacak şekilde hareket ediyorlar. Fizikte entropi, makroskopik bir duruma tekâbül eden mikroskopik durumların sayısı olarak tanımlanıyor. (Daha doğrusu bu sayının doğal logaritmasının bir sâbitle çarpımı, ama önemli değil!) 

Oturduğumuz odadaki hava molekülleri bu sâyede odanın bir köşesinde toplanmıyorlar! (Daha doğrusu, odadaki hava moleküllerinin odanın bir köşesine neden toplanmadığını böylece anlamış oluyoruz) Çünkü bu olayın olma ihtimâli düşük veyâ yukarıdaki şekilde söylersek, çok daha düzenli bir duruma karşılık geliyor.

---

Teşekkürler. Ama ben de moleküller odanın bir köşesine toplansınlar demiyorum ki. Bir molekül odanın ortasında vakit geçirdiği kadar köşelerde niye vakit geçirmiyor acaba diye soruyorum. Her molekül bunu yapsa, odanın köşelerindeki hava yoğunluğu ortadakinden az olur. 

Acaba benim simulasyon mu yanlış, yoksa moleküller bu yukarıdaki stratejiye göre mi hareket etmiyor?

İşte bir taşın $5\times 5$ lik tahtadaki 10000 adımlık serüveninin kaç adımını hangi karede geçirdiğinin tablosu:

230	328	346	329	221
342	510	538	526	331
308	492	550	559	381
367	546	531	570	377
244	385	387	365	237

Görüldüğü gibi taşlar kenarları ve hele köşeleri hiç sevmiyorlar. Belki de benim simulasyonda hata vardır, üşenmeyen bir arkadaş kendisi yazıp denese keşke.

---

2x2'lik durumu analitik olarak hesaplamak mümkün belki 3x3 de hesaplanır. Bu değerlerle simülâsyonu kontrol etmek mümkün olabilir. 2x2 için kaba kuvvetle $<T>=\frac{4^3}{3^2}\sim 7$ buldum.

---

Çok güzel soru.

---

Ben yarın ya da cumartesi bir simülasyon yapıp deneyeceğim. Taşların köşeye gitmemesinden ziyade, ortaya gelmeleri gibi bir durum olmalı. Köşedeki bir kareye gelinebilecek dört kare varken, ortadaki bir kareye gelinebilecek dokuz kare var.

---

Bu soru markov modeli ile cozulmez mi ?  Bir seyleri mi kaciriyorum ?

---

Çözülür tabii ama $T$ için $n$'ye bağlı kapalı bir formül bulamamıştım ben.

Answer 1

İkinci soruya yanıtı buldum bu sefer galiba. Her adımda taşları hareket ettireceğimize, her adımda taşları yeniden tahtaya yerleştiriyormuş gibi düşünebiliriz. Ama tamamen rastgele değil, belli bir olasılık dağılımına göre yerleştireceğiz. Bu olasılık dağılımının nasıl birşey olduğu yukarıdaki soruya yaptığım yorumdan biraz anlaşılıyor. Örneğin köşeleri pek tercih etmeyeceğiz. Ama olasılık dağılımının ne olduğu çok önemli değil. Her adımda hem beyaz hem siyah taşı bu dağılıma göre rastgele yerleştireceğiz.

Her adımda siyah ile beyazı aynı kareye koyma olasılığımız aynı. Buna $p$ diyelim.

Bu durumda $T$, $p$ parametreli geometrik dağılım olur.

Bunun beklentisi $\displaystyle \frac{1}{p}$, standart sapması $\displaystyle \sqrt{\frac{1-p}{p^2}}$ olur. Yani eşit değil, ama $p$ küçük olduğu için çok yakın değerler.