If $τ_x^k$ is the time of the $k$-th entrance of a Markov chain into $x$, then $\text P_x[τ_y^k<∞]=\text P_x[τ_y^1<∞](\text P_y[τ_y^1<∞])^{k-1}$ Let


*

*$E$ be at most countable and equipped with the discrete topology and $\mathcal E$ be the Borel $\sigma$-algebra on $E$

*$X=(X_n)_{n\in\mathbb N_0}$ be a discrete Markov chain with values in $(E,\mathcal E$) and distributions $(\operatorname P_x)_{x\in E}$

*$\tau_x^0:=0$ and $$\tau_x^k:=\inf\left\{n>\tau_x^{k-1}:X_n=x\right\}$$ for $x\in E$ and $k\in\mathbb N$


Let $$\varrho(x,y):=\operatorname P_x\left[\tau_y^1<\infty\right]\color{blue}{=\operatorname P_x\left[\exists n\in\mathbb N:X_n=y\right]}\;.$$
I want to prove, that $$\operatorname P_x\left[\tau_y^k<\infty\right]=\varrho(x,y)\varrho(y,y)^{k-1}\;\;\;\text{for all }k\in\mathbb N\tag 1$$ using the strong Markov property: $$\operatorname E_x\left[f\circ (X_{\tau+t})_{t\in \mathbb N_0}\mid\mathcal F_\tau\right]=\operatorname E_{X_\tau}\left[f\circ X\right]\tag 2$$ for all $x\in E$, $\sigma(X)$-stopping times $\tau$ and bounded, $\mathcal E^{\otimes\mathbb N_0}$-measurable $f:E^{\mathbb N_0}\to\mathbb R$.

I want to prove $(1)$ by induction over $k\in\mathbb N$. Since, $k=1$ is trivial, we only need to care about $k-1\to k$. Since $$\left\{\tau_y^{k-1}<\infty\right\}\cap\left\{\tau_y^k<\infty\right\}=\left\{\tau_y^k<\infty\right\}$$ and $$\left\{\tau_y^{k-1}<\infty\right\}\in\mathcal F_{\tau_y^{k-1}}\;,$$ we've got $$\operatorname P_x\left[\tau_y^k<\infty\right]=\operatorname E_x\left[1_{\left\{\tau_y^{k-1}<\infty\right\}}\color{red}{\operatorname P_x\left[\tau_y^k<\infty\mid\mathcal F_{\tau_y^{k-1}}\right]}\right]\;,\tag 4$$ by definition of the conditional expectation. Now, I think, that we somehow need to apply $(2)$ with $\tau=\tau_y^{k-1}$ to the $\color{red}{\text{red}}$ term in order to obtain $$\operatorname E_x\left[1_{\left\{\tau_y^{k-1}<\infty\right\}}\color{red}{\operatorname P_x\left[\tau_y^k<\infty\mid\mathcal F_{\tau_y^{k-1}}\right]}\right]=\operatorname E_x\left[1_{\left\{\tau_y^{k-1}<\infty\right\}}\varrho(y,y)\right]\;,$$ but I can't figure out how I need to choose $f$.
 A: In order to use the strong Markov property $(2)$ at time $\tau:=\tau_y^{k-1}$, we need to find a bounded, $\mathcal E^{\otimes\mathbb N_0}$-measurable function $f:E^{\mathbb N_0}\to\mathbb R$ with $$f\circ\tilde X=1_{\left\{\tau^+<\infty\right\}}\;,$$ where $\tilde X:=\left(X_{\tau+n}\right)_{n\in\mathbb N_0}$ and $\tau^+:=\tau_y^k$. Since
\begin{equation}
\begin{split}
\left\{\tau^+<\infty\right\}&=&\left\{\exists n>\tau:X_n=y\right\}\\
&=&\left\{\exists n\in\mathbb N:\tilde X_n=y\right\}\\
&=&\left\{\exists n\in\mathbb N:\pi_n\circ\tilde X=y\right\}\;,
\end{split}
\end{equation}
where $\pi_n:E^{\mathbb N_0}\to E$ denotes the $n$-th coordinate map, we can choose $f$ to be the indicator function of $$\bigcup_{n\in\mathbb N}\left\{\pi_n=y\right\}\;.$$
Noting that $f\circ X$ is the indicator function of $$\bigcup_{n\in\mathbb N}\left\{X_n=y\right\}=\left\{\tau_y^1<\infty\right\}$$ and $X_\tau=y$ on $\left\{\tau<\infty\right\}$, we're now able to conclude, that
\begin{equation}
\begin{split}
\operatorname E_x\left[1_{\left\{\tau<\infty\right\}}\operatorname E_x\left[f\circ\tilde X\mid\mathcal F_{\tau}\right]\right]&\stackrel{(2)}=&\;\operatorname E_x\left[1_{\left\{\tau<\infty\right\}}\operatorname E_{X_\tau}\left[f\circ X\right]\right]\\
&=&\;\operatorname E_x\left[1_{\left\{\tau<\infty\right\}}\operatorname P_{X_\tau}\left[\tau_y^1<\infty\right]\right]\\
&=&\;\operatorname E_x\left[1_{\left\{\tau<\infty\right\}}\operatorname P_y\left[\tau_y^1<\infty\right]\right]\\
&\stackrel{\text{def}}=&\;\operatorname E_x\left[1_{\left\{\tau<\infty\right\}}\varrho(y,y)\right]\\
&=&\;\varrho(y,y)\operatorname P_x\left[\tau<\infty\right]\\
&\stackrel{\text{IH}}=&\;\varrho(y,y)\varrho(x,y)\varrho(y,y)^{k-2}\;.
\end{split}
\end{equation}
