5.2 Martingale and Random walk

Random walk: The process $\{S_n;n\ge1\}$ is called a random walk if $\{X_i;i\ge1\}$ are IID (identical and independently distributed) random variables and $S_n=X_1+\cdots X_n$, where $n=1,2,\cdots$. The term comes from the fact that we can think of $S_n$ as the position at time $n$ for a walker who makes successive random steps $X_1,X_2,\cdots$

If $X_i$ takes values 1 and -1 with probabilities $p$ and $1-p$ respectively, $S_n$ is called a simple random walk with parameter $p$. Furthermore, if $p=\frac12$, the process $S_n$ is a symmetric random walk. For symmetric random walk, it’s easy to show that $E[S_n]=0$ and $\operatorname{var}(S_n)=E[S_n^2]-E[S_n]^2=E[S_n^2]=n$.⁵

Symmetric random walk is the process that is most often tested in quantitative interviews. The interview questions on random walk often revolve around finding the first $n$ for which $S_n$ reaches a defined threshold $\alpha$, or the probability that $S_n$ reaches $\alpha$ for any given value of $n$.

Martingale: a martingale $\{Z_n;n\ge1\}$ is a stochastic process with the properties that $E[|Z_n|]\lt\infty$ for all $n$ and $E[Z_{n+1}\mid Z_n=z_n,Z_{n-1}=z_{n-1},\cdots,Z_1=z_1]=z_n$. The property of a martingale can be extended to $E[Z_m;m>n\mid Z_n=z_n,Z_{n-1}=z_{n-1},\cdots,Z_1=z_1]=z_n$, which means the conditional expected value of future $Z_m$ is the current value $Z_n$.⁶

A symmetric random walk is a martingale. From the definition of the symmetric random walk we have $\displaystyle S_{n+1}=\begin{cases}S_n+1&\text{with probability }1/2\\S_n-1&\text{with probability }1/2\end{cases}$, so $E[S_{n+1}\mid S_n=s_n,\cdots,S_1=s_1]=s_n$. Since $E[S_{n+1}^2-(n+1)]=\frac12[(S_n+1)^2+(S_n-1)^2]-(n+1)=S_n^2-n$, $S_n^2-n$ is a martingale as well.

Stopping rule: For an experiment with a set of IID random variables $X_1,X_2,\cdots$, a stopping rule for $\{X_i;i\ge1\}$ is a positive integer-value random variable $N$ (stopping time) such that for each $n>1$, the event $\{N\le n\}$ is independent of $X_{n+1},X_{n+2},\cdots$. Basically it says that whether to stop at $n$ depends only on $X_1,X_2,\cdots,X_n$ (i.e., no look ahead).

Wald’s Equality: Let $N$ be a stopping rule for IID random variables $X_1,X_2,\cdots$ and let $S_N=X_1+X_2+\cdots+X_N$, then $E[S_N]=E[X]E[N]$.

Since it is an important—yet relatively little known—theorem, let’s briefly review its proof. Let $I_n$ be the indicator function of the event $\{N\ge n\}$. So $S_N$ can be written as

$\displaystyle S_N=\sum_{n=1}^{\infty}X_nI_n$, where $I_n=1$ if $N\ge n$ and $I_n=0$ if $N\le n-1$.

From the definition of stopping rules, we know that $I_n$ is independent of $X_n,X_{n+1},\cdots$ (it only depends on $X_1,X_2,\cdots,X_{n-1}$). So $E[X_nI_n]=E[X_n]E[I_n]=E[X]E[I_n]$ and

A martingale stopped at a stopping time is a martingale.

Drunk man

A drunk man is at the 17th meter of a 100-meter-long bridge. He has a 50% probability of staggering forward or backward one meter each step. What is the probability that he will make it to the end of the bridge (the 100th meter) before the beginning (the 0th meter)? What is the expected number of steps he takes to reach either the beginning or the end of the bridge?

Solution: The probability part of the problem—often appearing in different disguises—is among the most popular martingale problems asked by quantitative interviewers. Interestingly, few people use a clear-cut martingale argument. Most candidates either use Markov chain with two absorbing states or treat it as a special version of the gambler’s ruin problem with $p=1/2$. These approaches yield the correct results in the end, yet a martingale argument is not only simpler but also illustrates the insight behind the problem.

Let’s set the current position (the 17th meter) to 0; then the problem becomes a symmetric random walk that stops at either 83 or -17. We also know that both $S_n$ and $S_n^2-n$ are martingales. Since a martingale stopped at a stopping time is a martingale, $S_N$ and $S_N^2-N$ (where $S_N=X_1+X_2+\cdots+X_N$ with $N$ being the stopping time) are martingales as well. Let $p_\alpha$ be the probability that it stops at $\alpha=83$, $p_\beta$ be the probability it stops at $-\beta=-17$ ($p_\beta=1-p_\alpha$), and $N$ be the stopping time. Then we have

Hence, the probability that he will make it to the end of the bridge (the 100th meter) before reaching the beginning is 0.17, and the expected number of steps he takes to reach either the beginning or the end of the bridge is 1441.

We can easily extend the solution to a general case: a symmetric random walk starting from 0 that stops at either $\alpha$ ($\alpha>0$) or $-\beta$ ($\beta>0$). The probability that it stops at $\alpha$ instead of $-\beta$ is $p_\alpha=\beta/(\alpha+\beta)$. The expected stopping time to reach either $\alpha$ or $-\beta$ is $E[N]=\alpha\beta$.

Dice game

Suppose that you roll a dice. For each roll, you are paid the face value. If a roll gives 4, 5 or 6, you can roll the dice again. If you get 1, 2 or 3, the game stops. What is the expected payoff of this game?

Solution: In Chapter 4, we used the law of total expectation to solve the problem. A simpler approach—requiring more knowledge—is to apply Wald’s Equality since the problem has clear stopping rules. For each roll, the process has 1/2 probability of stopping. So the stopping time $N$ follows a geometric distribution with $p=1/2$ and we have $E[N]=1/p=2$. For each roll, the expected face value is $E[X]=7/2$. The total expected payoff is $E[S_N]=E[X]E[N]=7/2\times2=7$.

Ticket line

At a theater ticket office, $2n$ people are waiting to buy tickets. $n$ of them have only $5 bills and the other $n$ people have only $10 bills. The ticket seller has no change to start 118 with. If each person buys one $5 ticket, what is the probability that all people will be able to buy their tickets without having to change positions?

Solution: This problem is often considered to be a difficult one. Although many can correctly formulate the problem, few can solve the problem using the reflection principle.⁸ This problem is one of the many cases where a broad knowledge makes a difference.

Assign $+1$ to the $n$ people with $5 bills and $-1$ to the $n$ people with $10 bills. Consider the process as a walk. Let $(a,b)$ represent that after $a$ steps, the walk ends at $b$. So we start at $(0,0)$ and reaches $(2n,0)$ after $2n$ steps. For these $2n$ steps, we need to choose $n$ steps as $+1$, so there are $\displaystyle\binom{2n}{n}=\frac{2n!}{n!n!}$ possible paths. We are interested in the paths that have the property $b\ge0,\ \forall0\lt a\lt2n$ steps. It’s easier to calculate the number of complement paths that reach $b=-1,\ \exists0\lt a\lt2n$. As shown in Figure 5.6, if we reflect the path across the line $y=-1$ after a path first reaches -1, for every path that reaches $(2n,0)$ at step $2n$, we have one corresponding reflected path that reaches $(2n,-2)$ at step $2n$. For a path to reach $(2n,-2)$, there are $(n-1)$ steps of $+1$ and $(n+1)$ steps of $-1$. So there are $\displaystyle\binom{2n}{n-1}=\frac{2n!}{(n-1)!(n+1)!}$ such paths. The number of paths that have the property $b=-1,\ \exists0\lt a\lt2n$, given that the path reaches $(2n,0)$ is also $\binom{2n}{n-1}$ and the number of paths that have the property $b\ge0,\ \forall0\lt a\lt2n$ is

Hence, the probability that all people will be able to buy their tickets without having to change positions is $1/(n+1)$.

Coin sequence

Assume that you have a fair coin. What is the expected number of coin tosses to get $n$ heads in a row?

Solution: Let $E[f(n)]$ be the expected number of coin tosses to get $n$ heads in a row. In the Markov chain section, we discussed the case where $n=3$ (to get the pattern $HHH$). For any integer $n$, we can consider an induction approach. Using the Markov chain approach, we can easy get that $E[f(1)]=2$, $E[f(2)]=6$ and $E[f(3)]=14$. A natural guess for the general formula is that $E[f(n)]=2^{n+1}-2$. As always, let’s prove the formula using induction. We have shown the formula is true for $n=1,2,3$. So we only need to prove that if $E[f(n)]=2^{n+1}-2$, $E[f(n+1)]=2^{n+2}-2$. The following diagram shows how to prove that the equation holds for $E[f(n+1)]$:

The state before $(n+1)$ heads in a row (denoted as $(n+1)H$) must be $n$ heads in a row (denoted as $nH$). It takes an expected $E[f(n)]=2^{n+1}-2$ tosses to reach $nH$. Conditioned on state $nH$, there is a 1/2 probability it will go to $(n+1)H$ (the new toss yields $H$) and the process stops. There is also a 1/2 probability that it will go to the 120 starting state 0 (the new toss yields $T$) and we need another expected $E[f(n+1)]$ tosses to reach $(n+1)H$. So we have

General Martingale approach: Let’s use $HH\cdots H_n$ to explain a general approach for the expected time to get any coin sequence by exploring the stopping times of martingales.⁹ Imagine a gambler has $1 to bet on a sequence of $n$ heads ($HH\cdots H_n$) in a fair game with the following rule: Bets are placed on up to $n$ consecutive games (tosses) and each time the gambler bets all his money (unless he goes bankrupt). For example, if $H$ appears at the first game, he will have $2 and he will put all $2 into the second game. He stops playing either when he loses a game or when he wins $n$ games in a roll, in which case he collects $$2^n$ (with probability $1/2^n$). Now let’s imagine, instead of one gambler, before each toss a new gambler joins the game and bets on the same sequence of $n$ heads with a bankroll of $1 as well. After the $i$-th game, $i$ gamblers have participated in the game and the total amount of money they have put in the game should be $$i$. Since each game is fair, the expected value of their total bankroll is $$i$ as well. In other words, if we denote $x_i$ as the amount of money all the participating gamblers have after the $i$-th game, then $(x_i-i)$ is a martingale.

Now, let’s add a stopping rule: the whole game will stop if one of the gamblers becomes the first to get $n$ heads in a roll. A martingale stopped at a stopping time is a martingale. So we still have $E[(x_i-i)]=0$. If the sequence stops after the $i$-th toss ($i\ge n$), the $(i-n+1)$-th player is the (first) player who gets $n$ heads in a roll with payoff $2^n$. So all the $(i-n)$ players before him went bankrupt; the $(i-n+2)$-th player gets $(n-1)$ heads in a roll with payoff $2^{n-1}$; …; the $i$-th player gets one head with payoff 2. So the total payoff is fixed and $x_i=2^n+2^{n-1}+\cdots+2^1=2^{n+1}-2$.

Hence, $E[(x_i-i)]=2^{n+1}-2-E[i]=0\Rightarrow E[i]=2^{n+1}-2$.

This approach can be applied to any coin sequences—as well as dice sequences or any sequences with arbitrary number of elements. For example, let’s consider the sequence $HHTTHH$. We can again use a stopped martingale process for sequence $HHTTHH$. The gamblers join the game one by one before each toss to bet on the same sequence $HHTTHH$ until one gambler becomes the first to get the sequence $HHTTHH$. If the sequence stops after the $i$-th toss, the $(i-5)$th gambler gets the $HHTTHH$ with payoff 121 $2^6$. All the $(i-6)$ players before him went bankrupt; the $(i-4)$th player loses in the second toss ($HT$); the $(i-3)$th player and the $(i-2)$th player lose in the first toss ($T$); the $(i-1)$th player gets sequence $HH$ with payoff $2^2$ and the $i$-th player gets $H$ with payoff 2.

Hence, $E[(x_i-i)]=2^6+2^2+2^1-E[i]=0\Rightarrow E[i]=70$.