Stationary Markov Chains and Ergodic Limits

For every $m\ge 0$ one has $\pi K^m=\pi$ as probability measures: for $m=0$ this is $\pi K^0=\pi I=\pi$, and if $\pi K^m=\pi$ then associativity of iterated kernel composition gives $\pi K^{m+1}=(\pi K^m)K=\pi K=\pi$ by [F1].

For fixed $m$ the family ${\mathcal{D}}_m:=\{B\in {\mathcal{E}}^{\otimes {\mathbb{N}}_0}:{\mathbb{P}}_X({\theta }^{-m}B)={\mathbb{P}}_X(B)\}$ is a lambda-system: it contains $E^{{\mathbb{N}}_0}$, and ${\theta }^{-m}(B^c)=({\theta }^{-m}B{)}^c$ together with ${\theta }^{-m}\left({\bigcup }_l{B}_l\right)={\bigcup }_l{\theta }^{-m}{B}_l$ for pairwise disjoint families give closure under complements and disjoint countable unions by additivity of the probability measure ${\mathbb{P}}_X$ of [F6].

Fix $m\ge 0$, times $0\le n_0<\cdots <n_r$ and bounded measurable $f_0,\dots ,f_r$. [F3] applied to the shifted tuple $(m+n_0,\dots ,m+n_r)$, whose successive gaps are again $n_1-n_0,\dots ,n_r-n_{r-1}$, expresses $\mathbb{E}{\prod }_{j=0}^r{f}_j(X_{m+n_j})$ as ${\int }_E\pi (dx){\int }_E{K}^{m+n_0}(x,d{x}_0)f_0(x_0){\prod }_{j=1}^r{\int }_E{K}^{n_j-n_{j-1}}(x_{j-1},d{x}_j)f_j(x_j)$, while [F3] applied to $(n_0,\dots ,n_r)$ gives the same expression with $K^{n_0}$ in place of $K^{m+n_0}$; associativity [F4] gives $K^{m+n_0}=K^m{K}^{n_0}$, so step 1.1 gives $\pi K^{m+n_0}=(\pi K^m)K^{n_0}=\pi K^{n_0}$, the two outermost integrals over $\pi$ coincide, and all remaining factors are identical.

Taking $f_j={\mathbf{1}}_{A_j}$ in step 2.1 shows $\mathbb{P}(X_{m+n_j}\in A_j,0\le j\le r)=\mathbb{P}(X_{n_j}\in A_j,0\le j\le r)$ for all measurable $A_0,\dots ,A_r$; measurable rectangles form a pi-system generating ${\mathcal{E}}^{\otimes (r+1)}$, and by [F5] two probability measures agreeing on it agree on the whole product sigma-algebra, so $\mathcal{L}(X_{m+n_0},\dots ,X_{m+n_r})=\mathcal{L}(X_{n_0},\dots ,X_{n_r})$, which is the asserted shift invariance of every finite-dimensional law.

Let ${\mathbb{P}}_X:=\mathcal{L}((X_n{)}_{n\ge 0})$ be the canonical path law on $(E^{{\mathbb{N}}_0},{\mathcal{E}}^{\otimes {\mathbb{N}}_0})$ [F6], and fix $m\ge 0$; for the cylinder $C=\{z:z_{n_j}\in A_j,0\le j\le r\}$ one has ${\theta }^{-m}C=\{z:(z_{m+n_j}{)}_j\in {\prod }_j{A}_j\}$, so step 3.1 gives ${\mathbb{P}}_X({\theta }^{-m}C)=\mathbb{P}(X_{m+n_j}\in A_j\text{ for all }j)=\mathbb{P}(X_{n_j}\in A_j\text{ for all }j)={\mathbb{P}}_X(C)$.

By step 4.1 the family ${\mathcal{D}}_m$ contains every finite-dimensional cylinder, and cylinders form a pi-system generating ${\mathcal{E}}^{\otimes {\mathbb{N}}_0}$, so [F5] gives ${\mathcal{D}}_m={\mathcal{E}}^{\otimes {\mathbb{N}}_0}$; hence ${\mathbb{P}}_X({\theta }^{-m}B)={\mathbb{P}}_X(B)$ for every measurable $B$, and for $m=1$ the left shift preserves the canonical path law.

Boundary and axiom cases: if $E$ is a singleton the canonical path law is the point mass at the constant path and every shift preserves it; if $r=1$ and $m=0$ the identities in steps 2.1–3.1 are trivial; the equivalence between the finite-dimensional and canonical formulations is proved in both directions, steps 1.1–3.1 giving the finite-dimensional statement and steps 4.1–5.1 the path-space statement; and AC [A1] enters exactly through the finite-dimensional-law supplier [F3], whose statement itself assumes Choice, while the induction, the rectangle comparison and the lambda-system computation are ordinary measure-theoretic algebra.

Fix the state $x_1$ and let $\mu$ be its point mass. For every $N\ge 1$ define the row vector ${\nu }_N:=\frac{1}{N}{\sum }_{k=0}^{N-1}\mu p^{(k)},$ where $p^{(k)}$ is the $k$-th matrix power. Its entries are finite nonnegative sums of products of the entries of $p$, hence ${\nu }_N(y)\in [0,1]$ for every $y\in E$; and using [F1] twice, ${\sum }_{y\in E}{\nu }_N(y)=\frac{1}{N}{\sum }_{k=0}^{N-1}{\sum }_{y\in E}\mu p^{(k)}(y)=\frac{1}{N}{\sum }_{k=0}^{N-1}1=1$, since a point mass is a probability vector and rows of every $p^{(k)}$ sum to one. So every ${\nu }_N$ lies in $S:=\{\rho :E\to [0,1]:{\sum }_y\rho (y)=1\}$.

For every $N\ge 1$ the exact telescoping identity ${\nu }_{N}p-{\nu }_N=\frac{1}{N}{\sum }_{k=0}^{N-1}(\mu p^{(k+1)}-\mu p^{(k)})=\frac{1}{N}(\mu p^{(N)}-\mu )$ holds coordinatewise as an identity of finite real sums, its entries being differences of numbers in $[0,1]$, so no infinite sum is rearranged.

There is a strictly increasing sequence $N_j$ and a vector $\pi :E\to [0,1]$ such that ${\nu }_{N_j}(y)\to \pi (y)$ for every $y\in E$. Enumerate $E=\{x_1,\dots ,x_n\}$ and argue by induction on the number $i$ of coordinates already handled: the $i$-th coordinate sequence along the subsequence produced so far is bounded in $[0,1]$, so [F3] supplies a further strictly increasing subsequence on which it converges; after finitely many successive subsequence choices, every coordinate converges. Finite induction on these existential choices requires no choice axiom.

Consequently ${\nu }_{N}p-{\nu }_N\to 0$ coordinatewise as $N\to \mathrm{\infty }$: each entry of $\frac{1}{N}(\mu p^{(N)}-\mu )$ has absolute value at most $\frac{2}{N}$, since every entry of $\mu p^{(N)}$ and of $\mu$ lies in $[0,1]$.

The limit $\pi$ is a probability vector: $\pi (y)\ge 0$ for every $y$ because a limit of nonnegative numbers is nonnegative; and ${\sum }_{y\in E}\pi (y)=1$ because a finite sum of convergent sequences converges to the sum of the limits, applied to the constant sums $1$ from step 2.1 and step 1.1.

Passing to the subsequence of step 2.1, ${\nu }_{N_j}\to \pi$ coordinatewise and hence ${\nu }_{N_j}p\to \pi p$ coordinatewise, because each entry of the finite matrix product is a finite sum ${\sum }_{y\in E}{\nu }_{N_j}(y)p(y,z)$ of finitely many convergent sequences. By step 2.2 the left side of ${\nu }_{N}p-{\nu }_N$ tends to $0$ along $N_j$, so $\pi p-\pi =0$, that is, $\pi p=\pi$.

By step 3.1, $\pi$ is a probability vector and by step 3.2 it satisfies $\pi p=\pi$; [F2] then identifies it as an invariant probability distribution for $p$. The state space was required nonempty so that $x_1$ exists; the empty matrix has no probability vector, so $E=\mathrm{\varnothing }$ is excluded by the hypothesis. If $n=1$, then $p(x_1,x_1)=1$ and $\pi ={\delta }_{x_1}$ is invariant, consistent with the construction. The argument uses only finite enumerations, finite sums and the subsequence theorem; no irreducibility, aperiodicity, recurrence, product-space path law or choice principle is used, and the conclusion is a one-way existence assertion rather than an equivalence.

Define the survival masses ${\alpha }_n(y):={\mathbb{P}}_b(X_n=y,T_b^{+}>n)$ for $n\ge 0$, $y\in E$. For $n\ge 1$, $T_b^{+}>n$ requires $X_1,\dots ,X_n$ all to avoid $b$, so ${\alpha }_n(y)={\mathbb{P}}_b(X_1\mathrm{\ne }b,\dots ,X_n\mathrm{\ne }b,X_n=y)$ and in particular ${\alpha }_n(b)=0$. At $n=0$ the avoidance condition is empty, and [F3] with initial law ${\delta }_b$ gives $X_0=b$ almost surely, so ${\alpha }_0(b)=1$ and ${\alpha }_0(y)=0$ for $y\mathrm{\ne }b$.

For every $y$ we have ${\mu }_b(y)={\sum }_{n\ge 0}{\alpha }_n(y)$: by the monotone convergence theorem [F5] applied to the partial sums of the nonnegative terms ${\mathbf{1}}_{\{X_n=y\}}{\mathbf{1}}_{\{n<T_b^{+}\}}$, the expectation of the series is the series of the expectations ${\mathbb{P}}_b(X_n=y,T_b^{+}>n)={\alpha }_n(y)$.

Put $Q(x,y):=p(x,y){\mathbf{1}}_{\{y\mathrm{\ne }b\}}$. A nonnegative $\nu$ satisfies $\nu (b)=1$ and $\nu (y)={\sum }_x\nu (x)p(x,y)$ for all $y\mathrm{\ne }b$ if and only if $\nu ={\delta }_b+\nu Q$ as extended nonnegative functions, because at $y=b$ the right side is $1+0=\nu (b)$ and at $y\mathrm{\ne }b$ it is $(\nu p)(y)$.

If $E=\mathrm{\varnothing }$ there is no starting state $b$, so the hypotheses cannot be met.

If $b$ is absorbing, the finite-dimensional law [F3] and the initial law ${\delta }_b$ imply $X_n=b$ almost surely for every $n\ge 0$; hence $T_b^{+}=1$ by [F1].

The absorbing path of step 1.5 has exactly one occupation before $T_b^{+}$, at time $0$, so ${\mu }_b={\delta }_b$, ${\sum }_y{\mu }_b(y)=1={\mathbb{E}}_b{T}_b^{+}$.

For every $n\ge 0$ and $y\mathrm{\ne }b$ the recursion ${\alpha }_{n+1}(y)={\sum }_{x\in E}{\alpha }_n(x)p(x,y)$ holds. Since $y\mathrm{\ne }b$, the event $\{T_b^{+}>n,X_{n+1}=y\}$ equals $\{T_b^{+}>n+1,X_{n+1}=y\}$. Partition the first event by $X_n=x$: the cylinder formula [F3] gives ${\mathbb{P}}_b(T_b^{+}>n,X_n=x,X_{n+1}=y)={\alpha }_n(x)p(x,y)$ for each $x$, and countable additivity gives the displayed sum. At $n=0$ only $x=b$ contributes, with mass $p(b,y)$; for $n\ge 1$, the $x=b$ term is zero by step 1.1.

${\mu }_b(b)=1$ by steps 1.1 and 1.2, since the series for ${\mu }_b(b)$ has the single nonzero term ${\alpha }_0(b)=1$.

${\sum }_{y\in E}{\mu }_b(y)={\mathbb{E}}_b{T}_b^{+}$: for every outcome the sum ${\sum }_{y\in E}{\mathbf{1}}_{\{X_n=y\}}$ equals one exactly for the $T_b^{+}$ indices $n<T_b^{+}$, so both sides equal the expectation of ${\sum }_{n\ge 0}{\mathbf{1}}_{\{n<T_b^{+}\}}$; applying [F4] to the nonnegative double sequence ${\mathbb{P}}_b(X_n=y,n<T_b^{+})$ interchanges the sums over $y$ and $n$, [F5] identifies ${\sum }_n{\mathbb{P}}_b(T_b^{+}>n)$ with ${\mathbb{E}}_b{T}_b^{+}$ by the indicator tail identity, and infinite values are allowed on both sides.

For every $n\ge 0$, using the survival-mass definition in step 1.1, the last-step factorization [F3] gives ${\sum }_{x\in E}{\alpha }_n(x)p(x,b)={\mathbb{P}}_b(X_{n+1}=b,T_b^{+}>n)={\mathbb{P}}_b(T_b^{+}=n+1)$, since $T_b^{+}>n$ rules out an earlier return and $X_{n+1}=b$ makes the next time the first return.

Since $b$ is absorbing, $p(b,b)=1$; with ${\mu }_b={\delta }_b$ from step 2.1 and the matrix convention [F2], $({\mu }_{b}p)(b)=1$. Thus the absorbing case satisfies the occupation-mass, return-time, and return-flow identities.

Interchanging the nonnegative sums by [F4] and using step 1.2 gives $({\mu }_{b}p)(b)={\sum }_{x\in E}{\mu }_b(x)p(x,b)={\sum }_{n\ge 0}{\mathbb{P}}_b(T_b^{+}=n+1)={\mathbb{P}}_b(T_b^{+}<\mathrm{\infty })$, since the positive finite return times partition $\{T_b^{+}<\mathrm{\infty }\}$.

For $y\mathrm{\ne }b$, ${\mu }_b(y)={\sum }_{x\in E}{\mu }_b(x)p(x,y)$: by step 1.2, [F4] applied to the nonnegative terms ${\alpha }_n(x)p(x,y)$, and step 2.2, ${\sum }_{x\in E}{\mu }_b(x)p(x,y)={\sum }_{n\ge 0}{\sum }_{x\in E}{\alpha }_n(x)p(x,y)={\sum }_{n\ge 0}{\alpha }_{n+1}(y)={\mu }_b(y)-{\alpha }_0(y)={\mu }_b(y),$ the last step because ${\alpha }_0(y)=0$ for $y\mathrm{\ne }b$.

For such $\nu$ and every $N\ge 1$, $\nu ={\sum }_{n<N}{\delta }_b{Q}^n+\nu Q^N$, where $Q^n$ are powers of the substochastic matrix $Q$. Induct on $N$ from step 1.3; each reassociation of the countable nonnegative matrix sums is justified by [F4]. By step 2.2 and the zero $b$-coordinate in step 1.1, ${\alpha }_n={\delta }_b{Q}^n$ with ${\alpha }_0={\delta }_b$, so the first sum is the $N$th partial sum of the series in step 1.2.

The time-$0$ term contributes ${\mu }_b(b)=1$ although no return has occurred, since the occupation sum starts at $n=0$ while the return time is strictly positive.

If $b$ is transient then $({\mu }_{b}p)(b)={\mathbb{P}}_b(T_b^{+}<\mathrm{\infty })<1$ by step 3.2, so item 4 genuinely uses recurrence; item 3's minimality inequality remains valid.

Letting $N\to \mathrm{\infty }$ in step 3.4 gives $\nu (y)\ge {\sup }_{N\ge 1}{\sum }_{n<N}{\alpha }_n(y)={\mu }_b(y)$ for every $y$, since the remainder $\nu Q^N(y)$ is nonnegative and a nonnegative series is the supremum of its partial sums; this is the asserted pointwise minimality.

If $b$ is recurrent then ${\mathbb{P}}_b(T_b^{+}<\mathrm{\infty })=1$, so $({\mu }_{b}p)(b)=1={\mu }_b(b)$ by steps 2.3 and 3.2, while step 3.3 gives equality at every $y\mathrm{\ne }b$; hence ${\mu }_{b}p={\mu }_b$.

AC [A1] is used through the finite-dimensional-law supplier [F3]; once that chain law is supplied, the recursion and nonnegative summations are finite-time or Tonelli/monotone-convergence calculations with no further choice. The pointwise minimality assertion is one-way, not an if-and-only-if.

For every $n\ge 0$ one has $\pi p^{(n)}=\pi$ whenever $\pi$ is an invariant probability, where $(\pi p^{(n)})(y):={\sum }_{x\in E}\pi (x)p^{(n)}(x,y)$: the case $n=0$ is $p^{(0)}(x,y)={\mathbf{1}}_{\{x=y\}}$, and if $\pi p^{(n)}=\pi$, then $(\pi p^{(n+1)})(y)={\sum }_x\pi (x){\sum }_z{p}^{(n)}(x,z)p(z,y)={\sum }_z({\sum }_x\pi (x)p^{(n)}(x,z))p(z,y)={\sum }_z\pi (z)p(z,y)=\pi (y)$ for every $y$, using [F2] with $m=n$, $n=1$ and the interchange of the two nonnegative series in [F6].

Conversely, assume some state $b$ is positive recurrent. Then ${\mathbb{P}}_b(T_b^{+}<\mathrm{\infty })=1$ and $0<{\mathbb{E}}_b{T}_b^{+}<\mathrm{\infty }$; by [F4] the measure ${\mu }_b$ satisfies ${\mu }_{b}p={\mu }_b$, and ${\mu }_b\ge 0$ with $1={\mu }_b(b)\le {\sum }_y{\mu }_b(y)={\mathbb{E}}_b{T}_b^{+}<\mathrm{\infty }$; hence ${\pi }_{\ast }(y):={\mu }_b(y)\mathrm{/}{\mathbb{E}}_b{T}_b^{+}$ defines a probability vector with ${\pi }_{\ast }p={\pi }_{\ast }$, i.e. an invariant probability by [F5].

Assume there is an invariant probability $\pi$. Then $\pi (b)>0$ for every $b\in E$: by [F1] irreducibility gives $n$ with $p^{(n)}(x,b)>0$ for an arbitrary fixed $x$, and step 1.1 gives $\pi (b)={\sum }_{x^{\mathrm{\prime }}\in E}\pi (x^{\mathrm{\prime }})p^{(n)}(x^{\mathrm{\prime }},b)\ge \pi (x)p^{(n)}(x,b)$, so if $\pi (b)=0$ then $\pi (x)=0$ for every $x$, contradicting ${\sum }_x\pi (x)=1$.

With $\pi$ invariant, define $\nu (y):=\pi (y)\mathrm{/}\pi (b)$ for $y\in E$; this is well defined and finite by step 2.1, $\nu \ge 0$, $\nu (b)=1$, and for $y\mathrm{\ne }b$ the invariance identity [F5] gives $(\nu p)(y)={\sum }_x\nu (x)p(x,y)=\frac{1}{\pi (b)}{\sum }_x\pi (x)p(x,y)=\pi (y)\mathrm{/}\pi (b)=\nu (y)$.

The pointwise minimality of [F4] applied to $\nu$ yields ${\mu }_b(y)\le \nu (y)$ for every $y$; summing and using ${\sum }_y{\mu }_b(y)={\mathbb{E}}_b{T}_b^{+}$ from [F4] gives ${\mathbb{E}}_b{T}_b^{+}\le {\sum }_y\nu (y)=1\mathrm{/}\pi (b)<+\mathrm{\infty }$, so $b$ is recurrent with finite expected return time, i.e. positive recurrent by [F3]. Since $b$ was arbitrary, every state is positive recurrent.

The three statements are equivalent: every state positive recurrent implies some state positive recurrent because $E\mathrm{\ne }\mathrm{\varnothing }$; some state positive recurrent implies the existence of an invariant probability by step 1.2; and the existence of an invariant probability implies every state positive recurrent by steps 2.1–4.1. In the construction of step 1.2, ${\pi }_{\ast }(y)={\mu }_b(y)\mathrm{/}{\mathbb{E}}_b{T}_b^{+}$ and ${\pi }_{\ast }(b)={\mu }_b(b)\mathrm{/}{\mathbb{E}}_b{T}_b^{+}=1\mathrm{/}{\mathbb{E}}_b{T}_b^{+}$, which are the two displayed formulas of the statement, while the bound ${\mathbb{E}}_b{T}_b^{+}\le 1\mathrm{/}\pi (b)$ for an invariant $\pi$ is step 4.1.

Boundary and axiom cases: if $E$ is a singleton then $p(1,1)=1$, every state is positive recurrent with $T_b^{+}=1$, and $\pi ={\delta }_b$ is the invariant probability, consistent with all three clauses; no state is transient here, so the alternatives of [F3] are exhaustive; the equivalence is proved in both directions through steps 4.1 and 1.2, not assumed; the arguments never subtract infinite quantities, since all sums of occupation masses are nonnegative and are shown finite only after the minimality bound; and AC [A1] is used exactly through [F4], the published chain-law and return-cycle supplier, whose statement assumes AC, while the remaining steps are nonnegative matrix algebra.