0
$\begingroup$

Let $P$ be a probability distribution of an ergodic Markov chain on the space $\Omega_{n}=\left\{\omega=\omega_{1},\ldots,\omega_{n}\right\}$ with finite state space $X$. Then, for any $x \in X$, we have that $P(\omega: \omega_{i} \neq x, 1 \leq i \leq n) \leq C q^{n},$ for some constant $C$ and $0 < q <1$.

Is there any nice way of doing this? Thanks!

1 Answers 1

0

You don't need the Markov chain to be ergodic, just that state $x$ is accessible from every other state. Thus from any other state $w$ there is a path from $w$ to $x$ consisting of transitions with nonzero probability, and thus there is some $m$ such that starting in state $w$, with nonzero probability you get to state $x$ in $m$ steps. Doing this for all other states, there exist $m$ and $\epsilon > 0$ such that, no matter what state you start in, the probability that you get to state $x$ in at most $m$ steps is at least $\epsilon$: $P(\omega_i \ne x \text{ for } i=k+1 \ldots k+m\ |\ \omega_k = w) < 1-\epsilon$. Use the Markov property to get your desired estimate with $q = (1-\epsilon)^{1/m}$.