most recent 30 from http://mathoverflow.net 2013-05-26T03:10:17Z http://mathoverflow.net/feeds/user/27222 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109563/bound-the-hitting-time-in-markov-chain Jialin 2012-10-13T22:55:49Z 2012-12-04T23:22:00Z

<p>Given a finite-state Markov chain $M$ and assume there is a terminate state $f$ which is reached with prob. 1, I am interested in the distribution of hitting time $T$ of $f$, namely, $T$ is defined as a RV which is the number of steps before reaching $f$, and $P(T\geq N)$ for natural number $N$ is the probability of reaching $f$ by at least $N$ steps. In particular, I want to obtain a nontrivial bound of $N$ such that $P(T\geq N)\leq \epsilon$, in terms of the transition probabilities of $M$ and $\epsilon$. </p> <p>Is there any existing research on this problem, as it seems to be a very natural problem to consider. </p> <p>Thanks. </p>