Notların üçüncü bölümünde Stochastic Process'ler konusunda önemli bir denklem olan Chapman-Kolmogorov denklemini ele alacağız. Öncesinde Markov süreçlere dair temel birkaç tanım yaptıktan sonra denklemi ifade edip, çözümüne dair birkaç laf ederek sonunda 'Master Equation' olarak adlandırılan önemli bir denklemi elde edeceğiz.
(NOT: Bu yazıda farklı bir kaynaktan yararlandığım için serinin diğer yazılarından biraz farklı bir notasyon kullandım. Kaynağım V. Balakrishan'ın 'Physical Applications of Stochastic Processes' ders videoları (Lecture 6).)
Elimizde zamanla farklı durumlar arasında 'dolaşan' bir süreç var ve bu süreci gözleyerek zaman serisi şeklinde veriler elde ediyoruz. $\mathbb{X}$ olarak adlandıracağımız bu sürecin durum uzayı ${j_1, j_2, ...}$ (ve kimi zaman da $k$ ve $l$ olarak) ve zaman örnekleri de ${t_1, t_2, ...}$ şeklinde etiketlensin. $\mathbb{X}$ sürecini tanımlayabilmemiz için $j_1$'den başlayıp $n$ adım sonunda $j_n$ durumuna gelen zincir için şu olasılığı yazabilmemiz gerekir:
$$P_n(j_n, t_n; j_{n-1}, t_{-1};...;j_1, t_{-1}) \tag{1}$$ $P_n$ ifadesindeki $n$ kaç adımlık bir olasılık yazdığımızı gösteriyor.
Bu ifadeyi koşullu olasılıklar şeklinde yazarsak şunu elde ederiz:
$$P_n(j_n, t_n; j_{n-1}, t_{-1};...;j_1, t_{-1}) = P_n(j_n, t_n| j_{n-1}, t_{n-1}; ...; j_1, t_1) P_{n-1}(j_{n-1}, t_{n-1}; ... ; j_1, t_1) \tag{2}$$
Üstteki iki olasılık ifadesinden ilki ($P_n$) terimi, fiziksel bir varsayımda bulunursak epey sadeleşiyor; bu da gözlemlediğimiz çoğu sürecin eğer yeteri kadar değişken kullandığımız takdirde bir sonraki adımı, sadece bir önceki adımına bağlı, geçmişteki tüm durumlarından bağımsız olması. Buna Markov özelliği diyoruz. Bu durumda ilk terim şu şekilde sadeleşiyor:
$$P_n(j_n, t_n| j_{n-1}, t_{n-1}; ...; j_1, t_1) = P_2(j_n, t_n|j_{n-1}, t_{n-1}) \tag{3}$$
Markov varsayımını kullandığımızda $(1)$'i aşağıdaki gibi iki adımlık olasılıkların çarpımı şeklinde yazabiliyoruz:
$$P_n(j_n, t_n; j_{n-1}, t_{-1};...;j_1, t_{-1}) = \big(\prod_{r=1}^{n-1}P_2(j_n, t_n|j_{n-1}, t{n-1})\big)P_1(j_1, t_1) \tag{4}$$
Zincirin yapısı gereği, zamanla durumların istatistiklerinin değişmediği yani zincirin evriminin zamana özel olarak bağlı olmadığı süreçleri durağan (stationary) süreçler olarak tanımlıyoruz. Durağanlık, iki durum arası geçiş olasılıklarının her bir durumun ilgili zamanı yerine, iki durumun zaman farklarına bağlı olmasına neden oluyor. Yani hangi zamanlarda değil de aralarında ne kadar zaman farkı ile geçtikleri önem kazanıyor.
$$P_2(k,t|j, t') = f(t-t')$$
Sadece arada geçen zaman önemli olduğuna göre zamanın başlangıç noktasını kaydırarak (bir önceki yazıdaki Markov zincirlerinin zamanda homojen olma özelliğini kullanarak) bu olasılığı şöyle ifade edebiliriz:
$$P_2(k,t|j, t') = P_2(k, t-t'|j, 0) \equiv P_2(k, t- t'|j) \tag{5}$$
Son adımda başlangıç zamanı $0$'ı notasyondan çıkardık ve bundan sonra verilmediği her durum için $0$'dan başladığını düşünüyoruz. Bu tanımlamalar altında $(1)$ denklemini aşağıdaki gibi ifade ediyoruz: $$P_n(j_n, t_n; j_{n-1}, t_{-1};...;j_1, t_{-1}) = \big(\prod_{r=1}^{n-1}P_2(j_{r+1}, t_{r+1} - t_r|j_r)\big) P_1(j) \tag{6}$$
Son olarak zamanda ilerledikçe ($t \to \infty$) $P(k, t| j)$'nin başlangıç durumu $j$'den bağımsızlaşacağını ve durağan duruma eriştiğinde erişilen durumun durağan olasılığına eşit olacağını varsayıyoruz; kısacası zincir yeteri kadar beklendiğinde geçiş hafızasını tamamen unutuyor. Bu durum Markov zincirlerinde 'mixing' (karışma) şeklinde ifade ediliyor. Kısacası elimizdeki olasılıklar şuna indirgeniyor: $$ P(k, t |j) \longrightarrow P(k)$$
Bu şartlar altında zincirin ilk başta $j$ durumundayken, $t$ kadar süre sonra $k$ konumunda olma olasılığını şu şekilde yazabiliriz:
$$\boxed{ P(k, t|j) = \sum_{l = 1}^N P(k, t - t'| l) P(l, t'|j)} \tag{7}$$
Bu denklem bize şunu söylüyor: Eğer $j$'den $k$'ya gitme olasılığını hesaplamak istiyorsak, aradaki her bir $l$ durumundan geçme olasılıklarını bulup çarparak sonuca erişiyoruz. Bu denklem 'Chapman-Kolmogorov Denklemi' olarak biliniyor. Denklem iki olasılık çarpımından oluşuyor; olasılıklara göre doğrusal olmayan (nonlinear) bir denklem olduğundan hesaplaması oldukça güç. Bunu doğrusal bir şekilde yazabilsek hayat çok daha kolaylaşacak. Bunun için de durumların birim zamanda birbirine ortalama geçiş sayısını belirten bir parametre olarak 'geçiş oranı' (transition rate) $w(k,j)$ tanımlıyoruz.
$$P(k, \delta t|j) = w(k|j)\delta t\hspace{1.5cm} k \not= j \tag{8}$$
Kolmogorov-Chaapman denklemindeki geçiş olasılıkları yerine $(8)$'deki ifadeyi yerleştirip $t - t' = \delta t$ olarak aldığımızda aşağıdaki diferansiyel denklemi elde ederiz.
$$ \boxed{\frac{d}{dt} P(k, t |j) = \sum_{l = 1}^N \big[ w(k,l)P(l,t|j) - w(l,k)P(k,t|j)\big]} \tag{9}$$
Bu denklem 'Master Equation' olarak adlandırılıyor. Görüldüğü gibi $(9)$ birinci dereceden bir diferansiyel denklem. $(7)$'deki doğrusal olmayan terim yerine $P$'nin doğrusal terimleri var artık denklemde. Sağdaki toplam, tüm $l$ ara durumları üzerinden yapılıyor. Denklemin sağ tarafında toplam içindeki terim $j$'den önce ara durum olan $l$'ye, ardından nihai durum $k$'ya geçişi yani olasılıktaki artışı(gain term); ikincisi ise önce $j$'den nihai durum $k$'ya, ardından ara durumlardan biri olan $l$'ye geçişi yani olasılıktaki azalmayı (loss term) veren terimler.
Böylece elimizdeki Markov Zinciri'nin başlangıçtaki bir durumdan $t$ kadar süre sonra başka bir duruma geçme olasılığının zamanla değişimini veren bir denklem elde etmiş olduk.
31 Ocak 2018 Çarşamba
30 Ocak 2018 Salı
Stochastic Processes - II
Notlarımızın ikinci kısmına basit bir toplam 2 duruma sahip basit bir Markov Zinciri'ni inceleyerek başlayalım. Elimizde, 1 ve 2 ile etiketlenmiş iki duruma sahip bir Markov Zinciri olsun; durumlar arasındaki geçişler de aşağıdaki diyagramda gösterildiği gibi verilmiş olsun. Okların üzerinde yazan sayılar geçiş olasılıklarını versin.
Zincirin geçiş matrisi $P$'yi şu şekilde yazabiliriz: $$ \begin{pmatrix} 1- \alpha & \alpha \\ \beta & 1 - \beta \end{pmatrix}$$
$\alpha, \beta \in (0,1)$. Geçiş matrisini başlangıç olasılık dağılımı ($\lambda_0$) ile çarparak bir sonraki adımlardaki dağılımları elde ediyoruz. $$ P \lambda_0 = \lambda_1 \\ P \lambda_1 = \lambda_2 = P^2 \lambda_0 \\ ... \\ P^n \lambda_0 = \lambda_n $$
$P^n$ matrisinin büyük $n$ değerleri için nasıl davranacağını anlamak için, $P$'yi orthogonalize edip özdeğer (eigenvalue) ve özvektörlerini (eigenvecor) bulalım.
$$\text{det} (P - \nu \mathbb{I}) = \begin{vmatrix} 1- \alpha - \nu & \alpha \\~\\ \beta & 1 - \beta - \nu \end{vmatrix} = 0 \\~\\ (1- \alpha - \nu) (1 - \beta - \nu) -\alpha \beta = 0 \\~\\ \nu_{1,2} = \frac{2 - \alpha - \beta \pm (\alpha + \beta)}{2}$$
Bu denklemlerden iki özdeğeri $\nu_1 = 1$, karşılık gelen özvektörü $\begin{bmatrix} 1 \\ 1 \end{bmatrix} $ ve $\nu_2 = 1- \alpha - \beta$, karşılık gelen özvektörü de $\begin{bmatrix} - \alpha \\ \beta \end{bmatrix}$ olarak elde ederiz.
$\nu_1 = 1$ değeri sonradan göreceğiz ki Markov Zinciri'nin uzun vadede durağan dağılımını veren özdeğer olacak. $$\lambda^* P = 1 \lambda^* \hspace {1cm} (\lambda^* \hspace{0.2cm} \text{durağan dağılım})$$
$P$'nin $n$. kuvvetini alabilmek için orthogonalleştirmeye çalışıyorduk. Bunun için $M$, $M^{-1}$ ve $D$ matrislerini oluşturmamız gerekiyor: $$ P = M D M^{-1}$$
$M$ matrisi kolonları $P$'nin özvektörleri, $D$ matrisi de $P$'nin özdeğerlerini köşegenlerinde bulunduran matris; $M^{-1}$ de $M$ matrisinin tersi.
$$M = \begin{pmatrix} 1 & \alpha \\ 1 & \beta \end{pmatrix} \hspace{0.5cm} D = \begin{pmatrix} 1 &0 \\ 0 & 1- \alpha - \beta \end{pmatrix}\hspace{0.5cm} M^{-1} = \frac{1}{\beta + \alpha} \begin{pmatrix} \beta & \alpha \\ -1 & -1 \end{pmatrix}$$
$$P^n = (M D M^{-1})^n = M D^n M^{-1} = \frac{1}{\alpha + \beta} \begin{pmatrix} 1 & \alpha \\ 1 & \beta \end{pmatrix} \begin{pmatrix} 1^n &0 \\ 0 & (1- \alpha - \beta)^n \end{pmatrix} \begin{pmatrix} \beta & \alpha \\ -1 & -1 \end{pmatrix} \\~\\ \\~\\ P^n= \frac{1}{\alpha + \beta}\begin{pmatrix} \beta + \alpha(1-\alpha-\beta)^n & \alpha - \alpha (1-\alpha-\beta)^n \\ \beta - \beta(1-\alpha-\beta)^n & \alpha + \beta(1-\alpha-\beta)^n \end{pmatrix} $$
İlgilendiğimiz soru, büyük $n$ değerleri için ($n \to \infty$) $P^n$ matrisinin nasıl davranacağı. $n$'i sonsuza götürdüğümüzde matriste parantez içindeki üslü terimler sıfıra gidecekler çünkü $(1 - \alpha + \beta) \in (-1, 1).$ $$\lim_{n\to\infty} P^n = \begin{pmatrix} \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \\ \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \end{pmatrix} = P^{\infty}$$
Bu limite bakarak belirli bir zaman geçtikten sonra, durumlar arasındaki geçişlerin dengeye oturacağını ve geçiş olasılıklarının sabitleneceğini görüyoruz. Bu durum $n \to \infty$ için Markov zincirinin bir durağan dağılıma erişiyor olmasıyla da ilişkili. İleriki bölümlerde buna da detaylıca değineceğiz.
Zincirin geçiş matrisi $P$'yi şu şekilde yazabiliriz: $$ \begin{pmatrix} 1- \alpha & \alpha \\ \beta & 1 - \beta \end{pmatrix}$$
$\alpha, \beta \in (0,1)$. Geçiş matrisini başlangıç olasılık dağılımı ($\lambda_0$) ile çarparak bir sonraki adımlardaki dağılımları elde ediyoruz. $$ P \lambda_0 = \lambda_1 \\ P \lambda_1 = \lambda_2 = P^2 \lambda_0 \\ ... \\ P^n \lambda_0 = \lambda_n $$
$P^n$ matrisinin büyük $n$ değerleri için nasıl davranacağını anlamak için, $P$'yi orthogonalize edip özdeğer (eigenvalue) ve özvektörlerini (eigenvecor) bulalım.
$$\text{det} (P - \nu \mathbb{I}) = \begin{vmatrix} 1- \alpha - \nu & \alpha \\~\\ \beta & 1 - \beta - \nu \end{vmatrix} = 0 \\~\\ (1- \alpha - \nu) (1 - \beta - \nu) -\alpha \beta = 0 \\~\\ \nu_{1,2} = \frac{2 - \alpha - \beta \pm (\alpha + \beta)}{2}$$
Bu denklemlerden iki özdeğeri $\nu_1 = 1$, karşılık gelen özvektörü $\begin{bmatrix} 1 \\ 1 \end{bmatrix} $ ve $\nu_2 = 1- \alpha - \beta$, karşılık gelen özvektörü de $\begin{bmatrix} - \alpha \\ \beta \end{bmatrix}$ olarak elde ederiz.
$\nu_1 = 1$ değeri sonradan göreceğiz ki Markov Zinciri'nin uzun vadede durağan dağılımını veren özdeğer olacak. $$\lambda^* P = 1 \lambda^* \hspace {1cm} (\lambda^* \hspace{0.2cm} \text{durağan dağılım})$$
$P$'nin $n$. kuvvetini alabilmek için orthogonalleştirmeye çalışıyorduk. Bunun için $M$, $M^{-1}$ ve $D$ matrislerini oluşturmamız gerekiyor: $$ P = M D M^{-1}$$
$M$ matrisi kolonları $P$'nin özvektörleri, $D$ matrisi de $P$'nin özdeğerlerini köşegenlerinde bulunduran matris; $M^{-1}$ de $M$ matrisinin tersi.
$$M = \begin{pmatrix} 1 & \alpha \\ 1 & \beta \end{pmatrix} \hspace{0.5cm} D = \begin{pmatrix} 1 &0 \\ 0 & 1- \alpha - \beta \end{pmatrix}\hspace{0.5cm} M^{-1} = \frac{1}{\beta + \alpha} \begin{pmatrix} \beta & \alpha \\ -1 & -1 \end{pmatrix}$$
$$P^n = (M D M^{-1})^n = M D^n M^{-1} = \frac{1}{\alpha + \beta} \begin{pmatrix} 1 & \alpha \\ 1 & \beta \end{pmatrix} \begin{pmatrix} 1^n &0 \\ 0 & (1- \alpha - \beta)^n \end{pmatrix} \begin{pmatrix} \beta & \alpha \\ -1 & -1 \end{pmatrix} \\~\\ \\~\\ P^n= \frac{1}{\alpha + \beta}\begin{pmatrix} \beta + \alpha(1-\alpha-\beta)^n & \alpha - \alpha (1-\alpha-\beta)^n \\ \beta - \beta(1-\alpha-\beta)^n & \alpha + \beta(1-\alpha-\beta)^n \end{pmatrix} $$
İlgilendiğimiz soru, büyük $n$ değerleri için ($n \to \infty$) $P^n$ matrisinin nasıl davranacağı. $n$'i sonsuza götürdüğümüzde matriste parantez içindeki üslü terimler sıfıra gidecekler çünkü $(1 - \alpha + \beta) \in (-1, 1).$ $$\lim_{n\to\infty} P^n = \begin{pmatrix} \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \\ \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \end{pmatrix} = P^{\infty}$$
Bu limite bakarak belirli bir zaman geçtikten sonra, durumlar arasındaki geçişlerin dengeye oturacağını ve geçiş olasılıklarının sabitleneceğini görüyoruz. Bu durum $n \to \infty$ için Markov zincirinin bir durağan dağılıma erişiyor olmasıyla da ilişkili. İleriki bölümlerde buna da detaylıca değineceğiz.
29 Ocak 2018 Pazartesi
Discrete Stochastic Processes - I
Matematik Köyü'nde Kış döneminde takip ettiğim Arif Mardin hocanın 'Discrete Stochastic Processes' dersinin notlarnı gün gün tutmaya çalışıyorum. Elimdeki notlardan kendi anladığım şekliyle burada da bir seri şeklinde kısa kısa yazmayı planlıyorum. İlk yazı ile başlayalım o halde.
İlk derse 'Basit Rastgele Yürüyüş' (Simple Random Walk) ile başladık ve sonrasında onun Markov özelliklerinden yola çıkarak Markov Zincir'lerini inceledik. Rastgele yürüyüşü elindeki bir miktar parası olup, kumar masasında her oyunda $p$ olasılıkla parasını $1$ arttıran, $1-p$ olasılıkla da 1 azaltan bir kumarbazın durumu için değerlendirebiliriz. Bu durumda $n$ oyun/adım sonrasında kumarbazın elindeki parayı şu şekilde yazabiliriz: $$S_n = S_0 + \sum_{i = 1}^n X_i$$ Burada $S_0$ başlangıçtaki para ve $X_i$'ler de her oyunda kazanıp kaybettiğimiz parayı gösteren rassal değişken. $X_i$ rassal değişkeni yalnızca $+1$ ve $-1$ değerleri alabilen bir 'Bernouilli rassal değişkeni'. $X_0, X_1, ... , X_n$ serisi $p$ olasılıkla $+1$, $1-p$ olasılıkla da $-1$ değerleri alabilen Bernoulli rassal değişkenlerinden oluşan bir dizidir.
Bu tip basit bir kurala dayalı olarak kurgulanmış bu oyuna dair birçok ilginç soru sorulabilir. Örneğin:
- $n$ oyun sonrasında ne kadar kazanmayı bekleriz?
- Kazancımızın ya da kaybımızın yeteri kadar oynadığımızda sonsuz olmasını bekler miyiz? Hangi koşulda böyle bir durum oluşur?
- Herhangi bir zamanda cebimizdeki bir para değerine sonra tekrar dönmeyi bekler miyiz? Kaç kere döneriz? Bu durum tüm para değerleri için gerçekleşir mi?
Rastgele yürüyüş problemi bunlar gibi birbirinden ilginç ve çoğu zaman çözümü epey uğraştırıcı birçok probleme kaynaklık yapıyor. İlerleyen zamanda daha detaylıca inceleyeceğiz. Birkaç özelliğine göz atalım şimdi.
Lemma 1: Basit rastgele yürüyüş uzayda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}(S_ n = j +b | S_0 = a+b)$$
Kanıt: $ \mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}( \sum_i^n X_i = j - a) = \mathbb{P}(S_n = j +b | S_0 = a + b)$
Lemma 2: Basit rastgele yürüyüş zamanda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}(S_{n+m} = j | S_m= a) $$
Kanıt: $ \mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}( \sum_i^n X_i = j - a) = \mathbb{P}( \sum_{i = m+1}^{m+n} X_i = j - a) = \mathbb{P}(S_{n+m} = j | S_m = a)$
Lemma 3 (Markov Özelliği): Rastgele yürüyüşün belirli bir andan sonraki adımları sadece bulunduğu adımdan bir önceki adımına bağlıdır, ondan öncekilerden tamamen bağımsızdır. $$\mathbb{P} = (S_{m+n} = j | S_0,S_1, ..., S_m) = \mathbb{P}(S_{m+n} = j | S_m)$$ Yukarıdaki şartlı olasılık ifadesindeki $S_0,S_1, ..., S_m$, 0. adımda $S_0$, 1. adımdaki $S_1$, $...$ m. adımda $S_m$ olayının gerçekleştiğini gösteriyor. Rastgele yürüyüş'ün bu özelliği ona birçok ilginç davranış kazandırıyor. Bunları anlayabilmek için öncelikle Markov Zincir'lerine kısaca bir göz atalım.
MARKOV ZİNCİRLERİ
Belirli bir sayılabilir (countable) durumu barındıran bir 'durum uzayı' $\mathcal{S}$ üzerinde tanımlı, bu durumları $n$ ile gösterilen adımlarda dolaşan bir proses olarak tanımlayabiliriz.
$\mathbb{X} = (X_n, n \in \mathbb{N}$, $\mathcal{S}$'den değerler alan birer rassal değişkenler dizisi olsun.
Tanım: $\mathbb{X}$ dizisi tüm $\forall n \in \mathbb{N}$ ve $\forall i_0, i_1, ..., i_n \in \mathcal{S}$ için Markov özelliği $$ \mathbb{P} (X_{n+1} = i_{n+1} | X_0 = i_0, X_1= i_1, ... , X_n = i_n) = \mathbb{P}(X_{n+1} = i_{n+1} | X_n = i_n)$$ sağlıyorsa Markov Zinciri (Markov Chain - MC) olarak adlandırılır.
Markov Zinciri eğer $\forall i, j \in \mathcal{S}$ için $\mathbb{P} ( X_{n+1} = j|X_n = 1)$ $n$'e bağlı değilse homojen olarak adlandırılır.
Olasılıkları hesaplamak için iki şeyi bilmemiz gerekir:
a) Geçiş matrisi (Transition Matrix) $P = (p_{ij} \hspace{0.5cm} i,j \in \mathcal{S})$ aşağıdaki gibi verilir: $$ P_{ij} = \mathbb{P}(X_1 = j| X_0 = i)$$
b) Başlangıç olasılık dağılımı $\lambda = (\lambda_i, i \in \mathcal{S})$
Homojenlik varsayımı gereği şunu yazabiliriz: $$\mathbb{P} (X_{n+1} = j | X_n = i) = P_{ij}$$
Önermeler:
a)$\lambda$ vektörü bir olasılık dağılımıdır. $$ \lambda_i \geqslant 0 \hspace{0.5cm} \forall i \in \mathcal{S} \hspace{0.3cm} \text{ve} \sum_{i \in \mathcal{S}}\lambda_i = 1$$
b) $P = (p_{ij}\hspace{0.3cm}; i,j \in \mathcal{S})$ matrisi bir 'stochastic matris'tir.
i) $P_{ij} \geqslant 0 \forall i,j \in \mathcal{S}$
ii)$\sum_{j \in \mathcal{S}} P_{ij} = 1 \forall i \in \mathcal{S} $ ($P$'nin satır toplamları $1$'e eşit.
Önermelerin kanıtları:
a) $\lambda_i$'ler bir olasılık olduğundan sıfırdan büyük eşit olmalılar. $$\sum_{i \in \mathcal{S}} \lambda_i = \sum_{i \in \mathcal{S} } \mathbb{P} (X_0 = i) = 1 \hspace {1.5cm} \square$$
b)$P_{ij}$'ler olasılık değerleri olduğundan dolayı sıfırdan büyük eşit olmalılar. $$ \sum_{j \in \mathcal{S}}P_{i,j} = \sum_{i \in \mathcal{S}}\mathbb{P} (X_1 = j |X_0 = i) = \mathbb{P}(X_1 \in \mathcal{S} | X_0 = i) = 1 \hspace{1.5cm} \square$$
İlk derse 'Basit Rastgele Yürüyüş' (Simple Random Walk) ile başladık ve sonrasında onun Markov özelliklerinden yola çıkarak Markov Zincir'lerini inceledik. Rastgele yürüyüşü elindeki bir miktar parası olup, kumar masasında her oyunda $p$ olasılıkla parasını $1$ arttıran, $1-p$ olasılıkla da 1 azaltan bir kumarbazın durumu için değerlendirebiliriz. Bu durumda $n$ oyun/adım sonrasında kumarbazın elindeki parayı şu şekilde yazabiliriz: $$S_n = S_0 + \sum_{i = 1}^n X_i$$ Burada $S_0$ başlangıçtaki para ve $X_i$'ler de her oyunda kazanıp kaybettiğimiz parayı gösteren rassal değişken. $X_i$ rassal değişkeni yalnızca $+1$ ve $-1$ değerleri alabilen bir 'Bernouilli rassal değişkeni'. $X_0, X_1, ... , X_n$ serisi $p$ olasılıkla $+1$, $1-p$ olasılıkla da $-1$ değerleri alabilen Bernoulli rassal değişkenlerinden oluşan bir dizidir.
Bu tip basit bir kurala dayalı olarak kurgulanmış bu oyuna dair birçok ilginç soru sorulabilir. Örneğin:
- $n$ oyun sonrasında ne kadar kazanmayı bekleriz?
- Kazancımızın ya da kaybımızın yeteri kadar oynadığımızda sonsuz olmasını bekler miyiz? Hangi koşulda böyle bir durum oluşur?
- Herhangi bir zamanda cebimizdeki bir para değerine sonra tekrar dönmeyi bekler miyiz? Kaç kere döneriz? Bu durum tüm para değerleri için gerçekleşir mi?
Rastgele yürüyüş problemi bunlar gibi birbirinden ilginç ve çoğu zaman çözümü epey uğraştırıcı birçok probleme kaynaklık yapıyor. İlerleyen zamanda daha detaylıca inceleyeceğiz. Birkaç özelliğine göz atalım şimdi.
Lemma 1: Basit rastgele yürüyüş uzayda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}(S_ n = j +b | S_0 = a+b)$$
Kanıt: $ \mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}( \sum_i^n X_i = j - a) = \mathbb{P}(S_n = j +b | S_0 = a + b)$
Lemma 2: Basit rastgele yürüyüş zamanda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}(S_{n+m} = j | S_m= a) $$
Kanıt: $ \mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}( \sum_i^n X_i = j - a) = \mathbb{P}( \sum_{i = m+1}^{m+n} X_i = j - a) = \mathbb{P}(S_{n+m} = j | S_m = a)$
Lemma 3 (Markov Özelliği): Rastgele yürüyüşün belirli bir andan sonraki adımları sadece bulunduğu adımdan bir önceki adımına bağlıdır, ondan öncekilerden tamamen bağımsızdır. $$\mathbb{P} = (S_{m+n} = j | S_0,S_1, ..., S_m) = \mathbb{P}(S_{m+n} = j | S_m)$$ Yukarıdaki şartlı olasılık ifadesindeki $S_0,S_1, ..., S_m$, 0. adımda $S_0$, 1. adımdaki $S_1$, $...$ m. adımda $S_m$ olayının gerçekleştiğini gösteriyor. Rastgele yürüyüş'ün bu özelliği ona birçok ilginç davranış kazandırıyor. Bunları anlayabilmek için öncelikle Markov Zincir'lerine kısaca bir göz atalım.
MARKOV ZİNCİRLERİ
Belirli bir sayılabilir (countable) durumu barındıran bir 'durum uzayı' $\mathcal{S}$ üzerinde tanımlı, bu durumları $n$ ile gösterilen adımlarda dolaşan bir proses olarak tanımlayabiliriz.
$\mathbb{X} = (X_n, n \in \mathbb{N}$, $\mathcal{S}$'den değerler alan birer rassal değişkenler dizisi olsun.
Tanım: $\mathbb{X}$ dizisi tüm $\forall n \in \mathbb{N}$ ve $\forall i_0, i_1, ..., i_n \in \mathcal{S}$ için Markov özelliği $$ \mathbb{P} (X_{n+1} = i_{n+1} | X_0 = i_0, X_1= i_1, ... , X_n = i_n) = \mathbb{P}(X_{n+1} = i_{n+1} | X_n = i_n)$$ sağlıyorsa Markov Zinciri (Markov Chain - MC) olarak adlandırılır.
Markov Zinciri eğer $\forall i, j \in \mathcal{S}$ için $\mathbb{P} ( X_{n+1} = j|X_n = 1)$ $n$'e bağlı değilse homojen olarak adlandırılır.
Olasılıkları hesaplamak için iki şeyi bilmemiz gerekir:
a) Geçiş matrisi (Transition Matrix) $P = (p_{ij} \hspace{0.5cm} i,j \in \mathcal{S})$ aşağıdaki gibi verilir: $$ P_{ij} = \mathbb{P}(X_1 = j| X_0 = i)$$
b) Başlangıç olasılık dağılımı $\lambda = (\lambda_i, i \in \mathcal{S})$
Homojenlik varsayımı gereği şunu yazabiliriz: $$\mathbb{P} (X_{n+1} = j | X_n = i) = P_{ij}$$
Önermeler:
a)$\lambda$ vektörü bir olasılık dağılımıdır. $$ \lambda_i \geqslant 0 \hspace{0.5cm} \forall i \in \mathcal{S} \hspace{0.3cm} \text{ve} \sum_{i \in \mathcal{S}}\lambda_i = 1$$
b) $P = (p_{ij}\hspace{0.3cm}; i,j \in \mathcal{S})$ matrisi bir 'stochastic matris'tir.
i) $P_{ij} \geqslant 0 \forall i,j \in \mathcal{S}$
ii)$\sum_{j \in \mathcal{S}} P_{ij} = 1 \forall i \in \mathcal{S} $ ($P$'nin satır toplamları $1$'e eşit.
Önermelerin kanıtları:
a) $\lambda_i$'ler bir olasılık olduğundan sıfırdan büyük eşit olmalılar. $$\sum_{i \in \mathcal{S}} \lambda_i = \sum_{i \in \mathcal{S} } \mathbb{P} (X_0 = i) = 1 \hspace {1.5cm} \square$$
b)$P_{ij}$'ler olasılık değerleri olduğundan dolayı sıfırdan büyük eşit olmalılar. $$ \sum_{j \in \mathcal{S}}P_{i,j} = \sum_{i \in \mathcal{S}}\mathbb{P} (X_1 = j |X_0 = i) = \mathbb{P}(X_1 \in \mathcal{S} | X_0 = i) = 1 \hspace{1.5cm} \square$$
Kaydol:
Kayıtlar (Atom)