bound the hitting time in Markov chain - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T03:27:34Z http://mathoverflow.net/feeds/question/109563 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109563/bound-the-hitting-time-in-markov-chain 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> http://mathoverflow.net/questions/109563/bound-the-hitting-time-in-markov-chain/110483#110483 Answer by gmath for bound the hitting time in Markov chain gmath 2012-10-23T22:18:01Z 2012-10-23T22:18:01Z <p>You can take a look at the book: Markov Chains and mixing times by Y.Peres, D.evin and E.Wilmer (you can get this from the webpage of Yuval Peres). See chapter 10 for example.</p> <p>Different techniques are useful for different models, It would be helpful to know the model.</p>