Two families with an explicit stationary law
Section of Classes, recurrence, and reversibility, part of Stochastic processes
Two families with an explicit stationary law
| Type | Section |
| Taught in | Classes, recurrence, and reversibility |
| Part | Stochastic processes |
On an undirected graph, the simple random walk steps from i to a uniformly chosen neighbour, so p_{ij}=1/\deg(i) when \{i,j\} is an edge. The weights \pi_i=\deg(i)/(2|E|) satisfy detailed balance: on every edge,
\pi_i p_{ij}=\frac{\deg(i)}{2|E|}\cdot\frac{1}{\deg(i)}=\frac{1}{2|E|}=\pi_j p_{ji}.
Long-run occupancy follows degree. It is uniform only when the graph is regular.
On a nearest-neighbour birth–death chain, let p_i be the probability of a step from i to i+1 and q_i the probability of a step from i to i-1. Local balance \pi_i p_i=\pi_{i+1} q_{i+1} iterates to
\pi_n=\pi_0\prod_{k=0}^{n-1}\frac{p_k}{q_{k+1}},
provided the positive weights have a finite sum, so that they can be normalised to a probability. A formal solution whose total mass is infinite is not a stationary probability distribution. The reflected walk on Markov chains is this product: \pi_j=(p/q)^j\pi_0, normalisable precisely when p<q.
Used in
See also
Recurrence and period · Finite irreducible chains · Detailed balance · Communicating classes · Return and period · Global balance and detailed balance · When a stationary law fails to be unique · Period and time averages