Lower bound on the convergence rate of a specific Markov chain - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T08:59:44Z http://mathoverflow.net/feeds/question/37302 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37302/lower-bound-on-the-convergence-rate-of-a-specific-markov-chain Lower bound on the convergence rate of a specific Markov chain Heinzi 2010-08-31T19:35:18Z 2010-08-31T20:42:54Z <p>I have a Markov chain <code>$\mathbf{A} = (A_0, A_1, \ldots)$</code> with state space <code>$\{0, \ldots, n\}$</code> which converges towards a stationary distribution $\pi$. There are a lot of well-known results on upper-bounding the convergence rate. However, I'm interested in getting a lower bound.</p> <hr> <p>In detail, the problem looks like this: The transition probability is given as</p> <p>$p_{ij} = {n \choose i}\left(1-({1\over 2})^j\right)^i\left(({1\over 2})^j\right)^{n-i}$ for $j\neq 0$,</p> <p>$p_{ij} = {n \choose i}\left(1-({1\over 2})^n\right)^i\left(({1\over 2})^n\right)^{n-i}$ for $j = 0$,</p> <p>and the initial distribution $A_0$ is $(1, 0, \ldots, 0)^T$, i.e., the chain starts in state $0$ with probability $1$.</p> <p>Given this information, is it possible to derive a lower bound on the convergence rate? Since I'm particularly interested in state 0, I would like to come up with something like this:</p> <p>$\lvert \mathbb{P}(A_k = 0) - \pi_0 \rvert \geq \ldots$ some function of $k$ and $n$.</p> <p>Any hints on how to approach this would be appreciated. Please also speak up if you think that it is unlikely that such a closed-form expression exists and I should stop wasting my time on this problem. I'm a computer scientist, not a mathematician, so it's quite possible that I've overlooked something obvious.</p> http://mathoverflow.net/questions/37302/lower-bound-on-the-convergence-rate-of-a-specific-markov-chain/37312#37312 Answer by Steve Huntsman for Lower bound on the convergence rate of a specific Markov chain Steve Huntsman 2010-08-31T20:42:54Z 2010-08-31T20:42:54Z <p>See Chapter 7 of <a href="http://www.uoregon.edu/~dlevin/MARKOV/" rel="nofollow"><em>Markov Chains and Mixing Times</em></a> by Levin, Peres, and Wilmer.</p>