markov chain

Markov chain

Given a directed graph $G=(V,E),e=(u,v)\in E$, with weighted edges $p_{(u,v)}\in [0,1]$, where the sum of probabilities on outgoing edges for any node $x$ is ${\sum }_y{p}_{(x,y)}=1$.
We call the entire object a markov chain:

$$(V,E,\{p_e{\}}_{e\in E})$$

Convergence of the stationary distribution on a markov chain

Let $G$ be a strongly connected graph with associated edge probabilities $\{p_e{\}}_{e\in E}$ forming a Markov chain. For a probability vector $x_0$, define $x_{t+1}=A{x}_t$ for all $t\ge 1$, and let $v_t$ be the long-term average $v_t=\frac{1}{t}{\sum }_{s=1}^t{x}_s$. Then:
→ There is a unique probability vector $\pi$ with $A\pi =\pi$.
→ For all $x_0$, the limit ${\lim }_{t\to \infty }{v}_t=\pi$.

Proof: Since $v_t$ is a probability vector we just want to show that $|A{v}_t-v_t|\to 0$ as $t\to \infty$. Indeed, we can expand this quantity as

$$\begin{array}{rl}A{v}_t-v_t& =\frac{1}{t}(A{x}_0+A{x}_1+\cdots +A{x}_{t-1})-\frac{1}{t}(x_0+\cdots +x_{t-1})\\ & =\frac{1}{t}(x_t-x_0)\end{array}$$

But $x_t,x_0$ are unit vectors (length 1), so their difference is at most 2, meaning $|A{v}_t-v_t|\le \frac{2}{t}\to 0$. Now it’s clear that this does not depend on $v_0$. For uniqueness we will cop out and appeal to the Perron-Frobenius theorem that says any matrix of this form has a unique such (normalized) eigenvector.

Link to original

References

https://www.jeremykun.com/2015/04/06/markov-chain-monte-carlo-without-all-the-bullshit/