Consider a countable-state Markov chain; for the sake of concreteness identify the set of states with the set of nonnegative integers {0, 1, 2, ... }. Suppose the transition probabilities $P_{ij} = \mathbb{P}(j \to i)$ are such that the chain has a stationary probability distribution $(\pi_j)$: that is, $\pi_j \geq 0$, $\sum_j \pi_j = 1$, and $\sum_j P_{ij} \pi_j = \pi_i$ for every $i$; in other words, the chain is positive recurrent.

Let $\tau_1$ denote the first return time to the state labeled 1. Suppose that we also know the extra fact that $\pi_j$ decays exponentially in $j$: that is, there are $C,\lambda>0$ such that $\pi_j \leq C e^{-\lambda j}$ for every $j$. Does it follow that the return time distribution satisfies $$ \mathbb{P}(\tau_1 > n ) \leq C' e^{-\lambda' n} $$ for some $C',\lambda'>0$?

If it makes any difference, the examples we are interested in have the property that $P_{ij}=0$ whenever $|i-j|>1$, so one can really think of them as a random walk on the nonnegative numbers, where at each step you can either go left, right, or stay where you are, and the transition probabilities depend only on your current location, but can vary from location to location.

  • $\begingroup$ I'm inclined to think about it this way: you have $\pi_j=(E_j[\tau_j])^{-1}$, so given $\pi_1 \geq m$ you get $E_1[\tau_1] \leq 1/m$, hence $P_1(\tau_1 \geq n) \leq 1/mn$ by Markov's inequality. You could get such a lower bound on $\pi_1$ if you know $C'$ such that $\sum_{k \neq 1} \pi_k \leq C'<1$. Getting any better than $O(1/n)$ will require much more careful ergodicity analysis I think, because proving that will require you to demonstrate that Markov's inequality is far from tight, which means the tail distribution is "spread out" rather than concentrated near one point. $\endgroup$ – Ian Feb 23 '17 at 18:53

Assume $p_{i(i+1)}>0$ for all $i$. For any fixed $k$, you have $\mathbb{P}(\tau_1>n)\geq p_{12}p_{23}\dots p_{(k-1)k}p_{kk}^n$ for all $n$. So if $\sup_k p_{kk}=1$, then the exponential tail bound that you want for the return time can't hold.

But you can still get exponential decay of the stationary probabilities by making $\limsup_{k\to\infty} \frac{p_{k(k+1)}}{p_{(k+1)k}}$ bounded away from $1$. (For a nearest-neighbour chain, $\frac{\pi_{k+1}}{\pi_k}=\frac{p_{k(k+1)}}{p_{(k+1)k}}$ by detailed balance.)

For example try $p_{k(k+1)}=\frac{1}{3k}$, $p_{k(k-1)}=\frac{2}{3k}$, $p_{kk}=1-\frac{1}{k}$. (With, say, $p_{01}=1$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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