9
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ Welcome to MathOverflow! Two comments regarding your point 1.: (i) "since irreducibility implies that $−1$": No, irreducibility is independent of the question whether $-1$ is an eigenvalue. (ii) "this lazification implies that we may assume that all eigenvalues of $P$ are non-negative": That's not quite correct, since there can be complex eigenvalues. $\endgroup$ Aug 1, 2023 at 9:10
  • $\begingroup$ @JochenGlueck Yes, of course, thanks for pointing this out. Not sure what I was thinking! I actually associate aperiodicity with $-1$ eigenvalue more (eg, non-lazy random walk on a cycle). I almost always work with reversible chains in my research, so I often forget about complex eigenvalues! Still, at least all have non-negative real part... $\endgroup$
    – user24601
    Aug 1, 2023 at 11:36
  • $\begingroup$ There is actually another proof here, on MSE: math.stackexchange.com/questions/2330328/…. Reading that, I now remember having seen it in the past. Tbh, it's kind of the same idea as the maximum principle that I outline below. But, it's more direct, not going via ranks of matrices $\endgroup$
    – user24601
    Aug 21, 2023 at 8:48
  • $\begingroup$ Please note, though, that the argument on Math Stackexchange that you linked in your comment only works for finite state spaces, but not for countable ones. $\endgroup$ Aug 21, 2023 at 16:50
  • 1
    $\begingroup$ Good point! Won't necessarily be able to choose the minimiser/maximiser of the ratio $\endgroup$
    – user24601
    Aug 24, 2023 at 10:25

2 Answers 2

16
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ This is excellent, thank you. I need to check the details of Step 1 myself carefully, but seems obvious: $f_i = \sum_j f_j p_{j,i}$ being $0$ implies $f_j$ is $0$ for all $j \sim i$; iterate. But, Step 3 is less clear to me—both parts, in fact. I'll have a think some more, but might comment here again if I'm still stuck! (if that's ok) $\endgroup$
    – user24601
    Aug 1, 2023 at 11:41
  • 1
    $\begingroup$ I added a few details to Step 3, for the benefit of anyone else reading this. Hopefully you're happy with them? Step 1 was simple enough that I just left it as it was $\endgroup$
    – user24601
    Aug 2, 2023 at 10:50
  • 1
    $\begingroup$ @user24601 Thanks for the edit! I just made a small additional change to your edit: I replaced "both $f^\pm > 0$" with "both $f^\pm$ are $> 0$ componentwise". While the symbol $\ge$ works great for pointwise inequalities, I try to avoid the notation $>$ for pointwise strict inequalities, since this at odds with how the symbol is used in the theory of partially ordered sets (and since this notation isn't well-suited for generalizations to abstract ordered Banach spaces). $\endgroup$ Aug 2, 2023 at 11:31
  • $\begingroup$ @user24601: I just noted that I had forgotten the important words "at most" in the theorem. Under the conditions of the theorem, it can of course happen that the fixed space if $P^T$ consists of $0$ only. $\endgroup$ Oct 5, 2023 at 5:50
7
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.