# Stopping time intuition

Let $(X_n)_{n \geq 1}$ be independent and identically distributed random variables with $P(X_n=1)=P(X_n=-1)=\frac {1}{2}$ for all $n \geq 1$ and let $S_n = X_1+X_2+ \cdots +X_n$. If we define a stopping time $T=min\{n:S_n=X_1+X_2+ \cdots + X_n=1\}$, we obviously have $E[S_T]=1$ and Wald's identity forces $E[T]= \infty$ because otherwise it would be that $E[S_T]=E[T]E[X_1]=0$.

Could someone explain the intuition behind this result? Why is $E[T]$ infinite? It seems very counter-intuitive.

If the events $T>n$ occur a lot (i.e. not only they occur but also the number of occurrences compensates the how small their probabilities are) then this pushes the expected value to be large.

Now notice that $T=2n+1$ can occur for many sequences $-1,1,-1,...$.

You can think of $-1$ as an opening parenthesis and $1$ as a closing parenthesis. We can count how many proper configurations of parentheses are there of length $2n$. For each of them we add a $1$ (a closing parenthesis) at the end and this corresponds to an event in which $T=2n+1$. The number of parenthesis configurations is the Catalan number $C_{n}\sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$. The probability of each of these events is $2^{-2n-1}$ and the value of $T=2n+1$. In the expectation $E[T]$ these three numbers appear multiplying as terms of a sum/integral.

Let's multiply

$$(2n+1)C_nP(T=2n+1)\sim(2n+1)\frac{4^{n}}{n^{3/2}}2^{-2n-1}\sim \frac{1}{n^{1/2}}$$

but $$\sum \frac{1}{n^{1/2}}=\infty.$$

In retrospective, I guess that expectation being infinite is as counter-intuitive as the fact that the series $$\sum \frac{1}{\sqrt{n}}$$ is divergent.

• Thanks! That was very helpful! I was beginning to suspect a divergent series. – Nocturne Nov 20 '14 at 23:59

Since the random walk does not have any lower barrier, it can go all the way down to, say $-1000$, with ups and downs. We therefore expect the stopping time to be very, very long.

• This is a good start for the intuition. One needsto be careful, though. Notice that even if the random variable can take arbitrarily large values, if the probabilities of the corresponding events are small we can still have finite expectation. Compare, for example, the time a Brownian motion, starting at $0$, takes to exit the interval $[-1,1]$. There are trajectories that take arbitrarily long time, but still the expected value of this time is finite. – user194228 Nov 21 '14 at 2:01