4 Markov Zincirlerine Giriş
4.1 Markov Özelliği
Şimdiye kadar incelediğimiz süreçlerde geleceği tahmin etmek için sürecin bütün geçmişine ihtiyaç duyulabiliyordu. Markov süreçleri bu yükü ortadan kaldırır: şu anki durumu bilmek yeterlidir, geçmiş fazladan bilgi taşımaz.
Tanım 4.1 (Markov Özelliği) \(\{X_n \mid n \geq 0\}\) bir stokastik süreç olsun. Her \(n\) ve her durum dizisi için
\[P\{X_{n+1} = j \mid X_n = i_n,\; X_{n-1} = i_{n-1},\; \dots,\; X_0 = i_0\} = P\{X_{n+1} = j \mid X_n = i_n\}\]
eşitliği sağlanıyorsa sürecin Markov özelliğine sahip olduğu söylenir ve sürece Markov süreci denir.
\(X_i\) rasgele değişkenlerinin bütün olası değerlerinin kümesi durum uzayı olarak adlandırılır ve \(S\) ile gösterilir.
Tanım 4.2 (Markov Zinciri) Durum uzayı kesikli olan bir Markov sürecine Markov zinciri denir.
Markov zincirleri, stokastik sistemlerin kısa veya uzun dönemdeki davranışlarının modellenmesinde kullanılır.
Bir adımlık geçiş olasılığı çoğu kaynakta
\[P\{X_{n+1} = j \mid X_n = i\} = p_{ij}(n, n+1)\]
biçiminde yazılır. Geçiş olasılıkları \(n\)’den bağımsızsa zincire homojen denir ve kısaca \(p_{ij}\) yazılır. Bu derste aksi belirtilmedikçe zincirler homojendir.
\(n\) adımlık geçiş olasılığı ise
\[P\{X_n = j \mid X_0 = i\} = p_{ij}(0, n) = p_{ij}^{(n)}\]
ile gösterilir.
4.2 Geçiş Olasılık Matrisi
Tanım 4.3 (Geçiş Olasılık Matrisi) \(\{X_n \mid n \geq 0\}\), durum uzayı \(S = \{0, 1, 2, \dots\}\) olan bir Markov zinciri olsun. \(i\) durumundan \(j\) durumuna bir adım geçiş olasılığı
\[p_{ij} = P\{X_{n+1} = j \mid X_n = i\}\]
ile tanımlansın. Bu olasılıkların oluşturduğu
\[P = [\,p_{ij}\,] = \begin{pmatrix} p_{00} & p_{01} & \cdots \\ p_{10} & p_{11} & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix}\]
matrisine sürecin geçiş olasılık matrisi denir.
Bu matrisin iki temel özelliği vardır:
\[p_{ij} \geq 0 \quad \text{ve} \quad \sum_{j} p_{ij} = 1 \quad \text{(her } i \text{ için)}\]
İkinci koşul şunu söyler: her satırın toplamı \(1\) olmalıdır. Bunun sebebi açıktır — \(i\) durumundan bir adım sonra mutlaka bir yere gidilir.
Tanım 4.4 (Stokastik Süreç Matrisi (SSM)) Örnek uzay sonlu, \(S = \{1, 2, \dots, m\}\) ise geçiş matrisi \(m \times m\) boyutlu
\[P = \begin{pmatrix} p_{11} & p_{12} & \cdots & p_{1m} \\ \vdots & \vdots & & \vdots \\ p_{m1} & p_{m2} & \cdots & p_{mm} \end{pmatrix}\]
olur. Elemanları negatif olmayan ve her satırının toplamı \(1\) olan bu tür bir kare matrise Markov matrisi ya da stokastik süreç matrisi (SSM) denir.
4.3 Olasılık Vektörleri
Tanım 4.5 (Olasılık Vektörü) Bir stokastik matrisin her satırı bir olasılık vektörü olarak adlandırılır. Bir vektörün olasılık vektörü olması için iki koşul birlikte sağlanmalıdır:
- bütün elemanları negatif olmamalı;
- elemanlarının toplamı \(1\) olmalıdır.
Örnek 4.1 (Hangileri Olasılık Vektörüdür?) Aşağıdakilerden hangileri olasılık vektörüdür?
\[\text{i)} \; \left(\tfrac13, \tfrac13, -\tfrac13, \tfrac13\right) \qquad \text{ii)} \; \left(0, \tfrac12, \tfrac32, \tfrac12\right) \qquad \text{iii)} \; \left(0, \tfrac12, \tfrac12\right)\]
Çözüm
i) \(-\tfrac13 < 0\) olduğundan negatif olmama koşulu sağlanmaz. Olasılık vektörü değildir.
ii) Bütün elemanlar negatif değildir, ancak toplam
\[0 + \tfrac12 + \tfrac32 + \tfrac12 = \tfrac52 \neq 1\]
olduğundan olasılık vektörü değildir.
iii) Bütün elemanlar negatif değil ve toplamları \(0 + \tfrac12 + \tfrac12 = 1\)’dir. Olasılık vektörüdür.
\(\blacksquare\)
Örnek 4.2 (Hangileri SSM’dir?) Verilen matrislerden hangileri stokastik süreç matrisidir?
\[A = \begin{pmatrix} \tfrac13 & \tfrac13 & \tfrac13 \\[2pt] \tfrac12 & 0 & \tfrac12 \end{pmatrix} \qquad B = \begin{pmatrix} \tfrac{15}{16} & \tfrac{1}{16} \\[2pt] \tfrac23 & \tfrac23 \end{pmatrix} \qquad C = \begin{pmatrix} 1 & 0 \\[2pt] \tfrac12 & \tfrac12 \end{pmatrix} \qquad D = \begin{pmatrix} \tfrac32 & -\tfrac12 \\[2pt] \tfrac14 & \tfrac34 \end{pmatrix}\]
Çözüm
\(A\): Her satırın toplamı \(1\)’dir, elemanlar negatif değildir; ancak matris kare değildir (\(2 \times 3\)). SSM değildir.
\(B\): İlk satır \(\tfrac{15}{16} + \tfrac{1}{16} = 1\) ✓; fakat ikinci satır \(\tfrac23 + \tfrac23 = \tfrac43 \neq 1\)’dir. SSM değildir.
\(C\): Kare matristir, elemanlar negatif değildir, satır toplamları \(1 + 0 = 1\) ve \(\tfrac12 + \tfrac12 = 1\)’dir. SSM’dir.
\(D\): Satır toplamları \(1\)’dir, ancak \(-\tfrac12 < 0\) olduğundan negatif olmama koşulu sağlanmaz. SSM değildir.
\(\blacksquare\)
4.4 Olasılık Vektörünün Korunması
Bir Markov zincirinde durum dağılımı, olasılık vektörünün geçiş matrisiyle çarpılmasıyla ilerletilir. Bu işlemin bizi olasılık vektörleri dünyasının dışına çıkarmadığını göstermemiz gerekir.
Teorem 4.1 (Olasılık Vektörü Korunur) \(A\) bir SSM ve \(u\) herhangi bir olasılık vektörü olsun. Bu durumda \(uA\) çarpımı da bir olasılık vektörüdür.
İspat
Gösterimi somutlaştırmak için \(3 \times 3\) hâlini yazalım; genel durum aynı biçimde yürür. \(u = (u_1, u_2, u_3)\) ve
\[A = \begin{pmatrix} a_1 & b_1 & c_1 \\ a_2 & b_2 & c_2 \\ a_3 & b_3 & c_3 \end{pmatrix}\]
olsun. Çarpım
\[uA = \big(u_1 a_1 + u_2 a_2 + u_3 a_3,\;\; u_1 b_1 + u_2 b_2 + u_3 b_3,\;\; u_1 c_1 + u_2 c_2 + u_3 c_3\big)\]
biçimindedir.
Negatif olmama. \(u\) bir olasılık vektörü olduğundan \(u_1, u_2, u_3 \geq 0\); \(A\) bir SSM olduğundan bütün \(a_i, b_i, c_i \geq 0\)’dır. Negatif olmayan sayıların çarpımları ve toplamları da negatif olmadığından \(uA\)’nın bütün bileşenleri negatif değildir.
Toplamın \(1\) olması. \(uA\)’nın bileşenlerini toplayıp \(u_i\)’lere göre gruplayalım:
\[ \begin{aligned} \sum (uA)_j &= u_1(a_1 + b_1 + c_1) + u_2(a_2 + b_2 + c_2) + u_3(a_3 + b_3 + c_3) \end{aligned} \]
Parantez içindeki her ifade \(A\)’nın bir satır toplamıdır ve \(A\) bir SSM olduğundan hepsi \(1\)’e eşittir:
\[\sum (uA)_j = u_1 + u_2 + u_3 = 1\]
Son eşitlik \(u\)’nun olasılık vektörü olmasından gelir. Dolayısıyla \(uA\) bir olasılık vektörüdür.
\(\blacksquare\)
Teorem 4.2 (Markov Matrisinin Kuvvetleri) \(P\) bir Markov matrisi ise, her pozitif \(n\) tam sayısı için \(P^n\) de bir Markov matrisidir.
İspat
\(P\), \(m \times m\) boyutlu bir Markov matrisi olsun. Bütün bileşenleri \(1\) olan
\[v = \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix}_{m \times 1}\]
sütun vektörünü alalım. \(Pv\) çarpımının \(i\). bileşeni, \(P\)’nin \(i\). satırının toplamıdır; \(P\) bir Markov matrisi olduğundan bu toplam \(1\)’dir. O hâlde
\[Pv = v\]
olur. Şimdi her iki tarafı soldan \(P\) ile çarpalım:
\[P(Pv) = Pv \implies P^2 v = v\]
Aynı işlem tekrarlanırsa
\[P^3 v = v, \quad P^4 v = v, \quad \dots, \quad P^n v = v\]
elde edilir. \(P^n v = v\) eşitliği, \(P^n\)’in satır toplamlarının \(1\) olduğunu söyler. Ayrıca negatif olmayan sayıların çarpımı ve toplamı negatif olmadığından \(P^n\)’in bütün elemanları da negatif değildir.
O hâlde \(P^n\) de bir Markov matrisidir.
\(\blacksquare\)
4.5 Regüler Matrisler
Tanım 4.6 (Regüler Matris) Bir SSM’nin bir \(n\) kuvveti alındığında bütün sıfır bileşenlerinden kurtuluyorsa, yani öyle bir \(n\) pozitif tam sayısı için \(P^n\)’in bütün elemanları pozitif oluyorsa, \(P\) matrisine regüler denir.
Bir SSM’nin esas köşegeninde \(1\) varsa, o satırın diğer bütün elemanları sıfır olmak zorundadır (satır toplamı \(1\)’dir). Bu durumda o durumdan hiç çıkılamaz; \(P^n\)’in aynı satırı her \(n\) için değişmez ve içinde sıfırlar kalır. Dolayısıyla matris hiçbir zaman regüler olamaz.
Dikkat: bu kontrol yalnızca soruda verilen \(P\) matrisi için yapılır. \(P^2\), \(P^3\) gibi kuvvetlerin esas köşegeninde \(1\) çıkması bir engel değildir.
Örnek 4.3 (Regülerlik İncelemesi) Aşağıdaki matrislerin regüler olup olmadığını inceleyiniz.
\[A = \begin{pmatrix} \tfrac12 & \tfrac12 \\[2pt] 0 & 1 \end{pmatrix} \qquad B = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \qquad C = \begin{pmatrix} \tfrac12 & \tfrac12 \\[2pt] \tfrac12 & \tfrac12 \end{pmatrix} \qquad D = \begin{pmatrix} 0 & 0 & 1 \\[2pt] \tfrac12 & \tfrac14 & \tfrac14 \\[2pt] 0 & 1 & 0 \end{pmatrix}\]
Çözüm
\(A\): Esas köşegende \(1\) vardır (ikinci satır \((0,\,1)\)). O hâlde \(A\) regüler değildir.
\(B\): Kuvvetlerini alalım:
\[B^2 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \qquad B^3 = B^2 B = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = B\]
Buradan \(B^4 = B^2\), \(B^5 = B\), … olur; kaç kere çarparsak çarpalım içindeki sıfırlardan kurtulamayız. \(B\) regüler değildir.
\(C\): Hiç sıfır elemanı yoktur; \(n = 1\) ile koşul zaten sağlanır. \(C\) regülerdir.
\(D\): Esas köşegende \(1\) yoktur (matriste \(1\) vardır ama köşegen üzerinde değil), o hâlde sıfırlardan kurtulmayı deneyelim:
\[D^2 = \begin{pmatrix} 0 & 1 & 0 \\[2pt] \tfrac18 & \tfrac{5}{16} & \tfrac{9}{16} \\[2pt] \tfrac12 & \tfrac14 & \tfrac14 \end{pmatrix}, \qquad D^3 = \begin{pmatrix} \tfrac12 & \tfrac14 & \tfrac14 \\[2pt] \tfrac{5}{32} & \tfrac{41}{64} & \tfrac{13}{64} \\[2pt] \tfrac18 & \tfrac{5}{16} & \tfrac{9}{16} \end{pmatrix}\]
\(D^3\)’ün bütün elemanları \(0\)’dan büyük olduğundan \(D\) regülerdir.
\(\blacksquare\)
Bir Markov matrisinin her kuvveti yine Markov olduğundan (Teorem 4.2), hesapladığınız her satırın toplamı \(1\) çıkmalıdır. Örneğin \(D^2\)’nin ikinci satırı:
\[\tfrac18 + \tfrac{5}{16} + \tfrac{9}{16} = \tfrac{2}{16} + \tfrac{5}{16} + \tfrac{9}{16} = 1 \;\checkmark\]
Bu, elle matris çarpımı yaparken hata yakalamanın en hızlı yoludur.