Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider an irreducible, aperiodic Markov chain with stationary distribution $\pi$. We will use $E_{\pi} T_j$ to be the hitting time of node $j$ when the initial distribution is $\pi$, and $E_i T_j$ to be the same hitting time when the chain is started at node $i$. If $$ f(i,j) = E_i T_j - E_{\pi} T_j$$ then $$ f(i,j) = f(j,i).$$ Is there a simple proof of this? This is a byproduct of a number of identities in Aldous & Fill textbook, Chapter 2, which are proved using (what seems to me) to be advanced ideas.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Let me doubt very much that Aldous and Fill are saying that. For a counterexample of the assertion in your post, consider the random walk on a discrete circle of size $n\geqslant3$, with steps $+1$ and $0$ with probabilities $p$ and $1-p$.

Then $\pi$ is uniform and $\mathbb E_\pi(T_i)$ does not depend on $i$ hence $f(i,j)=f(j,i)$ would mean that $\mathbb E_i(T_j)=\mathbb E_j(T_i)$ for every $(i,j)$. But, when $p\to1$, $\mathbb E_i(T_{i+1})\to1$ and $\mathbb E_{i+1}(T_i)\to n-1$.

share|improve this answer
    
Thank you for the answer. I believe I omitted the requirement that the chain should be reversible. –  pierre Feb 9 '13 at 22:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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