Martingales

Colloquially, a stochastic process is a martingale if ‘we expect the next step to be right where we are.’ In other words, martingales are stochastic processes which ‘stay the same on average’.

Definition Mathematically, we say that a stochastic process \(S_n\) for \(n\ge 1\) is a martingale with respect to the sequence \(X_1, X_2, \ldots\) if for all \(n\ge 1\)

  1. \(E|S_n|<\infty\).

  2. \(E(S_{n+1}\ |\ X_1, X_2, \ldots ,X_n)=S_n\).

Warning Note Conditional expectations are ubiquitous in this lecture. They are random variables, and formulas as \(E(X\ |\ Y)=Z\) hold only ‘almost surely’ (with probability 1).

So, at any time \(n\), a stochastic process is a martingale if, conditioning on the entire observed history of the stochastic process up to time \(n\) (this is often called the filtration), the expected value of the next step \(X_{n+1}\) is just \(X_n\) (which has already been observed, since we are at time \(n\)).

Let \(X_n\) be a player’s fortune at stage \(n\) of a game. The martingale property captures the notion of a game being fair in that the player’s fortune on teh next play is, on the average, his current fortune and is not otherwise affected by the previous history. In fact, the name martingale derives from a French acronym for the gambling strategy of doubling ones bets until a win is secured. See Example~2 below.

Examples

  1. Simple Random Walk

A particle jumps either one step to the right or one step to the left, with corresponding probabilities \(p\) and \(q=1-p\). Assuming the ususl independence of different moves, it is clear that the position \(S_n=X_1+X_2+\ldots +X_n\) of the particle after \(n\) steps satisfies \(E|S_n|\le n\) and \[ E(S_{n+1}\ |\ X_1, X_2, \ldots, X_n)=S_n+(p-q). \] Consider \(Y_n=S_n-n(p-q)\). We have \[ E(Y_{n+1}\ |\ X_1,\ldots ,X_n)=E(S_{n+1}-(n+1)(p-q)\ |\ X_1, \ldots ,X_n)\\ =S_n+(p-q)-(n+1)(p-q)=S_n-n(p-q)=Y_n. \] Thus, \(Y_n\) is a martingale.

Exercise 13

Let \(X_1, X_2, \ldots\) be independent identically distributed random variables of which each can take the values -1 and +1 with probability 1/2. Show that the partial sums \[ Z_n=\sum_{j=1}^n \frac{1}{j} X_j \qquad n=1,2,\ldots \] form a martingale with respect to \(X_1, X_2, \ldots\).

Hint Show that \[ E\left( Z_n+\frac{1}{n+1}X_{n+1}\ |\ X_1, \ldots , X_n\right) =Z_n. \] Exercise 14

Let \(X_1, X_2, \ldots\) be independent random variables with means \(\mu_1, \mu_2, \ldots\), respectively. Let \[ Z_n= X_1+X_2+\ldots +X_n, \] and let \(Z_0=X_0=0\). Show that the random variable \[ Y_n=Z_n-\sum_{i=1}^n \mu_i \qquad n=1,2,\ldots \] is a martingale with respect to \(X_1, X_2, \ldots\).

Hint Note that \(E(Z_n\ |\ X_1, X_2, \ldots, X_n)=Z_n\).

  1. The Martingale

The following gambling strategy is called a martingale. A gambler has a large fortune. He wages 1 dollar on an event bet. If he loses then he wagers 2 dollars on the next bet. If he loses teh first \(n\) plays, then he bets \(2^n\) dollars on the \((n+1)\)th. He is bound to win sooner or later, say on the \(T\)th bet, at which point he ceases to play, and leaves with his profit of \(2^T-(1+2+4+\ldots + @^{T-1})\). Thus, following this strategy, he is assured an ultimate profit. This sounds like a good strategy.

Writing \(Y_n\) for the accumulated gain of the gambler after the \(n\)th play (losses count negative), we have that \(Y_0=0\) and (summing the geometric progression) \[ |Y_n|\le 1+2+\ldots +2^{n-1}=\frac{1-2^n}{1-2}=2^n-1. \] Furthermore, \(Y_{n+1}=Y_n\) if the gambler has stopped by time \(n+1\), and \[ Y_{n+1}= \left\{ \begin{array}{ll} Y_n-2^n & \mbox{with probability} \quad \frac{1}{2},\\ Y_n+2^n & \mbox{with probability }\quad \frac{1}{2}, \end{array} \right. \] implying that \(E(Y_{n+1}\ |\ Y_1, Y_2, \ldots , Y_n)=Y_n\). Therefore \(Y\) is a martingale.

This martingale possesses a particularly disturbing feature. The random time \(T\) has a geometric distribution, \(P(T=n)=\left(\frac{1}{2}\right)^n\) for \(n\ge 1\), so the mean loss of the gambler just before his ultimate win is \[ \sum_{n=1}^\infty \left(\frac{1}{2}\right)^n (1+2+\ldots +2^{n-1}), \] which equals infinity. Do not follow this strategy unless your initial capital is considerablly greater than that of the casino.

  1. De Moivre’s Martingale

About a century before the martingale was fashionable among Paris gamblers, Agraham de Moivre made use of a (mathematical) martingale to answer teh following gambler’s ruin question. A simple random walk on teh set \(\{0, 1, 2, \ldots , N\}\) stops when it first hits either of the absorbing barriers at 0 and at \(N\); what is the probability that it stops at the barrier 0? Write \(X_1, X_2, \ldots\) for the steps of the walk, and \(S_n\) for the position after \(n\) steps, where \(S_0=k\). Define \[ Y_n=\left(\frac{q}{p}\right)^{S_n}, \qquad \mbox{where}\quad p=P(X_i=1), \quad p+q=1, \quad 0<p<1. \] We claim that \[ E(Y_{n+1}\ |\ X_1, X_2, \ldots , X_n)=Y_n \qquad \mbox{for all}\ n. \] If \(S_n\) equals 0 or \(N\) then the process has stopped by time \(n\), implying that \(S_{n+1}=S_n\) and therefore \(Y_{n+1}=Y_n\). If, on the other hand \(0<S_n<N\), then $$ E(Y_{n+1} | X_1, X_2, , X_n)=E(()^{S_n+X_{n+1}} | X_1, X_2, , X_n)\ = ()^{S_n}=Y_n.

$$

Thus, the above claim is proved. It follows, by taking expectation of both sides, that \(E(Y_{n+1})=E(Y_n)\) for all \(n\), and hence \[ E|Y_n|=E|Y_0|=\left(\frac{q}{p}\right)^k \qquad \mbox{for all}\ n. \] In particular, \(Y\) is a martingale.

Let \(T\) be the number of steps before teh absorption of the particle at either 0 or \(N\). De Moivre argued as follows: \[ E(Y_n)=\left(\frac{q}{p}\right)^k \qquad \mbox{for all $n$ and therefore}\qquad E(Y_T)=\left(\frac{q}{p}\right)^k. \] If you are willing to accept this remark, then the answer to the original question is a simple consequence, as follows. Expanding \(E(Y_T)\), we have taht \[ E(Y_T)=\left(\frac{q}{p}\right)^0 p_k+\left(\frac{q}{p}\right)^N(1-p_k), \] where \[ p_k=(\mbox{absorbed at 0}\ |\ S_0=k). \] However, \(E(Y_T)=(q/p)^k\) by assumption, and therefore \[ p_k=\frac{\rho^k-\rho^N}{1-\rho^N}\qquad \mbox{where}\quad \rho=\frac{q}{p}, \] (so long as \(\rho\ne 1\)).

This is a very attractive method, which relies on the statement that \(E(Y_T)=E(Y_0)\) for a certain type of random variable \(T\). In our further applications of martingales, we will have to determine conditions on such random Variable \(T\) which ensure that the desired statements are true.

  1. Is our Bernoulli Process a martingale?

Well, since each step is independent, we have: \[ E(X_{n+1}\ |\ X_1, \ldots ,X_n)=E(X_{n+1}) \] and since \(X_{n+1}\sim Bern (\frac{1}{2})\), like all of the other steps, we have: \[ E(X_{n+1})=\frac{1}{2}. \] However, we know that \(X_n\) will either be 0 or 1, so we can say: \[ E(X_{n+1}\ |\ X_1, \ldots ,X_n)\ne X_n \] and therefore our Bernoulli Process is not a martingale.

  1. Gaussian Random Walk

Can we construct a simple stochastic process that is a martingale? Let’s try defining \(Y_t\), where: \[ Y_0=0, \qquad Y_t=Y_{t-1}+\varepsilon_t, \] where \(t=1,2,\ldots\) and \(\varepsilon_t\) isa series of i.i.d. \(N(0,1)\) random variables (standard normal random variables). This is called a Gaussian Random Walk. The Gaussian part means ‘Normal’ and the Random Walk part means that, well, the process looks like it’s randomly walking around! We can easily simulate this process in R:

library("xts")
## Loading required package: zoo
## 
## Attaching package: 'zoo'
## The following objects are masked from 'package:base':
## 
##     as.Date, as.Date.numeric
#library("roll")
library("ggplot2")
library("data.table")
## 
## Attaching package: 'data.table'
## The following objects are masked from 'package:xts':
## 
##     first, last
# replicate
set.seed(0)
# generate a Gaussian Random Walk
data <- data.table(t = 1:100,
Y = cumsum(rnorm(100)))
# visualize
ggplot(data, aes(x = t, y = Y)) +
geom_line() +
theme_bw() +
geom_hline(yintercept = 0) +
ggtitle("Martingale?")

Let’s try to calculate the expectation of \(Y_{n+1}\) given the history of \(Y\) up to time \(n\). We have: \[ E(Y_{n+1}\ |\ Y_1, \ldots, Y_n)=E(Y_{n+1}\ |\ Y_n), \] because \(Y_{n+1}\) is conditionally independednt of \(Y_1, Y_2, \ldots, Y_{n-1}\) given \(Y_n\) (i.e., if we know the value of \(Y_n\) it doesn’t matter how we got there).

We can plug in for \(Y_{n+1}\) \[ E(Y_n+\varepsilon\ |\ Y_n)=Y_n, \] because \(\varepsilon_n\sim N(0,1)\) and the expected value of \(Y_n\) given \(Y_n\) is, well \(Y_n\) (the ’finite expectation” piece is also satisfied; we know that \(E(Y_n)=0\), because \(Y_n\) is essentially the sum of many standard normal random variables, each of which has expectation 0).

Therefore, \(Y_t\) is a martingale, because the expected value of the next step is the step that we are currently at (conditioning on the history of \(Y_t\) up to the current moment). Intuitively, this is because at each step we add something \((\varepsilon )\) with a mean of zero, so the expected value of the next time point in the series doesn’t move from where we are now (we are adding zero)!

Branching Processes and Martingales

Consider again the branching process starting with one individual so that \(X_0=1\) As before \(X_n\) represents the population size of the \(n\)-th generation. Suppose we look at the expected value of the random variable \(X_{n+1}\) given the random variables \(X_1, X_2, \ldots , X_n\). Such a conditional expectation is not a number but itself a random variable. Each set of descendants created by \(X_n\) will have mean \(\mu\). Since there are \(X_n\) such means, then \[\begin{equation} \label{9.14} E(X_{n+1}\ |\ X_0, X_1, \ldots, X_n)=X_n \mu. \end{equation}\] Let \[ M_n= \frac{X_n}{E(X_n)}=\frac{X_n}{\mu^n}. \]

The random variable \(M_n\) is the random variable \(X_n\) normalized by its own mean. Hence \[ E(M_n)=\left(\frac{X_n}{\mu^n}\right)=\frac{E(X_n)}{\mu^n}=1=E(X_0), \] since the process starts with one individual. Hence (\(\ref{9.14}\)) becomes \[ E(M_{n+1}\mu^{n+1}\ |\ X_0, X_1, \ldots, X_n)=M_n \mu^{n+1} \] or \[ E(M_{n+1}\ |\ X_0, X_1, \ldots, X_n)=M_n, \] since \(E(aX)=aE(x)\), where \(a\) is a constant and \(X\) is any random variable. Therefore \(M_n\) is a martingale.