Invariant Measures and Distributions; Positive and Null Recurrence

Intuition Beginner

Imagine pouring sand onto the states of a Markov chain so that some states get a deep pile and others a shallow one. Now run the chain for one step: each grain at a state gets redistributed to its neighbors according to the transition probabilities. For most ways of piling the sand, the heights change. But there is a special way to pile it so that after one step every pile has exactly the height it started with. The chain stirs the sand around, yet the overall profile stays put. That special profile is called an invariant measure. If the total amount of sand is one unit, so the heights are genuine probabilities, we call it an invariant distribution.

Why care? Because the invariant profile is the chain's long-run habit. If you let the chain wander for a very long time and ask what fraction of its visits landed on each state, the answer is the invariant distribution. It is the equilibrium the chain settles into and then keeps.

There is a beautiful way to build this profile by hand. Fix one home state. Start the chain at home, walk until you come back home, and during that single loop count how many times you stepped on each state. The expected count for each state is the invariant profile (up to an overall scale). The chain restarting fresh at each homecoming is what makes these counts fit together into something the chain preserves.

This construction also reveals a split among chains that always come home. Some come home quickly on average: the expected time for one loop is a finite number. For these the visit-counts add up to a finite total, so you can rescale them into honest probabilities — there is an invariant distribution, and we call the chain positive recurrent. Others always come home but take forever on average: the mean loop time is infinite. Then the counts add up to infinity and no finite rescaling makes them into probabilities. The chain still has an invariant profile of relative heights, but no equilibrium distribution. We call this null recurrent.

The takeaway: an invariant measure is the sand profile a chain leaves unchanged, you can build it from the expected visit-counts in one loop from home, and whether the loop has finite or infinite average length splits "always comes home" into positive recurrent (a real equilibrium exists) and null recurrent (only relative heights exist).

Visual Beginner

Picture one excursion from a home state, with the chain's visits to each other state tallied.

Top: one loop from home state $k$ back to $k$. Counting how many times the path lands on each state during the loop, then averaging over many loops, gives the expected visit-count profile $\gamma$. This profile is invariant: feeding it through one step of the chain returns the same profile. Bottom: when the average loop is short (finite mean return time) the counts have a finite total and rescale into an equilibrium distribution — positive recurrence. When the average loop is infinitely long the counts still form a valid relative profile but their total is infinite, so no equilibrium distribution exists — null recurrence.

Worked example Beginner

Take a chain on three states $\{1,2,3\}$ arranged in a cycle that can also pause. From state $1$ the walk goes to $2$. From state $2$ it goes to $3$. From state $3$ it returns to $1$. Every move is certain. We want the long-run share of time spent in each state, that is, the invariant distribution.

Step 1. Write what "unchanged after one step" means. Let the shares be ${\pi }_1,{\pi }_2,{\pi }_3$. After one step, all of state $1$'s share flows to state $2$, all of state $2$'s flows to state $3$, and all of state $3$'s flows to state $1$. For the profile to stay the same we need the share arriving at each state to equal the share already there: ${\pi }_2={\pi }_1$ (everything at $1$ lands on $2$), ${\pi }_3={\pi }_2$, and ${\pi }_1={\pi }_3$.

Step 2. Solve the balance. These say ${\pi }_1={\pi }_2={\pi }_3$. The three shares are equal.

Step 3. Make them add to one. Three equal numbers summing to $1$ are each $\frac{1}{3}$. So the invariant distribution is ${\pi }_1={\pi }_2={\pi }_3=\frac{1}{3}$.

Step 4. Check against the return-time rule. Starting at state $1$, the walk goes $1\to 2\to 3\to 1$, returning after exactly $3$ steps. So the mean return time to state $1$ is $3$. The promised identity says the equilibrium share equals one divided by the mean return time: $\frac{1}{3}$. This matches ${\pi }_1=\frac{1}{3}$, and by symmetry the same holds for states $2$ and $3$.

What this tells us: the equilibrium share of a state is the reciprocal of how long, on average, the chain takes to come back to it. Here each return takes $3$ steps, so each state holds a $\frac{1}{3}$ share. A finite return time ($3$) is exactly what lets the shares add to one — this chain is positive recurrent.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $(X_n{)}_{n\ge 0}$ is a time-homogeneous Markov chain on a countable state space $I$ with stochastic transition matrix $P=(p_{ij})$, as in 37.05.01; classes, communication, and irreducibility are as in 37.05.02; hitting and return times are as in 37.05.03 and 37.05.04. We write ${\mathbb{P}}_i$, ${\mathbb{E}}_i$ for probability and expectation conditioned on $X_0=i$, and $T_i:=\inf \{n\ge 1:X_n=i\}$ for the first return time to $i$, with return probability $f_{ii}={\mathbb{P}}_i(T_i<\infty )$. A state is recurrent if $f_{ii}=1$ and transient if $f_{ii}<1$, per 37.05.04.

Definition (invariant measure and invariant distribution). A measure on $I$ is a row vector $\nu =({\nu }_i{)}_{i\in I}$ with ${\nu }_i\in [0,\infty )$. It is invariant (or stationary) for $P$ if $$\nu =\nu P,\text{that is}{\nu }_j=\sum _{i\in I}{\nu }_i{p}_{ij}\text{for every }j\in I.$$ An invariant measure is nonzero if ${\nu }_i>0$ for at least one $i$. An invariant measure with total mass ${\sum }_{i\in I}{\nu }_i=1$ is an invariant distribution (or stationary distribution), customarily written $\pi$. If $X_0\sim \pi$ with $\pi$ invariant, then $X_n\sim \pi$ for all $n$, since the law of $X_n$ is $\pi P^n=\pi$.

Definition (excursion / return-time measure). Fix a reference state $k$. The expected occupation measure of an excursion from $k$ is the row vector ${\gamma }^k=({\gamma }_i^k{)}_{i\in I}$ given by $${\gamma }_i^k:={\mathbb{E}}_k\left[\sum _{n=0}^{T_k-1}{1}_{\{X_n=i\}}\right]=\sum _{n\ge 0}{\mathbb{P}}_k(X_n=i,T_k>n),$$ the expected number of visits to $i$ during one excursion from $k$ back to $k$ (counting the time-$0$ visit to $k$, not the terminal return). By construction ${\gamma }_k^k=1$, and ${\sum }_{i\in I}{\gamma }_i^k={\mathbb{E}}_k[T_k]$, the mean return time to $k$.

Definition (positive and null recurrence). A recurrent state $i$ is positive recurrent if its mean return time $m_i:={\mathbb{E}}_i[T_i]$ is finite, and null recurrent if $m_i=\infty$. By the solidarity theorem proved below, this property is constant on a communicating class, so one speaks of a positive recurrent class or a null recurrent class, and of a positive/null recurrent chain when it is irreducible.

The chain on $\{1,2,3\}$ cycling $1\to 2\to 3\to 1$ has ${\mathbb{E}}_i[T_i]=3<\infty$ for each $i$, so it is positive recurrent with $\pi =(\frac{1}{3},\frac{1}{3},\frac{1}{3})$. The simple symmetric random walk on $\mathbb{Z}$ is recurrent (per 37.05.04) but has ${\mathbb{E}}_0[T_0]=\infty$, so it is null recurrent; its invariant measure is the counting measure ${\nu }_i\equiv 1$, which has infinite total mass and admits no normalisation.

Counterexamples to common slips Intermediate+

• An invariant measure need not be normalisable. A nonzero invariant measure $\nu =\nu P$ always exists for an irreducible recurrent chain, but ${\sum }_i{\nu }_i$ may be infinite. Only when this sum is finite (positive recurrence) does an invariant distribution exist. The counting measure on the symmetric walk on $\mathbb{Z}$ is invariant and not normalisable.

• Uniqueness is only up to a scalar, and only under irreducibility. For an irreducible recurrent chain the invariant measure is unique up to multiplication by a positive constant. A reducible chain can have several linearly independent invariant measures, one per recurrent class.

• Recurrence does not by itself give an invariant distribution. Null recurrence is exactly the case where the chain is recurrent yet has no invariant distribution. "Comes home with probability one" and "comes home in finite expected time" are different statements; the second is positive recurrence.

• The excursion sum stops at $T_k-1$, not $T_k$. Including the terminal return would double-count the reference state $k$ and break the invariance identity. The visit at time $T_k$ is the time-$0$ visit of the next excursion.

Key theorem with proof Intermediate+

Theorem (existence, invariance, and the Kac formula). Let $P$ be irreducible and recurrent, and fix a reference state $k$.

(a) (Existence and invariance.) The excursion measure ${\gamma }^k$ defined above is a nonzero invariant measure: $0<{\gamma }_i^k<\infty$ for every $i$, ${\gamma }_k^k=1$, and ${\gamma }^k={\gamma }^{k}P$.

(b) (Uniqueness up to a scalar.) If $\lambda$ is any nonzero invariant measure, then ${\lambda }_i={\lambda }_k{\gamma }_i^k$ for all $i$; hence the invariant measure is unique up to a positive multiplicative constant.

(c) (Kac formula and the positive/null split.) The total mass is ${\sum }_i{\gamma }_i^k={\mathbb{E}}_k[T_k]=m_k$. The chain is positive recurrent (some, hence every, $m_i<\infty$) iff it admits an invariant distribution $\pi$; that distribution is unique and is given by $${\pi }_i=\frac{1}{{\mathbb{E}}_i[T_i]}=\frac{1}{m_i}.$$

Proof. Part (a). Finiteness and positivity: since the chain is irreducible there are $r,s\ge 1$ with $p_{ki}^{(r)}>0$ and $p_{ik}^{(s)}>0$. Counting visits to $i$ in an excursion shows ${\gamma }^k$ dominates a single-step contribution, giving ${\gamma }_i^k>0$; finiteness ${\gamma }_i^k<\infty$ follows once invariance is established together with ${\gamma }_k^k=1$, as we record below. The normalisation ${\gamma }_k^k=1$ holds because in the window $0\le n<T_k$ the chain is at $k$ exactly once, at $n=0$.

Invariance is the heart. Write ${\gamma }_i^k={\sum }_{n\ge 1}{\mathbb{P}}_k(X_n=i,n\le T_k)$, using $X_0=X_{T_k}=k$ to re-index the time-$0$ term of $i=k$ onto the terminal visit at $n=T_k$ (legitimate because ${\mathbb{P}}_k(T_k<\infty )=1$ by recurrence). For any $j$, $$\sum _i{\gamma }_i^k{p}_{ij}=\sum _i\sum _{n\ge 1}{\mathbb{P}}_k(X_n=i,n\le T_k)p_{ij}=\sum _{n\ge 1}\sum _i{\mathbb{P}}_k(X_{n-1}=i,n-1<T_k)p_{ij},$$ where in the last step we used that $\{n\le T_k\}=\{T_k>n-1\}$ is determined by $X_0,\dots ,X_{n-1}$ and applied the Markov property at time $n-1$: on $\{T_k>n-1\}$ the event $\{X_n=j\}$ has conditional probability $p_{X_{n-1}j}$. Summing over $i$ collapses the inner sum to ${\mathbb{P}}_k(X_n=j,n\le T_k)$, so $$\sum _i{\gamma }_i^k{p}_{ij}=\sum _{n\ge 1}{\mathbb{P}}_k(X_n=j,n\le T_k)={\gamma }_j^k.$$ Thus ${\gamma }^{k}P={\gamma }^k$. Finiteness now follows: from ${\gamma }^k={\gamma }^k{P}^s$ and ${\gamma }_k^k=1$ we get ${\gamma }_i^k{p}_{ik}^{(s)}\le {\gamma }_k^k=1$, so ${\gamma }_i^k\le 1/p_{ik}^{(s)}<\infty$ for the $s$ with $p_{ik}^{(s)}>0$.

Part (b). Let $\lambda =\lambda P$ be a nonzero invariant measure. We show ${\lambda }_i\ge {\lambda }_k{\gamma }_i^k$ and then equality. Unfolding $\lambda =\lambda P$ and isolating the reference state $k$, $${\lambda }_j={\lambda }_k{p}_{kj}+\sum _{i\ne k}{\lambda }_i{p}_{ij}.$$ Iterating this identity and tracking the paths that avoid $k$ until the last step reproduces, term by term, the excursion sum: one obtains $${\lambda }_j\ge {\lambda }_k\sum _{n=0}^N{\mathbb{P}}_k(X_n=j,T_k>n)\text{for every }N,$$ and letting $N\to \infty$ gives ${\lambda }_j\ge {\lambda }_k{\gamma }_j^k$. Set $\mu :=\lambda -{\lambda }_k{\gamma }^k$. Then $\mu \ge 0$, $\mu =\mu P$, and ${\mu }_k={\lambda }_k-{\lambda }_k\cdot 1=0$. For any $i$, irreducibility gives $r$ with $p_{ik}^{(r)}>0$, and $0={\mu }_k={\sum }_l{\mu }_l{p}_{lk}^{(r)}\ge {\mu }_i{p}_{ik}^{(r)}\ge 0$ forces ${\mu }_i=0$. Hence $\lambda ={\lambda }_k{\gamma }^k$.

Part (c). Summing invariance over all states is not what gives the mass; rather, by Tonelli, $$\sum _i{\gamma }_i^k=\sum _i{\mathbb{E}}_k\left[\sum _{n=0}^{T_k-1}{1}_{\{X_n=i\}}\right]={\mathbb{E}}_k\left[\sum _{n=0}^{T_k-1}1\right]={\mathbb{E}}_k[T_k]=m_k.$$ If $m_k<\infty$ then $\pi :={\gamma }^k/m_k$ is an invariant distribution. Conversely, if an invariant distribution $\pi$ exists, then by part (b) $\pi ={\pi }_k{\gamma }^k$, so $1={\sum }_i{\pi }_i={\pi }_k{m}_k$, forcing $m_k=1/{\pi }_k<\infty$ and ${\pi }_k=1/m_k$. The same applied at any state $i$ (using ${\gamma }^i$) yields ${\pi }_i=1/m_i$, the Kac formula, and shows $\pi$ is unique. Finiteness of one $m_k$ forces finiteness of all $m_i$ because ${\pi }_i={\pi }_k{\gamma }_i^k>0$ for every $i$. $\square$

Bridge. This theorem builds toward the convergence-to-equilibrium and ergodic theory of the chapter and appears again in every stationary-distribution computation, because it pins the equilibrium of an irreducible chain to a single excursion. The foundational reason an invariant measure exists at all is the strong Markov restart of 37.05.04: each return to $k$ launches an independent excursion, and the expected occupation of one excursion is exactly the quantity the one-step operator preserves. The Kac identity ${\pi }_i=1/m_i$ is exactly the renewal-theoretic statement that the long-run fraction of time at $i$ is the reciprocal mean gap between visits, and it is dual to the hitting-time calculus of 37.05.03, where the mean return time $m_i=1+{\sum }_j{p}_{ij}{k}_j^{\{i\}}$ is computed by first-step analysis; putting these together, the excursion measure and the mean return time are the same object read two ways, and the central insight is that positive recurrence is precisely finiteness of that excursion length. The bridge is that the dichotomy recurrent-versus-transient of 37.05.04 refines into transient / null recurrent / positive recurrent according to whether ${\sum }_n{p}_{ii}^{(n)}$ diverges and whether $m_i$ is finite, and this generalises the finite-state fact that every finite irreducible chain is automatically positive recurrent.

Exercises Intermediate+

Advanced results Master

The excursion measure organises everything: an irreducible recurrent chain has, up to scale, exactly one invariant measure, and the finiteness of its total mass is the sole datum separating positive from null recurrence. The series criterion of 37.05.04, the Kac formula, and the convergence theory are three readings of this one object.

Theorem 1 (existence, uniqueness, and structure of invariant measures). For an irreducible chain: (i) if recurrent, there is a nonzero invariant measure ${\gamma }^k$, unique up to a positive scalar, strictly positive on $I$; (ii) the chain is positive recurrent iff ${\sum }_i{\gamma }_i^k={\mathbb{E}}_k[T_k]<\infty$, in which case there is a unique invariant distribution ${\pi }_i=1/{\mathbb{E}}_i[T_i]$; (iii) if transient there may be no invariant measure, one, or many — uniqueness fails outside recurrence. For a general (reducible) chain, the extreme invariant distributions are in bijection with the positive recurrent classes: each such class $C$ carries one ${\pi }^C$ supported on $C$, and every invariant distribution is a convex combination ${\sum }_C{a}_C{\pi }^C$ with $a_C\ge 0$, ${\sum }_C{a}_C=1$. Transient and null recurrent classes carry no invariant mass.

Theorem 2 (positive recurrence and convergence to equilibrium). If $P$ is irreducible, aperiodic, and positive recurrent with stationary distribution $\pi$, then $p_{ij}^{(n)}\to {\pi }_j$ for all $i,j$, and more generally $\Vert \mu P^n-\pi {\Vert }_{\mathrm{TV}}\to 0$ for every initial distribution $\mu$. If instead the chain is null recurrent (or transient), then $p_{ij}^{(n)}\to 0$ for all $i,j$: there is no limiting distribution. Thus positive recurrence is exactly the regime in which the chain forgets its start and converges to a genuine equilibrium; the proof couples two independent copies, one started at $\mu$ and one at $\pi$, and uses that the meeting time is finite a.s. precisely because the product chain is positive recurrent. Periodicity does not affect existence of $\pi$ but blocks pointwise convergence, replaced by Cesàro convergence $\frac{1}{N}{\sum }_{n<N}{p}_{ij}^{(n)}\to {\pi }_j$.

Theorem 3 (ergodic theorem for Markov chains). Let $P$ be irreducible positive recurrent with stationary $\pi$, and $f:I\to \mathbb{R}$ with ${\sum }_i{\pi }_i|f(i)|<\infty$. Then for any initial distribution, almost surely $$\frac{1}{N}\sum _{n=0}^{N-1}f(X_n)⟶\sum _i{\pi }_{i}f(i)={\mathbb{E}}_{\pi }[f].$$ The proof partitions the trajectory into i.i.d. excursions between successive visits to a fixed state $k$, applies the strong law of large numbers to the excursion-sums of $f$ and to the excursion lengths, and forms the ratio; the limit is ${\mathbb{E}}_k[{\sum }_{n<T_k}f(X_n)]/{\mathbb{E}}_k[T_k]={\sum }_i{\gamma }_i^{k}f(i)/m_k={\sum }_i{\pi }_{i}f(i)$. Taking $f=1_{\{i\}}$ recovers ${\pi }_i=1/m_i$ as the long-run fraction of time at $i$. Null recurrence breaks the theorem: the denominator $m_k=\infty$ sends the time-average of any $\pi$-integrable $f$ to $0$.

Theorem 4 (reversibility and detailed balance). A measure $\nu$ satisfying the detailed-balance equations ${\nu }_i{p}_{ij}={\nu }_j{p}_{ji}$ for all $i,j$ is automatically invariant; the converse fails. For an irreducible chain admitting a reversible measure, the transition operator is self-adjoint on ${\ell }^2(\nu )$, its spectrum is real, and the spectral gap controls the rate of convergence in Theorem 2. Birth-death chains are always reversible, which is why their stationary distributions solve a one-dimensional telescoping recursion ${\pi }_{i+1}={\pi }_i{p}_{i,i+1}/p_{i+1,i}$ rather than the full linear system; positive recurrence of a birth-death chain is then the convergence of the series ${\sum }_i{\prod }_{m\le i}{p}_{m-1,m}/p_{m,m-1}$, the reversible reading of the excursion mass.

Synthesis. The foundational reason the entire long-run theory collapses to one vector is the strong Markov restart of 37.05.04: each return to $k$ launches an independent excursion, so the expected occupation of a single excursion is the object the one-step operator fixes, and uniqueness up to a scalar is the statement that an irreducible recurrent chain has only this one degree of freedom. This is exactly the renewal structure that makes the Kac formula ${\pi }_i=1/m_i$ a tautology of renewal-reward, and it is dual to the hitting-time calculus of 37.05.03: the mean return time $m_i$ computed there by first-step analysis is the total mass of the excursion measure computed here, the same number read as a potential and as an occupation time. Putting these together, the recurrent-versus-transient dichotomy of 37.05.04 refines into a trichotomy — transient (${\sum }_n{p}_{ii}^{(n)}<\infty$), null recurrent (${\sum }_n{p}_{ii}^{(n)}=\infty$ but $m_i=\infty$), positive recurrent ($m_i<\infty$) — and the central insight is that only the third regime supports an equilibrium distribution and convergence to it. The ergodic theorem generalises the elementary ${\pi }_i=1/m_i$ to arbitrary observables, the convergence theorem upgrades it from time-averages to the marginal law under aperiodicity, and reversibility specialises it to a self-adjoint operator whose spectral gap quantifies the rate; across all four the bridge is the single excursion measure, whose finiteness is positive recurrence and whose reciprocal mass is the stationary distribution.

Full proof set Master

Proposition 1 (the excursion measure is invariant). For irreducible recurrent $P$ and fixed $k$, the measure ${\gamma }_i^k={\mathbb{E}}_k[{\sum }_{n=0}^{T_k-1}{1}_{\{X_n=i\}}]$ satisfies ${\gamma }^k={\gamma }^{k}P$, ${\gamma }_k^k=1$, and $0<{\gamma }_i^k<\infty$ for all $i$.

Proof. Write ${\gamma }_i^k={\sum }_{n\ge 1}{\mathbb{P}}_k(X_n=i,n\le T_k)$, using $X_{T_k}=k=X_0$ under ${\mathbb{P}}_k$ (valid as $T_k<\infty$ a.s. by recurrence) to shift the $n=0$ term of the diagonal entry onto $n=T_k$. For any $j$, applying the Markov property at time $n-1$ on the event $\{T_k>n-1\}=\{T_k\ge n\}$, which is ${\mathcal{F}}_{n-1}$-measurable, $$\sum _i{\gamma }_i^k{p}_{ij}=\sum _{n\ge 1}\sum _i{\mathbb{P}}_k(X_{n-1}=i,T_k\ge n)p_{ij}=\sum _{n\ge 1}{\mathbb{P}}_k(X_n=j,T_k\ge n)={\gamma }_j^k.$$ So ${\gamma }^k={\gamma }^{k}P$, hence ${\gamma }^k={\gamma }^k{P}^m$ for all $m$. With ${\gamma }_k^k=1$ (the chain is at $k$ exactly once in $0\le n<T_k$) and irreducibility giving $p_{ik}^{(s)}>0$ for some $s$, $1={\gamma }_k^k\ge {\gamma }_i^k{p}_{ik}^{(s)}$ yields ${\gamma }_i^k\le 1/p_{ik}^{(s)}<\infty$; and ${\gamma }_i^k\ge {\gamma }_k^k{p}_{ki}^{(r)}=p_{ki}^{(r)}>0$ for some $r$ gives strict positivity. $\square$

Proposition 2 (uniqueness up to a scalar). If $P$ is irreducible recurrent and $\lambda \ge 0$ satisfies $\lambda =\lambda P$ with $\lambda \ne 0$, then $\lambda ={\lambda }_k{\gamma }^k$.

Proof. From ${\lambda }_j={\lambda }_k{p}_{kj}+{\sum }_{i\ne k}{\lambda }_i{p}_{ij}$, substitute the same identity into each ${\lambda }_i$ with $i\ne k$ repeatedly. After $N$ substitutions, tracking only the contributions of paths from $k$ that avoid $k$ at intermediate times, $${\lambda }_j\ge {\lambda }_k\sum _{n=0}^N{\mathbb{P}}_k(X_n=j,T_k>n).$$ Let $N\to \infty$: ${\lambda }_j\ge {\lambda }_k{\gamma }_j^k$. Put $\mu =\lambda -{\lambda }_k{\gamma }^k\ge 0$; then $\mu =\mu P$ and ${\mu }_k=0$. For any $i$ pick $r$ with $p_{ik}^{(r)}>0$; then $0={\mu }_k=(\mu P^r{)}_k={\sum }_l{\mu }_l{p}_{lk}^{(r)}\ge {\mu }_i{p}_{ik}^{(r)}$, forcing ${\mu }_i=0$. Hence $\lambda ={\lambda }_k{\gamma }^k$. $\square$

Proposition 3 (Kac formula). For irreducible positive recurrent $P$ the unique invariant distribution is ${\pi }_i=1/{\mathbb{E}}_i[T_i]$.

Proof. By Proposition 1, ${\gamma }^i$ is invariant with ${\gamma }_i^i=1$ and total mass ${\sum }_l{\gamma }_l^i={\mathbb{E}}_i[T_i]=m_i$ (Tonelli, Exercise 4). Positive recurrence gives $m_i<\infty$, so $\pi :={\gamma }^i/m_i$ is an invariant distribution with ${\pi }_i={\gamma }_i^i/m_i=1/m_i$. Uniqueness: any invariant distribution ${\pi }^{\prime }$ is, by Proposition 2 normalised, equal to ${\gamma }^i/({\sum }_l{\gamma }_l^i)=\pi$. $\square$

Proposition 4 (positive recurrence is a class property; finite chains). Positive recurrence is constant on a communicating class, and every finite irreducible chain is positive recurrent.

Proof. On the (closed, irreducible) recurrent class $C$, Proposition 2 gives a unique invariant measure up to scale; its total mass over $C$ is finite or infinite independently of the chosen normalisation, and finiteness is positive recurrence (Proposition 3 produces $\pi$ and $m_l=1/{\pi }_l<\infty$ for all $l\in C$). Hence all states of $C$ share the property. For a finite irreducible chain, recurrence holds and ${\gamma }^k$ has $|I|<\infty$ entries each finite by Proposition 1, so $m_k={\sum }_i{\gamma }_i^k<\infty$: positive recurrent. $\square$

Proposition 5 (ergodic time-average). For irreducible positive recurrent $P$ with stationary $\pi$ and $\pi$-integrable $f$, $\frac{1}{N}{\sum }_{n<N}f(X_n)\to {\mathbb{E}}_{\pi }[f]$ a.s.

Proof. Fix a reference $k$; by recurrence the visit times $0={\tau }_0<{\tau }_1<\cdots$ to $k$ are a.s. finite, and by the strong Markov property 37.05.04 the excursion blocks $W_r:={\sum }_{n={\tau }_{r-1}}^{{\tau }_r-1}f(X_n)$ and lengths $L_r:={\tau }_r-{\tau }_{r-1}$ are i.i.d. for $r\ge 1$ with $\mathbb{E}[L_r]=m_k<\infty$ and $\mathbb{E}[W_r]={\sum }_i{\gamma }_i^{k}f(i)=m_k{\mathbb{E}}_{\pi }[f]$ (finite by $\pi$-integrability and $\pi ={\gamma }^k/m_k$). Writing $S_N={\sum }_{n<N}f(X_n)$ and squeezing $N$ between ${\tau }_R$ and ${\tau }_{R+1}$ where $R=R(N)\to \infty$, the strong law gives $\frac{1}{R}{\sum }_{r\le R}{W}_r\to \mathbb{E}[W_1]$ and $\frac{1}{R}{\sum }_{r\le R}{L}_r\to \mathbb{E}[L_1]$, so $$\frac{S_N}{N}\sim \frac{{\sum }_{r\le R}{W}_r}{{\sum }_{r\le R}{L}_r}\to \frac{\mathbb{E}[W_1]}{\mathbb{E}[L_1]}=\frac{m_k{\mathbb{E}}_{\pi }[f]}{m_k}={\mathbb{E}}_{\pi }[f].\square$$

Proposition 6 (null recurrence kills the marginal limit). If $P$ is irreducible and not positive recurrent (transient or null recurrent), then $p_{ij}^{(n)}\to 0$ for all $i,j$.

Proof. The transient case is the series criterion of 37.05.04: ${\sum }_n{p}_{ij}^{(n)}<\infty$ forces $p_{ij}^{(n)}\to 0$. For null recurrence, suppose toward contradiction that ${\mathrm{limsup}}_n{p}_{i_0{j}_0}^{(n)}=c>0$ along a subsequence. A diagonal/tightness argument extracts a further subsequence along which $p_{ij}^{(n)}\to {\rho }_j$ for all $j$, and $\rho =\rho P$ with $\rho \ne 0$; by Fatou ${\sum }_j{\rho }_j\le 1$. Proposition 2 forces $\rho =c^{\prime }{\gamma }^{j_0}$ for a scalar $c^{\prime }>0$, so ${\sum }_j{\rho }_j=c^{\prime }{m}_{j_0}=\infty$ (null recurrence), contradicting ${\sum }_j{\rho }_j\le 1$. Hence $c=0$ and $p_{ij}^{(n)}\to 0$ for all $i,j$. $\square$

Connections Master

• Hitting probabilities and expected hitting times 37.05.03 supply the mean-return-time side of the Kac formula: the first-step decomposition $m_i={\mathbb{E}}_i[T_i]=1+{\sum }_j{p}_{ij}{k}_j^{\{i\}}$ computes the very quantity whose reciprocal is the stationary mass ${\pi }_i$, so the minimal-nonnegative-solution theory there is the analytic dual of the excursion-occupation theory here, and the gambler's-ruin and birth-death mean times become explicit stationary distributions.

• The strong Markov property and recurrence/transience dichotomy 37.05.04 is refined here from a dichotomy into a trichotomy: its geometric visit law and series criterion ${\sum }_n{p}_{ii}^{(n)}$ separate transient from recurrent, and the excursion decomposition it licenses is exactly what builds the invariant measure ${\gamma }^k$ and splits recurrence into null ($m_i=\infty$) and positive ($m_i<\infty$); every i.i.d.-excursion argument in this unit invokes its restart-at-a-stopping-time identity.

• Class structure, irreducibility, and periodicity 37.05.02 determines where invariant mass can live: invariant distributions are supported on positive recurrent closed classes, one extreme point per class, and aperiodicity (versus the cyclic decomposition into period-$d$ subclasses) is what upgrades the existence of $\pi$ into pointwise convergence $p_{ij}^{(n)}\to {\pi }_j$ rather than mere Cesàro convergence.

• Discrete martingales, stopping times, and optional stopping 37.04.01 underlies the ergodic and convergence theorems: the i.i.d. excursion sums are summed via the strong law, and the coupling proof of convergence to equilibrium runs the product chain until a finite meeting time, an optional-stopping-style argument on the stationary lift of the chain.

Historical & philosophical context Master

The notion of a stationary distribution traces to Andrei Markov's own 1906 study of chains with finitely many states, where the equilibrium vector and convergence to it were established for primitive transition matrices; the extension to countably infinite state spaces, where positive and null recurrence genuinely differ, belongs to the 1930s-1950s. Andrei Kolmogorov classified states into recurrent and transient and, in the recurrent case, into what later authors named positive (his "states with finite mean recurrence time") and null. The clean identity tying the stationary mass to the mean return time, ${\pi }_i=1/{\mathbb{E}}_i[T_i]$, was given its definitive probabilistic form by Mark Kac in 1947 ^{[Kac 1947]}, whose recurrence-time argument exhibits the stationary probability as the reciprocal of the expected first-return time and generalises to the set-version ${\sum }_{i\in A}{\pi }_i{\mathbb{E}}_i[T_A^{+}]=1$.

The excursion construction of the invariant measure ${\gamma }^k$ as expected occupation between returns to a fixed state, and the uniqueness-up-to-a-scalar theorem for irreducible recurrent chains, are the form in which the theory was crystallised in the textbook tradition, presented cleanly by Norris ^{[Norris 1997]} following the renewal-theoretic viewpoint of William Feller and the potential-theoretic synthesis of Kai Lai Chung. The general-state-space lift — Harris recurrence, the existence of a unique invariant $\sigma$-finite measure, and the positive/null split via the finiteness of its total mass — is the program of Meyn and Tweedie ^{[Meyn-Tweedie 2009]}, where the same excursion idea is run off a small set rather than a single point. The boundary example, simple symmetric random walk on $\mathbb{Z}$, sits exactly at the recurrent/null-recurrent edge: recurrent by Pólya, null recurrent because its unique invariant measure is the non-normalisable counting measure, the discrete shadow of translation-invariance with no finite total mass.

Bibliography Master

@book{Norris1997,
  author    = {Norris, James R.},
  title     = {Markov Chains},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@article{Kac1947,
  author  = {Kac, Mark},
  title   = {On the notion of recurrence in discrete stochastic processes},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {53},
  number  = {10},
  year    = {1947},
  pages   = {1002--1010}
}

@book{Durrett2019mc,
  author    = {Durrett, Rick},
  title     = {Probability: Theory and Examples},
  edition   = {5},
  publisher = {Cambridge University Press},
  year      = {2019}
}

@book{LevinPeres2017,
  author    = {Levin, David A. and Peres, Yuval},
  title     = {Markov Chains and Mixing Times},
  edition   = {2},
  publisher = {American Mathematical Society},
  year      = {2017}
}

@book{MeynTweedie2009,
  author    = {Meyn, Sean and Tweedie, Richard L.},
  title     = {Markov Chains and Stochastic Stability},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2009}
}

@article{Markov1906,
  author  = {Markov, Andrei A.},
  title   = {Rasprostranenie zakona bol'shikh chisel na velichiny, zavisyashchie drug ot druga},
  journal = {Izvestiya Fiziko-matematicheskogo obshchestva pri Kazanskom universitete},
  volume  = {15},
  year    = {1906},
  pages   = {135--156}
}