5
$\begingroup$

If the MC is reversible, then $\pi(x)P(x,y) = \pi(y)P(y,x)$ for some distribution $\pi$ and for all states $x,y$. I see that if $\pi$ is the uniform distribution, then $P$ is symmetric and thus has real eigenvalues. But what if $P$ is not symmetric?

$\endgroup$

3 Answers 3

5
$\begingroup$

(Typed after the answer of Fnacool was already accepted, only a complement that may make the same argument "human" / structural.)

The usual argument considers the Hilbert spacce $H=L^2(\pi)$, and the operator $P$ (well, same letter, sorry) on $H$ given by $$ (Pf)(x)=\sum_{y\in\Omega}P(x,y)f(y)\ . $$ It is selfadjoint, $$ \begin{aligned} \langle Pf, g\rangle &= \sum_{x}\pi(x)\; (Pf)(x)\;\bar g(x)\\ &= \sum_{x,y}\pi(x)\; P(x,y)\;f(y)\;\bar g(x)\\ &= \sum_{x,y}\pi(y)\; P(y,x)\;f(y)\;\bar g(x)\\ &= \sum_{x,y}\pi(y) \;f(y)\;\overline{P(y,x)\; g(x)}\\ &= \sum_{y}\pi(y)\; f(y)\;\overline {Pg(y)}\\ &= \langle f, Pg\rangle \end{aligned} $$ so the operator $P$ is selfadjoint (and a contraction). Its eigenvalues are thus real and contained in $[-1,1]$.

$\endgroup$
2
  • $\begingroup$ Do you have a good reference for this? I thought the book I'm using was a pretty standard source, but these Hilbert space arguments seem to be of a whole other flavour. $\endgroup$
    – theQman
    Mar 22, 2019 at 0:11
  • $\begingroup$ I only saw the accepted solution, and remembered immediately the structure. (The square roots "must come" from making an orthogonal basis orthonormal, i had it in the feeling, said it to myself, so where is the Hilbert space...?!) I only remembered a situation with professor Ion Cuculescu (probabilistic setting) long time ago, and because the operator algebras were next door, and i had to write an operator algebraic work coordinated by Serban Stratila... Now, years after, a random search gave for instance ime.usp.br/~tassio/TMP/… $\endgroup$
    – dan_fulea
    Mar 22, 2019 at 1:27
3
$\begingroup$

You're pretty close. Here's what's missing.

We will assume further that $P$ is irreducible so that up to a multiplicative constant: $\pi$ is unique and strictly positive.

Let $D= \mbox{diag} (\sqrt{\pi(1)},\dots, \sqrt{\pi(n)})$. Let $Q = D P D^{-1}$. Observe that

$$ Q_{i,j} = (D P D^{-1})_{i,j} = \sqrt{\pi(i)} p_{i,j} \frac{1}{\sqrt{\pi(j)}}.$$

By assuming

$$(*)\quad \pi(i) p_{i,j} = \pi(j) p_{j,i},$$ we have

\begin{align*} Q_{j,i} &\overset{\mbox{def}}{=} \sqrt{\pi(j)} p_{j,i} \frac{1}{\sqrt{\pi(i)}} \\ & =\frac{1}{\sqrt{\pi(j)}} \pi (j) p_{j,i} \frac{1}{\sqrt{\pi(i)}}\\ & \overset{(*)}{=} \frac{1}{\sqrt{\pi(j)}} \pi(i) p_{i,j} \frac{1}{\sqrt{\pi(i)}} \\ & = \sqrt{\pi(i)} p_{i,j} \frac{1}{\sqrt{\pi(j)}}\\ & = Q_{i,j}. \end{align*}

Therefore $Q$ is symmetric. As a result, all its eigenvalues are real and it is diagonalizable. Since $P$ and $Q$ are similar, the same holds for $P$.

$\endgroup$
2
  • $\begingroup$ This is less straight-forward than I expected. Is it a commonly known result? I'm reading "Markov Chains and Mixing Times" by Levin and Peres and they just state this fact in chapter 12 as if it's obvious... $\endgroup$
    – theQman
    Mar 21, 2019 at 17:23
  • $\begingroup$ Yes, perhaps not in this form. Another way to state reversibility is through $P$ being symmetric WRT to inner product $(v,u) = \sum_{i=1}^n \pi(i) v(i) u(i)$ (check). $\endgroup$
    – Fnacool
    Mar 21, 2019 at 17:27
2
$\begingroup$

This thread has aged, but it is less than a year old. This is a simple and extremely important result, so I'll give a very simple, motivated proof.

In particular for simplicity, I assume the chain has one communicating class. I assume this (time homogenous) markov chain has finitely many states since we're discussing eigenvalues; the underlying chain is thus positive recurrent. Let diagonal matrix $D := diag(\mathbf \pi)$ where $\pi$ is the steady state distribution.

Such a chain is reversible iff it satisfies detailed balance equations
$\pi(x)P(x,y) = \pi(y)P(y,x)$

Now calculate $P(x,y)$ two different ways.

First way
$P(x,y) = \mathbf e_x^T P\mathbf e_y $
(with standard basis vector $\mathbf e_k$)

Second way
$P(x,y)= \frac{\pi(y)}{\pi(x)}P(y,x) = \frac{\pi(y)}{\pi(x)}\cdot \mathbf e_y^T P \mathbf e_x = \frac{\pi(y)}{\pi(x)}\cdot \mathbf e_x^T P^T \mathbf e_y = \mathbf e_x^T \big(\frac{\pi(y)}{\pi(x)} P^T\big) \mathbf e_y = \mathbf e_x^T \big(D^{-1}P^T D\big)\mathbf e_y $
where we make use of the fact that transposing a scalar gives the same scalar. As a gut check
$\big(D^{-1}P^T D\big)\mathbf 1 = D^{-1}P^T\mathbf \pi = D^{-1}\mathbf \pi =\mathbf 1 $
so this is a stochastic matrix

Putting this together gives
$ \mathbf e_x^T P\mathbf e_y = P(x,y) = \mathbf e_x^T \big(D^{-1}P^T D\big)\mathbf e_y $
for arbitrary natural numbers $x$ and $y$ so we know $P = \big(D^{-1}P^T D\big) $

effecting a similarity transform with $D^\frac{1}{2}$ gives
$D^\frac{1}{2} PD^\frac{-1}{2} = \big(D^\frac{-1}{2}P^T D^\frac{1}{2}\big) $

this matrix is symmetric, because
$\big(D^\frac{1}{2} PD^\frac{-1}{2}\big) = \big(D^\frac{-1}{2}P^T D^\frac{1}{2}\big) = \big(D^\frac{-T}{2}P^T D^\frac{T}{2}\big) = \big(D^\frac{1}{2}P D^\frac{-1}{2}\big)^T$

and of course this matrix is similar to $P$, so in particular

$P $
$= D^\frac{-1}{2}\big(D^\frac{1}{2} PD^\frac{-1}{2}\big)D^\frac{1}{2} $
$= D^\frac{-1}{2}\big(U \Lambda U^T \big)D^\frac{1}{2} $
$=\big(D^\frac{-1}{2}U\big) \Lambda \big(U^{-1} D^\frac{1}{2}\big) $
$=\big(D^\frac{-1}{2}U\big) \Lambda \big(D^\frac{-1}{2}U\big)^{-1} $
$= S \Lambda S^{-1}$

for some orthogonal matrix $U$. Thus $P$ has real spectrum, is always diagonalizable and while not generally symmetric itself, we can easily estimate/bound say the Frobenius norm (or any Schatten p norm) of $S$ and $S^{-1}$ if we have estimates on the steady state distribution $\mathbf \pi$.

$\endgroup$
3
  • $\begingroup$ If a non-stochastic $P$ satisfy the detailed balance equations for some positive $\pi$, then this proof that $P$ is diagonal still holds, right? I asked this as a separate question. Thanks $\endgroup$
    – G Frazao
    Mar 16, 2023 at 15:07
  • $\begingroup$ @GFrazao "then this proof that 𝑃 is diagonal still holds" -- my proof does no such thing. Please re-read it. $\endgroup$ Mar 16, 2023 at 17:22
  • $\begingroup$ Yeah, I meant that $P$ is diagonalizable... You never use the fact that $P$ is stochastic, or that $\pi$ is the eigenvector with unit eigenvalue. Isn't the proof general for any matrix $P$ and positive vector $\pi$ satisfying the detailed balance equations? $\endgroup$
    – G Frazao
    Mar 16, 2023 at 19:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .