Let $\{X_n\}_{n=0}^{\infty}$ be a Discrete Time Markov Chain (DTMC) with finite state space $X$. For any state $y \in X$ we define $Ty := \inf\{n \ge 1 \mid X_n = y\}$.
Let $p(n)(x, y)$ denote the $n$-step transition probability of going from state $x$ to $y$. For $n \ge $1, let $$f(n)(x, y) := P r(Ty = n\mid X_0 = x).$$ Prove that for all $n \ge 1$ and all $x, y \in X$, $p(n)(x, y) = $$\sum_{k=0}^n f(k) (x, y)p(n−k) (y, y)$
I don't understand how to start with the proof.
We have:
$p(n)(x,y)=P(X_n=y|X_0=x)$
So if $X_n=y$ this means that the first time that $X$ hits $y$ shall be before $n$. Told another way $Ty|_{X_0=x} \le n$. Worst case scenario, it hits $y$ after $n$ steps.
We can than split (law of total probability) using the partition $\{Ty=k\}$:
$P(X_n=y|X_0=x)=\sum_{k=0}^nP(X_n=y|X_0=x,Ty=k)P(Ty=k|X_0=x)$
Than we recognize:
$P(Ty=k|X_0=x)=f(k)(x,y)$
and:
$P(X_n=y|X_0=x,Ty=k)=P(X_n=y|X_k=y)=p(n-k)(y,y)$