One lemma about the irreducible Markov chain $\mathbb{P}_x[\tau_{y}>2n]\leq (1-a)^2$

Question

Lemma: For any states $x, y$ of an irreducible Markov chain, $$\mathbb{E}_x[\tau_{y}]< \infty.$$ where $\mathbb{E}_x[\tau_{y}]=\mathbb{E}[\tau_{y}| X_{0}=x]$ and $\tau_{y}:=\min\{t\geq 1: X_t=y\}$.

My question is when I try to prove the inequality:

$$\mathbb{P}_x[\tau_{y}>kn]\leq (1-a)^k, \forall k \in \mathbb{N}.$$

I am stuck in how to show

$$\mathbb{P}_x[\tau_{y}>2n]\leq (1-a)^2$$

I know that there exists constants $a>0$ and $n \geq 1$ such that $\mathbb{P}_x[\tau_{y}>n]\leq 1-a$, but how to prove:

$$\mathbb{P}_x[\tau_{y}>2n]\leq (1-a) \mathbb{P}_x[\tau_{y}>n] ?$$

Answer 1

This should technically go to the comment by mbartczak, but the idea is using the Markov property of the Markov chain in an extended fashion. Note that we require finiteness of the state space, since the simple symmetric random walk gives a counterexample to the lemma.

Given that $P_x[\tau_y > n] < 1-a_x$, we can just take the maximum over all $x \neq y$(which can be done because as you see in my comment, we need a finite state space) to get an $a$ such that $\forall x, P_x [\tau_y > n] < 1-a$.

Now, consider the event $P_x[\tau_y > 2n]$. By the law of total probability, it is equal to $P_x[\tau_y > 2n | \tau_y > n] P_x[\tau_y > n]$. The latter is less than $1-\alpha$, now we just need the former to be less than $1-\alpha$.

Why is it heuristically less than $1-\alpha$? The answer is follows : suppose the Markov chain never hit $y$ in $n$ steps, and say it reached some point $z$ after $n$ steps. The probability that the original Markov chain does not hit $y$ after $2n$ steps, is the probability that a new Markov chain started at $z$ with the same transition matrix, does not hit $y$ after $n$ steps. This is the content of the Markov property. This new Markov chain , wherever it starts(which is why I required all states to have the bound), avoids $y$ for $n$ steps with probability at most $1-\alpha$(the bound for the original Markov chain), which gives the bound.

Now, all we need to do is put the Markov property into use. Let us see a statement of the Markov property and apply it here.

Markov Property : Let $X_n$ be a Markov chain ,then for every $m > n \geq 0$ : $$ P(X_{m} = j | X_k = x_k , 0 \leq k<n , X_n = l) = P(X_{m} = j | X_n = l) = P(X_{m-n} = j | X_0 = l) $$

In words, this may be written as follows : conditioned on $X_n = l$, the process $(X_{n + m})_{m \geq 0}$ is a Markov chain, which is independent of $X_k, k < n$, and has the same transition matrix as the original MC.

We can move to functions very easily, giving the following statement:

Let $m, n \geq 0$ , $X_n$ be a Markov chain , and $k$ be an arbitrary state. For any function $f$ from $\Omega^{m}$ (where $\Omega$ is the state space) to $\mathbb R$ we have : $$ P[f(X_{n+1} , X_{n+2},...,X_{n +m}) | X_n = k] = P[f(X_{1}, X_2, ..., X_m) | X_0 = k] $$

With this in mind, let us look at the quantity $P_x(\tau_y > 2n | \tau_y > n)$. We may write this as : $$P_x(X_{n+1} \neq y, X_{n+2} \neq y , ... X_{2n} \neq y | X_0 \neq y , X_1 \neq y, ..., X_n \neq y)$$, now since the left hand side of the conditional is independent of $X_0,X_1,...,X_{n-1}$, we get $$P_x(X_{n+1} \neq y, X_{n+2} \neq y , ... X_{2n} \neq y | X_0 \neq y , X_1 \neq y, ..., X_n \neq y) = P_x(X_{n+1} \neq y , ..., X_{2n} \neq y | X_{n} \neq y)$$.

Now, if $f(x_1,x_2,...,x_n) = 1$ if none of $x_1,...,x_n$ equal $y$, and $0$ otherwise, then we get that the above just equals $$\sum_{k \neq y} P_x[f(X_{n+1},X_{n+2},...,X_{2n}) | X_n = k]P_x[X_n = k] = \sum_{k \neq y} P[f(X_1,X_2,...,X_n) | X_0 = k]P_x[X_n = k] \\ = \sum_{k \neq y} P_k[\tau_y > n]P_x[X_n = k] < (1-a)\sum_{k \neq y} P_x[X_n = k] = (1-a)P_x[X_n \neq y] \leq (1-a)$$

Giving the desired inequality.

Now, we may replace $n$ and $2n$ by $kn$ and $(k+1)n$ above(not exactly a copy-paste replace, but you get the point!) To get $P_x[\tau_y > (k+1)n | \tau_y > kn] < (1-\alpha)$. One can then use the tower of expectations : $$ P_x[\tau_y > (k+1)n] = P_x[\tau_y > (k+1)n | \tau_y > kn] P_x[\tau_y > kn | \tau_y > (k-1)n] ... P_x[\tau_y > n] $$

to conclude.