mathematics//probability//stochastic process//Markov chain
A Markov chain is a stochastic process over a discrete set of states in which the probability of the next state depends only on the current one, and it is used to model a machine moving between healthy, degraded and failed, the availability that follows, a walk over a graph, the samplers of MCMC and the environments of reinforcement learning. A machine that degrades with probability 2 % a day, fails from degraded with 10 % and is repaired with 50 % is fully described by those numbers. The random state \(S_k\) is one object; its distribution \(\ca{p_k}\), with \(\ca{p_{k,i}}=\Pr(S_k=i)\), is another. One machine occupies one state; the vector is our uncertainty about it, or the proportions of a fleet. The distribution in green, the transition matrix in blue.
A Markov chain is a stochastic process over a discrete set of states in which the probability of the next state depends only on the current one, and it is used to model a machine moving between healthy, degraded and failed, the availability that follows, a walk over a graph, the samplers of MCMC and the environments of reinforcement learning. A machine that degrades with probability 2 % a day, fails from degraded with 10 % and is repaired with 50 % is fully described by those numbers. The random state SkS_kSk is one object; its distribution pk\ca{p_k}pk, with pk,i=Pr(Sk=i)\ca{p_{k,i}}=\Pr(S_k=i)pk,i=Pr(Sk=i), is another. One machine occupies one state; the vector is our uncertainty about it, or the proportions of a fleet. The distribution in green, the transition matrix in blue.
All these notes share one convention for the transition matrix:
Pij=Pr(Sk+1=j∣Sk=i),Pij≥0,∑jPij=1.\cb{P_{ij}}=\Pr(S_{k+1}=j\mid S_k=i),\qquad \cb{P_{ij}}\ge0,\qquad\sum_j\cb{P_{ij}}=1.Pij=Pr(Sk+1=j∣Sk=i),Pij≥0,j∑Pij=1.
P\cb{P}P is row-stochastic, and with distributions written as columns pk+1=PTpk\ca{p_{k+1}}=\cb{P}^{\mathsf T}\ca{p_k}pk+1=PTpk, so pk=(PT)kp0\ca{p_k}=(\cb{P}^{\mathsf T})^k \ca{p_0}pk=(PT)kp0. With row distributions one writes pk+1T=pkTP\ca{p_{k+1}}^{\mathsf T}=\ca{p_k}^{\mathsf T}\cb{P}pk+1T=pkTP; either is valid, and mixing P=D−1W\cb{P}=D^{-1}WP=D−1W with pk+1=Ppk\ca{p_{k+1}}=\cb{P}\ca{p_k}pk+1=Ppk for a column is not.
A two-state example can be checked by hand. With P\cb{P}P rows (0.9, 0.1)(0.9,,0.1)(0.9,0.1) and (0.2, 0.8)(0.2,,0.8)(0.2,0.8) and the chain started in state 1, after one step p1=(0.9,0.1)T\ca{p_1}=(0.9,0.1)^{\mathsf T}p1=(0.9,0.1)T, after two p2=(0.83,0.17)T\ca{p_2}=(0.83,0.17)^{\mathsf T}p2=(0.83,0.17)T. (Pk)ij(\cb{P}^k)_{ij}(Pk)ij is the probability of ending in jjj after kkk steps from iii, summed over every allowed intermediate walk (adjacency and degree). NNN objects following these probabilities have expected counts that obey the same linear evolution, while the observed counts fluctuate.
stationary π(0.67, 0.33) chainTwo states Starting in state 1, the distribution evolves by p(k+1) = Pᵀ p(k): p0 = (1.00, 0.00); p1 = (0.90, 0.10); p2 = (0.83, 0.17); p3 = (0.78, 0.22); p4 = (0.75, 0.25). A population of tokens hopping by the same probabilities fluctuates around these numbers.
Press Step a few times and watch the green bars settle on π while the copper count of sixty real tokens keeps wobbling around them.
Memorylessness is a modelling choice. If the future depends on the past (a machine's age, the time since its last service), the state is enlarged until it includes it, the Markov property of a sufficient state. A Markov decision process is a chain whose matrix the decision maker chooses at each step; fixing the policy removes the choice and leaves a Markov chain, which is how a maintenance policy is evaluated.
A weighted graph defines a random walk on a graph: P=D−1W\cb{P}=D^{-1}WP=D−1W picks neighbours in proportion to their weights, and the walker lingers in densely connected regions and rarely crosses bottlenecks, the observation behind spectral clustering. Px\cb{P}xPx averages a function on nodes, which is consensus, while PTp\cb{P}^{\mathsf T}\ca{p}PTp transports a distribution; the two are dual and not interchangeable (normalized Laplacian). When rows and columns both sum to one (a doubly stochastic matrix, such as I−εLI-\varepsilon LI−εL with ε≤1/dmax\varepsilon\le1/d_{\max}ε≤1/dmax) the uniform distribution is stationary, and consensus is a chain that mixes to the average.
In continuous time a row generator QQQ, with non-negative off-diagonal entries and zero row sums, drives p˙=QTp\dot{\ca{p}}=Q^{\mathsf T}\ca{p}p˙=QTp, for example Q=ν(P−I)Q=\nu(\cb{P}-I)Q=ν(P−I) with a rate ν>0\nu>0ν>0 (discretization). The long run belongs to the stationary distribution; convention and theory follow Levin and Peres, Markov Chains and Mixing Times, chapter 1.