Strong Markov Propery

Question

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with transition matrix $\Pi$ and state space $E$. I want to prove that for $T_y=\inf\{n\geq 1:X_n=y\}$ $$ \Pi^n(x,y)=\sum_{k=1}^{n}P_x(T_y=k)\Pi^{n-k}(y,y) $$ for any $x\in E$. Clearly, this uses somehow the strong Markov property. I tried induction; but it wasn't fruitful.

Answer 1

Clearly,

$$\mathbb{P}_x(X_n = y) = \mathbb{P}_x(X_n = y, T_y \leq n) = \sum_{k=1}^n \mathbb{P}_x(X_n = y, T_y = k). \tag{1}$$

If we denote by $(\mathcal{F}_n)_{n \in \mathbb{N}}$ the canonical filtration, then by the tower property

$$\mathbb{P}_x(X_n = y, T_y = k) = \mathbb{P}_x \bigg[ \mathbb{P}_x(X_n = y, T_y = k \mid \mathcal{F}_k) \bigg].$$

Since $\{T_y = k\} \in \mathcal{F}_k$ this implies

$$\mathbb{P}_x(X_n = y, T_y = k) = \mathbb{P}_x \bigg[ 1_{\{T_y=k\}} \mathbb{P}_x(X_n = y \mid \mathcal{F}_k) \bigg].$$

Using the Markov property we get

$$\begin{align*} \mathbb{P}_x(X_n = y, T_y = k) = \mathbb{P}_x \bigg[ 1_{\{T_y=k\}} \mathbb{P}_{X_k}(X_{n-k} = y) \bigg] &= \mathbb{P}_x \bigg[ 1_{\{T_y=k\}} \mathbb{P}_{y}(X_{n-k} = y) \bigg] \\ &= \Pi^{n-k}(y,y) \mathbb{P}_x(T_y=k). \end{align*}$$

Plugging this into $(1)$, proves the assrtion.