# Random Walk Stopping Time Using a Simple Martingale

January 14, 2019 -

Random walks are simple processes used to describe many real world phenomena such as gambling and the stock market. The underlying mechanism is straightfoward: at round $n$, we have a random variable $Y_n$ which takes the value $+1$ or $-1$ with probability $p$ and $1-p$. Here we will consider symmetric random walks with $p = 1/2$, corresponding to a fair game.

If we let $X_n = \sum\limits_{i=0}^n Y_i$, a natural question to consider is:

Starting at $0$ and given some finite interval $]-a, b[$ how long will the random walk stay contained within this interval?

As an example, consider a game in which we quit once we have either lost $a$ dollars or won $b$ dollars. If we win or lose $1 on each round with equal probability, how long do we expect to play this game? We can simulate such a game below. a = 2 Play b = 2 One way to answer this question is through the use of martingales. In order for$X_n$to be a martingale we must have$\forall n$: •$E(|X_n|) < \infty$•$E(X_{n+1} | X_0, \ldots, X_n) = X_n$Clearly, for$X_n$describing our random walk, both conditions are true since$|X_n| \le n$and One nice property of a martingales is that we have$E(X_n) = E(X_0)$by the law of total expectation. Using the given parametization for the random walk does not shed any light on how long we should expect it take to exit the interval$]-a, b[$. However, if we reformulate our random walk as a game between two parties, we can describe it as two random variables$A_n = a + X_n$and$B_n = b -X_n$where$A_n$and$B_n$describe the amount of money each party has after$n$rounds when each starts with$-a$and$b$dollars, respectively. Then, asking the question of when$X_n$exits$]-a, b[$is equivalent to asking when$A_n = 0$or$B_n = 0$. We can formalize this question using the notion of a stopping time where we define$\tau$as and consider$E(\tau)$. The trick to answering this question comes from observing that$A_nB_n + n$is also a martingale since$\forall n$It turns out that even though$\tau$is a random quantity, under certain conditions, we have$E(X_\tau) = E(X_0)$by the optional stopping theorem. In the case of our random walk,$E(\tau) < \infty$and$E(|X_n - X_{n+1}||X_0,\ldots,X_n)\le c$are sufficient for the optional stopping theorem to hold. Applying this to the martingale$A_nB_n + n$, and we have and thus we conclude that the long-term average of the time for our random walk to exit the interval$]-a, b[$is simply$ab\$.

The simulation below confirms this fact.

a = 2
Simulate one game
Simulate 50 games
b = 2

The code for the D3.js simulations can be found on Github.