stationary distribution

Stationary distribution of a random walk.

For long random walks on a markov chain, the probability of ending at a particular node is the same, regardless of wher you started.
This theorem is true for markov chains with strongly connected graphs.

Transition probability matrix $A$ (here transpose of weighted adjacency matrix)

$$\begin{array}{r}\{\begin{array}{ll}{a}_{j,i}=p_{i,j}& \text{if }(i,j)\in E\\ a_{j,i}=0& \text{otherwise}\end{array}\end{array}$$

Each column forms the probability of transitioning from state $i$ to some other state in one step of the random walk.
Let $e_i$ be a basis vector “the random walk at vertex $i$” → $A{e}_i$ gives the a vector whose $j^{\text{th}}$ coordinate is the probability that the random walk would be at vertex $j$ after one more step in the random walk.
→ If a random walk is in state $i$ with probability $q_i$, then the $j^{\text{th}}$ entry of $Aq$ is the probability that after one more step in the random walk you get to vertex $j$.
→ The stationary distribution is a probability distribution $\pi$ such that $A\pi =\pi$, in other words, $\pi$ is an eigenvector of $A$ with eigenvalue $1$.

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.