Invariant Weights on a Countable State Space
For a finite Markov chain, stationary balance equations often produce a finite list of weights that can be normalized to sum to one. On a countably infinite state space, the same equations may have nonnegative solutions whose total mass is infinite. Such a solution is still useful: it records a balance of incoming and outgoing probability flow at each state, even though it cannot serve as a probability distribution. The key distinction is between satisfying the balance equations and having finite total mass.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). Each row is a probability distribution, so \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\in S\). Write \(\nu_i\) for a nonnegative weight assigned to state \(i\). These weights need not sum to one.
The equation at state \(j\) says that the weight at \(j\) equals the total weight flowing into \(j\) in one step. The sum is over all possible predecessor states \(i\); it is not a sum over destinations from \(j\). Because all terms are nonnegative, the countable sum is well-defined, with the invariant-measure condition requiring it to equal the finite value \(\nu_j\).
Balance Equations and Normalization
Proof. Suppose first that the coordinate equations hold. For any \(A\subseteq S\), nonnegativity permits the order of the countable sums to be interchanged. Therefore $$ \sum_{i\in S}\nu_iP(i,A) =\sum_{i\in S}\nu_i\sum_{j\in A}p_{ij} =\sum_{j\in A}\sum_{i\in S}\nu_i p_{ij} =\sum_{j\in A}\nu_j =\nu(A). $$ Conversely, suppose the set equation holds for every \(A\). Taking \(A=\{j\}\) gives \(\nu_j=\sum_i\nu_i p_{ij}\) for each \(j\), which is the coordinate equation. This also covers \(A=\varnothing\): both sides are zero. \(\square\)
Proof. Since \(\nu\) is nonzero and nonnegative, at least one \(\nu_i>0\), so \(\nu(S)>0\). If \(\nu(S)<\infty\), define \(\pi_i=\nu_i/\nu(S)\). Then each \(\pi_i\ge0\), and \(\sum_i\pi_i=1\). For every \(j\), $$ \sum_{i\in S}\pi_i p_{ij} =\frac{1}{\nu(S)}\sum_{i\in S}\nu_i p_{ij} =\frac{\nu_j}{\nu(S)} =\pi_j. $$ Thus \(\pi\) is a stationary distribution. Conversely, a stationary distribution is a nonzero invariant measure whose total mass is one, so it has finite total mass. If \(\nu(S)=\infty\), dividing all weights by a finite positive constant still leaves infinite total mass; therefore that scaling cannot produce a probability distribution. \(\square\)
This theorem gives a practical two-part check: first verify the balance equations, then calculate the total mass. The first check alone does not establish that a stationary distribution exists. In particular, a countable list of individually finite weights can have an infinite sum.
Worked Example: Counting Measure for a Symmetric Walk
Let \(S=\mathbb{Z}\), and let \((X_n)_{n\ge0}\) be the simple symmetric random walk: from each \(i\in\mathbb{Z}\), the chain moves to \(i-1\) with probability \(\tfrac12\) and to \(i+1\) with probability \(\tfrac12\). The row sum at every state is \(\tfrac12+\tfrac12=1\), so these transitions define a probability distribution from each state. Define \(\nu_i=1\) for every \(i\in\mathbb{Z}\).
For a fixed \(j\), the only states that can move into \(j\) are \(j-1\) and \(j+1\). Thus $$ \sum_{i\in\mathbb{Z}}\nu_i p_{ij} =\nu_{j-1}\frac12+\nu_{j+1}\frac12 =1\cdot\frac12+1\cdot\frac12 =1 =\nu_j. $$ So \(\nu\) is invariant. Its total mass is \(\sum_{j\in\mathbb{Z}}1=\infty\), since even the partial sum over \(\{-m,\ldots,m\}\) equals \(2m+1\) and grows without bound. It cannot be normalized into a stationary distribution.
Check: At \(j=0\), the incoming weight is \(\nu_{-1}/2+\nu_1/2=1/2+1/2=1=\nu_0\). At every state the same two incoming contributions occur, so the coordinate check holds throughout the state space.
Worked Example: A Nonconstant Invariant Measure for a Biased Walk
Again take \(S=\mathbb{Z}\), but let the chain move from \(i\) to \(i+1\) with probability \(\tfrac13\) and to \(i-1\) with probability \(\tfrac23\). Each row sums to \(\tfrac13+\tfrac23=1\). Consider the positive weights \(\nu_j=2^{-j}\), defined for every integer \(j\). These weights are finite at each individual state, including negative \(j\).
For a fixed \(j\), the possible incoming transitions come from \(j-1\), with probability \(\tfrac13\), and \(j+1\), with probability \(\tfrac23\). Substitution gives $$ \sum_i\nu_i p_{ij} =\frac13\,2^{-(j-1)}+\frac23\,2^{-(j+1)} =\frac23\,2^{-j}+\frac13\,2^{-j} =2^{-j} =\nu_j. $$ Hence these nonconstant weights are invariant.
The total mass is infinite. For each integer \(m\ge1\), the single term at \(j=-m\) equals \(2^m\), so the sum over all states cannot be finite. Thus the balance equations admit a strictly positive invariant measure, but this particular measure cannot be normalized. The conclusion follows from its total mass, not from whether its individual weights are bounded.
Check: At \(j=0\), the incoming weight is \(\tfrac13\nu_{-1}+\tfrac23\nu_1=\tfrac13(2)+\tfrac23(\tfrac12)=\tfrac23+\tfrac13=1=\nu_0\), as required.
Worked Example: A Finite Invariant Measure on a Countable Space
Let \(S=\{(n,b):n\ge0,\ b\in\{0,1\}\}\). From \((n,0)\) the chain moves to \((n,1)\) with probability \(1\), and from \((n,1)\) it moves to \((n,0)\) with probability \(1\). Each row has its single entry equal to \(1\), so every row sums to \(1\). Set \(\nu_{(n,0)}=\nu_{(n,1)}=2^{-(n+1)}\).
For the state \((n,0)\), the only incoming transition is from \((n,1)\), with probability \(1\). Its incoming weight is therefore \(\nu_{(n,1)}=2^{-(n+1)}=\nu_{(n,0)}\). For \((n,1)\), the only incoming transition is from \((n,0)\), giving \(\nu_{(n,0)}=2^{-(n+1)}=\nu_{(n,1)}\). This verifies the balance equations at every state.
For each fixed \(n\), the two weights at level \(n\) sum to \(2\cdot2^{-(n+1)}=2^{-n}\). Therefore $$ \nu(S)=\sum_{n=0}^{\infty}2^{-n}=2. $$ The normalized weights are \(\pi_{(n,b)}=\nu_{(n,b)}/2=2^{-(n+2)}\). For each \(b\), \(\sum_{n=0}^{\infty}2^{-(n+2)}=\tfrac12\), so the sum over both values of \(b\) is \(1\). Since the normalized weights satisfy the same balance equations, \(\pi\) is a stationary distribution.
Check: At \((0,0)\), the incoming normalized weight is \(\pi_{(0,1)}=2^{-2}=\tfrac14=\pi_{(0,0)}\). The same one-to-one incoming transition verifies the equation at every other state.
What Infinite Mass Does—and Does Not—Mean
An invariant measure of infinite total mass still satisfies a precise local balance condition at every state. It is not a probability law for \(X_n\), because a probability distribution must assign total mass one. Nor does infinite total mass mean that any single state has infinite weight: in the examples, every coordinate \(\nu_i\) is finite. The distinction is between the value at each state and the sum across all states.
Scaling preserves invariance: if \(\nu\) is invariant and \(c\) is a finite positive constant, then \(c\nu\) is invariant because $$ \sum_i(c\nu_i)p_{ij}=c\sum_i\nu_i p_{ij}=c\nu_j. $$ But scaling cannot change whether a positive total mass is finite or infinite. A finite invariant measure can be normalized; an infinite one cannot be made into a stationary distribution by multiplying all its weights by the same positive finite constant.
Common mistake. For the simple symmetric walk, one might try to normalize counting measure by writing \(\pi_j=1/\sum_{k\in\mathbb{Z}}1=1/\infty=0\). This is not a probability distribution: assigning zero to every integer gives total mass \(\sum_{j\in\mathbb{Z}}0=0\), not \(1\). The correction is to keep the two questions separate: the weights satisfy the invariant balance equations, but their infinite total mass prevents normalization.
When examining balance equations on a countable state space, check both the local equations and the global sum. Local balance identifies invariant weights. The global sum decides whether those weights can represent a stationary distribution.
Check Your Understanding
For each question, distinguish the coordinate balance calculation from the total-mass calculation.
- For the symmetric random walk on \(\mathbb{Z}\), compute the incoming weight at state \(j\) when \(\nu_i=1\), and explain why the measure cannot be normalized.
- For the biased walk in the example, calculate \(\nu_2\) and the two incoming contributions to state \(2\). Verify that they sum to \(\nu_2\).
- In the chain on \(\{(n,b):n\ge0,\ b\in\{0,1\}\}\), what is the normalized mass at \((3,1)\)? Check its incoming balance equation.
- State the condition on \(\nu(S)\) that allows a nonzero invariant measure to be normalized into a stationary distribution.
- Why does assigning zero mass to every state fail to normalize an infinite invariant measure?