Two Different Questions About Equilibrium
A continuous-time Markov chain can approach its stationary distribution from every fixed starting state without doing so at a rate that is uniform over the whole state space. The distinction matters on countable spaces: states farther and farther away may require longer and longer to reach the region where most stationary probability lies. Thus a statement about every fixed starting state does not automatically control all starting states at once.
Let \((X_t)_{t\ge0}\) be a continuous-time Markov chain on a countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition probabilities \(P_t(i,j)=\mathbb{P}_i(X_t=j)\). A probability distribution is written as a row vector. A stationary distribution \(\pi\) satisfies \(\pi P(t)=\pi\) for every \(t\ge0\). For probability distributions \(\nu,\eta\) on \(S\), their total-variation distance is \(\|\nu-\eta\|_{\mathrm{TV}}=\sup_{A\subseteq S}|\nu(A)-\eta(A)|=\tfrac12\sum_{j\in S}|\nu(j)-\eta(j)|\).
Total variation is useful because it measures the largest discrepancy in the probability assigned to any event. In particular, \(d_i(t)\) is at least the discrepancy for any one chosen subset \(A\). On a countable space, the sum formula also shows why it is a strong notion: convergence in total variation controls the whole distribution, not just the probability of each individual state.
What Pointwise Convergence Does Guarantee
Proof. If \(F\) is empty, there are no starting states to check, so the assertion is vacuous. Otherwise, write \(F=\{i_1,\ldots,i_m\}\), where \(m\) is a positive integer. Fix \(\varepsilon>0\). For each \(r\in\{1,\ldots,m\}\), pointwise convergence gives a finite time \(T_r\) such that \(d_{i_r}(t)<\varepsilon\) whenever \(t\ge T_r\). Set \(T=\max_{1\le r\le m}T_r\), which is finite because it is the maximum of finitely many finite numbers. For \(t\ge T\), every \(r\) satisfies \(d_{i_r}(t)<\varepsilon\), so \(\max_{i\in F}d_i(t)<\varepsilon\). This is the claimed convergence. The argument relies on finiteness: it takes a maximum of finitely many convergence times, and an infinite family of such times need not be bounded. \(\square\)
There is also a useful interpretation in terms of initial distributions. If \(\mu\) is any initial distribution, then \(\mu P(t)\) is a mixture of the rows \(P_t(i,\cdot)\). By the triangle inequality, \(\|\mu P(t)-\pi\|_{\mathrm{TV}}\le\sum_i\mu(i)d_i(t)\le\sup_i d_i(t)\). Conversely, choosing \(\mu\) to put all its mass at a particular \(i\) gives distance \(d_i(t)\). Therefore the supremum over starting states is exactly the worst distance over all initial distributions.
Worked Example: A Pure-Death Chain
Consider a CTMC on \(S=\{0,1,2,\ldots\}\) with generator \(Q\) given by \(q_{n,n-1}=1\) for \(n\ge1\), \(q_{n,n}=-1\) for \(n\ge1\), and \(q_{0,0}=0\); all other entries are zero. Every row sums to zero: at \(n\ge1\), the two nonzero entries sum to \(1-1=0\), and row \(0\) sums to \(0\). State \(0\) is absorbing, so \(\pi=\delta_0\), the distribution putting probability one at \(0\), is stationary.
Starting from \(i\), the chain makes jumps downward at rate \(1\) until it reaches \(0\). Its number of jumps by time \(t\), before accounting for absorption, has the Poisson distribution with mean \(t\). Thus \(X_t=(i-N_t)^+\), where \(N_t\) has that Poisson distribution and \(x^+=\max(x,0)\). Since the equilibrium is concentrated at \(0\), the total-variation distance is exactly the probability of not yet being at \(0\):
For each fixed \(i\), this is a finite sum of terms that tend to zero as \(t\to\infty\), so \(d_i(t)\to0\). For example, if \(i=2\) and \(t=1\), then \(d_2(1)=e^{-1}(1+1)=2e^{-1}\); this is the probability of zero or one jump by time \(1\). For a check, the complementary probability of having reached \(0\) is \(\mathbb{P}(N_1\ge2)=1-e^{-1}(1+1)\), and the two probabilities sum to \(1\).
Now fix any finite \(t\). As \(i\) increases, the event \(N_t<i\) increases to the whole sample space, because \(N_t\) is finite with probability one. Hence \(d_i(t)\to1\) as \(i\to\infty\), and \(\sup_i d_i(t)=1\). It follows that the chain converges pointwise to \(\delta_0\) but not uniformly. The stationary distribution is not itself a limiting distribution uniformly over starting states: at every finite time, sufficiently high starting states retain probability arbitrarily close to one of being away from \(0\).
An Irreducible Example: The M/M/1 Queue
The preceding example is reducible. Nonuniform convergence is not merely a consequence of reducibility or of having an absorbing equilibrium. Consider instead the M/M/1 queue-length CTMC on \(S=\{0,1,2,\ldots\}\), with arrival rate \(\lambda=\tfrac12\) and service rate \(\mu=1\). Its transitions are \(n\to n+1\) at rate \(\tfrac12\) for every \(n\ge0\), and \(n\to n-1\) at rate \(1\) for every \(n\ge1\). The generator has \(q_{0,0}=-\tfrac12\), \(q_{0,1}=\tfrac12\), and, for \(n\ge1\), \(q_{n,n-1}=1\), \(q_{n,n+1}=\tfrac12\), \(q_{n,n}=-\tfrac32\); every row sums to zero. Its total jump rates are bounded by \(\tfrac32\), so the chain is nonexplosive. It is irreducible.
The stationary distribution is \(\pi_n=2^{-(n+1)}\) for \(n\ge0\). Its entries sum to one because \(\sum_{n\ge0}2^{-(n+1)}=1\). The balance equation at \(0\) is \(\pi_0(\tfrac12)=\pi_1(1)\), and both sides equal \(\tfrac14\). For \(n\ge1\), incoming rate is \(\pi_{n-1}(\tfrac12)+\pi_{n+1}(1)=2^{-(n+1)}+2^{-(n+2)}=3\cdot2^{-(n+2)}\); outgoing rate is \(\pi_n(\tfrac32)=3\cdot2^{-(n+2)}\). Thus the generator balance equations hold. The standard convergence theorem for irreducible, positive-recurrent CTMCs gives convergence in total variation to the stationary distribution from each fixed state; this pointwise convergence result is part of the earlier material on convergence to equilibrium.
Worked Example: Why the Queue Does Not Converge Uniformly
For this queue, positive recurrence follows also from the stationary probability distribution just computed and the standard irreducible-chain criterion. We show directly that, despite pointwise convergence, the distance cannot converge uniformly. Fix \(t<\infty\) and a nonnegative integer \(K\). Starting from \(i>K\), the event \(X_t\le K\) requires at least \(i-K\) service completions by time \(t\), since arrivals can only increase the queue length.
Service completions occur at rate \(1\) whenever the queue is nonempty. They can be counted using a rate-one Poisson process, ignoring its proposed service events when the queue is empty. Therefore the number of actual completions by time \(t\) is no greater than a Poisson random variable \(N_t\) with mean \(t\). In particular,
Use the set \(A_K=\{0,1,\ldots,K\}\) in the definition of total variation. For each fixed \(K\), the preceding bound gives \(\lim_{i\to\infty}|\mathbb{P}_i(X_t\in A_K)-\pi(A_K)|=\pi(A_K)\). Consequently, \(\sup_i d_i(t)\ge\pi(A_K)=\sum_{n=0}^K2^{-(n+1)}=1-2^{-(K+1)}\). This holds for every \(K\). Letting \(K\to\infty\) makes the lower bound tend to \(1\), while total-variation distance between probability distributions is at most \(1\). Hence \(\sup_i d_i(t)=1\) for every finite \(t\): convergence is not uniform.
Check: For \(K=2\), the stationary mass is \(\pi(A_2)=\tfrac12+\tfrac14+\tfrac18=\tfrac78\), while a start at \(i\) has probability of being in \(A_2\) tending to zero as \(i\to\infty\), at this same fixed \(t\). The discrepancy therefore approaches \(\tfrac78\). Increasing \(K\) raises this lower bound toward \(1\), as required.
The queue example exhibits a general mechanism. Stationarity puts nearly all mass in some finite set, but from a sufficiently distant initial state the chain is very unlikely to reach that set by a fixed finite time. Pointwise convergence allows the time required to get close to equilibrium to depend on the starting state. Uniform convergence would require one time threshold that works for every state simultaneously.
Uniform Convergence Can Occur on a Countable Space
Worked Example: Resetting to an Absorbing State
Let \(S=\{0,1,2,\ldots\}\), and define a CTMC by \(q_{n,0}=1\) and \(q_{n,n}=-1\) for \(n\ge1\), with \(q_{0,0}=0\) and all other entries zero. Each row sums to zero. State \(0\) is absorbing, so \(\pi=\delta_0\) is stationary. From any \(i\ge1\), the chain waits an exponential time of rate \(1\) and then jumps directly to \(0\).
The probability it has not reset by time \(t\) is \(e^{-t}\). The distribution at time \(t\) is therefore \(P_t(i,\cdot)=e^{-t}\delta_i+(1-e^{-t})\delta_0\) for \(i\ge1\), while \(P_t(0,\cdot)=\delta_0\). Since \(i\ne0\), the two point masses \(\delta_i\) and \(\delta_0\) assign different probabilities to the event \(\{i\}\), so their total-variation distance is \(1\). It follows that \(d_i(t)=e^{-t}\) for every \(i\ge1\), and \(d_0(t)=0\). Thus \(\sup_i d_i(t)=e^{-t}\to0\). In particular, at \(t=1\), the distance from any nonzero state is \(e^{-1}\), and substituting this into the reset probability gives \(1-e^{-1}\) for the probability already at equilibrium. The two probabilities sum to \(1\).
The reset chain and the pure-death chain both have countably many states and the same stationary distribution \(\delta_0\), but their convergence differs because their return mechanisms differ. In the reset chain, every nonzero state has the same rate-one route to equilibrium. In the pure-death chain, a high state must make many successive jumps before reaching equilibrium, so no finite time controls all starting states.
A Common Mistake and a Practical Test
A common error is to infer uniform convergence by exchanging a limit and a supremum. For the pure-death chain, the calculation for each fixed \(i\) gives \(\lim_{t\to\infty}d_i(t)=0\). The incorrect conclusion is \(\lim_{t\to\infty}\sup_i d_i(t)=0\). But at every fixed \(t<\infty\), \(\sup_i d_i(t)=1\), so the latter limit is \(1\), not \(0\). The correction is to check the order of quantifiers: pointwise convergence allows a time threshold depending on \(i\), whereas uniform convergence requires a single threshold that works for all \(i\).
When studying a countable-state chain, it is often useful to test uniformity with a family of sets that captures most of \(\pi\). Choose a finite set \(A\) with \(\pi(A)\) close to \(1\), then ask whether starting states far from \(A\) can have small probability of reaching \(A\) by a fixed time. If they cannot, the difference between that probability and \(\pi(A)\) gives a lower bound on total-variation distance. This argument does not contradict convergence from each fixed state: the starting state used to make the discrepancy large may change as time changes.
Check Your Understanding
Use the definitions and calculations above to distinguish the two modes of convergence.
- For the pure-death chain, write \(d_3(t)\) explicitly and explain why it tends to zero for a fixed starting state \(3\).
- Why does the pure-death chain have \(\sup_i d_i(t)=1\) at each fixed finite time, even though \(d_i(t)\to0\) for every fixed \(i\)?
- In the M/M/1 example, why can arrivals not invalidate the lower bound based on the number of service completions needed to reach \(\{0,\ldots,K\}\)?
- Verify the stationary mass \(\pi(\{0,1\})\) in the queue example and state the resulting lower bound on \(\sup_i d_i(t)\).
- For the reset chain, calculate \(d_i(t)\) when \(i\ge1\) and explain why the supremum over all states tends to zero.