1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ You beat me to it! $\endgroup$ Aug 31, 2010 at 20:49
  • $\begingroup$ 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. $\endgroup$
    – Heinzi
    Sep 14, 2010 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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