Rastgele yürüyüş

Rastgele yürüyüş (ya da rassal yürüyüş) matematiksel bir nesne olup, bir stokastik veya rastgele süreç olarak bilinir. Bu süreç, herhangi bir matematiksel uzayda –örneğin tamsayılar uzayı–atılan rastgele adımların toplamından oluşan patikayı tanımlamaya yöneliktir. Örneğin, bir molekülün sıvı veya gaz içerisinde izlediği yol, hayvanların yem arayışında takip ettiği patika, değişkenlik gösteren hisse fiyatları ve de bir borsa oyuncusunun finansal durumu rastgele yürüyüş modelleri ile tahmin edilebilir; ancak gerçekte tamamen rastlantısal olmama ihtimalleri de vardır. Bu örneklerin de gösterdiği gibi, rastgele yürüyüş modelinin birçok bilim dalında uygulama alanı mevcuttur; ekoloji, psikoloji, bilgisayar bilimleri, fizik, kimya, biyoloji ve ekonomi bunlara örnektir.

Tek boyutta, sıfırdan başlayan, sekiz adet rastgele yürüyüş örneği. Grafik, anlık çizgi üzerindeki konum (dikey eksen) ile zaman adımlarını (düşey eksen) göstermektedir.

Rassal yürüyüş bahsi geçen alanlarda gözlenen birçok süreci açıklamakla beraber kaydedilmiş stokastik aktiviteyi açıklamak için de temel bir model sunar. Daha matematiksel bir uygulama olarak ise pi sayısına, ajan tabanlı modelleme çerçevesinde, rassal yürüyüş kullanılarak yapılan yaklaşım örnek olarak verilebilir. Rastgele Yürüyüş ilk defa 1905 senesinde tarafından ortaya konmuştur.

Rastgele yürüyüşler, ilginçtir ki, çeşitli şekillerde farklılık gösterebilirler. Rassal yürüyüş teriminin kendisi genelde Markov zincirlerinin veya Markov süreçlerinin özel bir kategorisini belirtir, ancak zamana bağımlı rassal yürüyüş süreçlerinin birçoğu özelliklerini belirten bir niteleyici ile birlikte anılır. Rastgele yürüyüş (Markov olsun ya da olmasın) çeşitli uzaylarda yer alabilir: yaygın olarak incelenenler arasında graf (çizge), tam sayılar ya da gerçek doğru, düzlem ya da yüksek boyutlu vektör uzayları, eğimli yüzeyler ya da daha yüksek boyutlu Riemann manifoldları ve sonlu, sonlu üretilmiş veya Lie grupları verilebilir. Ayrıca zaman parametresi de manipüle edilebilir. En basit bağlamda yürüyüş, ayrık zamanda doğal sayılar üzerinde indislenmiş rastgele değişkenlerin sıralanışıdır ${\displaystyle (X_{t})=(X_{1},X_{2},..)}$. Bununla birlikte adımların rastgele zamanlarda atıldığı rassal yürüyüşler tanımlamak da mümkündür ve bu durumda ${\displaystyle X_{t}}$ her zaman t ∈ [0,+∞) olarak tanımlanmalıdır. Lévy uçuşu, Brown hareketi ve difüzyon modelleri özel durumlar ya da limitler içeren rassal yürüyüş modelleridir.

Rassal yürüyüş, Markov süreçlerini anlamak için bilinmesi gereken temel modeldir.

Örgü Rastegele Yürüyüş

Örgü üzerinde gerçekleşen rassal yürüyüş en bilindik modellerden birisi olup düzenli bir örgüde her adım belirli bir olasılık dağılımına göre atılır. Basit bir rastgele yürüyüşte adımlar ancak bulunulan bölgeden içinde bulunulan örgüyü oluşturan komşu bölgelere atlanarak oluşturulabilir. Yerel olarak sonlu bir örgüde gerçekleştirilen basit simetrik bir rastgele yürüyüşte, bulunulan bölgeden komşulardan herhangi birine geçiş olasılığı aynıdır. En iyi incelenmiş rassal yürüyüş örneği d-boyutlu tam sayı örgüsündedir (bazen hiperkübik kafes olarak da adlandırılır) ${\displaystyle \mathbb {Z} ^{d}}$.

Eğer durum uzayı sonlu boyutlarla sınırlıysa, rastgele yürüyüş modeli basit sınırlandırılmış simetrik rastgele yürüyüş olarak adlandırılır ve geçiş olasılıkları uzayın konumuna bağlıdır, çünkü kenarlar ve köşe noktalarında hareket sınırlıdır.

Bir boyutta rastgele yürüyüş

Tam sayılar kümesinde tanımlı ${\displaystyle \mathbb {Z} }$ bir sayı doğrusu üzerinde 0'dan başlayarak her aşamada +1 veya -1 eşit olasılıkla gerçekleştirilen hareket rastgele yürüyüşün basit bir örneğidir.

Bu yürüyüş aşağıdaki şekilde gösterildiği gibi tasvir edilebilir. Bir gösterge sayı doğrusunda sıfıra yerleştirilir ve hilesiz madeni para çevrilir. Tura gelirse gösterge bir birim sağa taşınır. Yazı gelirse gösterge bir birim sola hareket ettirilir. Beş atıştan sonra gösterge artık 1, -1, 3, -3, 5 veya -5'te olabilir. Beş atıştan üçünün tura ve ikisinin yazı gelişi, sıradan bağımsız olarak, göstergeyi 1'e getirir. Toplamda 1’e ulaşmanın 10 farklı (üç tura ve iki yazı ) -1’e ulaşmanın 10 farklı (üç yazı iki tura), 3’e ulaşmanın 5 farklı (dört tura ve bir yazı) -3’e ulaşmanın 5 (dört yazı ve bir tura) 5’e ulaşmanın 1 (beş tura) ve -5'e ulaşmanın 1 yolu vardır (beş yazı). 5 atışın olası sonuçlarını gösteren illüstrasyon için aşağıdaki şekle bakınız.

5 adet yazı-tura denemesinin olası tüm rastgele yürüyüş sonuçları

2 boyutta içerisinde olası rastgele yürüyüş (animasyon7 Nisan 2017 tarihinde Wayback Machine sitesinde arşivlendi.)

2 boyutta, 25 bin adım ile oluşturulan rastgele yürüyüş (animasyon27 Ocak 2018 tarihinde Wayback Machine sitesinde arşivlendi.)

İki boyutta daha küçük adım boyutları ile oluşturulmuş iki milyon adımdan oluşan rastsal yürüyüş. Daha sık uğranılan kısımlardaki noktalar daha koyu renk olacak şekilde oluşturulmuştur. Adım boyutlarının daha da küçüldüğü limit durumlarında Brown Hareketi elde edilir.

Bu yürüyüşü resmi olarak tanımlamak için birbirinden bağımsız değişkenler alın. ${\displaystyle Z_{1},Z_{2},\dots }$. Bu değişkenlerden her birisi eşit %50 olasılığa sahip olan 1 ya da -1 değerlerinden oluşsun. ${\displaystyle S_{0}=0\,\!}$ olsun ve ${\displaystyle S_{n}=\sum _{j=1}^{n}Z_{j}.}$ şeklinde tanımlansın. {${\displaystyle \{S_{n}\}\,\!}$} serisi ${\displaystyle \mathbb {Z} }$ üzerinde tanımlı basit bir rastsal yürüyüşü ifade edecektir. Bu seri -1 ve 1 değerlerinden oluşan ve adım büyüklüklerinin bire eşit olduğu toplam sonucu verecektir. ${\displaystyle E(S_{n})\,\!}$ Olasılığında ${\displaystyle S_{n}\,\!}$ sıfırdır. Bu, yazı-tura atışları arttıkça ortalamanın sıfıra yaklaştığını anlatır. Buna göre sonlu eklenme özelliği:

${\displaystyle E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.}$ ile gösterilir.

Bağımsız rastsal değişkenler kullanılarak ve ${\displaystyle E(Z_{n}^{2})=1}$ kabulü yapılarak benzer bir hesaplama :

${\displaystyle E(S_{n}^{2})=\sum _{i=1}^{n}\sum _{j=1}^{n}E(Z_{j}Z_{i})=n.}$ ile gösterilir.

${\displaystyle E(|S_{n}|)\,\!}$ sonucuna göre n adım sonrasında beklenen ötelenme miktarı ${\displaystyle {\sqrt {n}}}$ mertebesinde olmalı ve:

${\displaystyle \lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}.}$

Bu sonuç şunu göstermektedir: karma durumlarda yayılım büyük ${\displaystyle N}$ değerleri için etkisizdir.

Sonsuza kadar gitmesine izin verildiği takdirde bir rastgele yürüyüşün kaç kere sınır çizgisinden geçmesi beklenir? ${\displaystyle \mathbb {Z} }$ içindeki basit bir rassal yürüyüş her noktadan sonsuz defa geçer. Bu sonuç kesişen seviyeler fenomeni (level-crossing phenomenon) ve sarhoş yürüyüşü(gambler’s ruin) gibi birçok isimle anılır. Sarhoş yürüyüşü isminin verilme nedeni ise basitçe kumarbazın (gambler) cebinde bulunan kısıtlı para ile bu paraya kıyasla sonsuz miktarda fazla denebilecek paraya sahip bankaya karşı oynadığı kumarı en sonunda kaybetmesi durumundan gelir. Kumarbazın parası (sarhoş yürüyüşü olarak tanımlanan nokta) rastgele yürüyüş ile modellendiğinde de görüldüğü üzere bir noktada sıfıra ulaşacaktır ve oyun bitmiş olacaktır.

a ve b nin pozitif tam sayılar olduğunu varsayarsak; bir boyutta ve 0 dan başlayarak b sayısı üzerinden geçen yahut 0 dan başlayarak -a sayısı üzerinden geçen basit bir rastgele yürüyüşün içerdiği beklenen adım sayısı ab dir. Yürüyüşün b sayısının üzerinden -a sayısından önce geçtiğinin olasılığı ise,bu rastgele yürüyüşün martingale olasılık teorisi gözönünde bulundurularak, ${\displaystyle a/(a+b)}$ şeklinde gösterilir.

Yukarıdaki hesaplamalarda bahsedilen sonuçların bazıları Pascal üçgeni’nin özellikleri kullanılarak türetilebilir. n tane +1 veya -1 adım içeren birbirinden farklı rastgele yürüyüş sayısı 2ⁿ şeklinde gösterilir. Basit bir rastgele yürüyüşte bu adımların atılma olasılığı birbirine eşittir. S_n in k sayısına eşit olması için rastgele yürüyüş içerisindeki +1 adımların, -1 adımların sayısınının üzerine çıkarılması ve böylece k nın çıkarılması gereklidir. ${\displaystyle S_{n}=k}$ durumunu sağlayan rastgele yürüyüş sayısı (n - k)/2 şeklinde gösterilir ve n izin verilen hareket sayısıdır. Bu durumda ${\displaystyle n \choose (n-k)/2}$ gösterimi de kullanılabilir. Anlamlı bir sonuç elde etmek için n ve k çift sayı olmalıdır. Bu nedenle ${\displaystyle S_{n}=k}$ olasılığı ${\displaystyle 2^{-n}{n \choose (n-k)/2}}$ kombinasyonuna eşittir. Pascal üçgeninin girdilerini faktöriyel cinsinden ifade ederek ve sonrasında faktöriyel hesaplaması için Stirling formülünü (Stirling’s approximation) kullanarak büyük n değerleri için yaklaşık sonuçlar elde edilebilir.

Eğer uzay özlük için ${\displaystyle \mathbb {Z} }$+ ile kısıtlanmışsa rastgele bir yürüyüşün beş atışa sahip herhangi bir sayı üzerine ineceği yolların sayısı {0,5,0,4,0,1} şeklinde gösterilebilir.

Pascal üçgeni ile olan bu ilişki, n in küçük değerleri için gösterilmiştir. 0 adımda ise tek ihtimal sıfırda kalacaktır. Ancak 1 adımda sonucun -1 veya +1 olma ihtimali söz konusudur. 2 adımda sonucun +2 ye veya 0 noktasına geri dönme ihtimali vardır. Aynı şekilde -1 noktasından atılan bir adımda ise adımın -2 ye veya 0 noktasına geri dönme ihtimali vardır. Bu nedenle -2 noktasına gitmek için 1 ihtimal, 0 noktasına gitmek için 2 ihtimal, +2 noktasına gitmek için 1 ihtimal vardır. Aşağıdaki tablo basitçe bu hesaplamayı göstermektedir.

k	−5	−4	−3	−2	−1	0	1	2	3	4	5
${\displaystyle P[S_{0}=k]}$						1
${\displaystyle 2P[S_{1}=k]}$					1		1
${\displaystyle 2^{2}P[S_{2}=k]}$				1		2		1
${\displaystyle 2^{3}P[S_{3}=k]}$			1		3		3		1
${\displaystyle 2^{4}P[S_{4}=k]}$		1		4		6		4		1
${\displaystyle 2^{5}P[S_{5}=k]}$	1		5		10		10		5		1

Merkezi limit teoremi ve tekrarlanan logaritma yasası (the law of iterated logarithm), ${\displaystyle \mathbb {Z} }$ içindeki basit bir rastgele yürüyüşün önemli davranışsal yönlerini tanımlar. Özellikle n (her sıradaki sayılar ile orantılı olarak) arttıkça olasılığın normal dağılıma yakınsadığı görülür.

Doğrudan bir genelleme olarak, kristal örgü içerisinde rastgele bir yürüyüşü göz önünde bulunduracak olursak, merkezi limit teoremi ve büyük sapma teoremi (large deviation theorem) saptamak olasıdır.

Markov zinciri açısından

Herhangi bir tek boyutlu rastgele yürüyüş Markov zinciri (Markov chain) açısından incelenebilir. Markov zincirinin belirlediği üzere uzay ${\displaystyle i=0,\pm 1,\pm 2,\dots .}$ şeklinde tanımlanmış olsun. ${\displaystyle \,0<p<1}$ değerini sağlayan p sayıları için adımın ilk durumdan son duruma geçiş olasılığı P_i,j aşağıdaki şekilde gösterilir;

${\displaystyle \,P_{i,i+1}=p=1-P_{i,i-1}.}$