Martingales

Conditional Expectation

Before defining conditional expectation, here’s a simple example to keep in mind. Suppose you have two (not i.i.d.) Bernoulli random variables $X_1$, $X_2$, which arise in sequence as part of a game. You observe several realizations of them and learn the joint distribution. Now, on one trial you observe $X_1$, but not $X_2$. What is the best approximation of $X_2$ given what you’ve observed? It should be $\E(X_2 \given X_1 = 0)$ if $X_1 = 0$, and $\E(X_2 \given X_1 = 1)$ if $X_1 = 1$. Or more concisely, it should be $$ \E(X_2 \given X_1 = 0)\one_{X_1 = 0} + \E(X_2 \given X_1 = 1) \one_{X_1 = 1} \,. $$ This is called the conditional expectation of $X_2$ given $X_1$, which we define in generality below.

Suppose $(\Omega, \mathcal F, \P)$ is a probability space, and $\set{A_n \st n \in \N}$ is a partition of $\Omega$ (and $\P(A_n) \neq 0$ for every $n \in \N$). Let $\mathcal G$ is the smallest $\sigma$-algebra containing each event $A_n$ (often called the $\sigma$-algebra generated by $\set{A_n}_{n \in \N}$). Every element in $\mathcal G$ can be expressed (uniquely) as a countable disjoint union of the form $\cup A_{n_k}$.

Example 1. Suppose $X$ is a discrete random variable, and $X(\Omega) = \set{x_n \st n \in \N}$, $\mathcal G$ is the smallest $\sigma$-algebra such that $X$ is a random variable, and $A_n = \set{X = x_n}$. (Here we assumed $\P( X = x_n) > 0$ for every $n \in \N$.)

Definition 2. Let $X$ be an integrable random variable (i.e. a random variable for which $\E X$ is finite). We define the conditional expectation of $X$ given $\mathcal G$ by $$ \E_\mathcal G X = \E( X \given \mathcal G ) = \sum_{n \in \N} \E(X \given A_n) \one_{A_n} \,. $$

Remark 3. Note $\E(X \given \mathcal G)$ is a random variable, where as $\E(X \given A_n)$ is a number.

Proposition 4. $\E_{\mathcal G} X$ is the unique random variable such that:

  1. $\E_{\mathcal G} X$ is a $\mathcal G$-measurable random variable.
  2. For every $A \in \mathcal G$, we have $\E(\one_A X) = \E( \one_A \E_{\mathcal G} X)$.

Remark 5. When we say unique above, we mean unique up to almost sure equality. The first point in the uniqueness condition above is essential; there are plenty of random variables that satisfy the second condition (e.g. the random variable $X$ itself). But there is only one $\mathcal G$-measurable random variable that satisfies the second condition.

If $\mathcal G$ is not generated by a countable partition $\set{A_n}_{n \in \N}$ as we had above, then there still exists a random variable that satisfies the conclusion of Proposition 4. We use this as the definition.

Theorem 6. Let $X$ be a random variable for which $\E X$ is finite, and $\mathcal G \subseteq \mathcal F$ be any $\sigma$-algebra. There exists a unique random variable, denoted by $\E_{\mathcal G} X$ (or $\E (X \given \mathcal G)$) such that:

  1. $\E_{\mathcal G} X$ is a $\mathcal G$-measurable random variable.
  2. For every $A \in \mathcal G$, we have $\E(\one_A X) = \E( \one_A \E_{\mathcal G} X)$.

Definition 7 (Conditional expectation). The unique random variable from Theorem 6 is defined to be the conditional expectation of $X$ given $\mathcal G$.

Basic properties

Proposition 8. $\E \E_{\mathcal G} X = \E X$

Proposition 9. If $X, Y$ are two integrable random variables, $\alpha \in \R$ then $\E_{\mathcal G} (X + \alpha Y) = \E_{\mathcal G} X + \alpha \E_{\mathcal G} Y$ almost surely.

Proposition 10 (Tower property). If $\mathcal G \subseteq \mathcal H$ are two $\sigma$-algebras, and $X$ is integrable, then $\E_{\mathcal G} \E_{\mathcal H} X = \E_{\mathcal G} X$ almost surely.

Proposition 11. If $X$ is $\mathcal G$-measurable then $\E_{\mathcal G} X = X$ almost surely.

Proposition 12. If $X, Y$ are two integrable random variables such that $X Y$ is integrable and $X$ is $\mathcal G$ measurable, then $$ \E_{\mathcal G} (X Y) = X \E_{\mathcal G} Y \quad\text{almost surely} \,. $$

Conditional expectations can be thought of as “best approximations” in the following sense.

Proposition 13. Let $X$ be a random variable, and $\mathcal G \subseteq \mathcal F$ be a $\sigma$-algebra. If $\E X^2 < \infty$, and $Y$ is any $\mathcal G$-measurable random such that $\E Y^2 < \infty$, then $$ \E(X - \E_{\mathcal G} X)^2 \leq \E(X - Y)^2 \,, $$

Proof sketch. Verify $\E( (X - \E_{\mathcal G} X)(\E_{\mathcal G} X - Y) = 0$.

Definition 14. We say a random variable $X$ is independent of the $\sigma$-algebra $\mathcal G$ if for every $x \in \R$, and every $A \in \mathcal G$, the events $\set{X \leq x}$ and $A$ are independent.

Remark 15. If $X$ is independent of $\mathcal G$ it’s easy to see that for every Borel set $B$, and every $A \in \mathcal G$, the events $\set{X \in B}$ and $A$ are independent.

Proposition 16. If $X$ is independent of $\mathcal G$, then $\E_{\mathcal G} X = \E X$ almost surely.

Proposition 17 (Independence lemma). Suppose $X, Y$ are random variables such that $X$ is independent of $\mathcal G$, and $Y$ is $\mathcal G$-measurable. Let $g$ be a continuous (or more generally a Borel measurable) function such that $\E g(X, Y)$ is finite.

  1. If $X$ is discrete, then $\E_{\mathcal G} g(X, Y) = \sum_{x \in X(\Omega)} g(x, Y) \P(X = x)$.
  2. If $X$ is continuous, then $\E_{\mathcal G} g(X, Y) = \int_\R g(x, Y) f_X(x) \, dx$.
  3. More generally, whether or not $X$ is continuous or discrete, $$ \E_{\mathcal G} g(X, Y) = h(Y) \quad\text{where}\quad h(y) = \E g(X, y) $$

Proposition 18. If $X \leq Y$ almost surely, then $\E_{\mathcal G} X \leq \E_{\mathcal G} Y$ almost surely.

Problem 19 (Jensen’s inequality). Let $I \subseteq \R$ be an interval, $\varphi \colon I \to \R$ be a convex (differentiable) function, and $X$ be a random variable such that $\P(X \in I) = 1$. If $X$ and $\varphi(X)$ are integrable, then show that $\varphi( \E_{\mathcal G} X ) \leq \E_{\mathcal G} \varphi(X)$ almost surely.

Discrete time martingales

Definition 20 (Filtration). We say $\set{\mathcal F_n}_{n \in \N}$ is a filtration if for every $n \in \N$, $\mathcal F_n \subseteq \mathcal F_{n+1}$, and each $\mathcal F_n \subseteq \mathcal F$ is a $\sigma$-algebra.

Example 21. Consider a sequence of random variables $\set{X_n}_{n \in \N}$, and think of them as outcomes of successive trials (or games), which are not necessarily independent, or identically distributed. After observing several realizations of the first $n$ random variables, $X_1$, …, $X_n$, you learn the all events that can be observed using only $X_1$, …, $X_n$ and their probabilities. That is, you would learn $\P(X_1 = 3, X_n = 6)$, but not $\P(X_{n+1} = 1)$. Let $\mathcal F_n$ be the collection of all events whose probabilities you learned using just $X_1$, …, $X_n$. It is not hard to see that $\mathcal F_n$ is the smallest $\sigma$-algebra under which $X_1$, …, $X_n$ are random variables, and $\set{F_n}_{n \in \N}$ is a filtration.

Definition 22 (Adapted process). Let $\set{\mathcal F_n}_{n \in \N}$ be a filtration. An adapted process is a family of random variables $\set{X_n}_{n \in \N}$ such that for every $n \in \N$, $X_n$ is a $\mathcal F_n$-measurable random variable.

In addition to the probability space $(\Omega, \mathcal F, \P)$, we will now also fix a filtration $\set{\mathcal F_n}_{n \in \N}$, and assume whenever we say adapted we are referring to this filtration.

Definition 23 (Martingale). We say an adapted process $\set{M_n}_{n \in \N}$ is a martingale if for every $n \in \N$, $M_n$ is integrable and we have $$ \E(M_{n+1} \given \mathcal F_n) = M_n \,. $$

Remark 24. We will almost always use $\E_n Y$ to denote the conditional expectation $\E_{\mathcal F_n} Y = \E(Y \given \mathcal F_n)$.

Remark 25. We think of martingales as “fair games”. If you’re playing a fair game (e.g. while gambling), and $M_n$ is your cumulative winnings up to time $n$. Given information you’ve learned at time $n$, your best approximation of your cumulative winnings at time $n+1$ is $\E_n M_{n+1}$. For a fair game, this should exactly be $M_n$, which is the definition of a martingale.

Example 26 (i.i.d. sum). Let $\set{\xi_n}_{n \in \N}$ be an adapted process such that $\set{\xi_n}$ are identically distributed, $\xi_{n+1}$ is independent of $\mathcal F_n$, $\E \xi_1 = 0$ and $\xi_1$ is not identically $0$. Let $M_0 \in \R$ be deterministic, $M_{n+1} = M_n + \xi_{n+1}$. Then $\set{M_n}_{n \in \N}$ is a martingale.

Remark 27 (Random walks). If $\set{\xi_n}$ above are Radamacher random variables, then the random walk is called a simple random walk, as it only jumps by $1$ either right or left. If $\set{\xi_n}$ are integer valued, $M_0 \in \N$, then the above is called an unbiased random walk, as it moves along the integers (randomly).

Problem 28.

  1. If $\set{M_n}_{n \in \N}$ is a martingale, then show that $\E M_n$ does not change with $n$.
  2. The converse is false, here’s a counter example: Let $\set{M_n}_{n \in \N}$ be the iid sum with $M_0 = 0$, $\E \xi_1^3 = 0$, and set $X_n = M_n^3$. Show that $\E X_n$ does not change with $n$, but $\set{X_n}_{n \in \N}$ is not a martingale.

Problem 29. Let $\set{X_n}_{n \in \N}$ be an adapted process. If $X_{n+1} - X_n$ is independent of $\mathcal F_n$ and $\E(X_{n+1} - X_n) = 0$ then show that $\set{X_n}_{n \in \N}$ is a martingale.

Again the converse is false, and the martingale transform provides a good counter example.

Definition 30 (Predictable). A process $\set{A_n}_{n \in \N}$ is called predictable if for every $n \in \N$, the random variable $A_n$ is $\mathcal F_{n-1}$-measurable.

Example 31 (Martingale transform). Let $\set{M_n}_{n \in \N}$ be a martingale, and $\set{A_n}_{n \in \N}$ be a predictable process. The martingale transform of $M$ by $A$ is the process $$ X_n \defeq \sum_{1}^n A_k (M_k - M_{k-1}) \,. $$

Proposition 32. Let $A$ be a predictable process, and $M$ be a martingale. If $A_k (M_k - M_{k-1})$ is integrable for every $k$, then the martingale transform of $M$ by $A$ is also a martingale.

Remark 33. Intuitively this means you can’t turn a fair game into an unfair game by betting cleverly. For example, let $\set{\xi_n}$ be i.i.d. Radamacher random variables, interpreted as winning / losing a fair game played repeatedly at a casino. At time $n$, before the $n$-th game is played, you choose to stake $A_n$ (so $A_n$ must be $\mathcal F_{n-1}$-measurable). Your cumulative winnings will be $$ X_n = \sum_1^n A_k \xi_k = \sum_{1}^n A_k (M_k - M_{k -1}) \,, $$ where $M_n = \sum_1^n \xi_k$ is the simple random walk. So $X$ is simply the martingale transform of $M$ by $A$. (One can also interpret this in terms of stock prices.)

Optional Sampling

Example 34 (Gamblers ruin). Suppose a gambler plays a game at a casino. He bets a dollar, and with probability $1/2$ he gets 2 dollars (so wins $1$ dollar total), and with probability $1/2$ he gets nothing and loses his bet. When he runs out of money, he is ruined and leaves. The game is clearly fair. What is the probability he gets ruined? Turns out, he gets ruined with probability $1$, even though the game is fair. We study this in a little more generality below.

Definition 35 (Stopping time). We say a random variable $\tau$ is a stopping time if for all $n \in \N$, the event $\set{\tau = n} \in \mathcal F_n$.

Remark 36. It is often convenient to allow $\tau$ to also take on the value $\infty$; so instead of requiring $\tau \colon \Omega \to \N$, we allow $\tau \colon \Omega \to \N \cup \infty$. We say $\tau$ is a finite stopping time if $\tau < \infty$ almost surely.

Remark 37. Think of $\tau$ as the time a gambler decides to stop playing a game. The decision to stop playing at time $n$ has to be based on information available up to time $n$, and can not involve outcomes of the games at future times.

Problem 38. Let $\set{X_n}_{n \in \N}$ be an adapted process, and $\set{A_n}_{n \in \N}$ be a family of Borel subsets of $\R$. Show that $\tau = \min \set{ n \in \N \st X_n \in A_n}$ is a stopping time, however $\sigma = \max \set{ n \in \N \st X_n \in A_n }$ need not be. (Here, and subsequently we use the convention that $\min \emptyset = \infty$, and $\max \emptyset = 0$.)

Remark 39. Think of $X_n$ as the outcome of a game at time $n$ (or stock price). The first time $\set{X_n \in A_n}$ is exactly $\tau$, and the last time $\set{X_n \in A_n}$ is $\sigma$. The first time your condition $\set{X_n \in A_n}$ is met can be decided using only knowledge of events that have transpired, and so is a valid stopping time. The last time your condition $\set{X_n \in A_n}$ is met needs to inspect all future events so is not a valid stopping time.

Proposition 40.

  1. If $N \in \N$ is fixed, then $\tau = N$ is a stopping time.
  2. If $\sigma, \tau$ are stopping times, then so is $\sigma \varmin \tau$ and $\sigma \varmax \tau$.

Problem 41. Let $\set{\xi_n}_{n \in \N}$ be i.i.d. random variables with $\E \xi_1 = 0$ and $\P(\xi_1 = 0) < 1$. Let $N \in \N$, $X_0 \in \set{0, \dots, N}$ and define $X_{n+1} = X_n + \xi_n$. Consider the stopping time $\tau = \min \set{n \in \N \st X_n \not\in (0, N) }$. Show that $\E \tau < \infty$.

Hint. Let $p = \P(\xi_n \geq 1) > 0$, and show that for every $m \in \N$, $\P(\tau > m N) \leq (1 - p^N)^m$.

Proposition 42. If $\set{X_n}_{n \in \N}$ is an adapted process and $\tau$ is a stopping time, then $Y_n = X_{\tau \varmin n}$ is $\mathcal F_n$-measurable (and so $\set{Y_n}_{n \in \N}$ is also an adapted process).

Theorem 43 (Optional sampling).

Let $\set{M_n}_{n \in \N}$ be a martingale, and $\tau$ be a bounded stopping time. Then $\E_n M_\tau = M_{\tau \varmin n}$.

Proof sketch. Let $N = \max \tau$, and note $$ \E_n M_\tau = \one_{\tau \leq n} M_\tau + \sum_{k = n}^N \E_n \one_{\tau = k} M_k = \one_{\tau \leq n} M_\tau + \sum_{k = n}^N \E_n \one_{\tau = k} M_N = \one_{\tau \leq n} M_\tau + \one_{\tau > n} M_n = M_{\tau \varmin n} $$

Remark 44. More generally, the optional sampling theorem holds under either of the following assumptions:

  1. If $\tau < \infty$ almost surely, and $M_{\tau \varmin k}$ is dominated (i.e. there exists a random variable $X$ such that $\E X < \infty$ and for all $k$, $\abs{M_{\tau \varmin k}} \leq X$).
  2. If $\E \tau < \infty$ and the increments $M_{k+1} - M_k$ are uniformly bounded (i.e. there exists $C > 0$ such that $\abs{M_{k+1} - M_k} \leq C$ for all $k$).

While we currently do not have the tools to prove this, we will occasionally need this more general version.

Corollary 45. If $M$ is a martingale and $\tau$ is a bounded stopping time then $\E M_\tau = \E M_1$.

Corollary 46. If $M$ is a martingale, and $\tau$ is a stopping time, then $\set{M_{\tau \varmin n}}_{n \in \N}$ is a martingale.

The previous corollary says you can’t make a fair game unfair by stopping early; provided your stopping time satisfies the conditions where the optional sampling theorem applies. You can, easily, construct strategies where the optional sampling theorem doesn’t apply which (seemingly) allow you to profit.

Problem 47 (Exponential martingale). Let $\set{S_n}$ be the simple random walk with $S_0 = 0$.

  1. For any $\lambda \in \R$, show that $ M_n = e^{\lambda S_n}/ (\cosh \lambda)^n $ is a martingale.

  2. Show that for every $a > 0$ and $N \in \N$, $$ \P\paren[\Big]{\max_{0 \leq n \leq N} S_n \geq a} \leq \exp\paren[\Big]{-\frac{a^2}{2N}} \,. $$

Hint. Let $\tau = \min\set{n \in \N \st S_n \geq a}$. Apply optional sampling to $M_{\tau \varmin N}$, use $\log\cosh\lambda \leq \lambda^2/2$, and optimize over $\lambda > 0$. (Note this is stronger than Hoeffding’s inequality as we control the probability of the maximum.)

Gamblers ruin

Example 48 (Gambling paradox). Let $M_n$ be the simple random walk. Let $\tau = \min \set{ n \in \N \st M_n = 1}$. Clearly $M$ is a martingale, $\tau$ is a stopping time. One can also show $\tau < \infty$ almost surely. However, $\E M_\tau = 1 \neq 0 = M_0 = \E M_1$.

In reality, this doesn’t allow you to profit because $\E \tau = \infty$. Also, for any $N \in \N$, there is a non-zero chance you lose $\dollar N$ before time $\tau$; meaning you will have to find a bank that is infinitely patient, and is willing to cover arbitrarily high losses you may make.

Proposition 49. Let $N \in \N$, $M_n$ be the simple random walk with $M_0 \in \set{0, \dots, N}$. Let $\tau = \min \set{n \in \N \st M_n \in \set{0, N}}$. Then $$ \P( M_\tau = 0 ) = 1 - \frac{M_0}{N} \,,\quad \P( M_\tau = N ) = \frac{M_0}{N} \,,\quad \E \tau = M_0 (N - M_0) \,. $$

Proof sketch.

  1. Check optional sampling applies using one of the conditions in Remark 44.
  2. Hence $\E M\tau = M_0$ which gives the first two equalities claimed.
  3. Check $X_n = M_n^2 - n$ is a martingale and that optional sampling applies, and use optional sampling with the bounded stopping time $\tau \varmin n$, and then send $n \to \infty$.

Proposition 50. Let $M_n$ be the simple random walk with some $M_0 \in \N$, and let $\tau = \min \set{n \in \N \st M_n = 0 }$. Then $\P( \tau < \infty ) = 1$, and $\E \tau = \infty$.

Proof sketch. Say first $M_0 > 0$, and let $N \geq M_0$. Let $\tau_N = \min \set{n \in \N \st M_n \in \set{0, N} }$, and note $\set{\tau < \infty } = \cup_N \set{M_{\tau_N} = 0}$. To prove $\E \tau = \infty$, we need to use the fact that $\E \tau = \lim_{N \to \infty} \E \tau_N = \infty$.

Remark 51. As mentioned in Example 34, this means that even though the game is fair, no matter how large a fortune you start with, you will (almost surely) lose it all. And even if you start with only $\dollar 1$, you will (on average) take infinitely long to lose it.

Lemma 52. Let $\set{\xi_n}_{n \in \N}$ be an i.i.d. adapted process such that $\xi_{n+1}$ is independent of $\mathcal F_n$. Let $X_0 \in \R$ and $X_{n+1} = X_n + \xi_{n+1}$. If $f \colon \R \to \R$ is a function such that $\E f(x + \xi_1) = f(x)$ for every $x \in \R$, then show that $\set{ f(X_n) }_{n \in \N}$ is a martingale.

Proposition 53. Let $\set{\xi_n}$ be i.i.d. random variables with $\P(\xi_n = 1) = p \in (0, 1)$ and $\P(\xi_n = -1) = 1 - p = q$. Suppose $p \neq 1/2$. Let $S_0 = k \in \set{0, \dots, N}$, $S_{n+1} = S_n + \xi_{n+1}$, $\tau = \min \set{n \in \N \st S_n \in \set{0, N}}$. $$ \P(S_\tau = 0) = \frac{\paren{\frac{q}{p}}^k - \paren{\frac{q}{p}}^N} {1 - \paren{\frac{q}{p}}^N} \quad\text{and}\quad \E \tau = \frac{k}{q - p} - \frac{N}{q-p} \paren[\Big]{ \frac{1 - (\frac{q}{p})^k}{1 - (\frac{q}{p})^N} } \,. $$

Proof sketch.

  1. Use Lemma 52 and find a function $f$ so that $\set{f(S_n)}_{n \in \N}$ is a martingale. (Answer – $f(x) = x^r$ works with $r = q/p$.)
  2. Check optional sampling applies, and use $\E M_\tau = M_0$ to obtain $\P(S_\tau = 0)$.
  3. For the second part check $M_n = S_n - (p - q)n$ is a martingale (and that optional sampling applies)

Remark 54. If $p > q$, then the game is biased in the gamblers favor. In this case the probability of eventually going bankrupt converges to $(q/p)^k < 1$ as $N \to \infty$. If $p < q$, then the game is biased against the gambler, and the probability of eventually going bankrupt converges to $1$ as $N \to \infty$.

Sequence waiting time

Let $\set{X_n}$ be i.i.d. $\Bernoulli(1/2)$ random variables, $N \in \N$, and $\omega \in \set{0, 1}^N$ some fixed sequence of length $N$. Let $\tau$ be the first time $\omega$ is observed. Explicitly $$ \tau = \min \set{ n \geq N \st X_{n - N + 1} = \omega_1, X_{n - N + 2} = \omega_2, \dots, X_{n} = \omega_N} \,. $$

Proposition 55. The expected waiting time to see the sequence $\omega$ is $$ \E \tau = \sum_{j \in J} 2^j \quad\text{where}\quad J = \set{ j \in \set{1, \dots, N} \st \operatorname{prefix}_j(\omega) = \operatorname{suffix}_j(\omega) } \,. $$ Here $\operatorname{prefix}_j(\omega) = (\omega_1, \dots, \omega_j)$ and $\operatorname{suffix}_j(\omega) = (\omega_{N - j + 1}, \dots, \omega_N)$.

Remark 56. If $\omega = (1, \dots, 1)$, or $\omega = (0, \dots, 0)$ then this is the same as this problem we did before.

Remark 57. You may be mildly surprised by the fact that any two length $N$ sequences have the same probability of occurring in $N$ i.i.d. trials. However the waiting times to see some of them is longer. The reason for this is common prefix / suffixes. If you enumerate all sequences of length $N + 1$, your sequence $N$ will occur exactly $4$ times. However, a sequence with a common prefix / suffix (e.g. $(0, 0)$) occurs twice in one $N + 1$ length sequence; and so occurs in only $3$ distinct sequences of length $N + 1$. This makes the expected waiting time longer.

Proof sketch. Design a martingale as follows. At time $n$, a gambler enters with $\dollar 1$. Every gambler bets their entire fortune on the sequence in order, and leaves either when they lose, or exhaust the sequence. (So when a gambler first enters, they bet a dollar on $\omega_1$; if they win the next time they bet $\dollar 2$ on $\omega_2$. If they lose they leave with nothing.) Check $M_n = G_n - n$ is a martingale, and that $G_\tau$ is exactly $\sum_J 2^j$. Justify the application of optional sampling to conclude.