5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Jan 19, 2011 at 22:55
  • $\begingroup$ Did you get something out of the answer below? $\endgroup$
    – Did
    Apr 7, 2011 at 8:07

1 Answer 1

4
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ +1, although do you mean $C_{2n}$ and $K_{2n}$ in the second paragraph? $\endgroup$ Mar 16, 2011 at 3:35
  • $\begingroup$ @Mike Indeed, corrected, thanks. $\endgroup$
    – Did
    Mar 16, 2011 at 6:28

You must log in to answer this question.