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 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|improve this question
    
What's wrong with the usual approach for finding expected hitting times in a (not necessarily reversible) Markov chain? See planetmath.org/encyclopedia/MeanHittingTime.html –  Mike Spivey Jan 19 '11 at 22:55
    
Did you get something out of the answer below? –  Did Apr 7 '11 at 8:07

1 Answer 1

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|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

 
discard

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