There are many interesting consequences of reversibility. Here is one that I talked about at the end of today's lecture and which has a very practical application.
Theorem. If $P$ is the transition matrix of a reversible Markov chain on $N$ states then for all $i$,
$$
P_i(X_n=i)=p_{ii}^{(n)} = \sum_{k=1}^N a_k \lambda_k^n,
$$where all $a_k\geq 0$ and all $\lambda_k$ are real and $\lambda_k\leq 1$.
Hint. To prove this, let $\pi$ be the invariant distribution and consider $A=VPV^{-1}$, where $V$ is the diagonal matrix with $V_{ii}=\sqrt{\pi_i}$. Show that $A$ is symmetric, and think about what that implies.
Similarly, for the continuous time version of a Markov chain (a so-called Markov process)
$$
P_i(X(t)=i)=p_{ii}(t) = \sum_{k=1}^N a_k e^{-\lambda_k t}.
$$where all $a_k\geq 0$ and all $\lambda_k$ are real and $\lambda_k\geq 0$.
I have used this fact to prove what I call the fast retries lemma (Theorem 1 in the paper Optimal call routing in VoIP). Suppose that you ring up your friend and find that his phone is engaged. There is a minimum time that it takes to retry the call, say $\tau$, so you could try to reach him at times $0,\tau,2\tau,\dotso$ until you get through. But might the expected time to get through be less if you retry at $\rho,2\rho,\dotso$, for some $\rho>\tau$? You might get through on the second attempt rather than the third, and $2\rho< 3\tau$.
It turns out the answer is no. Your best policy is to attempt contact at $0,\tau,2\tau,\dotso$, provided that the state of your friend can be modelled as a state of a reversible Markov process, and that you get through to him as soon as you ring and find that he is not in the state (engaged) which he was at time $0$. For example, your friend might be performing a random walk on a graph whose vertices are "engaged on the phone", "cooking", "sleeping", "watching tv", etc.
The expected time to connect is $ET$ where
$$
ET = t + p_{00}(t)ET = \frac{t}{1-p_{00}(t)}.
$$
So the lemma is saying that, subject to the constraint $t\geq \tau$, $ET$ is minimized by $ t=\tau$.
Theorem. If $P$ is the transition matrix of a reversible Markov chain on $N$ states then for all $i$,
$$
P_i(X_n=i)=p_{ii}^{(n)} = \sum_{k=1}^N a_k \lambda_k^n,
$$where all $a_k\geq 0$ and all $\lambda_k$ are real and $\lambda_k\leq 1$.
Hint. To prove this, let $\pi$ be the invariant distribution and consider $A=VPV^{-1}$, where $V$ is the diagonal matrix with $V_{ii}=\sqrt{\pi_i}$. Show that $A$ is symmetric, and think about what that implies.
Similarly, for the continuous time version of a Markov chain (a so-called Markov process)
$$
P_i(X(t)=i)=p_{ii}(t) = \sum_{k=1}^N a_k e^{-\lambda_k t}.
$$where all $a_k\geq 0$ and all $\lambda_k$ are real and $\lambda_k\geq 0$.
I have used this fact to prove what I call the fast retries lemma (Theorem 1 in the paper Optimal call routing in VoIP). Suppose that you ring up your friend and find that his phone is engaged. There is a minimum time that it takes to retry the call, say $\tau$, so you could try to reach him at times $0,\tau,2\tau,\dotso$ until you get through. But might the expected time to get through be less if you retry at $\rho,2\rho,\dotso$, for some $\rho>\tau$? You might get through on the second attempt rather than the third, and $2\rho< 3\tau$.
It turns out the answer is no. Your best policy is to attempt contact at $0,\tau,2\tau,\dotso$, provided that the state of your friend can be modelled as a state of a reversible Markov process, and that you get through to him as soon as you ring and find that he is not in the state (engaged) which he was at time $0$. For example, your friend might be performing a random walk on a graph whose vertices are "engaged on the phone", "cooking", "sleeping", "watching tv", etc.
The expected time to connect is $ET$ where
$$
ET = t + p_{00}(t)ET = \frac{t}{1-p_{00}(t)}.
$$
So the lemma is saying that, subject to the constraint $t\geq \tau$, $ET$ is minimized by $ t=\tau$.
