Why Add a Chance to Stay Put?
A Markov chain can fail to settle toward equilibrium because its transitions force it to cycle through states in a regular pattern. A simple way to remove that timing obstruction is to give the chain a positive chance to remain where it is at every step. The resulting chain is called lazy. Its transitions change, but its stationary distributions do not: lazification adjusts the chain's timing without changing its equilibrium balance.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a nonempty finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix \(P=(p_{ij})\) is row-stochastic, so \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\in S\). Write distributions as row vectors; in particular, an initial distribution \(\mu\) evolves as \(\mu P\) after one step. A distribution \(\pi\) is stationary if \(\pi P=\pi\).
This matrix has a direct random construction. At each step, independently choose whether to stay put or to make an ordinary \(P\)-transition, with probability one-half for each choice. If the chain is at state \(i\), the resulting probability of being at \(j\) next is \(\tfrac12\mathbf{1}_{\{i=j\}}+\tfrac12p_{ij}\), exactly \(\widetilde p_{ij}\). The random choices may be added on an enlarged probability space if necessary.
What Lazification Guarantees
Proof. For each state \(i\), all entries \(\widetilde p_{ij}\) are nonnegative and \(\sum_j\widetilde p_{ij}=\tfrac12\sum_j\mathbf{1}_{\{i=j\}}+\tfrac12\sum_jp_{ij}=\tfrac12+\tfrac12=1\). So \(\widetilde P\) is row-stochastic. For any probability distribution \(\pi\), matrix multiplication gives \(\pi\widetilde P=(\pi+\pi P)/2\). If \(\pi P=\pi\), this equals \(\pi\). Conversely, if \(\pi\widetilde P=\pi\), then \(\pi+\pi P=2\pi\), hence \(\pi P=\pi\). This proves the equivalence of stationary distributions.
For a state \(i\), its period is \(d(i)=\gcd\{n\ge1:p_{ii}^{(n)}>0\}\), where \(p_{ii}^{(n)}\) is the probability of returning to \(i\) in \(n\) steps. Since \(\widetilde p_{ii}=(1+p_{ii})/2\ge1/2>0\), a one-step return is possible. Thus \(1\) belongs to the set whose greatest common divisor defines the period, so \(d(i)=1\).
Finally, if \(i\ne j\), then \(\widetilde p_{ij}=p_{ij}/2\), so a one-step transition from \(i\) to \(j\) has positive probability under one matrix exactly when it does under the other. A finite path from \(i\) to \(j\) using \(P\)-transitions therefore has positive probability under \(\widetilde P\) as well. Conversely, any positive-probability \(\widetilde P\)-path from \(i\) to \(j\) can have its steps that stay at the current state removed. Every remaining step is between distinct states, and then \(\widetilde p_{ab}>0\) implies \(p_{ab}>0\). The resulting \(P\)-path has positive probability. For \(i=j\), communication holds by a path of length zero under either matrix. Hence communication is unchanged. \(\square\)
The theorem does not require irreducibility for its claims about stationarity or period. In particular, it does not say that the chain has a unique stationary distribution or that its distribution converges to one. Aperiodicity removes a periodicity obstruction; it does not remove other obstructions.
Computing the Lazy Matrix
Worked Example: Turning a Two-State Cycle into an Aperiodic Chain
Let \(S=\{0,1\}\) and let the chain alternate deterministically between the two states. Its transition matrix and the row sums are
The original chain returns to either state only after an even number of steps, so each state has period \(2\). Adding half the identity gives
Each lazy row sums to \(\tfrac12+\tfrac12=1\), and the diagonal entries are positive, so each state now has period one. The stationary distribution of the original chain is \(\pi=(\tfrac12,\tfrac12)\): multiplying gives \(\pi P=(\tfrac12,\tfrac12)\). For the lazy matrix, \(\pi\widetilde P=(\tfrac12,\tfrac12)\) as well. In this example, both lazy rows are identical, so after one step the distribution is \((\tfrac12,\tfrac12)\) regardless of the initial state. The stationary-distribution equivalence, however, follows from the theorem and does not depend on this special calculation.
Worked Example: Lazifying a Three-State Directed Cycle
Let \(S=\{0,1,2\}\), with each state moving deterministically to the next state in the cycle \(0\to1\to2\to0\). The transition matrix is
Its row sums are \(0+1+0=1\), \(0+0+1=1\), and \(1+0+0=1\). A return to any state takes a multiple of three steps, so the original chain has period \(3\). Applying the formula row by row gives
Each row sums to \(1\): the sums are \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac12+\tfrac12=1\), and \(\tfrac12+0+\tfrac12=1\). The positive diagonal entries give each state a one-step return, hence period one. The uniform distribution \(\pi=(\tfrac13,\tfrac13,\tfrac13)\) is stationary for \(P\), because \(\pi P=(\tfrac13,\tfrac13,\tfrac13)\). Directly for the lazy matrix, its three coordinates after multiplication are \(\tfrac16+0+\tfrac16=\tfrac13\), \(\tfrac16+\tfrac16+0=\tfrac13\), and \(0+\tfrac16+\tfrac16=\tfrac13\). Thus \(\pi\widetilde P=\pi\), as the general result predicts.
Worked Example: A Nonuniform Stationary Distribution
Consider the chain on \(S=\{1,2,3\}\) with transition matrix
The row sums are \(0+1+0=1\), \(\tfrac12+0+\tfrac12=1\), and \(0+1+0=1\). The distribution \(\pi=(\tfrac14,\tfrac12,\tfrac14)\) is stationary for \(P\): the three coordinates of \(\pi P\) are \(\tfrac12\cdot\tfrac12=\tfrac14\), \(\tfrac14+\tfrac14=\tfrac12\), and \(\tfrac12\cdot\tfrac12=\tfrac14\). The lazy matrix is
Its row sums are \(\tfrac12+\tfrac12+0=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(0+\tfrac12+\tfrac12=1\). Multiplication verifies stationarity: the first coordinate of \(\pi\widetilde P\) is \(\tfrac14\cdot\tfrac12+\tfrac12\cdot\tfrac14=\tfrac18+\tfrac18=\tfrac14\); the second is \(\tfrac14\cdot\tfrac12+\tfrac12\cdot\tfrac12+\tfrac14\cdot\tfrac12=\tfrac18+\tfrac14+\tfrac18=\tfrac12\); and the third is \(\tfrac12\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac18+\tfrac18=\tfrac14\). Therefore \(\pi\widetilde P=\pi\), with \(\sum_i\pi_i=\tfrac14+\tfrac12+\tfrac14=1\). Lazification has not made the stationary distribution uniform.
What Changes, and What Does Not
The stationary balance equations are preserved exactly, but the step-by-step dynamics are different. At each step the lazy chain has a probability of staying put; off-diagonal transition probabilities are halved. This changes the rate at which the chain moves through the state space. It is therefore important to distinguish preserving the stationary distribution from preserving the original transition probabilities or the original rate of movement.
Irreducibility is preserved because communication is preserved: every path between distinct states under one matrix exists under the other. In a finite irreducible chain, lazification is a useful way to eliminate periodicity while retaining the same stationary distribution. Standard finite-state convergence results can then be applied under their stated hypotheses. The construction alone does not establish those hypotheses in a reducible chain, nor does it imply that every chain with a stationary distribution converges to that distribution.
For example, if \(P=I\) on \(S=\{0,1\}\), then both rows sum to \(1\) and \(\widetilde P=(I+P)/2=I\). Every state has period one, but a chain started at \(0\) remains at \(0\) forever. Every probability distribution is stationary, so there is no unique equilibrium distribution to which all initial states must converge. Aperiodicity is a specific property of return times, not a substitute for irreducibility or other conditions used in convergence results.
Common mistake. Lazification does not mean adding one-half to every entry of \(P\). For instance, the first row \((0,1,0)\) of the three-state cycle, if treated by the incorrect rule “halve \(P\) and add \(\tfrac12\) to every entry,” becomes \((\tfrac12,1,\tfrac12)\), whose sum is \(2\), not \(1\). The correct operation adds half of the identity matrix, not half of an all-ones matrix. That row becomes \((\tfrac12,\tfrac12,0)\), with sum \(1\). In general, check both the diagonal and off-diagonal entries: \(\widetilde p_{ii}=(1+p_{ii})/2\), while \(\widetilde p_{ij}=p_{ij}/2\) for \(i\ne j\).
| Property | Effect of lazification |
|---|---|
| Row sums | Remain equal to one. |
| Stationary distributions | Exactly the same probability distributions are stationary. |
| Communication and irreducibility | Unchanged. |
| Period of each state | Becomes one because the diagonal entry is positive. |
| Transition probabilities | Off-diagonal probabilities are halved; diagonal probabilities increase. |
| Convergence to equilibrium | Not guaranteed by aperiodicity alone. |
Check Your Understanding
Use the definition of \(\widetilde P\) and the period criterion to justify your answers.
- For \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\), compute \(\widetilde P\), check both row sums, and give the period of each state before and after lazification.
- Suppose \(\pi P=\pi\) for a probability row vector \(\pi\). Show by multiplication that \(\pi\widetilde P=\pi\).
- For the three-state directed cycle in the tutorial, compute the probability of moving from state \(1\) to state \(2\) in one lazy step and the probability of staying at state \(1\).
- Does lazification change whether two states communicate? Explain using positive-probability paths.
- Give a transition matrix for which lazification makes every state aperiodic but does not yield a unique stationary distribution. Explain why.