This set of notes is still being edited: the text may contain typos, inaccuracies, and locally unpolished passages. If you find something, please let the author know (contact information on the course page).
1 Introduction
Martingales are random processes that arose from the study of various betting strategies. Suppose a game consists of identical successive rounds, and the game is fair, i.e. the expected payoff on each round equals \(0\). Let us formalize this: let \(\xi_1, \xi_2, \ldots\) be random variables, where \(\xi_n\) is the payoff on the \(n\)-th round of the game per \(1\) unit staked, with \(\mathbb {E}\left[\xi_i\right] = 0\) (the game is fair). For example, if the game consists of tossing a coin, where heads means a win and tails means a loss, then \(\xi_i \sim \frac{1}{2}\delta_{-1} + \frac{1}{2}\delta_1\), i.e. \(\mathbb {P}\left(\xi_i = \pm 1\right) = \frac{1}{2}\). Let
\[
S_{n} = \xi _1 + \xi _2 + \ldots + \xi _n
\]
\(S_{n}\) is the random walk already familiar to us, but in this case the process can be interpreted as the playerβs capital after \(n\) rounds of the game, having started with zero in their pocket and staking \(1\) unit on every round.
Let \(\mathcal{F}_{n} = \sigma (\xi_1, \ldots ,\xi_n)\) be the natural filtration for this experiment. Suppose that instead of \(1\) unit, the player stakes some random amount \(C_n\) each time. Under a realistic scenario this stake may depend only on the past of the game: for every \(n \in \mathbb {N}\) the random variable \(C_n\) must be \(\mathcal{F}_{n-1}\)-measurable. The process \((C_n, n\in \mathbb {N})\) is called predictable with respect to the filtration \((\mathcal{F}_n, n \in \mathbb {Z}_+)\). Then the increment of the capital on the \(n\)-th round is defined by
Suppose for simplicity that the player starts with zero capital, \(X_0 = 0\) (the player may borrow money from the casino to stake, and may also stake negative amounts, i.e. bet on a loss). Then
is the process describing the evolution of the playerβs capital (now employing some complex betting strategy \(C_n, n \in \mathbb {N}\)). This process is also called the discrete stochastic integral or the martingale transform of the process \(S_n\) with respect to the (predictable) process \(C_n\).
What can be said about the process \(X_n = \left(C \bullet S\right)_n\)? Will it be Markov, for instance? Not always (only if \(C_n\) depends solely on \(\xi_{n-1}\)); see the details below. However, it does possess an interesting property:
The process not only preserves its mean value but has a much stronger property: the best forecast of the value \(X_{n+1}\), made on the basis of all information available at time \(n\), is precisely the current value \(X_n\).
In other words, if we know the entire history of the process up to time \(n\), then there is nothing to expect on the next step β neither growth nor decline: the process βstays put on average.β Formally:
This property is called the fair-game property: however history unfolds, on average the process neither gains nor loses on the next step. A process possessing this property carries a special name β a martingale.
Incidentally, the word βmartingaleβ itself comes from gambling: it was the name of the strategy of doubling oneβs stake after every loss. It is illustrated in the diagram below and nicely illustrates the meaning of what we proved above: no predictable betting strategy turns a fair game into a profitable one.
The βmartingaleβ betting strategy in a fair game: start with \(1\) unit, double the bet after each loss, and stop after the first win with a net gain of \(+1\). With unlimited capital, winning is guaranteed (\(\mathbb{P}\left(\text{eventually winning}\right) = 1\)), yet the martingale property of the capital \(X_n\) cannot be cheated: \(\mathbb{E}\left[X_n\right] = 0\) for all \(n\). Below is a simulator with a realistic capital constraint (the casino stops the game after \(L\) consecutive losses). Move the slider \(L\) and click βPlay a roundβ: the running average payoff accumulates over all rounds played, and for small \(L\) it noticeably dips below \(+1\) β a rare but enormous loss from ruin exactly offsets the frequent small wins.
Rounds played: 0Average payoff: β
2 General information
Definition 1 Let \(T \subset \mathbb {R}\). A real-valued process \(\left(X_{t}, t \in T\right)\) is called an \(L^p\)-process or a \(p\)-integrable process if \(\forall t \in T: \; X_t \in L^p\). That is,
\(L^1\)-processes are often simply called integrable processes.
Definition 2 Let \(T \subset \mathbb {R}\). A real-valued process \(\left(X_{t}, t \in T\right)\), adapted to the filtration \(\mathbb {F}=\left(\mathcal{F}_{t}, t \in T\right)\), is called a martingale with respect to the filtration \(\mathbb {F}\) if it is integrable and
\[
\mathbb {E}\left[X_{t} \mid \mathcal{F}_{s}\right] \stackrel{\text{a.s.}}{=} X_{s}, \qquad \forall t \geq s
\]
If, instead of equality, the (weaker) non-strict inequality
\[
\mathbb {E}\left[X_{t} \mid \mathcal{F}_{s}\right] \stackrel{\text{a.s.}}{\geq } X_{s} \qquad \forall t \geq s
\]
holds, then the process \(X_{t}\) is called a submartingale with respect to \(\mathbb {F}\). If
\[
\mathbb {E}\left[X_{t} \mid \mathcal{F}_{s}\right] \stackrel{\text{a.s.}}{\leq } X_{s} \qquad \forall s \leq t
\]
then the process is called a supermartingale.
Martingales (submartingales, supermartingales) without a specified filtration will mean martingales with respect to their natural filtration.
ExampleExample 1
Show that, in discrete time, the property from Definition Definition 2 need only be checked for adjacent time instants. Namely, prove that an \(L^{1}\)-process \(\left(X_{n}, n \in \mathbb {Z}_{+}\right)\), adapted to the filtration \(\mathbb {F}=\left(\mathcal{F}_{n}, n \in \mathbb {Z}_{+}\right)\), is a martingale with respect to \(\mathbb {F}\) if and only if \(\forall n \; X_{n-1} = \mathbb {E}\left[X_{n} \mid \mathcal{F}_{n-1}\right]\) (a.s.).
SolutionSolution
In the forward direction everything is obvious. Let \(n>k\); then, using the properties of conditional expectation, we obtain that \[
\begin{align} \mathbb {E}\left[X_n \mid \mathcal{F}_k\right] & \stackrel{\text{a.s.}}{=} \mathbb {E}\left[\mathbb {E}\left[X_{n} \mid \mathcal{F}_{n-1}\right] \mid \mathcal{F}_k\right] \stackrel{\text{a.s.}}{=} \\ & \stackrel{\text{a.s.}}{=} \mathbb {E}\left[X_{n-1} \mid \mathcal{F}_k\right] \stackrel{\text{a.s.}}{=} \\ & \stackrel{\text{a.s.}}{=} \ldots \stackrel{\text{a.s.}}{=} \\ & \stackrel{\text{a.s.}}{=} \mathbb {E}\left[X_{k+1} \mid \mathcal{F}_k\right] \stackrel{\text{a.s.}}{=} X_k \end{align}
\]
Submartingales and supermartingales are martingales βby half.β How can one remember the difference between a submartingale and a supermartingale? For a submartingale the expectation (weakly) increases, for a supermartingale it (weakly) decreases.
Theorem 1 (Martingale criterion for processes with independent increments) Let \(\left(X_{t}, t \in T\right)\) be an \(L^{1}\)-process, adapted to the filtration \(\mathbb {F} = \left(\mathcal{F}_t, \; t \in T\right)\), and having independent increments with respect to this filtration, i.e. \[
X_t - X_s \quad \text{ and } \quad \mathcal{F}_s \quad \text{are independent} \qquad \forall t \geq s
\] Then \[
(X_{t}, \mathcal{F}_t) \text{ is a martingale} \quad \iff \quad \mathbb {E}\left[X_t\right] = \operatorname {const}
\]
It is easy to check that if the mean function is non-decreasing, then a process with independent increments is a submartingale. If it is non-increasing, then it is a supermartingale.
Theorem Theorem 1 immediately gives us several good examples of martingales.
The Wiener process \(\left(W_{t}, t \geqslant 0\right)\) is a martingale.
\(\left(S_{n}, n \in \mathbb {Z}_{+}\right)\) is a random walk: \(S_{n} = \xi_{1}+\ldots +\xi_{n}\), \((\xi_{i})_{i \in \mathbb {N}} \subset L^1\) are independent integrable random variables (increments). Then
\[
S_{n} \text{ is a martingale} \iff \mathbb {E}\left[\xi _i\right] = 0, \; \forall i \in \mathbb {N}
\]
The Poisson process \(\left(N_{t}, t \geqslant 0\right)\) is a submartingale.
Let \(\xi_{n}, n \in \mathbb {N}\) be independent nonnegative integrable random variables, \(S_{n}=\xi_{1} \cdot \ldots \cdot \xi_{n}\). Then
\[
S_{n} \text{ is a martingale} \iff \mathbb {E}\left[\xi _i\right] = 1, \; \forall i \in \mathbb {N}
\]
Note that this (multiplicative) example does not follow from Theorem Theorem 1: the increments \(S_n - S_{n-1} = (\xi_n - 1)\, \xi_1 \cdots \xi_{n-1}\) are not independent of the past. The martingale property is checked by direct computation: \(\mathbb {E}\left[S_n \mid \mathcal{F}_{n-1}\right] = S_{n-1} \mathbb {E}\left[\xi_n\right]\).
ExampleExample 2
Prove that if \((X_t, t \in T)\) is a martingale with respect to the filtration \((\mathcal{F}_t, t \in T)\), then it is a martingale with respect to its own filtration.
SolutionSolution
It is known that \(\mathbb {E}\left[X_t \mid \mathcal{F}_{s}\right] \stackrel{\text{a.s.}}{=} X_s\). Apply conditional expectation with respect to \(\mathcal{F}^{X}_s\) to the left- and right-hand sides: \[
\begin{align} \mathbb {E}\left[\mathbb {E}\left[X_t \mid \mathcal{F}_{s}\right] \mid \mathcal{F}^{X}_{s}\right] & \stackrel{\text{a.s.}}{=} \mathbb {E}\left[X_t \mid \mathcal{F}^X_{s}\right] & & \text{(by the "tower" property of conditional expectation, since $\mathcal{F}^{X}_s \subseteq \mathcal{F}_s$)} \\ \mathbb {E}\left[X_s \mid \mathcal{F}^X_{s}\right] & \stackrel{\text{a.s.}}{=} X_{s} & & \text{(since $X_{s}$ is $\mathcal{F}^X_s$-measurable)} \end{align}
\] As a result we obtain \(\mathbb {E}\left[X_t \mid \mathcal{F}^X_{s}\right] \stackrel{\text{a.s.}}{=} X_s\)
ExampleExample 3
Prove that a martingale has a constant mean function. Prove that a submartingale has a non-decreasing mean function.
SolutionSolution
Let \(s \leq t\). For a martingale, by the tower property of expectation \[
\mathbb {E}\left[X_t\right] = \mathbb {E}\left[\mathbb {E}\left[X_t \mid \mathcal{F}_s\right]\right] = \mathbb {E}\left[X_s\right]
\] For a submartingale it is similar: taking the expectation of both sides of the inequality \(\mathbb {E}\left[X_t \mid \mathcal{F}_s\right] \overset {\text{a.s.}}{\geq } X_s\), we get \(\mathbb {E}\left[X_t\right] \geq \mathbb {E}\left[X_s\right]\).
ProblemProblem 1
Let \(\left(W_{t}, t \geq 0\right)\) be a Wiener process. Find all pairs \((\alpha , \beta ) \in \mathbb {R}^{2}\) such that the process \[
X_{t}=\mathrm{exp}\left(\alpha W_{t}+\beta t\right), \quad t \geq 0
\] is a martingale with respect to the natural filtration of the process \(W_{t}\).
ProblemProblem 2
Let \(\xi\) be an integrable random variable: \(\mathbb {E}\left[\left|\xi \right|\right] < +\infty\). Let \(\mathbb {F}=\left(\mathcal{F}_{t}, t \in T\right)\), \(T \subset \mathbb {R}\) be an arbitrary filtration. Prove that the process \[
X_{t} := \mathbb {E}\left[\xi \mid \mathcal{F}_{t}\right]
\] is a martingale with respect to \(\mathbb {F}\).
Let \(\left(X_{t}, t \in T\right)\) be a martingale with respect to \(\mathbb {F}=\left(\mathcal{F}_{t}, t \in T\right)\), and let \(h(x)\) be a convex function such that \(\mathbb {E}\left[\left|h(X_t)\right|\right] < +\infty\). Prove that the process \[
Y_{t}=h\left(X_{t}\right)
\] is a submartingale with respect to \(\mathbb {F}\).
SolutionSolution
Note that the function \(h\) is Borel, since it is convex. Integrability of \(Y_t\) is given in the statement, and adaptedness of \(Y_t = h(X_t)\) is obvious from the adaptedness of the process \(X_{t}\). It remains to check the submartingale inequality; for this we use Jensenβs inequality for conditional expectation:
If the state space of the process consists of the real numbers, i.e. if \((\mathsf{S}, \mathscr {B}) = (\mathbb {R}, \mathscr {B}\left(\mathbb {R}\right))\), then the definition of a Markov process and the definition of a martingale are very similar. Let us try to understand the difference between them. Note that adaptedness to the filtration is a common condition.
A martingale is necessarily an integrable process, while a Markov process may be non-integrable. From this we immediately get an example of a Markov process that is not a martingale: a random walk with a step distributed according to the Cauchy law.
In the case of integrability, the following theorem holds:
Theorem 2 A real-valued Markov process \((X_t, \mathcal{F}_t, t \in T), \; T \subset \mathbb {R}\) is a martingale (with respect to the same filtration \((\mathcal{F}_t)\)) if and only if \((X_t)\) is an integrable process and \[
\mathbb {E}\left[X_t \mid X_s \right] = X_s
\tag{1}\] holds for \(s \leq t, \; s,t \in T\).
For the process \((X_t)\) to satisfy condition Equation 1, it is necessary that its mean function be constant. From this we get a second example of a Markov process that is not a martingale: the Poisson process.
Furthermore, even if a Markov process is integrable and has a constant mean function, this still does not guarantee that it is a martingale, as the following problem shows.
ExampleExample 5
Let \(X_0 \sim \frac{1}{2}(\delta_1 + \delta_{-1})\), i.e. \(\mathbb {P}\left(X_0 = -1\right) = \mathbb {P}\left(X_0 = 1\right) = \frac{1}{2}\). Let \[
X_n = \begin{cases} X_{n-1} + 1, & X_{n-1} > 0 \\ X_{n-1} - 1, & X_{n-1} < 0\end{cases}, \qquad n \in \mathbb {N}
\] Sketch the sample paths of \((X_n)\). Prove that \((X_n, n \in \mathbb {Z}_+)\) is an integrable Markov process with a constant mean function that is not a martingale.
SolutionSolution
Integrability and the Markov property are obvious, and \(\mathbb {E}\left[X_n\right] = 0\) by symmetry: \(X_n \sim \frac{1}{2}\left(\delta_{n+1} + \delta_{-(n+1)}\right)\). At the same time \[
\mathbb {E}\left[X_n \mid \mathcal{F}_{n-1}\right] = X_{n-1} + \operatorname {sign}(X_{n-1}) \neq X_{n-1} \quad \text{a.s.},
\] so \((X_n)\) is not a martingale: it βstays putβ only on average unconditionally, but not conditionally.
The only possible trajectories (up to sign) of the process from the example: \(X_0 = \pm 1\) with equal probability, and then \(X_n = X_{n-1} + \operatorname{sign}(X_{n-1})\) β the process moves deterministically away from zero. The button below flips the coin again (a new \(X_0\)), and the slider \(n\) highlights a point on the current trajectory and shows next to it the conditional forecast \(\mathbb{E}[X_{n+1}\mid\mathcal F_n]\): it coincides exactly with the next point of the trajectory β βstanding stillβ is impossible for any \(n\), even though unconditionally \(\mathbb{E}[X_n]\equiv 0\).
Xβ = +1
ProblemProblem 3
If a real-valued random process \(\xi_t\) is Markov, then so is the process \(f(\xi_t)\), where \(f\) is an injective map. In particular, if \(W_t\) is a Wiener process, then \(W_t^3\) is Markov. But show that \(W_t^3\) is not a martingale.
Producing an example of a martingale that is not a Markov process is a bit trickier:
ExampleExample 6
Let \(\left(X_{n}, n \geqslant 0\right)\) be independent random variables uniformly distributed on the set \(\{ -1,0,1\}\). Consider the process \[
Y_{n}= X_{0} X_{1}+X_{1} X_{2}+\ldots +X_{n-1} X_{n}
\] Prove that \(Y_{n}\) is a martingale with respect to the filtration \[
\mathbb {F}=\left(\sigma \left(X_{0}, X_{1}, \ldots , X_{n}\right), n \in \mathbb {Z}_{+}\right),
\] but is not a Markov process with respect to it.
SolutionSolution
\[
Y_n = \left(BX \bullet S\right)_n
\]
where \(S_n = X_1 + X_2 + \ldots + X_n\), \((Bf)(n) = f(n-1)\), where \(f: \mathbb {Z}_+ \to \mathbb {R}\) is an arbitrary function. \(B\) is the time shift, the backward shift.
Not Markov: if \((Y_n)\) were Markov with respect to \(\mathbb {F}\), then the conditional probability \(\mathbb {P}\left(Y_2 = 1 \mid \mathcal{F}_1\right)\) would a.s. be a function of \(Y_1\). But on the event \(\left\{ X_1 = 0\right\}\) we have \(Y_1 = 0\) and \(Y_2 = X_1\left(X_0 + X_2\right) = 0\), whence
Both events lie in \(\mathcal{F}_1\) and have positive probability, i.e. the conditional distribution of \(Y_2\) given \(\mathcal{F}_1\) is not determined by the value of \(Y_1\).
4 Martingales in discrete time
In this section \(T = \mathbb {Z}_+ = \left\{ 0,1,2,3,\ldots \right\}\).
4.1 Doob decomposition
Definition 3 The process \(\left(X_{n}, n \in \mathbb {N}\right)\) is predictable with respect to the filtration \(\left(\mathcal{F}_{n}, n \in \mathbb {Z}_{+}\right)\) if \(X_{n}\) is measurable with respect to \(\mathcal{F}_{n-1}\) for all \(n \in \mathbb {N}\).
Theorem 3 (Doob decomposition) Let \(\left(X_{n}, n \in \mathbb {Z}_{+}\right)\) be an \(L^{1}\)-process, adapted to the filtration \(\mathbb {F}=\left(\mathcal{F}_{n}, n \in \mathbb {Z}_{+}\right)\). Then there exists a unique (up to stochastic equivalence in the narrow sense) decomposition of the form \[
X_{n}=M_{n}+A_{n}, \quad n \in \mathbb {Z}_+
\] where \(M_{n}\) is a martingale with respect to \(\mathbb {F}\), \(A_{n}\) is a predictable process with respect to \(\mathbb {F}\), and \(A_{0}=0\) a.s.
Note, in connection with the theorem, that the process \(\left(X_{n}, n \in \mathbb {Z}_{+}\right)\) is a submartingale with respect to \(\mathbb {F}\) if and only if, in its Doob decomposition, the sequence \(A_{n}\) is a.s. non-decreasing.
ProblemProblem 4
Prove the Doob decomposition theorem for representing an \(L^1\)-process as a sum of a martingale and a predictable process.
HintHint
For the existence proof, set \[
\begin{align} M_n & = X_0 + \sum _{k=1}^n \left(X_k - \mathbb {E}\left[X_k \mid \mathcal{F}_{k-1}\right]\right) \\ A_n & = X_n - M_n = \sum _{k=1}^n \left( \mathbb {E}\left[X_k \mid \mathcal{F}_{k-1}\right] - X_{k-1}\right) \end{align}
\]
ProblemProblem 5
Let \(\left(X_{n}, n \in \mathbb {Z}_{+}\right)\) be a Galton-Watson branching process with offspring distribution \(\operatorname {Pois}(3)\). Find the Doob decomposition for this process.
The Doob decomposition βup closeβ: for the simple symmetric random walk \(S_n\), the submartingale \(X_n = S_n^2\) splits into the sum of a martingale \(M_n = S_n^2 - n\) and a predictable nondecreasing compensator \(A_n = n\) β all of the submartingaleβs βsystematic growthβ is concentrated in the compensator. The slider \(\theta\) animates the subtraction of the compensator: at \(\theta = 0\), \(X_n\) is shown; at \(\theta = 1\), \(M_n = X_n - A_n\); intermediate values show \(X_n - \theta A_n\). The checkbox shows/hides \(A_n\) itself, and the button regenerates the random walk.
4.2 Convergence of martingales
The statements and problems below are formulated for discrete time, but they are in fact also true for continuous time.
Theorem 4 (Boundedness in \(L^1\) suffices for a.s. convergence of a martingale) Let \(\left(X_{n}, n \in \mathbb {Z}_+\right)\) be a submartingale such that \(\forall n \in \mathbb {Z}_+: \; \mathbb {E}\left[X_n^+\right] \leq M\) for some \(M > 0\) (i.e. the family \((X_n^+)_{n \in \mathbb {Z}_+}\) is bounded in the norm of the space \(L^1\))1. In particular, this holds if \(X_n\) is simply bounded in \(L^1\). Then there exists a random variable in \(L^1\), conventionally denoted \(X_\infty\), such that
If, in addition, \((X_n, n \in \mathbb {Z}_+)\) is uniformly integrable, then \(X_n \xrightarrow [n \to \infty ]{L^1} X_\infty\).
Recall that a family of random variables \((X_\alpha , \alpha \in A)\) is called uniformly integrable if there exists a function \(G: \mathbb {R}_+ \to \mathbb {R}_+\), growing faster than linearly (i.e. \(\frac{G(x)}{x} \xrightarrow [x \to +\infty ]{} + \infty\)), such that the expectations \(\mathbb {E}\left[G(\left|X_{\alpha }\right|)\right]\) are uniformly (in \(\alpha\)) bounded2. For example, boundedness (in norm) in the space \(L^1\) is not sufficient for uniform integrability, but boundedness in the space \(L^p\) for an arbitrary \(p > 1\) is already sufficient.
Let us recall a few properties of uniform integrability (UI):
\(X_t \xrightarrow [t\to \infty ]{L^1} X\) if and only if \(X_t \xrightarrow [t\to \infty ]{\mathbb {P}} X\) and the family \((X_t, t \in \mathbb {R}_+)\) is uniformly integrable.
Conditional expectations of an integrable random variable are UI. Namely, let \(X \in L^1 = L^1(\Omega , \mathcal{F}, \mathbb {P})\) and let \(\mathcal{G}_\alpha \subset \mathcal{F}, \; \alpha \in A\) be some family of sigma-subalgebras. Then the family \(\left(\mathbb {E}\left[X \mid \mathcal{G}_\alpha \right], \; \alpha \in A\right)\) is UI.
Theorem 5 (\(L^p\)-convergence of martingales) Let \(p>1\) and let \(X_n\) be a martingale bounded in the space \(L^p\). Then there exists an \(\mathcal{F}_\infty\)-measurable random variable \(X_\infty \in L^p\), such that \(X_n \xrightarrow [n \to \infty ]{\text{a.s.}, L^p} X_\infty\).
Let \(Z_1, Z_2, \ldots\) be independent random variables such that \[
Z_n =\begin{cases} a_n, & \text{with probability } \frac{1}{2n^2} \\ 0, & 1 - \frac{1}{n^2} \\ -a_n, & \frac{1}{2n^2} \end{cases},
\] where the sequence \(a_n\) is defined recurrently: \(a_1 = 2, \; a_n = 4\sum_{j=1}^{n-1} a_j\). Show that \(Y_n := \sum_{j=1}^n Z_j\) is a martingale. Show that \((Y_n, n \in \mathbb {N})\) has an a.s. limit, while there is no \(M > 0\) such that \(\mathbb {E}\left[\left|Y_n\right|\right] \leq M, \; \forall n \in \mathbb {N}\).
The problem shows that, in general, a martingale can converge a.s. even without the conditions of Theorem Theorem 4 holding.
ProblemProblem 8
Give an example of a nonnegative martingale \(X_n\) such that \(\mathbb {E}\left[X_n\right] = 1\), while \(X_n \xrightarrow [n\to \infty ]{\text{a.s.}} 0\).
A nonnegative martingale \(X_n = \xi_1 \cdots \xi_n\), where the \(\xi_i\) are independent and take the values \(\frac12\) and \(\frac32\) with equal probability (so that \(\mathbb{E}\left[\xi_i\right] = 1\)): \(12\) simulated trajectories. Almost all of them die out (\(X_n \to 0\) a.s., since \(\mathbb{E}\left[\ln \xi_i\right] < 0\)), even though \(\mathbb{E}\left[X_n\right] = 1\) for all \(n\) β there is no convergence in \(L^1\), and the family is not uniformly integrable. The button regenerates the bundle and simultaneously recomputes the sample mean of \(X_{80}\) over a much larger (unseen) batch of trajectories: the counter accumulates over all clicks and stays close to \(1\) thanks to rare but enormous outliers among the dying-out paths.
Trajectories in statistic: 0Sample mean Xββ: β
4.3 Optional stopping of a martingale
Theorem 6 (Optional stopping theorem: a stopped martingale is still a martingale) Let \(\left(X_{n}, \mathcal{F}_n, n \in \mathbb {Z}_+\right)\) be a submartingale (martingale). Let \(\tau\) be an arbitrary stopping time with respect to the filtration \(\mathbb {F} = (\mathcal{F}_n, n \in \mathbb {Z}_+)\). In particular, \(\tau\) may equal \(\infty\) with nonzero probability. Then the stopped process\[
X^\tau _n := X_{\min (\tau , n)} = \begin{cases} X_n, & n < \tau \\ X_\tau , & n \geq \tau \end{cases}
\] is also a submartingale (respectively, a martingale) with respect to \(\mathbb {F} = (\mathcal{F}_n, n \in \mathbb {Z}_+)\).
The stopped process \(S^\tau_n = S_{\min(\tau, n)}\) for seven simulated trajectories of the simple symmetric random walk started at \(s_0 = 3\), where \(\tau\) is the exit time from the strip \([a, b]\): once the boundary is reached, the trajectory βfreezesβ (a dot). By the optional stopping theorem, \(S^\tau\) is still a martingale: \(\mathbb{E}\left[S^\tau_n\right] = s_0\) for all \(n\). Move the sliders for the strip boundaries and click βRegenerateβ: the sample mean of the stopped value accumulates over all runs and stays close to \(s_0 = 3\) regardless of the stripβs width.
Runs in statistic: 0Mean SΟ: β (sβ = 3)
4.4 Optional sampling of a martingale
Theorem 7 (The optional sampling theorem, sometimes also called the optional stopping theorem) Let \((X_n, n \in \mathbb {Z}_+)\) be a martingale, let \(\sigma \leq \tau\) be two stopping times with values in \(\mathbb {Z}_+ \cup \left\{ +\infty \right\}\), and let the stopped process \((X_n^\tau )\) be uniformly integrable (on the event \(\left\{ \tau = +\infty \right\}\) we set \(X_\tau := \lim_{n\to \infty } X^\tau_n\); the limit exists a.s. by uniform integrability). Then \[
\mathbb {E}\left[X_\tau \mid \mathcal{F}_\sigma \right] \stackrel{\text{a.s.}}{=} X_\sigma
\] and, in particular, \[
\mathbb {E}\left[X_\tau \right] = \mathbb {E}\left[X_\sigma \right] = \mathbb {E}\left[X_0\right]
\] Uniform integrability of \((X_n^\tau )\), in turn, holds under any of the following conditions:
\(\tau \in L^\infty\), i.e. \(\tau\) is a.s. bounded: \(\exists M > 0: \; \mathbb {P}\left(\tau < M\right) = 1\). Here we have strong restrictions on the stopping time and no restrictions on the martingale.
\(\tau \in L^1\) and there exists a constant \(c > 0\) such that
(the conditional increments of the martingale are bounded up to time \(\tau\)). In particular, this holds if \(\left|X_n - X_{n-1}\right| \leq c\) a.s. for all \(n\).
Here we have moderate restrictions on the stopping time and moderate restrictions on the martingale.
\(\tau\) is arbitrary, but the process \((X_n)\) is itself UI. Here we have no restrictions on the stopping time and strong restrictions on the martingale.
The optional stopping theorem means that the mean value of a martingale at random time instants remains the same as at deterministic ones.
Corollary 1 Let \(S_n\) be a martingale, with \(S_n - S_{n-1}\) uniformly bounded by some constant. Let \((C_n)\) be a predictable process, also uniformly bounded by a constant, and let \(\mathbb {E}\left[T\right]<\infty\) for some stopping time \(T\). Then \[
\mathbb {E}\left[\left(C \bullet S\right)_{T}\right] = 0
\]
ExampleExample 7
Give an example of a martingale \((X_{n}, n \in \mathbb {Z}_+)\) and stopping times \(\tau , \sigma\) with respect to its natural filtration such that \(\mathbb {E}\left[X_{\tau }\right] \neq \mathbb {E}\left[X_{\sigma }\right]\).
HintHint
Take a random walk.
SolutionSolution
Consider the simplest symmetric random walk on the line \(\left(S_{n}, n \in \mathbb {Z}_{+}\right)\) and set \(\tau =\min \left\{ n: S_{n}=\right.\)\(1\} , \sigma =\min \left\{ n: S_{n}=2\right\}\). Recall that \(\tau , \sigma < \infty\) a.s., i.e. these are not merely stopping times in the general sense but stopping times that are a.s. finite. Furthermore, \(S_{n}\) is a martingale. But \[
\mathbb {E}\left[S_\tau \right] = 1 < 2 = \mathbb {E}\left[S_\sigma \right]
\]
We have already solved the following problem by combinatorial methods, but it is instructive to solve it by martingale methods as well.
ExampleExample 8 - The gamblerβs ruin problem
Let \(a<{s_0}<b\) be integers, and let \(S_{n} = {s_0} + \sum_{i=1}^{n} \xi_i, \; n \geqslant 0\), be the simplest random walk with probability \(p\) of a step to the right, started at the point \(s_0\). Denote by \(\tau = \min \left\{ n: S_{n} \in \left\{ a, b\right\} \right\}\) the time at which the process \(S_{n}\) exits the strip. Compute the distribution of \(S_\tau\) and \(\mathbb {E}\left[\tau \right]\) in the case \(p = \frac{1}{2}\) (i.e. the symmetric case).
HintHint
\(p = \frac{1}{2}\). To compute \(\operatorname {Law}\left(S_\tau \right)\) one must consider the martingale \(S_n\). To compute \(\mathbb {E}\left[\tau \right]\), prove that \(M_n := S_n^2 - n\) is also a martingale. Next, for an arbitrary \(k \in \mathbb {N}\) take the stopping time \(\tau_k := \tau \wedge k \in L^\infty\) and apply the optional sampling theorem to it and to \(M_n\). Then let \(k \to +\infty\).
SolutionSolution
We have \(a < {s_0} < b\) integers, \(S_n = {s_0} + \sum_{i=1}^n \xi_i\) a random walk:
Distribution of \(S_\tau\). \(S_n\) is a martingale. Note that \(\left|S_n^\tau \right| \leq \max (\left|a\right|,\left|b\right|)\), so we can use the optional stopping theorem: \(\mathbb {E}\left[S_\tau \right] = \mathbb {E}\left[S_0\right] = {s_0}\). At the same time
\[
\mathbb {E}\left[S_\tau \right] = a \mathbb {P}\left(S_\tau = a\right) + b \mathbb {P}\left(S_\tau = b\right) = a \mathbb {P}\left(S_\tau = a\right) + b (1 - \mathbb {P}\left(S_\tau = a\right) )
\]
We obtain the equation:
\[
{s_0} = a \mathbb {P}\left(S_\tau = a\right) + b (1 - \mathbb {P}\left(S_\tau = a\right) )
\]
Expectation \(\mathbb {E}\left[\tau \right]\). \(S_n\) is an \(L^2\)-process with independent increments and a constant mean function. Moreover \(\operatorname {Var}\left[S_n\right] = n \operatorname {Var}\left[\xi_1\right] = n\). Then \(M_n := S_n^2 - n\) is a martingale. Hence \(s_0^2 = \mathbb {E}\left[M_0\right] = \mathbb {E}\left[M_{\tau \wedge k}\right] = \mathbb {E}\left[S^2_{\tau \wedge k}\right] - \mathbb {E}\left[\tau \wedge k\right]\).
Let us prove that \(\mathbb {E}\left[\tau \wedge k\right] \xrightarrow [k \to \infty ]{} \mathbb {E}\left[\tau \right]\). Note that \(\tau \wedge k \xrightarrow [k \to \infty ]{\text{a.s.}}\tau\), and for every \(\omega\) the sequence \(\tau (\omega ) \wedge k\) is non-decreasing in \(k\). Hence, \(\mathbb {E}\left[\tau \wedge k\right] \xrightarrow [k \to \infty ]{} \mathbb {E}\left[\tau \right]\).
Let us prove that \(\mathbb {E}\left[S^2_{\tau \wedge k}\right] \xrightarrow [k \to \infty ]{} \mathbb {E}\left[S^2_{\tau }\right]\). Note that \(S^2_{\tau \wedge k} \xrightarrow [k \to \infty ]{\text{a.s.}} S^2_{\tau }\), and \(\left|S^2_{\tau \wedge k}\right| \leq \max (a^2, b^2)\), so we have \(L^1\)-convergence.
Solve the gamblerβs ruin problem (see the previous example) by the martingale method for the case \(p \neq \frac{1}{2}\)
HintHint
To compute \(\operatorname {Law}\left(S_\tau \right)\) consider \(Y_n := \frac{1}{\theta^{S_n}}\), where \(\theta = \frac{p}{1-p}\). Prove that \(Y_n\) is a martingale.
To compute \(\mathbb {E}\left[\tau \right]\) consider the process \(Z_n = S_n - (2p-1)n\), prove that \(Z_n\) is a martingale.
The gamblerβs ruin problem: the probability of reaching \(b\) before being ruined at \(a = 0\), as a function of the starting capital \(s_0\): \(\mathbb{P}\left(S_\tau = b\right) = \dfrac{\varrho^{a} - \varrho^{s_0}}{\varrho^{a} - \varrho^{b}}\), where \(\varrho = q/p\) (for \(p = \frac12\) this expression is the limit \(\varrho \to 1\), which degenerates into the linear function \(s_0/b\)). Move the slider \(p\) to see how the curve deforms from a straight line into an exponential βcliffβ β even a slight bias in the step probability makes winning with a small capital nearly impossible β and the slider \(b\) to change the width of the strip.
ExampleExample 9 - A monkey types ABRACADABRA
Suppose that at times \(1,2,3, \ldots\) a monkey types a capital letter at random, and the sequence of typed letters forms an independent and identically distributed sequence of random variables, each of which is chosen uniformly from 33 possible capital letters (of the Russian alphabet).
Let \(T = T_{\text{Π}}\) be the first time at which the monkey has typed the letter Π. Prove that \(T\) is a.s. finite and find \(\mathbb {E}\left[T\right]\);
Let \(T = T_{\text{ΠΠΠ ΠΠΠΠΠΠΠ Π}}\) be the first time at which the monkey has typed the sequence of letters ΠΠΠ ΠΠΠΠΠΠΠ Π (ABRACADABRA). Prove that \(T\) is a.s. finite and find \(\mathbb {E}\left[T\right]\).
SolutionSolution
Let \(A_1, A_{2}, \ldots\) be the letters typed by the monkey.
Enum-item(1)
Let \(\xi_i = \; \mathbb {1}_{\text{Π}}(A_i)\). Then \(\xi_1, \xi_2 ,\ldots\) are i.i.d.r.v.βs, distributed as \(\operatorname {Ber}(1/33)\).
\(T\) is the time of the first occurrence of ABRACADABRA, while \(T'\) is the index of the first block of \(11\) consecutive letters (blocks do not overlap) in which ABRACADABRA is written in full; such a block ends at step \(11(T'+1)\). The first occurrence overall could happen earlier, so \(T \leq 11(T' + 1)\). Moreover \(T' + 1 \sim \operatorname {Geom}\left((1/33)^{11}\right)\), i.e. \(T' \in L^1\). Hence \(T \in L^1\), it has finite expectation. But how do we find the exact value of this expectation?
Let us set up a casino next to the monkey! In our casino there is only one game: one can bet on the next letter the monkey will type. Moreover, let the casino be fair: the payout odds for a win are \(33\). In that case the expected result of the game is exactly \(0\).
Suppose that immediately before each time instant \(n=1,2, \ldots\) a new player arrives. They bet \(1\) ruble that the \(n\)-th letter will be Π. If they lose, they leave. If they win, they receive \(33\) rubles, all of which they bet on the \((n+1)\)-th letter being Π. If they lose, they leave. If they win, they bet their entire fortune of \(33^{2}\) on the \((n+2)\)-th letter being Π , and so on through the sequence ABRACADABRA.
Let \(X_n\) be the combined capital of all players at time \(n\) (we take \(X_0 = 0\)). Suppose we prove that \(X_n\) is a martingale, and that there exists a constant \(C > 0\) such that \(\left|X_n - X_{n-1}\right| < C\) a.s. for all \(n\). Then, by the optional sampling theorem, we get \(0 = \mathbb {E}\left[X_0\right] = \mathbb {E}\left[X_{T}\right]\). How do we find \(X_T\)? At every time instant a new player arrives, and they spend exactly \(1\) ruble on the game, regardless of whether they are still playing (i.e. have won every round they have played) or have already dropped out. Hence, the total expenditure of the players by time \(T\) is exactly \(T\). But how are the earnings determined? Only those still in the game at time \(T\) have earnings (everyone else has lost their ruble). There are 3 such people:
the player who arrived at step \(T - 1\), and correspondingly named Π. Their earnings equal \(33\);
the player who arrived at step \(T - 4\), and correspondingly guessed ΠΠΠ Π (ABRA). Their earnings equal \(33^4\);
the player who arrived at step \(T - 11\), and correspondingly guessed the entire word ΠΠΠ ΠΠΠΠΠΠΠ Π (ABRACADABRA). Their earnings equal \(33^{11}\);
The other players have already lost. For example, the player who entered at round \(T - 6\). They correctly guessed the first Π. But then they called the letter Π, while the monkey typed Π.
As a result we have \(X_T = 33^{11} + 33^4 + 33 - T\), \(\mathbb {E}\left[X_T\right] = 0\) and
What follows is a justification of the points left unproven.
Let \(C_{n}^{j}\) be the bet of player \(j\) at time \(n\).
\[
C_{n}^{j}= \begin{cases} 0 & \text{ if } n<j \\ 1 & \text{ if } n=j \\ 33^{k} & \text{ if } A_{j}, \ldots , A_{j+k-1} \text{ were correct and } n=j+k \\ 0 & \text{ otherwise } \end{cases}
\]
It is easy to see that each \(C_{n}^{j}\) is a predictable process, since it is determined using only information up to and including the \((n-1)^{\text{th }}\) bet. Now let us define the martingale \(M_{n}^{j}\) as the winnings after \(n\) bets for player \(j^{t h}\). Note that this definition of \(M_{n}^{j}\) already incorporates \(C_{n}^{j}\), since we defined \(M_{n}^{j}\) as the total winnings, not the winnings per unit stake. It will be easier to solve the problem by defining \(M_{n}^{j}\) this way. Also note that each player leaves the game if they lose even one of their bets. Thus, if the \((n+1)^{t h}\) bet is to be made, then \(M_{n}^{j}= 33^{n}\) and \(M_{n+1}^{j}=33^{n+1}\) with probability \(1 / 33\) and \(0\) with probability \(32 / 33\). This happens because the monkey types each letter at random and independently of the previous letters, with each letter having an equal probability of being typed at any given moment. To show that \(M_{n}^{j}\) is a martingale, we must show that
Is \(M_{n}^{j}\) adapted? \(M_{n}^{j}\) is determined by the event \(A_{n}\) and by whether the letter typed at time \(n\) is correct.
Is \(E\left(\left|M_{n}^{j}\right|\right)<\infty , \forall n\)? \(M_{n}^{j}\) is always nonnegative and the maximum value of \(M_{n}^{j}\) is \(33^{n}\), i.e. attained when the player has won all \(n\) previous times. Since \(33^{n}<\infty\) and \(E\left[\left|M_{n}^{j}\right|\right]=E\left[M_{n}^{j}\right]<33^{n}\), (2) holds.
Is \(E\left[M_{n}^{j} \mid \mathcal{F}_{n-1}\right]=M_{n-1}^{j}, n \geq 1\)? There are two cases. If the player has lost at some point before time \(n\), then, given this information, \(E\left[M_{n}^{j} \mid \mathcal{F}_{n-1}\right]=0=M_{n-1}^{j}\). If the player has won the first \((n-1)\) times, then
Is there a constant \(C>0\) such that \(\left|X_{n} - X_{n-1}\right| \leq C\) a.s. for all \(n\)? Yes: at every moment there are at most \(11\) players in the game (those who arrived over the last \(11\) steps), and a player who has made \(k\) winning bets by this moment holds capital \(33^{k}\), \(k \leq 10\). In one step such a player either loses all their capital (\(-33^k\)) or increases it by \(32 \cdot 33^{k}\); also \(1\) ruble is spent by the newly arrived player. In total
A fair coin is tossed an infinite number of times in succession. Find the expected time of the first appearance of the sequence
T
TTTT
HTHH
HTHT
5 Martingales in continuous time
Theorem 8 (Optional stopping theorem) Let \(\left(X_{t}, t \geqslant 0\right)\) be a martingale with respect to \(\mathbb {F}=\left(\mathcal{F}_{t}, t \geqslant 0\right)\) with right-continuous sample paths. Then \(\forall \tau , \sigma : \tau \leqslant \sigma\) (a.s.) β bounded (i.e. in \(L^{\infty }\)) stopping times with respect to \(\mathbb {F}\) β it holds that \[
\mathbb {E}\left[X_{\tau }\right] = \mathbb {E}\left[X_{\sigma }\right]
\]
ProblemProblem 11
Let \(\left(W_{t}, t \geqslant 0\right)\) be a Wiener process, and let \(\tau =\min \{ t:\)\(\left.\left|W_{t}\right|=1\right\}\). Compute \(\mathbb {E}\left[\tau \right]\).
HintHint
Prove that the process \(W_t^2 - t\) is a martingale with respect to the natural filtration of \(W_t\). Use the optional stopping theorem.