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,
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}.
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.
Logging you in...