Lower bound on the convergence rate of a specific Markov chain

2010-08-31T19:35:18Z

I have a Markov chain $\mathbf{A} = (A_0, A_1, \ldots)$ with state space $\{0, \ldots, n\}$ 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.

In detail, the problem looks like this: The transition probability is given as

$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_{ij} = {n \choose i}\left(1-({1\over 2})^n\right)^i\left(({1\over 2})^n\right)^{n-i}$ for $j = 0$,

and the initial distribution $A_0$ is $(1, 0, \ldots, 0)^T$, i.e., the chain starts in state $0$ with probability $1$.

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:

$\lvert \mathbb{P}(A_k = 0) - \pi_0 \rvert \geq \ldots$ some function of $k$ and $n$.

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.

Answer by Steve Huntsman for Lower bound on the convergence rate of a specific Markov chain

2010-08-31T20:42:54Z

See Chapter 7 of Markov Chains and Mixing Times by Levin, Peres, and Wilmer.

Lower bound on the convergence rate of a specific Markov chain - MathOverflow

Lower bound on the convergence rate of a specific Markov chain

Answer by Steve Huntsman for Lower bound on the convergence rate of a specific Markov chain