Proving Invariance by Counting Visits Between Returns

Why a Return Cycle Gives Balance

Stationary balance equations say that, in one step, the probability mass entering each state equals the mass already assigned to that state. A return cycle gives a different way to see the same balance: along a completed cycle, the number of transitions into a state equals the number of visits to it when departures are counted from the cycle's starting time. Taking expectations converts this pathwise fact into the stationary equations.

Let $(X_n)_{n\ge0}$ be a time-homogeneous Markov chain on a finite or countable state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with transition matrix $P=(p_{ij})$. The matrix is row-stochastic: $p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$ and $\sum_{j\in S}p_{ij}=1$ for each $i$. Fix a state $i$ and start the chain there, so probabilities and expectations are $\mathbb{P}_i$ and $\mathbb{E}_i$. Use the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$, and define the first return time $T_i^+=\inf\{n\ge1:X_n=i\}$.

Definition: For each state $j$, the expected visit count in the return cycle from $i$ is $\nu_j=\mathbb{E}_i\left[\sum_{n=0}^{T_i^+-1}\mathbf{1}_{\{X_n=j\}}\right]$. The cycle includes its starting state at time $0$, but not its endpoint at time $T_i^+$.

Assume throughout that $\mathbb{E}_i[T_i^+]<\infty$. This ensures the return occurs almost surely and the expected number of total visits in the cycle is finite. In fact, summing the visit counts over all states gives the cycle length: $\sum_{j\in S}\nu_j=\mathbb{E}_i[T_i^+]$. Also, $\nu_i=1$: before the first return there is exactly one visit to $i$, at time $0$.

The Arrival–Departure Identity

For a fixed state $j$, compare two counts along one realized cycle. The departure count is the number of times $X_n=j$ for $0\le n<T_i^+$. The arrival count is the number of times $X_{n+1}=j$ over those same steps. Write the cycle's states as $x_0=i,x_1,\ldots,x_{T_i^+}=i$. The departure count looks at $x_0,\ldots,x_{T_i^+-1}$; the arrival count looks at $x_1,\ldots,x_{T_i^+}$. The lists differ only by replacing the initial $i$ with the final $i$, so their counts of every state agree.

Lemma (Cycle arrival–departure identity): For every $j\in S$, almost surely, $$ \sum_{n=0}^{T_i^+-1}\mathbf{1}_{\{X_n=j\}} = \sum_{n=0}^{T_i^+-1}\mathbf{1}_{\{X_{n+1}=j\}}. $$

Proof. On the event $T_i^+=m<\infty$, the departure count is $\sum_{r=0}^{m-1}\mathbf{1}_{\{x_r=j\}}$, and the arrival count is $\sum_{r=1}^{m}\mathbf{1}_{\{x_r=j\}}$. Subtracting the second from the first leaves $\mathbf{1}_{\{x_0=j\}}-\mathbf{1}_{\{x_m=j\}}$. Since $x_0=x_m=i$, this difference is zero for every $j$. The return time is finite almost surely by the finite-mean assumption, so the identity holds almost surely. $\square$

Now take expectations. The Markov property connects the expected arrival count to the expected departures from each possible state. For each $n$, the event $\{n<T_i^+\}$ is determined by $X_0,\ldots,X_n$, so it belongs to $\mathcal{F}_n$. Therefore, for $k,j\in S$,

\mathbb{E}_i\!\left[\mathbf{1}_{\{n<T_i^+\}}\mathbf{1}_{\{X_n=k\}}\mathbf{1}_{\{X_{n+1}=j\}}\right] = p_{kj}\mathbb{E}_i\!\left[\mathbf{1}_{\{n<T_i^+\}}\mathbf{1}_{\{X_n=k\}}\right].

Summing over $n$ and $k$ yields the expected arrival count at $j$. These sums contain nonnegative terms, so they may be interchanged by Tonelli's theorem. The finite-mean condition also ensures that the resulting count is finite in expectation.

Theorem (Invariance from return-cycle counts): Suppose $(X_n)_{n\ge0}$ is a Markov chain on a finite or countable state space $S$, started at $i$, and $\mathbb{E}_i[T_i^+]<\infty$. Define $\nu_j$ as the expected visit count in the cycle from $i$. Then, for every $j\in S$, $$ \nu_j=\sum_{k\in S}\nu_k p_{kj}. $$ Consequently, $\pi_j=\nu_j/\mathbb{E}_i[T_i^+]$ defines a probability distribution satisfying $\pi P=\pi$.

Proof. By the arrival–departure identity, the expected arrival count at $j$ equals $\nu_j$. On the other hand, condition on the state at each departure time. Using the conditional expectation calculation above, then summing nonnegative terms over $n$ and $k$, gives

\begin{aligned} \mathbb{E}_i\!\left[\sum_{n=0}^{T_i^+-1}\mathbf{1}_{\{X_{n+1}=j\}}\right] &=\sum_{n\ge0}\sum_{k\in S} p_{kj}\mathbb{E}_i\!\left[\mathbf{1}_{\{n<T_i^+\}}\mathbf{1}_{\{X_n=k\}}\right]\\ &=\sum_{k\in S}p_{kj}\mathbb{E}_i\!\left[\sum_{n=0}^{T_i^+-1}\mathbf{1}_{\{X_n=k\}}\right]\\ &=\sum_{k\in S}\nu_kp_{kj}. \end{aligned}

Thus $\nu_j=\sum_k\nu_kp_{kj}$ for every $j$. Also, by summing nonnegative visit indicators over $j$, $\sum_j\nu_j=\mathbb{E}_i[T_i^+]$, which is finite and positive. Dividing each balance equation by this sum gives $\pi_j=\sum_k\pi_kp_{kj}$, and $\sum_j\pi_j=1$. Hence $\pi$ is a probability distribution and satisfies $\pi P=\pi$. $\square$

This argument proves invariance by matching counts, rather than by guessing a solution to a system of equations. It only needs a state with finite expected return time; it does not require aperiodicity. It establishes an invariant distribution from these cycle counts, not a claim that the distribution of $X_n$ converges to it.

Worked Cycle Counts

Worked Example: A Three-State Cycle with a Branch

Consider $S=\{1,2,3\}$ and start at state $1$, with transition matrix

P= \begin{bmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ 1&0&0 \end{bmatrix}.

The row sums are $0+1+0=1$, $\tfrac12+0+\tfrac12=1$, and $1+0+0=1$. From $1$, the chain moves to $2$; from $2$, it returns to $1$ or visits $3$ and then returns to $1$. Thus $T_1^+$ is either $2$ or $3$, so its mean is finite. The cycle starts with one visit to $1$. It visits $2$ once in either case, and visits $3$ with probability $\tfrac12$. Therefore $\nu=(1,1,\tfrac12)$, and $\mathbb{E}_1[T_1^+]=1+1+\tfrac12=\tfrac52$. Normalizing gives $\pi=(\tfrac25,\tfrac25,\tfrac15)$.

Check by balance equations: The mass entering state $1$ is $\tfrac25\cdot0+\tfrac25\cdot\tfrac12+\tfrac15\cdot1=\tfrac25$. The mass entering state $2$ is $\tfrac25\cdot1+\tfrac25\cdot0+\tfrac15\cdot0=\tfrac25$. The mass entering state $3$ is $\tfrac25\cdot0+\tfrac25\cdot\tfrac12+\tfrac15\cdot0=\tfrac15$. Thus $\pi P=\pi$, and $\tfrac25+\tfrac25+\tfrac15=1$.

Worked Example: Self-Loops Extend the Return Cycle

Let $S=\{1,2\}$ and start at $1$, with

P= \begin{bmatrix} \tfrac12&\tfrac12\\ \tfrac14&\tfrac34 \end{bmatrix}.

The first row sums to $\tfrac12+\tfrac12=1$, and the second to $\tfrac14+\tfrac34=1$. A return cycle has one visit to state $1$ at time $0$. It visits state $2$ only if the first transition goes there, an event with probability $\tfrac12$. Once at $2$, the number $L$ of visits to $2$ before returning to $1$ has $\mathbb{P}(L\ge r)=(\tfrac34)^{r-1}$ for each integer $r\ge1$: each additional visit requires another self-transition at $2$. Hence $\mathbb{E}[L]=\sum_{r\ge1}(\tfrac34)^{r-1}=1/(1-\tfrac34)=4$. It follows that $\nu_2=\tfrac12\cdot4=2$, so $\nu=(1,2)$, the mean return time is $3$, and $\pi=(\tfrac13,\tfrac23)$.

Check by balance equations: The mass entering state $1$ is $\tfrac13\cdot\tfrac12+\tfrac23\cdot\tfrac14=\tfrac16+\tfrac16=\tfrac13$. The mass entering state $2$ is $\tfrac13\cdot\tfrac12+\tfrac23\cdot\tfrac34=\tfrac16+\tfrac12=\tfrac23$. The entries sum to $1$, so this normalized cycle count satisfies $\pi P=\pi$.

Worked Example: A Cycle That Can Return in One Step

Take $S=\{1,2,3\}$, start at $1$, and use

P= \begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\ \tfrac12&0&\tfrac12\\ 1&0&0 \end{bmatrix}.

The row sums are $\tfrac12+\tfrac13+\tfrac16=1$, $\tfrac12+0+\tfrac12=1$, and $1+0+0=1$. A transition from $1$ to $1$ completes the cycle immediately, but state $1$ still contributes exactly one visit at time $0$. State $2$ is visited if and only if the first transition is to $2$, so $\nu_2=\tfrac13$. State $3$ is visited either by moving there directly from $1$, with probability $\tfrac16$, or by moving first to $2$ and then to $3$, with probability $\tfrac13\cdot\tfrac12=\tfrac16$. These routes are disjoint, so $\nu_3=\tfrac16+\tfrac16=\tfrac13$. Thus $\nu=(1,\tfrac13,\tfrac13)$, its total is $\tfrac53$, and $\pi=(\tfrac35,\tfrac15,\tfrac15)$.

Check by balance equations: The mass entering state $1$ is $\tfrac35\cdot\tfrac12+\tfrac15\cdot\tfrac12+\tfrac15\cdot1=\tfrac3{10}+\tfrac1{10}+\tfrac15=\tfrac35$. The mass entering state $2$ is $\tfrac35\cdot\tfrac13=\tfrac15$. The mass entering state $3$ is $\tfrac35\cdot\tfrac16+\tfrac15\cdot\tfrac12=\tfrac1{10}+\tfrac1{10}=\tfrac15$. The entries sum to $1$, and all three balance equations hold.

A Common Counting Error

A frequent mistake is to count arrivals only at times $1,\ldots,T_i^+-1$, leaving out the transition that completes the return. That is not the arrival count for the cycle: it omits the endpoint $X_{T_i^+}=i$. In the first example, a completed cycle has one departure from state $1$ (at time $0$). If the final return transition is omitted, the alleged arrival count into state $1$ is zero, contradicting the balance equation. The correct arrival count includes times $1,\ldots,T_i^+$; then the cycle starts and ends at $1$, and the pathwise identity holds for every state.

The convention about endpoints is therefore essential. The cycle's visit count uses $X_0,\ldots,X_{T_i^+-1}$, while its arrival count uses $X_1,\ldots,X_{T_i^+}$. Shifting the time indices without shifting the endpoint changes the count. Once the endpoint is included, the proof works on finite or countable state spaces because the counts are nonnegative and their expectations can be summed using Tonelli's theorem.

Check Your Understanding

Use the arrival–departure identity and verify each proposed count or balance equation.

In the first worked example, list the two possible return-cycle paths and their probabilities. Compute the return time on each path.
For the second worked example, explain why $\mathbb{P}(L\ge r)=(\tfrac34)^{r-1}$, and use the tail-sum formula to recover $\mathbb{E}[L]$.
In the third worked example, why does a one-step return contribute one visit to state $1$ to the cycle count, rather than zero or two?
State the exact two lists of states compared in the pathwise arrival–departure identity.
Which assumption ensures that the normalized expected visit counts have a finite, positive denominator?

Proving Invariance by Counting Visits Between Returns

What You'll Learn