Direct proof of unique invariant distribution for ergodic, positive-recurrent Markov chain

Question

I posted the following question on MSE, feeling that it perhaps isn't research level mathematics, but didn't get any bites. So, I am crossposting here.

The following ergodic theorem is well known.

Ergodic Theorem. Let $X$ be an ergodic (ie, irreducible and aperiodic) Markov chain on a countable state space $I$. Suppose that $X$ has an invariant distribution—$\pi$, say. Let $\mu$ be any distribution on $I$. Then,

$$ \mathbb P_i(X_t = j) \to \pi_j \quad\text{as}\quad t \to \infty \quad\text{for all}\quad i,j \in I. $$

In particular, since the limit exists, the invariant distribution is unique.

This is the way that I have seen uniqueness of the invariant distribution proved, eg via a coupling argument. It seems to me, though, that a direct, more algebraic, proof should exist.

Prove uniqueness of the invariant distirbution by direct, algebraic methods, not appealing to the probabilistic interpretation.

After all, it's just a system of linear equations! I haven't been able to find one, but below are some of my thoughts on the matter. They're not super insightful, though...

1. Irreducibility is necessary, but aperiodicity isn't

   • $\pi P = P \iff \pi (I + P)/2 = \pi$, so can just make the chain lazy
   • this removes aperiodicity issues, and implies that the real part of any eigenvalue is non-negative

2. $\pi P = P \iff \pi(I - P) = 0 \iff (I - P^T) \pi^T = 0$

   • so, we want to show that $I - P^T$ has a one-dimensional kernel
   • this is equivalent to showing that the multiplicity of eigenvalue $1$ of $P^T$ is $1$

3. An invariant distribution can be constructed via the expected return times

   • this is just a sufficient condition for $\pi P = \pi$ to hold
   • I'm after a necessary condition

4. Naturally, I've also searched a lot online, including SE, but have not been successful

If anyone can point me to a good reference online, or give a proof—or even an outline—that would be appreciated!

Answer 1

Yes, uniqueness can be proved without appealing to probabilistic arguments.

Generally speaking, one can study properties of Markov chains by arguments from functional analysis and operator theory, since Markov chains can be described by positive operators on appropriately chosen ordered Banach spaces.

Here's an argument that works in the situation described in the OP:

Let $P$ denote the (infinite) matrix that contains the transition probabilities of the Markov chain. Then all entries of $P$ are $\ge 0$ and each row sums up to $1$. So $P$ is an operator $\ell^\infty \to \ell^\infty$ that satisfies $P1 = 1$ and the transposed matrix $P^T$ acts as the pre-adjoint operator $\ell^1 \to \ell^1$.

Proposition. Assume that the Markov chain is irreducible. Then the fixed space of $P^T$ in $\ell^1$ is at most one-dimensional.

Proof. We use the following notation: for each $f \in \ell^1$ the notation $f \ge 0$ is meant componentwise.

Step 1. Irreducibility implies that if $0 \le f \in \ell^1$ is a non-zero fixed vector of $P^T$, then all its components are $> 0$.

Step 2. The fixed space of $P^T$ is a sublattice of $\ell^1$, meaning that if $f \in \ell^1$ is a fixed vector, then so is its componentwise modulus $\lvert f \rvert$. Indeed, since all entries of $P^T$ are $\ge 0$, one has $\lvert f \rvert = \lvert P^T f\rvert \le P^T \lvert f \rvert$; but $$ \langle P^T \lvert f \vert - \lvert f \rvert, 1 \rangle = 0, $$ so $P^T \lvert f \rvert = \lvert f \rvert $, as claimed.

Step 3. Let $f \in \ell^1$ be a fixed vector of $P^T$. According to Step 2 the positive and negative part $f^+$ and $f^-$ are also fixed vectors of $P^T$, since $f^+ = \tfrac12 (\lvert f \rvert + f)$ and $f^- = \tfrac12 (\lvert f \rvert - f)$. But, $f^+ \cdot f^- = 0$, so it cannot be the case that both $f^\pm$ are $> 0$ in each component. Hence, by (the contrapositive of) Step 1, at least one must be $0$: $f^+ = 0$ or $f^- = 0$, i.e., $f \ge 0$ or $f \le 0$.

Step 4. Let $0 \le f,g \in \ell^1$ be fixed vectors of $P^T$. According to Step 3 it only remains to prove that $f$ anf $g$ are linearly dependent; so assume that contrary. Then there exists $\alpha \in \mathbb{R}$ such that some components of $f - \alpha g$ are $> 0$ and some are $< 0$. But this contradicts Step 3. $\square$

This argument can be adapted to much more general situations. A very general setting where such arguments work well (under appropriate assumptions) are positive operators on Banach lattices; see for instance Chapter V in Helmut H. Schaefer's book "Banach lattices and positive operators" (1974).

Remark. The trick that makes the above argume work is that, despite being interested only in probability distributions, one leaves the set of probability distributions to employ the vector space structure (and also the vector lattice structure) of $\ell^1$.

Answer 2

I came across another proof, by chance, for finite $I$. I saw this in old lecture notes by Peres on mixing times: Mixing for Markov Chains and Spin Systems (2005).

Definition (Harmonic). A function $h : I \to \mathbb R$ is harmonic if

$$\textstyle h(x) = \sum_y P(x,y) h(y) \quad\text{for all}\quad x \in I.$$

An alternative expression of this last statement is "$Ph = h$".

Lemma (cf Maximum Principle and Louville's Theorem). Everywhere-harmonic functions on the finite set $I$ must be constant.

Proof. The usual: take $x$ which has $h(x)$ maximal; all its neighbours must be maximal too, otherwise $Ph = h$ fails; iterate using irreducibility.

Theorem (Uniqueness). The invariant distribution is unique.

Proof. We want to show that the solution to $\pi P = \pi \iff (P^T - I) \pi^T = 0$ is unique. To this end, we need only prove that $\operatorname{rank}(P^T - I) = |I| - 1$. But, $\operatorname{rank}(M) = \operatorname{rank}(M^T)$ for any matrix/linear operator $M$. Hence, it suffices to show that $\operatorname{rank}(P - I) = |I| - 1$. This is equivalent to the fact that $(P - I) f = 0$ has only constant solutions, which holds by the previous lemma. $\square$

---

The next part is my own, not mentioned in the lecture notes, but I'm pretty sure it's correct.

Following the last proof to the penultimate statement, we need only show that the constant vector is the only eigenvector with unit eigenvalue.

• The hamonicity approach shows this.

• The Perron–Frobenius theorem gives simplicity of eigenvalue $1$, but that's much more to prove than the maximum principle above.

• Perhaps there is an even more direct and/or simple proof of this simplicity?