Stationary Markov Chains and Ergodic Limits — Examples

The matrix $P$ is a transition matrix: all four entries are nonnegative because $0<a,b\le 1$, and each row sums to one, $(1-a)+a=1$ and $b+(1-b)=1$.

The chain is irreducible: $P(0,1)=a>0$ and $P(1,0)=b>0$, so $0$ and $1$ communicate in one step each way.

The vector $\pi :=(b\mathrm{/}(a+b),a\mathrm{/}(a+b))$ is a probability vector: $a+b>0$ and both coordinates are positive, with $\frac{b}{a+b}+\frac{a}{a+b}=1$.

The vector $\pi$ is invariant. At state $0$: $(\pi P)(0)=\pi (0)(1-a)+\pi (1)b=\pi (0)-a\pi (0)+b\pi (1)$ and $a\pi (0)=ab\mathrm{/}(a+b)=b\pi (1)$, so this equals $\pi (0)$; at state $1$: $(\pi P)(1)=\pi (0)a+\pi (1)(1-b)=\pi (1)+(a\pi (0)-b\pi (1))=\pi (1)$. Hence $\pi P=\pi$, which is invariance by [F2].

Uniqueness: by [F3] the finite chain has an invariant probability, so by the equivalence [F4] the irreducible chain is positive recurrent, and [F5] then gives that it has exactly one invariant probability.

Combining steps 2.1 and 2.2, the unique stationary law of the chain is $\pi =(b\mathrm{/}(a+b),a\mathrm{/}(a+b))$.

Boundary and scope cases: at $a=b=1$ the matrix is $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, the chain alternates deterministically, $\pi =(1\mathrm{/}2,1\mathrm{/}2)$, and the formula is unaffected by the period; at $a=1$, $b<1$ the matrix has $P(0,1)=1$ and the formula still gives a positive probability vector; if $a$ or $b$ were $0$ the chain would fail to be irreducible and the argument for uniqueness through [F5] would not apply, so the strict positivity of $a$ and $b$ is used exactly in step 1.2; the verification checks both rows of the stationarity equations rather than only the first; and the objects are determined by the two given parameters, so steps 1.1–2.1 are choice-free while the uniqueness argument of step 2.2 spends the axiom [A1] exactly through the AC-carrying suppliers [F4] and [F5], whose statements assume Choice.

The matrix $P$ is a transition matrix: its entries are nonnegative by the hypotheses, and each row sums to one, since row $i$ with $1\le i\le m-1$ has the three entries $q_i,p_i$ and $1-p_i-q_i$, row $0$ has $p_0$ and $1-p_0$, and row $m$ has $q_m$ and $1-q_m$.

Every weight is a positive finite number: $w_0=1$ and each $w_i$ is a finite product of positive ratios $p_j\mathrm{/}{q}_{j+1}$, since all $p_j,q_{j+1}>0$; consequently $W:={\sum }_{k=0}^m{w}_k$ is a finite sum of positive terms, so $0<W<+\mathrm{\infty }$.

Detailed balance holds on every edge: for $0\le i\le m-1$ the recursion gives $w_{i+1}=w_i{p}_i\mathrm{/}{q}_{i+1}$, hence $w_i{p}_i=w_{i+1}{q}_{i+1}$.

Detailed balance holds for every pair of states: if $x,y$ are distinct and non-adjacent then $P(x,y)=P(y,x)=0$ by hypothesis, so both sides vanish; if $x=y$ then both sides equal $w_{x}P(x,x)$; and the remaining case is the adjacent pair of step 2.1.

Define $\pi (i):=w_i\mathrm{/}W$. By step 1.2 each $\pi (i)$ is a finite nonnegative number, and ${\sum }_{i=0}^m\pi (i)=W\mathrm{/}W=1$, so $\pi$ is a probability vector; moreover $\pi (x)P(x,y)=\pi (y)P(y,x)$ for all $x,y$, because step 3.1 multiplies by the common positive factor $1\mathrm{/}W$. Hence $\pi$ is a reversible probability distribution for $P$ in the sense of [F2].

By [F3] the reversible probability distribution $\pi$ satisfies $\pi P=\pi$, so it is a stationary law for the birth-and-death chain.

Boundary and scope cases: for $m=0$ the state space is $\{0\}$, the products over $i$ are empty, $w_0=1$, $\pi (0)=1$ and both the detailed-balance identity and stationarity are trivial, so the formula remains valid when the positivity hypotheses are vacuous; if an interior denominator $q_{i+1}$ vanishes, the displayed recursion is undefined. If some $p_i=0$ but all $q_{i+1}>0$, it still gives finite nonnegative weights, with $w_0=1$, and the same detailed-balance and normalization argument gives a stationary law, possibly with zero masses. Either missing directed edge destroys irreducibility on the full interval, but strict positivity of both directions is needed only for positive weights in step 1.2, not for the recursion identity when all denominators are positive; the holding probabilities $P(i,i)$ never enter the detailed-balance identities; the finite sum $W$ is legitimately inverted, and no normalization of an infinite measure is attempted, so the countable birth-and-death case requires a separate summability hypothesis and is not claimed here; and no choice principle is used, all quantities being determined by the finite data.

Every vertex has ${\mathrm{deg}}_G(v)\ge 1$: if some $v$ had ${\mathrm{deg}}_G(v)=0$ then, by [F2], $v$ is adjacent to no vertex; if $\mathrm{\mid }V\mathrm{\mid }=1$ then $E=\mathrm{\varnothing }$ by [F1], contradicting $\mathrm{\mid }E\mathrm{\mid }\ge 1$, and if $\mathrm{\mid }V\mathrm{\mid }\ge 2$ then $v$ cannot be joined to any other vertex by a walk, contradicting connectedness. Hence $P$ is well defined and $P(v,w)\ge 0$ for all $v,w$.

The rows of $P$ sum to one: ${\sum }_{w\in V}P(v,w)=\mathrm{\mid }{N}_G(v)\mathrm{\mid }\mathrm{/}{\mathrm{deg}}_G(v)=1$ for every $v$, since the only nonzero entries are over the neighbors and $P(v,v)=0$ because there are no loops; thus $P$ is a transition matrix.

The measure $\pi (v):={\mathrm{deg}}_G(v)\mathrm{/}(2\mathrm{\mid }E\mathrm{\mid })$ is a probability vector: it is nonnegative, ${\sum }_{v\in V}\pi (v)=\frac{1}{2\mathrm{\mid }E\mathrm{\mid }}{\sum }_v{\mathrm{deg}}_G(v)=1$ by [F3], and $2\mathrm{\mid }E\mathrm{\mid }\ge 2>0$; moreover $\pi (v)>0$ for every $v$ by step 1.1, so $\pi$ is finite-valued on the finite set $V$.

Detailed balance holds. If $\{v,w\}\in E$ then $\pi (v)P(v,w)=\frac{{\mathrm{deg}}_G(v)}{2\mathrm{\mid }E\mathrm{\mid }}\cdot \frac{1}{{\mathrm{deg}}_G(v)}=\frac{1}{2\mathrm{\mid }E\mathrm{\mid }}$ and likewise $\pi (w)P(w,v)=\frac{1}{2\mathrm{\mid }E\mathrm{\mid }}$, using ${\mathrm{deg}}_G(v),{\mathrm{deg}}_G(w)>0$; if $v\mathrm{\ne }w$ and $\{v,w\}\mathrm{\notin }E$ then $P(v,w)=P(w,v)=0$ so both sides vanish; and for $v=w$ both sides are $\pi (v)P(v,v)=0$ since $P(v,v)=0$.

By [F4] the identity of step 3.1 makes $\pi$ a reversible probability distribution for $P$, and [F5] then gives $\pi P=\pi$, so $\pi$ is invariant.

Boundary and scope cases: the one-vertex edgeless graph is excluded because then $\mathrm{\mid }E\mathrm{\mid }=0$, the normalizer $2\mathrm{\mid }E\mathrm{\mid }$ vanishes and the displayed transition row would divide by the degree $0$; a graph with several connected components is not covered by the connectivity hypothesis, although the same computation applies to each component containing an edge, with its own positive degree normalizer. An isolated-vertex component has degree zero, so neither displayed formula defines a walk or probability there; a separate absorbing-row convention would give its point mass as a reversible law; the walk has no holding probability, so $P(v,v)=0$ and the diagonal detailed-balance identity is $0=0$; irreducibility of the walk follows from connectedness but is not needed for reversibility; and no choice principle is used, all objects being determined by the finite graph.

Define $\pi (x):=1\mathrm{/}n$ for $x\in E$. Since $n\ge 1$, each entry satisfies $\pi (x)\ge 0$ and ${\sum }_{x\in E}\pi (x)=n\cdot \frac{1}{n}=1$, so $\pi$ is a probability vector.

For every $y\in E$, $(\pi p)(y)={\sum }_{x\in E}\pi (x)p(x,y)=\frac{1}{n}{\sum }_{x\in E}p(x,y)=\frac{1}{n}\cdot 1=\frac{1}{n}=\pi (y)$, where the second equality factors the finite constant $\frac{1}{n}$ out of a finite sum and the third is the column-sum hypothesis.

By [F2] the identity of step 1.2 says exactly that $\pi$ is an invariant probability vector, i.e. a stationary distribution for $p$.

Irreducibility is not used: the identity matrix on a finite $E$ with $n\ge 2$ is doubly stochastic, has $\pi (x)=1\mathrm{/}n$ invariant by step 1.2, and is reducible, so the hypothesis cannot be weakened to a uniqueness statement; the uniform law is one invariant law among possibly several, and for $n=1$ it is the only one since $p(1,1)=1$.

Let $f:={\mathbf{1}}_{\{y\}}$. Then $0\le f\le 1$ and ${\sum }_{z\in E}\pi (z)\mathrm{\mid }f(z)\mathrm{\mid }=\pi (y)\le 1<+\mathrm{\infty }$, so the ergodic theorem [F2] applies to $f$ and the fixed starting state $x$; for every $n\ge 1$ and every path, ${\sum }_{k=0}^{n-1}{\mathbf{1}}_{\{X_k=y\}}=\mathrm{\#}\{0\le k<n:X_k=y\}$ by the definition of the counting notation.

For every $k\ge 0$, ${\mathbb{E}}_x[{\mathbf{1}}_{\{X_k=y\}}]={\mathbb{P}}_x(X_k=y)=K^k(x,\{y\})=p^{(k)}(x,y)$: the second equality is the $m=0$ case of [F4] applied to the singleton event $\{y\}$, and the third is [F6].

Dividing the identity of step 1.1 by $n\ge 1$ and applying the almost-sure conclusion of [F2] to $f$ gives $\frac{1}{n}\mathrm{\#}\{0\le k<n:X_k=y\}=\frac{1}{n}{\sum }_{k=0}^{n-1}f(X_k)\to {\sum }_z\pi (z)f(z)=\pi (y)$ almost surely under ${\mathbb{P}}_x$, which is the first displayed assertion.

Expectation by linearity: ${\mathbb{E}}_x[\frac{1}{n}\mathrm{\#}\{0\le k<n:X_k=y\}]=\frac{1}{n}{\sum }_{k=0}^{n-1}{\mathbb{E}}_x[{\mathbf{1}}_{\{X_k=y\}}]=\frac{1}{n}{\sum }_{k=0}^{n-1}{p}^{(k)}(x,y)$, and [F3] makes this tend to $\pi (y)$, which is the second displayed assertion.

Consistency by bounded convergence: the averages of step 2.1 are measurable, converge ${\mathbb{P}}_x$-almost everywhere to the constant $\pi (y)$, and satisfy $0\le \frac{1}{n}\mathrm{\#}\{0\le k<n:X_k=y\}\le 1$ for every $n\ge 1$; since ${\mathbb{P}}_x$ is a probability measure, [F5] gives ${\mathbb{E}}_x[\frac{1}{n}\mathrm{\#}\{0\le k<n:X_k=y\}]\to \pi (y)$, the same limit as in step 2.2, and the two expressions for the expectation agree term by term by step 1.2.

The averages are formed for $n\ge 1$. For the periodic two-cycle started at $0$ with $y=0$, the frequency is $\lceil n\mathrm{/}2\rceil \mathrm{/}n$, which tends to $1\mathrm{/}2$ despite periodicity. The indicator remains bounded and integrable on an infinite state space; the almost-sure and expectation limits were proved separately in steps 2.1 and 2.2. AC [A1] enters through [F2]–[F4].

The matrix $p$ is a transition matrix: both entries of each row are $0$ or $1$ and each row sums to one. Multiplying once, $p^2=I$, so by [F2] an induction gives $p^{(2m)}=I$ and $p^{(2m+1)}=p$ for every $m\ge 0$; in particular $p^{(n)}(0,0)=1$ for even $n$ and $p^{(n)}(0,0)=0$ for odd $n\ge 1$, while $p^{(n)}(0,\cdot )={\delta }_0$ for even $n$ and ${\delta }_1$ for odd $n$.

The chain is irreducible: $p(0,1)=1>0$ and $p(1,0)=1>0$ by step 1.1, so $0\to 1$ and $1\to 0$, and each state is accessible from itself with a zero-step path; by [F3] every pair communicates.

The law $\pi$ is invariant: ${\sum }_x\pi (x)p(x,0)=\pi (1)p(1,0)=\frac{1}{2}=\pi (0)$ and ${\sum }_x\pi (x)p(x,1)=\pi (0)p(0,1)=\frac{1}{2}=\pi (1)$, which is the criterion of [F4].

Ordinary convergence fails at the level of a single transition probability: by step 1.1 the diagonal sequence $p^{(n)}(0,0)$ equals $1$ at even $n$ and $0$ at odd $n$, so it alternates and does not converge as $n\to \mathrm{\infty }$; correspondingly the laws $p^{(n)}(0,\cdot )$ alternate between the two point masses ${\delta }_0$ and ${\delta }_1$ and do not converge.

Positive recurrence: the chain is irreducible by step 2.1 and has the invariant probability $\pi$ by step 2.2, so [F6] gives that every state is positive recurrent; in particular the hypotheses of the Cesàro supplier [F8] are met.

The chain is not aperiodic: by step 1.1 the positive return set of [F5] is $R_0=\{2,4,6,\dots \}$, whose greatest common divisor is $2$, so $d(0)=2$; the periods agree on the irreducible chain by [F7], so $\mathrm{per}(p)=2\mathrm{\ne }1$ and $p$ is not aperiodic.

Cesàro convergence: step 1.1 gives $p^{(k)}=I$ for even $k$ and $p^{(k)}=p$ for odd $k$, so for even $n=2m$ the average is $\frac{1}{2m}{\sum }_{k=0}^{2m-1}{p}^{(k)}=\frac{1}{2m}m(I+p)=\frac{1}{2}(I+p)$, and for odd $n=2m+1$ it is $\frac{m(I+p)+I}{2m+1}\to \frac{1}{2}(I+p)$; the matrix $\frac{1}{2}(I+p)$ has both rows equal to $(1\mathrm{/}2,1\mathrm{/}2)=\pi$. Hence $\frac{1}{n}{\sum }_{k=0}^{n-1}{p}^{(k)}(x,\cdot )\to \pi$ for each starting state $x$, which is the displayed Cesàro assertion; since the chain is irreducible and positive recurrent with invariant $\pi$ by steps 2.1, 2.2 and 3.1, this is exactly the conclusion of the general supplier [F8].

Boundary and scope cases: the identity at $n=0$ is included and is consistent with $p^{(0)}(0,0)=1$, so the alternation starts with the value $1$; the two-state chain is the smallest deterministic cycle and the period is exactly two, so the example exhibits the necessity of aperiodicity rather than a failure of irreducibility or of existence of $\pi$; the Cesàro average equals $\pi$ exactly for every even $n$ and converges otherwise, so no aperiodicity is needed for the averaged statement, and the example claims no converse implication in the other direction; the state space is finite, all sums are finite, and no limit is interchanged with an infinite sum; the two hypotheses needed by [F8], irreducibility and positive recurrence, are verified at steps 2.1 and 3.1 and the invariant law at step 2.2, while the matrices themselves are determined by the fixed data; and AC [A1] is spent exactly on the general suppliers [F6] and [F8], the direct computations of steps 1.1–4.1 being choice-free.

The walk is irreducible: for $z,w\in \mathbb{Z}$ with $m=w-z$, following the $\mathrm{\mid }m\mathrm{\mid }$ nearest-neighbor steps from $z$ toward $w$ has probability $2^{-\mathrm{\mid }m\mathrm{\mid }}>0$, so $p^{(\mathrm{\mid }m\mathrm{\mid })}(z,w)>0$; hence every pair of states communicates in the sense of [F3].

By [F2] every state $k$ is recurrent, ${\mathbb{P}}_k(T_k^{+}<\mathrm{\infty })=1$.

Suppose $\pi$ is an invariant probability. By [F5], $2\pi (k)=\pi (k-1)+\pi (k+1)$ for every $k\in \mathbb{Z}$; rearranging gives $\pi (k+1)-\pi (k)=\pi (k)-\pi (k-1)$ for every $k$, so the successive difference $c:=\pi (k+1)-\pi (k)$ is the same real number for all $k$.

If $c>0$ then $\pi (k)=\pi (0)+kc\to +\mathrm{\infty }$, so the nonnegative series ${\sum }_k\pi (k)$ diverges, contradicting ${\sum }_k\pi (k)=1$; if $c<0$ then $\pi (k)\to +\mathrm{\infty }$ as $k\to -\mathrm{\infty }$ along nonpositive indices, contradicting $\pi (k)\le 1$, which follows from $\pi$ being a probability; hence $c=0$ and $\pi$ is constant on $\mathbb{Z}$.

A constant probability mass on the countably infinite set $\mathbb{Z}$ sums to $0$ when the constant is $0$ and diverges otherwise, so it cannot satisfy ${\sum }_k\pi (k)=1$; this contradicts the assumed invariant probability, so the walk admits no invariant probability distribution.

Steps 1.3–3.1 derive nonexistence of an invariant probability from the finite-row stationarity equation and summability; this calculation does not assume recurrence.

By steps 1.1–1.2 the chain is irreducible and recurrent, and by step 3.1 it has no invariant probability; the equivalence [F4] then rules out positive recurrence of every state, so each recurrent state $k$ satisfies ${\mathbb{E}}_k{T}_k^{+}=+\mathrm{\infty }$ and is null recurrent by [F6].

Step 3.1 reaches a contradiction from the assumed probability $\pi$, so no other constructed object requires a well-definedness check; the stationarity equation used in step 1.3 is a finite row computation.

AC [A1] is used exactly at the AC-qualified supplier applications in steps 1.2 and 4.2; the difference calculation in step 1.3 uses no Choice.

The identity matrix $P=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$ is a transition matrix, and $\pi$ is invariant: $(\pi P)(0)=\pi (0)\cdot 1=1\mathrm{/}2=\pi (0)$ and likewise at $1$, which is exactly the identity of [F2].

The event $A:=\{z\in E^{{\mathbb{N}}_0}:z_n=0\text{ for infinitely many }n\}={\bigcap }_{m\ge 0}{\bigcup }_{n\ge m}\{z:z_n=0\}$ is a countable Boolean combination of coordinate events and is therefore measurable.

Both states are absorbing, so $X_n=X_0$ for every $n\ge 0$; hence every finite-dimensional law of $X$ is the law of the constant tuple $(X_0,\dots ,X_0)$, which is unchanged by any nonnegative time shift, and the chain is strictly stationary in the sense of [F3]. Its canonical path law is ${\mathbb{P}}_{\pi }=\frac{1}{2}{\delta }_{\bar{0}}+\frac{1}{2}{\delta }_{\bar{1}}$, where $\bar{0}=(0,0,0,\dots )$ and $\bar{1}=(1,1,1,\dots )$.

The event $A$ is strictly shift-invariant: ${\theta }^{-1}A=\{z:\theta z\in A\}=\{z:z_{n+1}=0$ for infinitely many $n\}=A$, because deleting the first coordinate of a sequence does not change whether infinitely many of its entries vanish.

The left shift preserves ${\mathbb{P}}_{\pi }$: by step 2.1 the path law is supported on the two fixed paths $\bar{0},\bar{1}$, and $\theta \bar{0}=\bar{0}$, $\theta \bar{1}=\bar{1}$, so ${\mathbb{P}}_{\pi }({\theta }^{-1}B)={\mathbb{P}}_{\pi }(B)$ for every measurable $B$.

Evaluating at $A$: $\bar{0}\in A$ and $\bar{1}\mathrm{\notin }A$, so ${\mathbb{P}}_{\pi }(A)=\frac{1}{2}$, and by step 2.2 this is the measure of a strictly invariant event; since $\frac{1}{2}\mathrm{\notin }\{0,1\}$, [F4] shows that the canonical shift is not ergodic, even though ${\mathbb{P}}_{\pi }$ is shift-invariant by step 3.1.

Boundary and axiom cases: the event $A$ is strictly invariant, not merely invariant modulo null sets, and step 2.2 verifies the identity on the whole path space; the value $1\mathrm{/}2$ is neither $0$ nor $1$, so the criterion of [F4] genuinely fails; $A^c$ and the events "infinitely many ones" behave the same way; if $\pi$ were concentrated on $0$ or on $1$ the chain would be ergodic, so the mixture is essential; the chain is reducible with two communicating classes $\{0\}$ and $\{1\}$, which is exactly why the ergodicity result for irreducible chains does not apply; the explicit description of ${\mathbb{P}}_{\pi }$ in step 2.1 makes no selection and no choice principle is used; and no convergence claim is made, the example refuting only the implication "stationary $\Rightarrow$ ergodic".