# Łańcuchy Markowa
$\newcommand{\P}{\mathbb{P}}$
$\newcommand{\E}{\mathbb{E}}$
[TOC]

Zajmujemy się skończoną przestrzenią.
## Oznaczenia
- $E = \{e_1, e_2,\ldots, e_n\}$ - zbiór wartości procesu
- $P(e_i, e_j) = P(i,j)$ (skrót)
- $P$ - macierz przejścia
- $X \sim (\mu, P)$, to łańcuch Markowa z macierzą przejść P, rozkładem początkowym $\mu$.
- $T_{ij} = \min\{n: X_n = e_j, X_0 = e_i\}$

## Definicje
$(X_0, X_1, \ldots)$ - proces losowy o wartościach w $E$ jest łańcuchem Markowa jeśli
$$
\forall n\forall e_i,e_j\in E~\forall i_0,i_1,\ldots,i_{n-1}
$$
$$
\P(X_{n+1}=e_j |
X_0 = e_{i_0}, \ldots, X_{n-1}=e_{i_{n-1}}, X_n = e_i) = P(X_{n+1}=e_j | X_n = e_i)
$$

Proces taki nazywamy jednorodnym, gdy
$$
P(X_{n+1}=e_j | X_n = e_i) = P(X_1 = e_j | X_0 = e_i)
$$

$P$ jest macierzą przejścia łańcucha Markowa, jeśli

$$
\forall i,j P(i,j) \ge 0 \land \forall i \Sigma_j P(i,j) = 1
$$

By w pełni opisać łańcuch Markowa trzeba podać dwie rzeczy
- macierz przejść
- rozkład $X_0$

Rozkład początkowy:
$\mu = \mu^{(0)} = (\mu(e_1), \ldots, \mu(e_m)) = (\P(X_0 = e_1), \ldots, P(X_0=e_m))$
$\mu^{(k)} = (\P(X_k=e_1),\ldots, \P(X_k=e_m)))$
$\mu^{(k)} = \mu P^k$
## Przykłady modeli
#### Model pogody LA

$$
P = \begin{pmatrix}1/2&1/2 \\ 1/10 & 9/10 \end{pmatrix}
$$
$e_1$ - deszcz
$e_2$ - słońce
:::info
Macierz stochastyczna ma zawsze wartość własną 1. :exploding_head:
:::
$\lim_k \mu^k$ = (1/6, 5/6)
#### Model Ehrenfestów
N kulek w pudełku A lub B
Stan to liczba kulek w pudełku A
Losujemy jedną kulkę z rozkładem jednostajnym i przekładamy ją do drugiego pudełka.
#### top-2-random
Tasowanie kart, bierzemy kartę z samej góry i wkładamy w losowe miejse w talii.
:::info
Macierz $P$ można opisać lokalnie.
:::
## Symulacja łańcuchów Markowa
$X \sim (\mu,P)$
### Jak symulować mi?
Klasycznie podzielić odcinek długości 1, na pewne części, aby pstwo wyglądało dobrze.

Funkcja inicjalizująca $\psi: [0,1]\to E$
- kawałkami stała
- $\forall e \int_0^1 1_{\psi(x)=e} dx = \mu(e)$

### Symulowanie procesu Markowa
Funkcja aktuzalizująca: $\varphi: E \times [0,1]\to E$
- Dla ustalonego $e_i$ funkcja $\phi(e_i,\cdot)$ kawałkami stała
- $\forall e_i,e_j \int_0^1 1_{\phi(e_i,x)=e_j}dx = P(e_i,e_j)$

## Rozkład stacjonarny
### Nieredukowalny
Łańcuch Markowa z macierzą przejść $P$ jest nieredukowalny jeśli
$$
\forall e_i, e_j \exists N_{ij}~\P(X_{N_{ij}}=e_j | X_0 = e_i) > 0
$$
### Okres stanu
$d(e_i) = \operatorname{gcd}\{n \ge 1: \P^n(e_i, e_i) > 0\}$

Łańcuch Markowa $X\sim P$ jest nieokresowy jeśli $\forall e_i~d(e_i) = 1$

#### Twierdzenie
$X\sim (\mu,P)$ jest nieokresowy, to $\exists N < \infty$, takie że
$$
\forall e_i \forall_{n\ge N} P^n(e_i, e_i) > 0
$$
##### Lemat (Bremaud)
Jeśli $A = \{a_1, a_2, \ldots\}$
- niekratowy, czyli $\operatorname{gcd}(a_1,\ldots)=1$
- $a, a' \in A \Rightarrow a+a' \in A$
to $\exists N$, takie że $\forall_{n\ge N}~n \in A$

#### Twierdzenie
$X \sim (\mu, P)$ jest nieredukowalny i nieokresowy, to $\exists N_0$, takie że
$$
\forall e_i, e_j P^{N_0}(e_i, e_j) > 0
$$

### Definicja
$X\sim(\mu, P)$ wektor (rozkład) $\pi= (\pi(e_1),\ldots,\pi(e_m))$, taki że
$$
\pi P = \pi
$$
nazywa się rozkładem **stacjonarnym**.

#### Lemat
$\{X_n\}$ - nieredukowalny i nieokresowy, to
$$
\forall i,j~P(T_{ij} < \infty) = 1 \text{ oraz } \E T_{ij} < \infty
$$

#### Twierdzenie
$\{X_n\}$ - nieredukowalny i nieokresowy łańcuch Markowa $\sim (\mu, P)$.
to istnieje przynajmniej jeden rozkład stacjonarny.

#### Twierdzenie
$$
\lim_n \mu^{(n)} = \pi
$$
### Norma całkowitego wahania
#### Definicja
$\mu, \nu$ - rozkłady prawdopodobieństwa na $\{e_1,\ldots,e_m\}$
$$
d_{TV} (\mu, \nu) = \frac 12 \sum_e |\mu(e) - \nu(e)|
$$

#### Definicja
Mówimy, że ciąg miar $\nu^{(k)}$ zbiega do $v$ w TV, jeśli
$$
\lim_{k\to\infty} d_{TV}(\nu^{(k)},v) = 0
$$

#### Twierdzenie
$\{X_n\} \sim (\mu,P)$ nieredukowalny i nieokresowy, to dla każdego rozkładu stacjonarnego
$$
\lim_{k\to\infty} d_{TV} (\mu^{(k)}, \pi) = 0
$$
:::success
Z tego twierdzenia wynika, że istnieje jeden rozkład stacjonarny (granica jest tylko jedna).
:::

## Coupling
### Definicja
Niech $X\sim\mu,~Y\sim\nu$.
Coupling zmiennych losowych $X$ i $Y$ (lub miar $\mu,\nu$) to jest zmienna
losowa $(X', Y')$, taka że $X'\sim \mu,~Y'\sim\nu$.
Inaczej $w: E \times E \to [0,1]$
- $w$ rozkład na $E \times E$
- $\forall e~\sum_{e'} w(e,e') = \mu(e)$
- $\forall e~\sum_{e'} w(e',e) = \nu(e)$

#### Coupling Markowski
$$
\forall e,e',e''~\P(X_{k+1} = e' | X_k = e, Y_k = e'') = P(e,e')\\
\P(Y_{k+1} = e' | Y_k = e, X_k = e'') = P(e,e')
$$

#### Coupling NieMarkowski
$X_k$ może zależeć od $Y_m$ dla $m > k$.

### Twierdzenia
#### Twierdzenie
Dane $X,Y (\mu,\nu)$
- dla każdego couplingu $w$ miar $\mu,\nu$
$$
d_{TV}(\mu,\nu) \le P(X\neq Y)
$$
- istnieje coupling, taki że
$$
d_{TV}(\mu,\nu) = P(X\neq Y)
$$
#### Lemat
Istnieje coupling $(X_k, Y_k),~(X_0\sim \mu, Y_0\sim \pi)$, taki że
$$
d_{TV}(\mu P^k, \pi) = P(T > k)
$$
#### Twierdzenie
$d_{TV}(\mu P^k, \pi)$ jest nierosnącą funkcją od $k$.
:::success
Dzięki temu twierdzeniu takie coś ma sens
$$
\tau^{TV}_{mix}(\varepsilon) = \min\{k: d(\mu P^k, \pi) \le \varepsilon) \}
$$
:::
#### Nierówność couplingowa
$$
d_{TV}(\mu P^k, \pi) \le P(T > k)
$$
#### lemat
Definicja:
$$
\overline d(k) = \max_{e',e''} d_{TV}(P^k(e',\cdot), P^k(e'', \cdot)) = \max_{e',e''} d_{TV}(\delta_{e'}P^k, \delta_{e''}P^k)\\
d(\mu P^k, \pi) \le \overline d(k)
$$

#### Twierdzenie (Griffeath)
Dla każdych $\mu, \nu$ i macierzy przejść $P$, istnieje coupling $(X_k,
Y_k),~X_k\sim P,~X_0\sim\mu,~Y_k\sim P,~Y_0\sim\nu~(X_k=Y_k \Rightarrow Y_{k+1} = X_{k+1})$, taki że
$$
d_{TV} (\mu P^k, \nu P^k) = P(T > k)
$$

## Łańcuchy odwracalne
$X_n$ jest ergodyczny (ERGOD) = nieokresowy + nieredukowalny

### Definicja
$X_n\sim(\mu,P)$ mówimy, że $\pi$ jest miarą odwracalną dla $X_k$ jeśli
$$
\forall e,e'\quad \pi(e) P(e,e') = \pi(e')P(e',e)
$$

#### Lemat
$\pi$-odwracalna $\Rightarrow$ $\pi$ - rozkład stacjonarny

### Definicja
$P$ - regularna = $\exists k\forall e_i,e_j P^k(e_i,e_j)>0$, czyli ergodyczna $\Rightarrow$ regularna.

#### Twierdzenie (Perrona – Frobeniusa)
$P$-macierz regularna, $m \times m$, to
- $|\lambda_1| > |\lambda_i|,~i=2,...,m$
- $|\lambda_1| \in \mathbb{R}$
gdzie $\lambda_i$ to $i$-ta wartość własna.
:::info
$P$ macierz Ł.M $\to~\lambda_1=1$
:::

#### Twierdzenie
$P$ - macierz, $X$ - ergodyczny Ł.M. $\exists \alpha >0$, taka że
$$
|P^k(e_i,e_j)-\pi(e_j)|\le \alpha |\lambda_2|^k
$$

#### Lemat
$X$- Ł.M odwracalny, to
$$
d_{TV}(\delta_eP^k,\pi)\le \frac{1}{2\sqrt{\pi(e)}} |\lambda_2|^k
$$

### Stała Cheegera
#### Definicja
Ł.M $X\sim P$ odwracalny, rozkład stacjonarny $\pi$
$$
\gamma_c = \min_{A\subseteq E, \pi(A) \le \frac{1}{2}} \frac{\sum_{e_i\in A}\sum_{e_j\in A^c}\pi(e_i)P(e_i,e_j)}{\pi(A)}
$$

#### Twierdzenie
$$
1-2\gamma_c \le |\lambda_2| \le 1 - \frac{1}{2}\gamma_c^2
$$

### Stała Poincarego
$$
\Lambda(e_i,e_j) = \pi(e_i)P(e_i,e_j) = \Lambda(e_j, e_i)
$$
GRAF $V = E = \{e_1,\ldots,e_n\},~K = \{\{e_i,e_j\}: \Lambda(e_i,e_j) >0\}$
$\Gamma(e_i,e_j)$ - jednoznacznie ustalona ścieżka z $e_i$ do $e_j$.
$|\Gamma(e_i,e_j)|$ - $\Sigma_{\hat e \in \Gamma(e_i,e_j)} 1$

#### Definicje
$$
\gamma_p = \max_{\hat e}\left\{\frac{1}{\Gamma(\hat e)}\sum_{(e_i,e_j): \hat e\in\Gamma(e_i,e_j)} |\Gamma(e_i,e_j)|\pi(e_i)\pi(e_j)\right\}
$$

#### Twierdzenie
$$
|\lambda_2| \le 1 - \frac{1}{\gamma_p}
$$

## Monte Carlo Markov Chains
Idea: dane $\pi$, chcemy skostruować łańcuch Markowa, tak aby $\pi$ było rozkładem stacjonarnym.
### Algorytm Metropolis
1. symetryczny łańcuch Markowa $Q(e_i,e_j) = Q(e_j, e_i)$
2. Zał, że $Y_n = e$
3. Wylosuj $e'$ zgodnie z $Q(e,e'),~\alpha=\min(1,\frac{\pi(e')}{\pi(e)})$
4. $U\sim U(0,1)$
5. Jeśli $U\le \alpha\Rightarrow Y_{n+1}=e'$, inaczej $Y_{n+1}=e$

#### Lemat
Algorytm metropolis, to łańcuch Markowa o rozkładzie stacjonarnym $\pi$.