Rasgele yürüyüş

Rasgele yürüyüş (ya da rasgele yürüyüş) matematiksel bir nesne olup, bir stokastik veya rasgele süreç olarak bilinir. Bu süreç, herhangi bir matematiksel uzayda –örneğin tamsayılar uzayı–atılan rasgele 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 rasgele 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, rasgele yürüyüş modelinin birçok bilim dalında uygulama alanı mevcuttur; ekoloji, psikoloji, bilgisayar bilimleri, fizik, kimya, biyoloji ve ekonomi bunlara örnektir.

Rasgele 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, rasgele yürüyüş kullanılarak yapılan yaklaşım örnek olarak verilebilir. Rasgele Yürüyüş ilk defa 1905 senesinde Karl Pearson tarafından ortaya konmuştur.

Rasgele yürüyüşler, ilginçtir ki, çeşitli şekillerde farklılık gösterebilirler. Rasgele yürüyüş teriminin kendisi genelde Markov zincirlerinin veya Markov süreçlerinin özel bir kategorisini belirtir, ancak zamana bağımlı rasgele yürüyüş süreçlerinin birçoğu özelliklerini belirten bir niteleyici ile birlikte anılır. Rasgele 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ş rasgele değişkenlerin sıralanışıdır $(X_{t})=(X_{1},X_{2},..)$ . Bununla birlikte adımların rasgele zamanlarda atıldığı rasgele yürüyüşler tanımlamak da mümkündür ve bu durumda $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 rasgele yürüyüş modelleridir.

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

Örgü Rastegele Yürüyüş

Örgü üzerinde gerçekleşen rasgele 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 rasgele 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 rasgele yürüyüşte, bulunulan bölgeden komşulardan herhangi birine geçiş olasılığı aynıdır. En iyi incelenmiş rasgele yürüyüş örneği d-boyutlu tam sayı örgüsündedir (bazen hiperkübik kafes olarak da adlandırılır) $\mathbb {Z} ^{d}$ .

Eğer durum uzayı sonlu boyutlarla sınırlıysa, rasgele yürüyüş modeli basit sınırlandırılmış simetrik rasgele 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 rasgele yürüyüş

Tam sayılar kümesinde tanımlı $\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 rasgele 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 rasgele yürüyüş sonuçları

Bu yürüyüşü resmi olarak tanımlamak için birbirinden bağımsız değişkenler alın. $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. $S_{0}=0\,\!$ olsun ve $S_{n}=\sum _{j=1}^{n}Z_{j}.$ şeklinde tanımlansın. { $\{S_{n}\}\,\!$ } serisi $\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. $E(S_{n})\,\!$ Olasılığında $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:

E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.

ile gösterilir.

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

E(S_{n}^{2})=\sum _{i=1}^{n}\sum _{j=1}^{n}E(Z_{j}Z_{i})=n.

ile gösterilir.

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

\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 $N$ değerleri için etkisizdir.

Sonsuza kadar gitmesine izin verildiği takdirde bir rasgele yürüyüşün kaç kere sınır çizgisinden geçmesi beklenir? $\mathbb {Z}$ içindeki basit bir rasgele 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) rasgele 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 rasgele 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 rasgele yürüyüşün martingale olasılık teorisi gözönünde bulundurularak, $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ı rasgele yürüyüş sayısı 2ⁿ şeklinde gösterilir. Basit bir rasgele 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 rasgele 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. $S_{n}=k$ durumunu sağlayan rasgele yürüyüş sayısı (n - k)/2 şeklinde gösterilir ve n izin verilen hareket sayısıdır. Bu durumda $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 $S_{n}=k$ olasılığı $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 $\mathbb {Z}$ + ile kısıtlanmışsa rasgele 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
$P[S_{0}=k]$						1
$2P[S_{1}=k]$					1		1
$2^{2}P[S_{2}=k]$				1		2		1
$2^{3}P[S_{3}=k]$			1		3		3		1
$2^{4}P[S_{4}=k]$		1		4		6		4		1
$2^{5}P[S_{5}=k]$	1		5		10		10		5		1

Merkezi limit teoremi ve tekrarlanan logaritma yasası (the law of iterated logarithm), $\mathbb {Z}$ içindeki basit bir rasgele 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 rasgele 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 rasgele yürüyüş Markov zinciri (Markov chain) açısından incelenebilir. Markov zincirinin belirlediği üzere uzay $i=0,\pm 1,\pm 2,\dots .$ şeklinde tanımlanmış olsun. $\,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;

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