Lemma 12.2 -- the spectral representation of a reversible chain

Let $P$ be a Markov chain on a finite state space $V$ with $n=|V|$ states, reversible with respect to a strictly positive probability distribution $\pi$ — that is, satisfying the detailed balance equations $\pi(x)P(x,y)=\pi(y)P(y,x)$. Equip real-valued functions on $V$ with the weighted inner product

the geometry in which a reversible chain is self-adjoint.

The theorem (Lemma 12.2 of Levin–Peres–Wilmer) asserts the existence of real numbers $\lambda_1,\dots,\lambda_n$ and functions $f_1,\dots,f_n:V\to\mathbb R$ such that:

1. each $f_j$ is an eigenfunction, $Pf_j=\lambda_jf_j$ (with $(Pf)(x)=\sum_yP(x,y)f(y)$);
2. the family is orthonormal in $\ell^2(\pi)$: $\langle f_j,f_k\rangle_\pi=1$ if $j=k$ and $0$ otherwise;
3. the transition probabilities decompose spectrally: for every time $t$ and all states $x,y$,

Every question about the long-run behaviour of a reversible chain thereby becomes a question about the decay of the powers $\lambda_j^t$ — the formula from which the relaxation-time bounds of this mission and the cutoff theory of later missions are read off.