Markov chain

Rozkład stacjonarny

Rozkład stacjonarny $\pi$ (czyli rozkład prawdopodobieństwa nad stanami łańcucha) dla łańcucha Markova z macierzą przejścia $P$ to taki rozkład, że $\pi =\pi P$Uwaga: istnieją łańcuchy Markova z nieskończenie wieloma rozkładami stacjonarnymi lub bez żadnego rozkładu stacjonarnego.

Zbieżność

Łańcuch Markova zbiega do rozkładu stacjonarnego wtedy i tylko wtedy gdy ${\lim }_{t\to \inf }{q}_t=\pi$ dla dowolnego $q_0$.

Uwaga: łańuch nie musi zbiegać do rozkładu stacjonarnego, nawet jeśli istnieje tylko jeden jaki rozkład stacjonarny.

Ergodyczność

Łańcuch Markova jest ergodyczny wtedy i tylko wtedy gdy prawdopodobieństwo przejścia z dowolnego stanu w dowolny inny w $t$ ruchach (dla dowolnego $t$) jest niezerowe.

Fundamentalne twierdzenie ergodycznych łańcuchów Markova

Ergodyczny łańcuch Markova ma unikalny rozkład stacjonarny oraz jest zbieżny do tego rozkładu.

Odwracalność (reversibility / detailed balance equation)

Łańcuch Markova jest odwracalny w odniesieniu do rozkładu $\pi$ wtedy i tylko wtedy gdy $\pi (x)p(x^{\prime }|x)=\pi (x^{\prime })p(x|x^{\prime })$ gdzie $p(x|x^{\prime })$ to prawdopodobieństwo osiągnięcia $x$ z $x^{\prime }$.

Twierdzenie

Jeśli skończony łańcuch Markova jest odwracalny w odniesieniu do rozkładu $\pi$, to $\pi$ jest rozkładem stacjonarnym.

Twierdzenie ergodyczne dla łańcuchów Markova

Jeśli mamy łańcuch Markova $(X_t{)}_{t\in \mathbb{N}}$ nad skończoną przestrzenią stanów $S$ i rozkładem stacjonarnym $\pi$ oraz mamy funkcję $f:S\to \mathbb{R}$, i jeśli $n\to \infty$ to $\frac{1}{n}{\sum }_{i=1}^{n}f(x_i)\to {\sum }_{x\in S}\pi (x)f(x)={\mathbb{E}}_{x\sim \pi }[f(x)]$ gdzie $x_i\sim X_i|x_{i-1}$. Analogiczne twierdzenie występuje dla rozkładów ciągłych.

O czym mówi ten zaskakujący wynik?

Gdybyśmy normalnie wzięli łańcuch Markova i zaczęli skakać po stanach to wydaje się, że poszczególne sample byłyby (poprzez konstrukcję łańcucha) zależne. My chcielibyśmy uzyskać sample niezależne (po to, żeby móc faktycznie samplować na potrzeby Variational Inference). No i ten wspaniały wynik mówi o tym, że samplując z pojedynczego łańcucha dostaniemy w granicy niezbiasowany estymator. Uwaga: to twierdzenie niestety nie mówi jak szybko dostaniemy taki estymator (jak szybko on zbiega) ani nie mówi o wariancji estymatora. W praktyce jest tak, że dla taiego łańcucha ustawia się tzw. “burn-in time”, czyli początkową ilość iteracji, w którym łańcuch nie zwraca dobrych estymacji.

Źródło: Probabilistic Artificial Intelligence