# 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$.

• Yup.    – Did Oct 2 '15 at 12:38
• $$f\circ (X_{t})_{t\in \mathbb N_0}=1_{\left\{\tau_y^{1}<\infty\right\}}$$ – Did Oct 2 '15 at 13:16
• Yes I am sure... Actually, either you apply "my" $f$ at time $\tau^{k-1}_y$, or you apply "your" $f$ at time $\tau^{1}_y$. – Did Oct 2 '15 at 16:30
• Sorry but this cannot go on forever... "Can you provide an answer?" I did. – Did Oct 2 '15 at 17:33
• No mistake, as I said there are two possible solutions. – Did Oct 3 '15 at 10:52

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{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}$$ 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{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}$$