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

  • 2
    $\begingroup$ Yup. $ $ $ $ $ $ $\endgroup$ – Did Oct 2 '15 at 12:38
  • 1
    $\begingroup$ $$f\circ (X_{t})_{t\in \mathbb N_0}=1_{\left\{\tau_y^{1}<\infty\right\}}$$ $\endgroup$ – Did Oct 2 '15 at 13:16
  • 1
    $\begingroup$ 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$. $\endgroup$ – Did Oct 2 '15 at 16:30
  • 1
    $\begingroup$ Sorry but this cannot go on forever... "Can you provide an answer?" I did. $\endgroup$ – Did Oct 2 '15 at 17:33
  • 1
    $\begingroup$ No mistake, as I said there are two possible solutions. $\endgroup$ – 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{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}

  • $\begingroup$ You guy made me feel dumb about maths. $\endgroup$ – off99555 Oct 3 '15 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.