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$$