Uniform Stationarity for Doubly Stochastic Chains

Uniform Mass and Incoming Probability

A transition matrix describes how probability moves out of each state. Its row sums ensure that the probability leaving any one state totals one. For a uniform distribution to remain unchanged, there is a second requirement: the total transition probability flowing into each state must also be one. This balance gives a direct test for whether the uniform distribution is stationary.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite, nonempty state space \(S=\{1,\ldots,m\}\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix is \(P=(p_{ij})\), where \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\). Thus \(p_{ij}\ge0\), and, for each state \(i\), \(\sum_{j\in S}p_{ij}=1\). Distributions are row vectors: if the distribution at time \(n\) is \(\mu_n\), then \(\mu_{n+1}=\mu_nP\).

A distribution \(\pi\) is stationary for \(P\) if \(\pi P=\pi\). This means that starting the chain with distribution \(\pi\) gives the same distribution after one transition. It does not, by itself, say that distributions from other starting points converge to \(\pi\).

The key calculation is coordinatewise. For a fixed destination state \(j\), the probability assigned to \(j\) by \(uP\) is the sum of the incoming probabilities \(p_{ij}\), weighted by the uniform mass \(1/m\) at each source state. It is the column sum, not the row sum, that appears in this calculation.

Proof. Assume first that every column of \(P\) sums to one. For each \(j\in S\), matrix multiplication gives \((uP)_j=\sum_{i\in S}u_i p_{ij}=(1/m)\sum_{i\in S}p_{ij}=1/m=u_j\). This holds for every coordinate \(j\), so \(uP=u\), and \(u\) is stationary. Conversely, suppose \(uP=u\). For any \(j\in S\), the same coordinate calculation gives \(1/m=(uP)_j=(1/m)\sum_{i\in S}p_{ij}\). Since \(m\) is positive, multiplying both sides by \(m\) yields \(\sum_{i\in S}p_{ij}=1\). This holds for every column. The matrix is already row-stochastic by assumption, so it is doubly stochastic. \(\square\)

This equivalence uses finiteness and the fact that the state space is nonempty, so that \(m\) is a positive integer and \(u\) is a probability distribution. It does not require irreducibility or aperiodicity. Nor does the theorem claim that the uniform distribution is the only stationary distribution.

Checking the Column Sums

Why Row Sums Are Not Enough

The theorem also gives a useful way to read the balance condition. Under the uniform law, every source state has mass \(1/m\). A destination \(j\) receives total mass \(\sum_i (1/m)p_{ij}\). It retains mass \(1/m\) exactly when the probabilities in column \(j\) sum to one. This is why “the rows sum to one” and “the uniform law is stationary” are different assertions: the former checks total probability leaving each source, while the latter additionally checks the incoming total at each destination.

Stationarity Is Invariance, Not a Convergence Claim

Proof. The theorem gives \(uP=u\). At time zero, the distribution is \(\mu_0=u\). If \(\mu_n=u\), the Markov transition rule gives \(\mu_{n+1}=\mu_nP=uP=u\). Induction starting at \(n=0\) proves \(\mu_n=u\) for every nonnegative integer \(n\). \(\square\)

This corollary concerns a chain whose initial law is already uniform. It does not state that a chain started from an arbitrary distribution will approach the uniform law. For example, the identity matrix on two states is doubly stochastic, and the uniform distribution is stationary. But for this matrix, a chain started in state 1 stays in state 1, so its distribution remains \((1,0)\), not the uniform distribution. The same matrix has many stationary distributions: for any \(a\in[0,1]\), the distribution \((a,1-a)\) satisfies \((a,1-a)P=(a,1-a)\).

Consequently, double stochasticity is a direct test for one particular stationary law, not a test of irreducibility, uniqueness, or convergence. Those are separate questions. In particular, do not infer from \(uP=u\) that all initial distributions converge to \(u\), or that no other stationary distributions exist.

Common mistake. In the unequal-probability example, an incorrect calculation might say that \((uP)_1=\tfrac13\) because “the first row sums to one.” But the first coordinate of the product uses column 1: \((uP)_1=\tfrac13(\tfrac12+\tfrac13+\tfrac16)=\tfrac13\). That coordinate happens to be correct in this example, but the reasoning is wrong: the row sum does not appear in the formula. The column calculation is what verifies it. On the two-state counterexample, the same mistaken row-based reasoning would predict a first coordinate of \(\tfrac12\); the actual coordinate is \(\tfrac12(\tfrac34+\tfrac12)=\tfrac58\). The correction is to check the appropriate column separately for each destination state.