32 Markov Zincirleri

Markov özelliği, geçiş matrisi, durağan dağılım

Bölüm bilgisi

Blitzstein’in videosu: YouTube — Lecture 31 (≈47 dk)
Okuma süresi: ≈22 dk

32.1 Bu Derste Ne Var?

Markov özelliği: geçmiş ⊥ gelecek | şimdi.
Geçiş matrisi $Q$: $q_{ij} = P(i \to j)$, satır toplamı 1.
$n$-adım: $X_n \sim s$ → $X_{n+m} \sim sQ^m$.
Durağan dağılım: $sQ = s$.

Builder Notu — ML Köprüleri

MCMC (Markov Chain Monte Carlo) — Bayesçi çıkarımın motoru, Metropolis-Hastings, Gibbs, HMC.
Diffusion modelleri — ileri/geri Markov zinciri.
RL = MDP (Markov Decision Process) — Bellman’ın temeli.
PageRank — web grafının durağan dağılımı.
n-gram dil modelleri = $(n-1)$. dereceden Markov; Transformer Markov varsayımını kırar.
HMM forward = $sQ$ belief güncellemesi.

32.2 Markov Özelliği

\[ P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i) \]

Yalnız son durum önemli. Geçmiş ve gelecek şimdi verildiğinde koşullu bağımsız.

“Past and future are conditionally independent given the present.” — Blitzstein, 11:43

Homojen: $q_{ij} = P(X_{n+1} = j \mid X_n = i)$, $n$’den bağımsız.

32.3 Geçiş Matrisi $Q$

Örnek (4 durum):

\[ Q = \begin{pmatrix} 1/3 & 2/3 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 1 \\ 1/2 & 0 & 1/4 & 1/4 \end{pmatrix} \]

Her satır 1’e toplanır (stokastik matris).

32.4 $n$-Adım Geçişler

$X_n$ dağılımı satır vektörü $s$. LOTP:

\[ P(X_{n+1} = j) = \sum_i s_i q_{ij} = (sQ)_j \]

\[ X_n \sim s \;\Rightarrow\; X_{n+m} \sim sQ^m \]

\[ P(X_{n+m} = j \mid X_n = i) = (Q^m)_{ij} \]

32.5 Durağan Dağılım

\[ \boxed{sQ = s} \]

Bir kez girilince sonsuza dek $s$. $Q$’nun özdeğer-1 sol özvektörü.

Dört soru: Var mı? Tek mi? Yakınsar mı? Nasıl hesaplanır?

Hafif koşullarda → evet, evet, evet.

import numpy as np
import matplotlib.pyplot as plt

Q = np.array([
    [1/3, 2/3,   0,   0],
    [1/2,   0, 1/2,   0],
    [  0,   0,   0,   1],
    [1/2,   0, 1/4, 1/4],
])

# Durağan dağılım
vals, vecs = np.linalg.eig(Q.T)
i = np.argmin(np.abs(vals - 1))
pi = np.real(vecs[:, i]); pi /= pi.sum()

# Yakınsama
fig, ax = plt.subplots(figsize=(11, 5))
renkler = ['#A51C30', '#DD6B20', '#2C5282', '#6B46C1']
labels = ['Durum 1', 'Durum 2', 'Durum 3', 'Durum 4']

for s0, ls in [(np.array([1.,0,0,0]), '-'), (np.array([0,0,0,1.]), '--')]:
    s = s0.copy()
    history = [s.copy()]
    for _ in range(40):
        s = s @ Q
        history.append(s.copy())
    history = np.array(history)
    for k, c in enumerate(renkler):
        ax.plot(history[:, k], color=c, linewidth=2, linestyle=ls, alpha=0.85,
                label=f'{labels[k]} (init {s0})' if ls == '-' else None)

for k, c in enumerate(renkler):
    ax.axhline(pi[k], color=c, linestyle=':', linewidth=1.5, alpha=0.6)

ax.set_xlabel('adım n', fontsize=12)
ax.set_ylabel('P(durum)', fontsize=12)
ax.set_title(f'Markov zinciri: farklı başlangıçlar → aynı durağan dağılım π ≈ {np.round(pi, 3)}',
             fontsize=11)
ax.legend(loc='upper right', fontsize=10, ncol=2)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

Şekil 32.1

Builder Notu — MCMC ve Diffusion

MCMC: durağan dağılımı hedef posterior olan zincir kur (Metropolis-Hastings, Gibbs, HMC), çalıştır, örnekle. Bayesçi ML’in motoru. Diffusion modelleri: ileri süreç gürültü ekleyen zincir, geri süreç onu çözen — üretim = zinciri tersine çalıştırma.

32.6 Tarihsel İki Kullanım

Modelleme: gerçek sistem (Pushkin’in sesli/sessiz harfleri, hava durumu).
MCMC: kendi zincirini kur, durağan dağılımı hedeflediğin dağılım.

“You can construct your own Markov chain that will converge to a distribution you’re interested in.” — Blitzstein, 23:19

32.7 Bu Dersin Özeti

Markov özelliği: koşullu bağımsızlık.
$Q$: stokastik, satır toplamı 1.
$sQ^m$: $m$ adım sonra.
$sQ = s$: durağan.

Tek bir cümle

Markov zinciri: gelecek geçmişe yalnız şimdi üzerinden bağlı. Tüm davranış $Q$’da; kuvvetleri zamanı sarar; durağan $sQ = s$ uzun-vade dengesi. MCMC, diffusion, RL (MDP), PageRank, n-gram, HMM — hepsi.

32.8 Kontrol Soruları

Soru 1: Markov özelliği = bağımsızlık mı?

Cevap: Koşullu bağımsızlık (şimdi verildiğinde). $X_n$ bilinmiyorsa $X_{n-1}$ hala bilgi taşır.

Soru 2: Q’nun yapısal özelliği?

Cevap: Her satır 1’e toplanır (negatif olmayan). Sütun toplamak zorunda değil.

Soru 3: X_n ~ s. 3 adım sonra?

Cevap: $sQ^3$ dağılım; $(Q^3)_{ij}$ nokta olasılığı.

Soru 4: sQ = s neden durağan?

Cevap: Bir adım sonra dağılım değişmez → sonsuza dek $s$. Özdeğer-1 sol özvektör.

32.9 Egzersizler

Egzersiz 1. Geçerli $Q$? (a) (.3,.7;.6,.4), (b) (.5,.5;.8,.3), (c) (1,0;.2,.8).

Egzersiz 2. $Q=$ (.9,.1;.5,.5). $(Q^2)_{11}$?

Egzersiz 3. $s = (1, 0)$. $sQ, sQ^2$ hangi yöne?

Egzersiz 4. Yukarıdaki Q için durağan dağılım çöz.

Egzersiz 5. (Python — Markov + durağan)

import numpy as np

Q = np.array([[1/3, 2/3, 0, 0], [1/2, 0, 1/2, 0], [0, 0, 0, 1], [1/2, 0, 1/4, 1/4]])
print("Satır toplamı:", Q.sum(axis=1))

# Yakınsama
for s0 in [np.array([1.,0,0,0]), np.array([0,0,0,1.])]:
    s = s0.copy()
    for _ in range(50):
        s = s @ Q
    print(f"  {s0} → {np.round(s, 4)}")

# Durağan
vals, vecs = np.linalg.eig(Q.T)
i = np.argmin(np.abs(vals - 1))
pi = np.real(vecs[:, i]); pi /= pi.sum()
print(f"Durağan (özvektör): {np.round(pi, 4)}")

32.10 Sonraki Ders İçin Hazırlık

Ders 32: Markov Sınıflandırma + Tersinirlik — irreducibility, periyot, detailed balance (MCMC’nin temeli).

Ders 32 öncesi yapılacak

Egzersizleri çöz.
Durağan denklemi içselleştir.

32.11 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Not
Markov özelliği	$P(X_{n+1}\\|X_n, \ldots) = P(X_{n+1}\\|X_n)$	Geçmiş ⊥ gelecek \| şimdi
$q_{ij}$	$P(X_{n+1}=j \mid X_n=i)$	Homojen
$Q$	$(q_{ij})$	Satır toplamı 1
Evrim	$sQ$	Satır vektörü
$m$-adım	$sQ^m$, $(Q^m)_{ij}$	Matris kuvveti
Durağan	$sQ = s$	Özdeğer-1 sol özvektör

32.12 ML Bağlantıları Özeti

6 köprü

MCMC → Metropolis-Hastings, Gibbs, HMC.
Diffusion → ileri/geri zincir.
RL (MDP) → Bellman, value iteration.
PageRank → durağan dağılım.
n-gram = $(n-1)$. Markov; Transformer kırar.
HMM forward = $sQ$.

Tek bir şey alıp gideceksen

Markov: gelecek yalnız şimdi üzerinden bağlı. $Q$ davranışı, $Q^n$ zaman, $sQ = s$ uzun-vade. MCMC + diffusion + RL + PageRank hepsi.

--- title: "Markov Zincirleri" subtitle: "Markov özelliği, geçiş matrisi, durağan dağılım" --- ::: {.callout-note title="Bölüm bilgisi"} - **Blitzstein'in videosu:** [YouTube — Lecture 31](https://www.youtube.com/watch?v=8AJPs3gvNlY) (≈47 dk) - **Okuma süresi:** ≈22 dk ::: ## Bu Derste Ne Var? {#sec-bu-derste} 1. **Markov özelliği:** geçmiş ⊥ gelecek | şimdi. 2. **Geçiş matrisi $Q$:** $q_{ij} = P(i \to j)$, satır toplamı 1. 3. **$n$-adım:** $X_n \sim s$ → $X_{n+m} \sim sQ^m$. 4. **Durağan dağılım:** $sQ = s$. ::: {.callout-tip title="Builder Notu — ML Köprüleri"} - **MCMC** (Markov Chain Monte Carlo) — Bayesçi çıkarımın motoru, **Metropolis-Hastings, Gibbs, HMC**. - **Diffusion modelleri** — ileri/geri Markov zinciri. - **RL = MDP** (Markov Decision Process) — Bellman'ın temeli. - **PageRank** — web grafının durağan dağılımı. - **n-gram dil modelleri** = $(n-1)$. dereceden Markov; **Transformer** Markov varsayımını kırar. - **HMM forward** = $sQ$ belief güncellemesi. ::: ## Markov Özelliği {#sec-markov-ozelligi} $$ P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i) $$ **Yalnız son durum önemli.** Geçmiş ve gelecek **şimdi verildiğinde koşullu bağımsız**. > *"Past and future are conditionally independent given the present."* — Blitzstein, 11:43 **Homojen:** $q_{ij} = P(X_{n+1} = j \mid X_n = i)$, $n$'den bağımsız. ## Geçiş Matrisi $Q$ {#sec-q} **Örnek (4 durum):** $$ Q = \begin{pmatrix} 1/3 & 2/3 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 1 \\ 1/2 & 0 & 1/4 & 1/4 \end{pmatrix} $$ **Her satır 1'e toplanır** (stokastik matris). ## $n$-Adım Geçişler {#sec-n-adim} $X_n$ dağılımı satır vektörü $s$. LOTP: $$ P(X_{n+1} = j) = \sum_i s_i q_{ij} = (sQ)_j $$ $$ X_n \sim s \;\Rightarrow\; X_{n+m} \sim sQ^m $$ $$ P(X_{n+m} = j \mid X_n = i) = (Q^m)_{ij} $$ ## Durağan Dağılım {#sec-duragan} $$ \boxed{sQ = s} $$ Bir kez girilince **sonsuza dek $s$**. $Q$'nun **özdeğer-1 sol özvektörü**. **Dört soru:** Var mı? Tek mi? Yakınsar mı? Nasıl hesaplanır? **Hafif koşullarda → evet, evet, evet.** ```{python} #| label: fig-markov-yakinsama #| fig-cap: "4-durumlu Markov zinciri farklı başlangıçlardan aynı durağan dağılıma yakınsar. PageRank, MCMC, diffusion'ın temel mekanizması: \"yeterince çalıştır, durağana git\"." #| fig-width: 11 #| fig-height: 5 import numpy as np import matplotlib.pyplot as plt Q = np.array([ [1/3, 2/3, 0, 0], [1/2, 0, 1/2, 0], [ 0, 0, 0, 1], [1/2, 0, 1/4, 1/4], ]) # Durağan dağılım vals, vecs = np.linalg.eig(Q.T) i = np.argmin(np.abs(vals - 1)) pi = np.real(vecs[:, i]); pi /= pi.sum() # Yakınsama fig, ax = plt.subplots(figsize=(11, 5)) renkler = ['#A51C30', '#DD6B20', '#2C5282', '#6B46C1'] labels = ['Durum 1', 'Durum 2', 'Durum 3', 'Durum 4'] for s0, ls in [(np.array([1.,0,0,0]), '-'), (np.array([0,0,0,1.]), '--')]: s = s0.copy() history = [s.copy()] for _ in range(40): s = s @ Q history.append(s.copy()) history = np.array(history) for k, c in enumerate(renkler): ax.plot(history[:, k], color=c, linewidth=2, linestyle=ls, alpha=0.85, label=f'{labels[k]} (init {s0})' if ls == '-' else None) for k, c in enumerate(renkler): ax.axhline(pi[k], color=c, linestyle=':', linewidth=1.5, alpha=0.6) ax.set_xlabel('adım n', fontsize=12) ax.set_ylabel('P(durum)', fontsize=12) ax.set_title(f'Markov zinciri: farklı başlangıçlar → aynı durağan dağılım π ≈ {np.round(pi, 3)}', fontsize=11) ax.legend(loc='upper right', fontsize=10, ncol=2) ax.grid(True, alpha=0.3) plt.tight_layout() plt.show() ``` ::: {.callout-important title="Builder Notu — MCMC ve Diffusion"} **MCMC:** durağan dağılımı hedef posterior olan zincir kur (**Metropolis-Hastings**, **Gibbs**, **HMC**), çalıştır, örnekle. Bayesçi ML'in motoru. **Diffusion modelleri:** ileri süreç gürültü ekleyen zincir, geri süreç onu çözen — üretim = zinciri tersine çalıştırma. ::: ## Tarihsel İki Kullanım {#sec-tarih} 1. **Modelleme:** gerçek sistem (Pushkin'in sesli/sessiz harfleri, hava durumu). 2. **MCMC:** kendi zincirini kur, durağan dağılımı hedeflediğin dağılım. > *"You can construct your own Markov chain that will converge to a distribution you're interested in."* — Blitzstein, 23:19 ## Bu Dersin Özeti {#sec-ozet} 1. **Markov özelliği:** koşullu bağımsızlık. 2. **$Q$:** stokastik, satır toplamı 1. 3. **$sQ^m$**: $m$ adım sonra. 4. **$sQ = s$:** durağan. ::: {.callout-important title="Tek bir cümle"} Markov zinciri: gelecek geçmişe **yalnız şimdi üzerinden** bağlı. Tüm davranış $Q$'da; kuvvetleri zamanı sarar; durağan $sQ = s$ uzun-vade dengesi. **MCMC, diffusion, RL (MDP), PageRank, n-gram, HMM** — hepsi. ::: ## Kontrol Soruları {#sec-sorular} ::: {.callout-note collapse="true" title="Soru 1: Markov özelliği = bağımsızlık mı?"} **Cevap:** **Koşullu bağımsızlık** (şimdi verildiğinde). $X_n$ bilinmiyorsa $X_{n-1}$ hala bilgi taşır. ::: ::: {.callout-note collapse="true" title="Soru 2: Q'nun yapısal özelliği?"} **Cevap:** Her **satır** 1'e toplanır (negatif olmayan). Sütun toplamak zorunda değil. ::: ::: {.callout-note collapse="true" title="Soru 3: X_n ~ s. 3 adım sonra?"} **Cevap:** $sQ^3$ dağılım; $(Q^3)_{ij}$ nokta olasılığı. ::: ::: {.callout-note collapse="true" title="Soru 4: sQ = s neden durağan?"} **Cevap:** Bir adım sonra dağılım değişmez → sonsuza dek $s$. Özdeğer-1 sol özvektör. ::: ## Egzersizler {#sec-egzersizler} **Egzersiz 1.** Geçerli $Q$? (a) (.3,.7;.6,.4), (b) (.5,.5;.8,.3), (c) (1,0;.2,.8). **Egzersiz 2.** $Q=$ (.9,.1;.5,.5). $(Q^2)_{11}$? **Egzersiz 3.** $s = (1, 0)$. $sQ, sQ^2$ hangi yöne? **Egzersiz 4.** Yukarıdaki Q için durağan dağılım çöz. **Egzersiz 5.** *(Python — Markov + durağan)* ```{python} #| label: ex-markov #| code-fold: false import numpy as np Q = np.array([[1/3, 2/3, 0, 0], [1/2, 0, 1/2, 0], [0, 0, 0, 1], [1/2, 0, 1/4, 1/4]]) print("Satır toplamı:", Q.sum(axis=1)) # Yakınsama for s0 in [np.array([1.,0,0,0]), np.array([0,0,0,1.])]: s = s0.copy() for _ in range(50): s = s @ Q print(f" {s0} → {np.round(s, 4)}") # Durağan vals, vecs = np.linalg.eig(Q.T) i = np.argmin(np.abs(vals - 1)) pi = np.real(vecs[:, i]); pi /= pi.sum() print(f"Durağan (özvektör): {np.round(pi, 4)}") ``` ## Sonraki Ders İçin Hazırlık {#sec-sonraki} **Ders 32: Markov Sınıflandırma + Tersinirlik** — irreducibility, periyot, **detailed balance** (MCMC'nin temeli). ::: {.callout-warning title="Ders 32 öncesi yapılacak"} - Egzersizleri çöz. - Durağan denklemi içselleştir. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet} | Kavram | Tanım | Not | |--------|-------|------| | **Markov özelliği** | $P(X_{n+1}\|X_n, \ldots) = P(X_{n+1}\|X_n)$ | Geçmiş ⊥ gelecek \| şimdi | | **$q_{ij}$** | $P(X_{n+1}=j \mid X_n=i)$ | Homojen | | **$Q$** | $(q_{ij})$ | Satır toplamı 1 | | **Evrim** | $sQ$ | Satır vektörü | | **$m$-adım** | $sQ^m$, $(Q^m)_{ij}$ | Matris kuvveti | | **Durağan** | $sQ = s$ | Özdeğer-1 sol özvektör | ## ML Bağlantıları Özeti {#sec-ml-baglantilar} ::: {.callout-tip title="6 köprü"} 1. **MCMC** → Metropolis-Hastings, Gibbs, HMC. 2. **Diffusion** → ileri/geri zincir. 3. **RL (MDP)** → Bellman, value iteration. 4. **PageRank** → durağan dağılım. 5. **n-gram** = $(n-1)$. Markov; Transformer kırar. 6. **HMM forward** = $sQ$. ::: ::: {.callout-important title="Tek bir şey alıp gideceksen"} Markov: **gelecek yalnız şimdi üzerinden** bağlı. $Q$ davranışı, $Q^n$ zaman, $sQ = s$ uzun-vade. **MCMC + diffusion + RL + PageRank** hepsi. :::

32 Markov Zincirleri

32.1 Bu Derste Ne Var?

32.2 Markov Özelliği

32.3 Geçiş Matrisi \(Q\)

32.4 \(n\)-Adım Geçişler

32.5 Durağan Dağılım

32.6 Tarihsel İki Kullanım

32.7 Bu Dersin Özeti

32.8 Kontrol Soruları

32.9 Egzersizler

32.10 Sonraki Ders İçin Hazırlık

32.11 Anahtar Kavramlar (Cheat Sheet)

32.12 ML Bağlantıları Özeti