# Proving a non-stopping time

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$?

• 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. Sep 9 '12 at 13:49
• @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. 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$.

• This is rather more advanced than my class, but after looking up some terms, you have taught me quite a lot. +1 Sep 9 '12 at 19:45
• 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$.
– Did
Sep 15 '12 at 4:50
• 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. Sep 15 '12 at 5:50
• 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.
– Did
Sep 15 '12 at 7:18
• 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" Sep 15 '12 at 9:54