Let me begin by first confirming that this is indeed the correct place to post this (other ideas I had were math.SE). That said,

Let $X_n$ be a Markov chain on the state space $\mathcal S$ and for $ y \in \mathcal S$ let $T_y = \min\{ n \ge 1 : X_n =y\}$ be the first return time to $y$. Let $W_y = T_y - 1$ be the time just before the first return to $y$

  • Explain why $W_y$ is not a stopping time

  • Show that the Strong Markov Property does not apply to $X_n$ at random time $W_y$.

My Work

When showing that $W_y$ is not a stopping time, is it sufficient to write $$W_y = \bigcap_{i = 1}^{n-1} \{X_i \ne y\} \cap X_n = y$$ and claim that since $X_n$ does not belong to the set $\{X_0, X_1, \dots, X_{n-1}\}$, we have that $W_y$ is not a stopping time?

Then, for showing that the Strong Markov Property does not apply, can I write $$\mathbf{P}(X_n = y \mid W_y = n-1, X_{n-1} = i, X_{n-2} = x_{n-2}, \dots, X_0 = y) = 1 \ne p(i, y)$$ where $p(i,y)$ is the one step transition probability from $i$ to $y$?

  • $\begingroup$ This question is on-topic both here and math.SE. It may receive slightly more attention on the math site. Is $\mathcal S$ countable? That seems to be an implicit assumption here. $\endgroup$ – cardinal Sep 9 '12 at 13:49
  • 1
    $\begingroup$ @cardinal Yes, this is my first Applied Stochastic Processes class so any assumptions I'm not being explicit stem from my inexperience with this subject. W/r/t your specific question, $|\mathcal{S}| = |\Bbb N|$ so $\mathcal{S}$ is indeed countable. $\endgroup$ – Moderat Sep 9 '12 at 16:17

First question. Denoting by $({\cal F}_n)$ the filtration generated by the process $(X_n)$ we will prove that the event $A:=\{W_y= 1\}$ does not belong to the $\sigma$-field ${\cal F}_1$. This implies that $W_y$ is not a stopping time. One has $A=\{X_1 \neq y\} \cap \{X_2=y\}$. If $A$ did belong to ${\cal F}_1$ then one would have $\Pr(A \mid {\cal F}_1)={\boldsymbol 1}_A$. But one has $\Pr(A \mid {\cal F}_1) = p(X_1,y){\boldsymbol 1}_{X_1 \neq y}$.

Second question. The process $(X_{W+k})_{k \geq 0}$ is Markovian but does not share the same Markov transition as the process $(X_n)$. Indeed, putting $Y_k=X_{W+k}$, the conditional distribution of $Y_1$ given $Y_0$ is the Dirac distribution at $y$. Hence the strong Markov property of $(X_n)$ does not apply for the random time $W$.

  • $\begingroup$ This is rather more advanced than my class, but after looking up some terms, you have taught me quite a lot. +1 $\endgroup$ – Moderat Sep 9 '12 at 19:45
  • 1
    $\begingroup$ Of course this proof is valid in the generic case. But it may happen that for some $x$, $X_2=y$ never happens, then $[W_y=1]=\varnothing$ hence, with respect to $\Pr_x$, the event $[W_y=1]$ does belong to $\mathcal F_1$. $\endgroup$ – Did Sep 15 '12 at 4:50
  • $\begingroup$ Thanks @did. That's true, in fact we are looking for a counter-example and we should define a specific Markov chain for which the stopping-time property fails to be true. $\endgroup$ – Stéphane Laurent Sep 15 '12 at 5:50
  • $\begingroup$ Not sure I understand your comment but if one looks for an example where no W_y is a stopping time, then the simpler the better, hence, you could try (X_n) i.i.d. uniform on a finite set. $\endgroup$ – Did Sep 15 '12 at 7:18
  • $\begingroup$ You have understood my comment: I meant it is more clear to prove that $W_y$ is not a stopping time for an example (such as your example) instead of proving that $W_y$ is not a stopping time for the "generic case" $\endgroup$ – Stéphane Laurent Sep 15 '12 at 9:54

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.