MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
You beat me to it! – Mark Meckes Aug 31 '10 at 20:49
Thanks! I cannot use the techniques mentioned there yet since I don't have a closed-form bound on $\pi_0$, but your answer has been helpful. – Heinzi Sep 14 '10 at 12:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.