mathematics//probability//Markov chain

How a distribution over states evolves when the transition probabilities are known. A **finite Markov chain** describes a random state \(S_k\) that belongs to a list of possibilities. Its distribution \(p_k\) is a different object: \(p_{k,i}=\Pr(S_k=i)\). One individual system occupies one state; the vector represents our uncertainty or the proportions of a population.

How a distribution over states evolves when the transition probabilities are known. A finite Markov chain describes a random state SkS_kSk​ that belongs to a list of possibilities. Its distribution pkp_kpk​ is a different object: pk,i=Pr⁡(Sk=i)p_{k,i}=\Pr(S_k=i)pk,i​=Pr(Sk​=i). One individual system occupies one state; the vector represents our uncertainty or the proportions of a population.

One convention for all these notes. Define

Pij=Pr⁡(Sk+1=j∣Sk=i),Pij≥0,∑jPij=1.P_{ij}=\Pr(S_{k+1}=j\mid S_k=i),\qquad P_{ij}\ge0,\qquad\sum_jP_{ij}=1.Pij​=Pr(Sk+1​=j∣Sk​=i),Pij​≥0,j∑​Pij​=1.

PPP is row-stochastic. Since distributions are written as columns,

pk+1=PTpk,pk=(PT)kp0.p_{k+1}=P^{\mathsf T}p_k,\qquad p_k=(P^{\mathsf T})^k p_0.pk+1​=PTpk​,pk​=(PT)kp0​.

With row distributions one writes pk+1T=pkTPp_{k+1}^{\mathsf T}=p_k^{\mathsf T}Ppk+1T​=pkT​P. Both conventions are valid. Mixing P=D−1WP=D^{-1}WP=D−1W with pk+1=Ppkp_{k+1}=Pp_kpk+1​=Ppk​ for a column generally is not.

A checkable example.

P=[0.90.10.20.8],p0=[10].P=\begin{bmatrix}0.9&0.1\\0.2&0.8\end{bmatrix},\qquad p_0=\begin{bmatrix}1\\0\end{bmatrix}.P=[0.90.2​0.10.8​],p0​=[10​].

After one step p1=(0.9,0.1)Tp_1=(0.9,0.1)^{\mathsf T}p1​=(0.9,0.1)T; after two, p2=(0.83,0.17)Tp_2=(0.83,0.17)^{\mathsf T}p2​=(0.83,0.17)T. (Pk)ij(P^k)_{ij}(Pk)ij​ is the probability of ending in jjj after kkk steps having started in iii: it sums every allowed intermediate walk (adjacency and degree). If NNN objects follow these probabilities, the expected counts obey the same linear evolution while the observed counts fluctuate. Nobody claims one object sits in every node at once.

From graph to walk. With non-negative weights and di>0d_i>0di​>0, P=D−1WP=D^{-1}WP=D−1W picks neighbors in proportion to their weights. The operator PxPxPx averages a function on nodes; PTpP^{\mathsf T}pPTp transports a column distribution. Dual actions, not interchangeable meanings (normalized Laplacian).

Continuous time. A row generator QQQ has non-negative off-diagonal entries and zero row sums, and probabilities satisfy p˙=QTp\dot p=Q^{\mathsf T}pp˙​=QTp; for example Q=ν(P−I)Q=\nu(P-I)Q=ν(P−I) with a rate ν>0\nu>0ν>0. A per-step transition and a generator are related but not the same object (discretization).

The memory condition that makes the chain well defined is the Markov property of a sufficient state. The long run belongs to the stationary distribution.

Convention and theory reference: Levin and Peres, Markov Chains and Mixing Times, 2nd edition, chapter 1