Markov Chain problem with first passage time Let $X$ a Markov Chain with space state $S$, and transition matrix $P$. Let $A \subset S$ and $\tau_A = \inf\{n \ge 0: X_n \in A\}$ . Suppose that exists $n \ge 1$ and $\alpha > 0$ that for all $x \in A^c$ (the complement of $A$), $p^n_{x,A} \ge \alpha$. i) Show that for all $k \in \mathbb{N}$ and $x \in S$, $\mathbb{P}_x(\tau_A > kn) \le (1 - \alpha)^k$. ii) Show that $\mathbb{E}_x[\tau_A] \le \frac{n}{\alpha}$, and in particular, $\mathbb{P}_x(\tau_A < \infty) = 1$.
This is how I tried to solve it:
If $x \in A$, we have
$$\mathbb P _x(\tau_A = 0) = 1 \implies \mathbb P _x(\tau_A > kn) = 0 \le (1-\alpha)^k.$$
Let $x \in A^c$. If $\lambda = (\lambda_i : i \in S)$ is a probability distribution of $X$, so $\lambda_x = \mathbb P_x(X_0 = x)$. Moreover, it's known that

*

*By definition of $\lambda$, we have $\lambda_x \le 1$;

*Since $X$ is Markov Chain, we have (from Chapman-Kolmogorov)
$$p^n_{x,A^c} = \sum_{i_1, \dots, i_{n-1} \in S}{p_{x,i_1} \cdots p_{i_{n-1},A^c} }$$

*Since $A^c \subset S$,
$$p_{x,A^c}\underbrace{p_{A^c,A^c} \cdots p_{A^c,A^c} }_{n-1 \text{ times}} \le \sum_{i_1, \dots, i_{n-1} \in S}{p_{x,i_1} \cdots p_{i_{n-1},A^c} } = p^n_{x,A^c}$$

*Similarly,
$$\underbrace{p_{A^c,A^c} \cdots p_{A^c,A^c} }_{n \text{ times}} \le \sum_{i_1, \dots, i_{n-1} \in S}{p_{A^c,i_1} \cdots p_{i_{n-1},A^c} } = p^n_{A^c,A^c} $$

*It's easy to see, that
$$p^n_{A^c,A^c} = 1 - p^n_{A^c,A^c}$$

*For $x \in A^c$,
$$p^n_{A^c,A} \ge p^n_{x,A}$$

*And finally,
$$p^n_{x,A^c} = 1 - p^n_{x,A} \le 1 - \alpha$$
Using some properties about Markov Chains and all these information, it follows that
$$\begin{aligned}\mathbb P_x(\tau_A > kn) &= \mathbb P (X_0 \not \in A,X_1 \not \in A, \dots, X_n \not \in A, X_{n+1} \not \in A, \dots, X_{2n} \not \in A,\dots, X_{kn - 1} \not \in A,X_{kn} \not \in A\mid X_0 = x)\\
&=\mathbb P(X_0 = x, X_1 \not \in A, \dots, X_n \not \in A, \dots, X_{2n} \not \in A,\dots, X_{kn} \not \in A )\\
&= \lambda_x p_{x,A^c}\underbrace{p_{A^c,A^c}\cdots p_{A^c,A^c}}_{n-1 \text{ times}}\underbrace{\underbrace{p_{A^c,A^c}\cdots p_{A^c,A^c}}_{n \text{ times}}\cdots \underbrace{p_{A^c,A^c}\cdots p_{A^c,A^c}}_{n \text{ times}}}_{k - 1 \text{ times}}\\
&\le p_{x,A^c}\underbrace{p_{A^c,A^c}\cdots p_{A^c,A^c}}_{n-1 \text{ times}}\underbrace{\underbrace{p_{A^c,A^c}\cdots p_{A^c,A^c}}_{n \text{ times}}\cdots \underbrace{p_{A^c,A^c}\cdots p_{A^c,A^c}}_{n \text{ times}}}_{k - 1 \text{ times}} \text{ (from 1)}\\
&\le \left(\sum_{i_1,\dots, i_{n-1} \in S}{p_{x,i_1}p_{i_1,i_2}\cdots p_{i_{n-1},A^c}}\right) \cdot \left(\sum_{i_1,\dots, i_{n-1} \in S}{p_{A^c,i_1}p_{i_1,i_2}\cdots p_{i_{n-1},A^c}}\right)^{k-1} \text{ (from 3 and 4)}\\
&= \left(p^n_{x,A^c}\right)\left(p^n_{A^c,A^c}\right)^{k-1} \text{ (from 2 and 4)}\\
&\le \left(p^n_{x,A^c}\right)\left(1 - p^n_{x,A}\right)^{k-1} \text{ (from 5 and 6)}\\
&\le (1-\alpha)^k \text{ ( from 7)}\end{aligned}$$
This is how I tried to solve item i). Note that,for $i \ge 1$
$$\{\tau_A > i + 1\} \subseteq \{\tau_A > i\}$$
It means that
$$\mathbb P_x(\tau_A = \infty) = \mathbb P_x(\lim_{k \to \infty}{\tau_A > kn}) = \lim_{k \to \infty} {\mathbb P_x({\tau_A > kn})} \le \lim_{k \to \infty}{(1-\alpha)^k} = 0$$
It implies that,
$$\mathbb P_x(\tau_A < \infty) = 1 - \mathbb P_x(\tau_A = \infty) = 1$$
Finally,
$$
\begin{aligned}
\mathbb{E}_x[\tau_A] &= \frac{n}{n}\mathbb E_x[\tau_A]\\
&= n\mathbb E_x\left[\frac{\tau_A}{n}\right]\\
&= n\left(\sum_{i \ge 1}{\mathbb P_x\left(\frac{\tau_A}{n} > i\right)}\right)\\
&= n\left(\sum_{i \ge 1}{\mathbb P_x(\tau_A > ni)}\right)\\
&\le n\left(\sum_{i \ge 1}{\mathbb (1-\alpha)^i}\right)\\
&=n \cdot \frac{1}{1 - (1-\alpha)} = \frac{n}{\alpha}
\end{aligned}
$$
Please, help me to find any mistakes. Thanks for the help!
 A: Note that if $x\in A$ then $\tau_A=0$ and so $$0=\mathbb{P}_x(\tau_A>kn)\leq (1-\alpha)^k$$ On the other hand, if $x\notin A$ we can say that $$\mathbb{P}_x(\tau_A>kn)=\mathbb{P}(X_1\notin A,X_2 \notin A,\ldots,X_{kn}\notin A|X_0=x)$$ The right hand side is bounded above by $$\mathbb{P}(X_n\notin A,X_{2n}\notin A,\ldots,X_{kn}\notin A|X_0=x)$$ Using the chain rule for conditional probability along with Markov this equals $$\mathbb{P}(X_n\notin A|X_0=x)\times \mathbb{P}(X_{2n}\notin A|X_n\notin A)\times \dots \times\mathbb{P}(X_{kn}\notin A|X_{(k-1)n}\notin A)$$ which is bounded above by $(1-\alpha)^k$. Clearly if $x\in A$ then $\mathbb{E}_x(\tau_A)=0$ so for $x \notin A$ we have that $$\mathbb{E}_x(\tau_A)=\sum_{j=0}^{\infty}\mathbb{P}_x(\tau_A > j)=1+\sum_{j=1}^{n-1}\mathbb{P}_x(\tau_A>j)+\sum_{k=1}^{\infty}\sum_{j=kn}^{kn+n-1}\mathbb{P}_x(\tau_A>j)$$ Because $$\sum_{j=1}^{n-1}\mathbb{P}_x(\tau_A>j)\leq(n-1)\mathbb{P}_x(\tau_A>1)\leq(n-1)(1-\alpha)$$ $$\sum_{j=kn}^{kn+n-1}\mathbb{P_x}(\tau_A>j)\leq n\mathbb{P}_x(\tau_A>kn)\leq n(1-\alpha)^k$$ it follows that $$\mathbb{E}_x(\tau_A)\leq1+(n-1)(1-\alpha)+n\sum_{k=1}^{\infty}(1-\alpha)^k=\alpha(1-n)+\frac{n}{\alpha}\leq \frac{n}{\alpha}$$ as desired. Now we'll prove $\mathbb{P}_x(\tau_A<\infty)=1$ for $x\notin A$. For $j\geq n$ we have $$\mathbb{P}(X_j\notin A,\ldots ,X_1 \notin A|X_0=x)\leq \mathbb{P}(X_{n\left \lfloor{j/n}\right \rfloor }\notin A,\ldots,X_n \notin A|X_0=x)$$ The right hand side is bounded above by $(1-\alpha)^{\left \lfloor{j/n}\right \rfloor }$ and finally $$\mathbb{P}_x(\tau_A=\infty)\leq \lim_{j\rightarrow \infty}(1-\alpha)^{\left \lfloor{j/n}\right \rfloor}=0 $$
