Martingales in Discrete Time
All the stochastic processes that we will study in this class will be generated from a sequence of random variables. The specific sequence used to generate the stochastic process \{M_{n}: 0 \leq n < \infty\} determines the information set \mathcal{F}_{n} available at time n. As time passes, we learn more about the processes and what was used to generate the process.
We call the collection of information sets \{\mathcal{F}_{n}: 0 \leq n < \infty\} a filtration. Since information accumulates over time, we always have that \mathcal{F}_{m} \subset \mathcal{F}_{n} for m < n.
Martingales
Earlier, we defined the simple random walk as the process \{S_{n}: 0 \leq n < \infty\}, built from a sequence \{X_{n}: 1 \leq n < \infty\} of independent random variables, where S_{n} = S_{0} + \sum_{i = 1}^{n} X_{i} for n \geq 1. Each X_{i} is a fair coin toss, taking values -1 or 1 with probability 1/2. At time n, the outcomes of the first n coin tosses are known, so the information set is \mathcal{F}_{n} = \{X_{1}, X_{2}, \ldots, X_{n}\}, containing all information revealed by X_{1}, X_{2}, \ldots, X_{n}.
We can then see that \operatorname{E}(S_{n + 1} \mid \mathcal{F}_{n}) = \operatorname{E}(S_{n} + X_{n + 1} \mid \mathcal{F}_{n}) = S_{n} + \operatorname{E}(X_{n + 1} \mid \mathcal{F}_{n}). There is an implicit assumption that the coin tosses are independent from each other. Intuitively, we do not expect to gain any information from the first n tosses to determine the next one. Thus, \operatorname{E}(X_{n + 1} \mid \mathcal{F}_{n}) = \operatorname{E}(X_{n + 1}) = 0, implying \operatorname{E}(S_{n + 1} \mid \mathcal{F}_{n}) = S_{n}.
The process just defined is what we call a martingale. A martingale is a stochastic process \{M_{n}\} adapted to a filtration \{\mathcal{F}_{n}\} such that for all n, \operatorname{E}(M_{n+1} \mid \mathcal{F}_{n}) = M_{n}. In other words, given all the information up to time n, the expected value of the next observation is equal to the current value. This property captures the idea that, on average, the process does not “drift” up or down given the available information.
Example 1 We can generalize the simple random walk by defining \{X_{n}: 1 \leq n < \infty\} as a sequence of independent random variables such that \operatorname{E}(X_{n}) = 0 for all n \geq 1. We do not assume any specific distribution nor we assume that the random variables are identically distributed. We can then define S_{n} = S_{0} + \sum_{i = 1}^{n} X_{i}. We can do as before to find \operatorname{E}(S_{n + 1} \mid \mathcal{F}_{n}) = \operatorname{E}(S_{n} + X_{n + 1} \mid \mathcal{F}_{n}) = S_{n} + \operatorname{E}(X_{n + 1} \mid \mathcal{F}_{n}) = S_{n} + \operatorname{E}(X_{n + 1}) = S_{n}, showing that \{S_{n}\} is a martingale with respect to \{\mathcal{F}_{n}\}.
Example 2 Let \{X_{n}: 1 \leq n < \infty\} be a sequence of independent random variables with \operatorname{E}(X_{n}) = 0 and \operatorname{V}(X_{n}) = \sigma^{2} for all n \geq 1. We do not require the random variables to be identically distributed, but each has mean zero and variance \sigma^{2}. Define S_{n} as in Example 1, and set M_{n} = S_{n}^{2} - n \sigma^{2}. Expanding M_{n+1}, M_{n+1} = (S_{n} + X_{n+1})^{2} - (n+1)\sigma^{2} = S_{n}^{2} + 2S_{n}X_{n+1} + X_{n+1}^{2} - (n+1)\sigma^{2}. Taking conditional expectation, \operatorname{E}(M_{n+1} \mid \mathcal{F}_{n}) = S_{n}^{2} + 2S_{n}\operatorname{E}(X_{n+1} \mid \mathcal{F}_{n}) + \operatorname{E}(X_{n+1}^{2} \mid \mathcal{F}_{n}) - (n+1)\sigma^{2}. Because X_{n+1} is independent of \mathcal{F}_{n}, we have \operatorname{E}(X_{n+1} \mid \mathcal{F}_{n}) = 0 and \operatorname{E}(X_{n+1}^{2} \mid \mathcal{F}_{n}) = \sigma^{2}. Therefore, \operatorname{E}(M_{n+1} \mid \mathcal{F}_{n}) = S_{n}^{2} + \sigma^{2} - (n+1)\sigma^{2} = S_{n}^{2} - n\sigma^{2} = M_{n}. Thus, \{M_{n}\} is a martingale with respect to \{\mathcal{F}_{n}\}.
Example 3 Let \{X_{n}: 1 \leq n < \infty\} be a sequence of independent random variables with X_{n} > 0 and \operatorname{E}(X_{n}) = 1 for all n \geq 1. Set M_{0} = 1 and define M_{n} = X_{1} X_{2} \cdots X_{n}. Since M_{n+1} = M_{n} X_{n+1}, we have \operatorname{E}(M_{n+1} \mid \mathcal{F}_{n}) = M_{n} \operatorname{E}(X_{n+1} \mid \mathcal{F}_{n}) = M_{n} \operatorname{E}(X_{n+1}) = M_{n}. Therefore, \{M_{n}\} is a martingale with respect to \{\mathcal{F}_{n}\}.
Betting Strategies
A gambler does not have to bet the same amount on every round. Suppose that M_{k} - M_{k - 1} is the gain from a bet of one dollar on round k, where \{M_{n}\} is a martingale, and that the gambler stakes H_{k} dollars on that round. The stake must be chosen before the round is played, so H_{k} can depend on everything observed up to time k - 1 but not on the outcome of round k. In other words, H_{k} is \mathcal{F}_{k - 1} measurable, and we say that the sequence \{H_{k}\} is predictable. Starting from W_{0}, the wealth of the gambler after n rounds is W_{n} = W_{0} + \sum_{k = 1}^{n} H_{k} (M_{k} - M_{k - 1}). The process \{W_{n}\} is called a martingale transform. In finance, M_{k} is a (discounted) price, H_{k} is the number of shares held from k - 1 to k, and W_{n} is the value of a self-financing trading strategy.
Proof.
Since W_{n + 1} = W_{n} + H_{n + 1} (M_{n + 1} - M_{n}) and H_{n + 1} is known at time n, \operatorname{E}(W_{n + 1} \mid \mathcal{F}_{n}) = W_{n} + H_{n + 1} \left(\operatorname{E}(M_{n + 1} \mid \mathcal{F}_{n}) - M_{n}\right) = W_{n}. The bound on H_{n + 1} guarantees that the expectations exist.No rule for sizing bets based on past outcomes can turn a fair game into a favorable one. The notes on stochastic calculus define the Itô integral as the continuous-time limit of these sums, with the integrand in the role of H_{k} and the increments of Brownian motion in the role of M_{k} - M_{k - 1}, and the result above becomes the martingale property of the Itô integral.
Example 4 The oldest betting system is the one that gave martingales their name. A gambler bets one dollar on a fair coin and doubles the stake after every loss, stopping at the first win. If the first win comes on round k, the gambler has lost 1 + 2 + \cdots + 2^{k - 2} = 2^{k - 1} - 1 dollars and then wins 2^{k - 1}, for a net gain of one dollar. A win eventually comes with probability one, so the strategy seems to guarantee a profit. Over n rounds, however, the gambler wins one dollar with probability 1 - 2^{-n} and loses 2^{n} - 1 dollars with probability 2^{-n}, so \operatorname{E}(W_{n}) = (1 - 2^{-n}) - 2^{-n} (2^{n} - 1) = 0, as the result above requires. The sure profit at the stopping time is paid for by an unbounded line of credit.
The doubling strategy shows that the value of a martingale at a stopping time need not have the same expectation as its starting value. The gambler stops at a time \tau that is finite with probability one, and W_{\tau} = 1 while W_{0} = 0. What fails is that the losses before \tau are unbounded. The optional stopping theorem below gives a condition that rules this out.
Stopped Processes
A random variable \tau taking values in \{0, 1, 2, \ldots\} \cup \{\infty\} is called a stopping time with respect to \{\mathcal{F}_{n}: 0 \leq n \leq \infty\} if \{\tau \leq n\} \in \mathcal{F}_{n} \text{ for all } 0 \leq n < \infty. If \tau < \infty almost surely, we can define the stopped process Y_{\tau} = \sum_{k = 0}^{\infty} \mathbf{1}_{\{\tau = k\}} Y_{k}. In cases where \operatorname{P}(\tau = \infty) > 0, we can always define the truncated stopping time n \land \tau = \min\{n, \tau\}. The stopped process Y_{n \land \tau} is always well defined.
Proof.
We can always write M_{(n + 1) \land \tau} = M_{n + 1} \mathbf{1}_{\{\tau \geq n + 1\}} + M_{n \land \tau} \mathbf{1}_{\{\tau \leq n\}}. Since \mathbf{1}_{\{\tau \geq n + 1\}} = 1 - \mathbf{1}_{\{\tau \leq n\}}, we see that \mathbf{1}_{\{\tau \geq n + 1\}} is \mathcal{F}_{n} measurable. Thus \begin{aligned} \operatorname{E}(M_{n + 1} \mathbf{1}_{\{\tau \geq n + 1\}} \mid \mathcal{F}_{n}) & = \operatorname{E}(M_{n + 1} \mid \mathcal{F}_{n}) \mathbf{1}_{\{\tau \geq n + 1\}} \\ & = M_{n} \mathbf{1}_{\{\tau \geq n + 1\}} \\ & = M_{n \land \tau} \mathbf{1}_{\{\tau \geq n + 1\}}. \end{aligned} Combining this with the decomposition above, \begin{aligned} \operatorname{E}(M_{(n + 1) \land \tau} | \mathcal{F}_{n}) & = \operatorname{E}(M_{n + 1} \mathbf{1}_{\{\tau \geq n + 1\}} \mid \mathcal{F}_{n}) + M_{n \land \tau} \mathbf{1}_{\{\tau \leq n\}} \\ & = M_{n \land \tau} \mathbf{1}_{\{\tau \geq n + 1\}} + M_{n \land \tau} \mathbf{1}_{\{\tau \leq n\}} \\ & = M_{n \land \tau}, \end{aligned} proving that \{M_{n \land \tau}\} is a martingale with respect to \{\mathcal{F}_{n}\}.Stopping is itself a betting strategy: bet one dollar per round while the game is running and nothing afterwards. With H_{k} = \mathbf{1}_{\{\tau \geq k\}}, M_{n \land \tau} = M_{0} + \sum_{k = 1}^{n} \mathbf{1}_{\{\tau \geq k\}} (M_{k} - M_{k - 1}), and H_{k} is predictable because \{\tau \geq k\} is the complement of \{\tau \leq k - 1\} \in \mathcal{F}_{k - 1}. The result on betting strategies therefore gives a second proof that stopped martingales are martingales.
Optional Stopping
Since \{M_{n \land \tau}\} is a martingale, \operatorname{E}(M_{n \land \tau}) = \operatorname{E}(M_{0}) for every n. If \tau is finite, then M_{n \land \tau} = M_{\tau} as soon as n \geq \tau, so M_{n \land \tau} \to M_{\tau} as n \to \infty. The question is whether the expectations converge too, and the doubling strategy shows that they need not. The following result gives a condition under which they do.
Proof.
The stopped process converges to M_{\tau} and is dominated by Y, so the dominated convergence theorem gives \operatorname{E}(M_{\tau}) = \operatorname{E}\left(\lim_{n \to \infty} M_{n \land \tau}\right) = \lim_{n \to \infty} \operatorname{E}(M_{n \land \tau}) = \operatorname{E}(M_{0}).In the doubling strategy, the wealth just before the winning round \tau is -(2^{\tau - 1} - 1), so any Y that dominates the stopped process must be at least 2^{\tau - 1} - 1. Since \operatorname{P}(\tau = k) = 2^{-k}, the expectation of 2^{\tau - 1} is \sum_{k} 2^{k - 1} 2^{-k} = \infty, and no integrable bound exists.
Ruin Probabilities Again
We now revisit the ruin probability problem, previously analyzed using elementary methods, and show how the martingale machinery yields both the ruin probability and the expected duration in a unified way. Consider the simple symmetric random walk: S_{n} = \sum_{i = 1}^{n} X_{i} for n \geq 1, where each X_{i} is an independent fair coin toss, taking values -1 or 1 with probability 1/2. Define the stopping time \tau = \min\{n > 0 : S_{n} = A \text{ or } S_{n} = -B\}, which is measurable with respect to the filtration \mathcal{F}_{n}.
The notes on ruin probabilities show that \tau is finite with probability one and that \operatorname{E}(\tau) < \infty.
The Probability
Recall that S_{n} is a martingale. Since the process stops when it reaches either A or -B, we have |S_{n \land \tau}| \leq \max(A, B) for all n. The stopped process is bounded, so the optional stopping theorem gives \operatorname{E}(S_{\tau}) = S_{0} = 0.
Since we can also write \operatorname{E}(S_{\tau}) = \operatorname{P}(S_{\tau} = A) A + (1 - \operatorname{P}(S_{\tau} = A)) (-B) = 0, we get that \operatorname{P}(S_{\tau} = A) = \frac{B}{A + B}.
The Expectation
Furthermore, since for the simple random walk \operatorname{E}(X_{n}) = 0 and \operatorname{V}(X_{n}) = 1, Example 2 with \sigma^{2} = 1 shows that M_{n} = S_{n}^{2} - n is also a martingale. Because the process stops when it hits A or -B, we have |S_{n \land \tau}| \leq \max(A, B), and therefore |M_{n \land \tau}| = |S_{n \land \tau}^{2} - (n \land \tau)| \leq \max(A^{2}, B^{2}) + \tau. The right-hand side does not depend on n, and it has a finite expectation because \operatorname{E}(\tau) < \infty. The optional stopping theorem therefore gives \operatorname{E}(M_{\tau}) = M_{0} = 0.
Since we also have that \operatorname{E}(M_{\tau}) = A^{2} \frac{B}{A + B} + B^{2} \frac{A}{A + B} - \operatorname{E}(\tau) = 0, we conclude that \operatorname{E}(\tau) = A B.
A Biased Coin
The same method handles a biased coin, where each bet is won with probability p and lost with probability q = 1 - p, with p \neq q. The walk S_{n} is no longer a martingale, so we need a different one. Each factor (q / p)^{X_{i}} is positive with \operatorname{E}\left((q / p)^{X_{i}}\right) = p \frac{q}{p} + q \frac{p}{q} = q + p = 1, so Example 3 shows that Z_{n} = (q / p)^{S_{n}} = \prod_{i = 1}^{n} (q / p)^{X_{i}} is a martingale. The argument in the notes on ruin probabilities, with (1/2)^{A + B} replaced by p^{A + B}, shows that \tau is finite with probability one and \operatorname{E}(\tau) < \infty. The stopped process Z_{n \land \tau} lies between (q / p)^{-B} and (q / p)^{A}, so it is bounded, and optional stopping gives \operatorname{E}(Z_{\tau}) = Z_{0} = 1. Writing P_{A} = \operatorname{P}(S_{\tau} = A), P_{A} (q / p)^{A} + (1 - P_{A}) (q / p)^{-B} = 1, and solving for P_{A}, P_{A} = \frac{(q / p)^{B} - 1}{(q / p)^{A + B} - 1}, which is the answer the notes on ruin probabilities found by solving a difference equation. If p > q and there is no upper barrier, letting A \to \infty sends (q / p)^{A} \to 0, and the probability of ever losing B dollars is 1 - P_{A} \to (q / p)^{B}.
The expected duration follows from a second martingale. The variables X_{i} - (p - q) are independent with mean zero, so Example 1 shows that S_{n} - n (p - q) is a martingale. Its stopped version satisfies |S_{n \land \tau} - (n \land \tau)(p - q)| \leq \max(A, B) + \tau, a bound with finite expectation that does not depend on n, so optional stopping gives \operatorname{E}(S_{\tau}) = (p - q) \operatorname{E}(\tau). Therefore, \operatorname{E}(\tau) = \frac{A P_{A} - B (1 - P_{A})}{p - q}.
The two martingales (q / p)^{S_{n}} and S_{n} - n (p - q) play the roles that S_{n} and S_{n}^{2} - n played for the fair coin. The notes on Poisson processes and Brownian motion follow the same pattern: an exponential martingale gives the ruin probability, with e^{-R} and e^{-2 \mu / \sigma^{2}} in the role of q / p.