Random Walk Stopping Time Using a Simple Martingale

January 14, 2019 -
math simulation

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
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.