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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a reversible markov chain Xn whose steady state distribution is known, can we find the expected hitting time to a subset A of the states starting from some state i ? Additionally you can assume the the chain has no self transitions.

share|cite|improve this question
What's wrong with the usual approach for finding expected hitting times in a (not necessarily reversible) Markov chain? See – Mike Spivey Jan 19 '11 at 22:55
Did you get something out of the answer below? – Did Apr 7 '11 at 8:07

The steady state distribution is not enough to determine the mean hitting time $E(T)$ of a given subset $A$. To see this in a simple case, assume there are $2n$ states and consider the simple random walks on the discrete circle $C_{2n}$ and on the complete graph $K_{2n}$. By symmetry, the steady state distribution is uniform in both cases.

Choose $A=\{j\}$ and $i$ at distance $n$ from $j$ in $C_{2n}$. Then, $T$ for $C_{2n}$ is distributed like the first hitting time of $\pm n$ by a standard symmetric random walk on the discrete line starting from $0$, hence $E_{C_{2n}}(T)=n^2$. On the other hand, $T$ for $K_{2n}$ is distributed like the time of first success in an i.i.d. sequence of trials with probability of success $1/(2n-1)$ at each trial, hence $E_{K_{2n}}(T)=2n-1$. For every $n\ge2$, $E_{C_{2n}}(T)\ne E_{K_{2n}}(T)$.

share|cite|improve this answer
+1, although do you mean $C_{2n}$ and $K_{2n}$ in the second paragraph? – Mike Spivey Mar 16 '11 at 3:35
@Mike Indeed, corrected, thanks. – Did Mar 16 '11 at 6:28

Your Answer


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