# If $(X_n)$ is simple random walk and $M_n=\max\limits_{0\leq k \leq n}X_k$ then $\tau_N = \min\{ n\mid X_n = M_N\}$ is not a stopping time

Let $(X_n)_{n\in\mathbb N}$ denote a simple, symmetric, random walk, defined by $X_0=0$ and $X_n = \sum\limits_{j=1}^n\xi_j$ where $(\xi_i)_{i \in \mathbb N}$ is i.i.d. with $\mathbb{P}(\xi_i = 1)= \mathbb{P}(\xi_i = -1) = \frac{1}{2}$. The maximum process of $(X_n)_{n\in\mathbb N}$ is defined by $M_n=\max\limits_{0\leq k \leq n} X_k$. I want to show that $$\tau = \min\{ n \in \mathbb{N} :X_n = M_{100}\}$$ is not a stopping time with respect to the natural filtration $\mathcal{(F_n)}_{n\in \mathbb{N}}$ of $(X_n)_{n\in\mathbb N}$.

I know why it isn't a stopping time, but I don't know how to write a formal proof.

Why I think it isn't a stopping time, is that $$\{ \tau = t\} = \{ X_0 \neq \max\limits_{0\leq k \leq 100} X_k\} \cap \{X_1 \neq \max\limits_{0\leq k \leq 100} X_k \}\cap \dots \cap \{ X_t = \max\limits_{0\leq k \leq 100} X_k\}$$ If it was a stopping time, then $\{ \tau = t\}$ must be in $\mathcal{F_t}$.

But if $t<100$ , then we still need the information on all $X_{t+1} \dots X_{100}$ which are not in $\mathcal{F_t}$.

Is my idea correct? How to prove it mathematically?

If $\tau$ was a stopping time, then by the optional stopping theorem

$$\mathbb{E}(X_{n \wedge \tau})=0 \qquad \text{for all n \geq 1}.$$

As $|X_{n \wedge \tau}| \leq 100$ this would imply by the dominated convergence theorem that

$$\mathbb{E}(X_{\tau})=0.$$

This, however, contradicts the fact that by the very definition of $\tau$

$$\mathbb{E}(X_{\tau}) = \mathbb{E}(M_{100})>0.$$

• Why the domination $|X_{n \wedge \tau}| \leq 100$? – Did Jul 9 '17 at 20:57
• @Did Clearly, $\tau \leq 100$ and so $$|X_{n \wedge \tau}| \leq \sum_{i=1}^{n \wedge \tau} \underbrace{|\xi|}_{= 1} \leq 100.$$ – saz Jul 10 '17 at 5:10
• Right, thanks.  – Did Jul 10 '17 at 5:28

Fix $1\leqslant t<T$ and consider the atom $A=\{\forall k\in[t],\xi_k=+1\}$ where $[t]=\{1,2,\ldots,t\}$.

Then $A$ is in the sigma-algebra $\mathcal F_t=\sigma(X_k;k\in[t])=\sigma(\xi_k;k\in[t])$ and $A\subseteq\{M_t=X_t\}$. Furthermore, $\{\tau_T=t\}\cap A=\{M^{(t)}_T\leqslant0\}\cap A$ where $M^{(t)}_T=\max\{X_v-X_t\mid t\leqslant v\leqslant T\}$. Then $M^{(t)}_T$ is measurable with respect to $\mathcal G^{(t)}_T=\sigma(\xi_k;k\in[T]\setminus[t])$ and $\mathcal F_t$ and $\mathcal G^{(t)}_T$ are independent hence $P(\tau_T=t,A)=P(\tau_T=t)P(A)$.

Since $0<P(\tau_T=t)<1$ and every event in $\mathcal F_t$ is a finite union of atoms $\{\forall k\in[t],\xi_k=x_k\}$ with $(x_k)_{k\in[t]}$ in $\{-1,1\}^t$, every event $C$ in $\mathcal F_t$ such that $C\subseteq A$ is such that $P(C)=0$ or $P(C)=P(A)$.

Thus, $\{\tau_T=t\}\cap A$ is not in $\mathcal F_t$ although $A$ is in $\mathcal F_t$, as desired to show that $\tau$ is not an $(\mathcal F_t)$-stopping time.

• Thank you for the answer. I would like to know if there is another way to prove this without using the properties of an atom, because in measure theory we didn't learn anything about atoms. – SaMath Jul 9 '17 at 20:02
• @SaMath Sorry but I do not understand your comment. Are you not letting yourself be frightened by a simple word? Atoms are what the name suggests, that is, $A$ is an atom for $P$ if $P(A)>0$ and if every event $B\subseteq A$ is such that $P(B)=0$ or $P(B)=P(A)$. – Did Jul 9 '17 at 20:59