Past exam of the probability, measure and martingales course of the University of Oxford / 2023 (B8.1, A16550W1)

Solutions to every part of all three questions of the probability, measure and martingales course of the University of Oxford Part B examination, sat on 5 June 2023. Source: original released PDF, bundle pages 288–291; paper pages 1–4. The native PDF confirms the endpoint defect in Question 2: its slope formula evaluates $f$ outside $[0,1]$ when $X=1$. We specify values on that null set below. Question 1(b)'s literal measurability assertion uses everywhere sign-valued random variables; for arbitrary versions with the stated probability distributions, it holds up to null sets, as explained in the solution.

Fix $A\in {\mathcal{A}}_1$ and defineThis is a Dynkin system: it contains $\Omega$; taking complements preserves the equality because $\mathbb{P}(A\cap B^c)=\mathbb{P}(A)-\mathbb{P}(A\cap B)$; and countable additivity preserves it under disjoint unions. The hypothesis says that ${\mathcal{D}}_A$ contains the pi-system ${\mathcal{A}}_2$. Hence Dynkin lemma gives ${\mathcal{D}}_A={\mathcal{G}}_2$.

Now fix any $B\in {\mathcal{G}}_2$ and putThe same complement and disjoint-union calculations make this a Dynkin system. The first step shows that it contains ${\mathcal{A}}_1$, so Dynkin lemma gives ${\mathcal{E}}_B={\mathcal{G}}_1$. ThusThis is precisely the definition of independent sigma-algebras, and proves independence extended from generating pi-systems.

For $m\ge 1$, fix signs $x_1,\dots ,x_m$. The constraints $X_j=x_j$ leave exactly two choices for the $(m+1)$ signs $Y_0,\dots ,Y_m$: choose $Y_0$ freely, then set $Y_1=Y_0{x}_1$ and $Y_j=x_{j-1}{x}_j$ for $2\le j\le m$. Each input tuple has probability $2^{-(m+1)}$ by independence. ConsequentlyEvery finite subfamily is a marginal distribution of one such initial segment, so the entire sequence is independent, with fair sign probability distributions.

Using the usual everywhere sign-valued representatives, for every $n\ge 1$ we haveThe right side is measurable with respect to $\sigma (\mathcal{Y},{\mathcal{T}}_n)$. Therefore $Y_0$ is measurable with respect to their intersection $\mathcal{G}$.

Write $\mathcal{T}={\bigcap }_n{\mathcal{T}}_n$. The Kolmogorov zero-one law applies to the independent random variables $(X_n)$, so every event $C\in \mathcal{T}$ has probability zero or one. Also $Y_0$ is independent of $\mathcal{Y}$: this follows first for finite intersections of sign events from the given independence, then for their generated sigma-algebra by part (a).

The sets $D\cap C$ with $D\in \mathcal{Y}$ and $C\in \mathcal{T}$ form a pi-system generating $\mathcal{H}$. If $\mathbb{P}(C)=0$, the event $D\cap C$ has probability zero and is independent of every event in $\sigma (Y_0)$. If $\mathbb{P}(C)=1$, it differs from $D$ by a null set, so the same independence follows from that of $Y_0$ and $\mathcal{Y}$. Another application of part (a) provesIn particular $\mathcal{H}$ cannot contain the nontrivial event $\{Y_0=1\}$, whereas $\mathcal{G}$ does. Thus adjoining a sigma-algebra need not commute with a decreasing intersection.

There is a small version qualification if the assumptions specify only the probability distributions, allowing exceptional values other than signs. Put $q_n=X_n/(Y_1\cdots Y_n)$ when the denominator is nonzero, and $q_n=0$ otherwise. For $k\ge n$, $q_k$ is measurable with respect to $\sigma (\mathcal{Y},{\mathcal{T}}_n)$. The limit superior of $(q_k)$, after scalar clipping to $[-1,1]$, is therefore $\mathcal{G}$-measurable and equals $Y_0$ almost surely. Literal measurability of an arbitrary version of $Y_0$ need not follow without choosing sign-valued representatives or adjoining the ambient null sets. All the independence conclusions are unaffected.

The first entrance time ${\tau }_K$ is a stopping time, because $\{{\tau }_K\le n\}={\bigcup }_{j=0}^n\{M_j\le -K\}\in {\mathcal{F}}_n$. Before this time $M_n>-K$; at entrance, the bounded increments give $M_{{\tau }_K}>-K-L$. Thus the stopped martingaleis a nonnegative martingale. Here the stopped process is a martingale since its increment is $1_{\{{\tau }_K>n\}}(M_{n+1}-M_n)$, whose conditional expectation given ${\mathcal{F}}_n$ is zero.

The martingale convergence theorem states that a nonnegative martingale converges almost surely to a finite integrable random variable; indeed its expectations are constant, giving the required bound in the L1 norm. Apply this theorem to $(N_n)$. On $\{{\tau }_K=\infty \}$ the stopped process equals the original one at every time. HenceThe overshoot bound is why the assumption of bounded increments matters.

Apply part (i) for every positive integer $K$ and discard the countable union of its exceptional null sets. A sample path bounded below never reaches $-K$ for some such $K$, and must therefore converge to a finite limit of a sequence.

Apply the same argument to the martingale $(-M_n)$. Outside one more null set, every sample path bounded above also converges finitely. Thus a sample path which does not converge finitely must be unbounded in both directions. Each finite initial segment has finite values, so removing any such segment preserves unboundedness. It follows that the limit superior is $+\infty$ and the limit inferior is $-\infty$. ConsequentlyThis proves the bounded-increment martingale convergence-or-oscillation dichotomy; in particular one-sided divergence to infinity is impossible with positive probability.

Choose versionsThe stochastic process $(A_n)$ is increasing, and its $k$th increment is ${\mathcal{F}}_{k-1}$-measurable, so it is predictable. The Doob decomposition theorem therefore givesTo check the martingale property directly, each summand is integrable and has zero conditional expectation given ${\mathcal{F}}_{k-1}$. The sums are an adapted process for the given filtration. Thus $\mathbb{E}[M_n\mid {\mathcal{F}}_{n-1}]=M_{n-1}$. Its bounded increments satisfy $|M_n-M_{n-1}|\le 1$.

Both $X_n$ and $A_n$ are increasing, so each has a limit of a sequence in $[0,\infty ]$. Apply part (c)(ii) to the martingale $M_n=X_n-A_n$, whose bounded increments were verified in part (i).

On $\{X_{\infty }<\infty ,A_{\infty }=\infty \}$ we would have $M_n\to -\infty$. On $\{X_{\infty }=\infty ,A_{\infty }<\infty \}$ we would have $M_n\to +\infty$. Both events have probability zero by the convergence-or-oscillation conclusion. Hence the two divergence events agree up to a null set. Since $X_{\infty }=\infty$ means precisely that infinitely many $B_n$ occur,Taking probabilities proves the displayed equality in the question. This stronger agreement of events is the Conditional Borel-Cantelli lemma.

Suppose the events $(B_n)$ are mutually independent events. Then $B_k$ is independent of ${\mathcal{F}}_{k-1}$, first by factorization against finite intersections of previous events and then by part (a). ThereforeIf ${\sum }_k\mathbb{P}(B_k)=\infty$, the sum in part (ii) is infinite almost surely, and consequentlyThis is the Second Borel-Cantelli lemma. In fact part (ii) also yields probability zero in the convergent case for these independent events.

The sigma-algebra generated by a random variable $X$ is the smallest sigma-algebra on $\Omega$ making $X$ a measurable function into $(\mathbb{R},\mathcal{B}(\mathbb{R}))$. Equivalently, it is the intersection of all sigma-algebras containing the inverse images $X^{-1}(C)$ of Borel sets $C$.

Let $\mathcal{D}=\{X^{-1}(C):C\in \mathcal{B}(\mathbb{R})\}$. This collection is already a sigma-algebra: $X^{-1}(\mathbb{R})=\Omega$,The right-hand sets are in $\mathcal{D}$, since the Borel sigma-algebra is closed under the indicated operations. Any sigma-algebra making $X$ measurable must contain every member of $\mathcal{D}$. Conversely $\mathcal{D}$ makes $X$ measurable by definition. HenceThis equality holds exactly as a collection of sets, without completing the sigma-algebra.

We prove the Doob-Dynkin lemma here by simple function approximation. Choose $C<\infty$ such that $|Z|\le C$ everywhere, and letEach $Z_m$ is a finite-valued $\sigma (X)$-measurable function and $Z_m\to Z$ pointwise. Write its level sets as $A_{m,j}$, with associated values $z_{m,j}$. By part (i), choose Borel sets $D_{m,j}$ with $A_{m,j}=X^{-1}(D_{m,j})$. Define the Borel measurable functionsAlthough the chosen $D_{m,j}$ need not partition all of $\mathbb{R}$, their inverse images do partition $\Omega$, so $g_m(X)=Z_m$ exactly.

Apply scalar clipping to each $g_m$ with bounds $[-C-1,C+1]$, preserving this equality, and define $g(x)={\mathrm{limsup}}_m{g}_m(x)$. A bounded limit superior of Borel measurable functions is a finite Borel measurable function. At every $\omega \in \Omega$ the limit of a sequence exists and givesThus the factorization is exact for a bounded, exactly $\sigma (X)$-measurable function. If hypotheses are instead given only up to null sets, the corresponding conclusion is a factorization holding almost surely after choosing a representative.

For this part and part (c), take $X$ to be $[0,1]$-valued everywhere. The uniform distribution gives $\mathbb{P}(X=1)=0$, but the paper's expression for $Z_n$ is undefined there because $X_n+2^{-n}>1$. Define $Z_n=0$ on $\{X=1\}$. Keep $X_n=\lfloor 2^{n}X\rfloor /2^n$ exactly as printed, including $X_n=1$ on that null set; this preserves the exact sigma-algebra equality in part (ii). Every slope formula below is asserted on $\{X<1\}$, hence almost surely.

The floor function gives the deterministic boundfor every outcome, including $X=1$. Thus all three convergence assertions hold: there is pointwise, and hence almost sure convergence, as well as convergence in probability and convergence in L2. In detail, for $\epsilon >0$ the probability $\mathbb{P}(|X-X_n|>\epsilon )$ is zero as soon as $2^{-n}\le \epsilon$; alsoThe uniform distribution even gives the exact second moment of the error by integrating over the dyadic partition:

Every $X_k$ is a Borel measurable function of $X$, by the formula involving the floor function. ThusConversely, part (i) gives the everywhere identity $X={\lim }_{k\to \infty }{X}_k$. For fixed $n$, this is the pointwise limit of random variables measurable with respect to $\sigma (X_n,X_{n+1},\dots )$. Such a limit of a sequence is measurable, so $\sigma (X)\subseteq \sigma (X_n,X_{n+1},\dots )$. ConsequentlyThese are increasing-precision observations even when the first finitely many are discarded; they do not behave like the independent random variables whose tail sigma-algebra appears in Question 1(b).

A family $({\xi }_i{)}_{i\in I}$ of integrable random variables is uniformly integrable whenThe Lipschitz condition gives, on $\{X<1\}$,Our chosen zero value on $\{X=1\}$ satisfies the same bound. Hence the random variables $(Z_n)$ are integrable, and for $K\ge L$ every tail expectation in the definition vanishes. Therefore the family is uniformly integrable.

For $1\le j\le n$, repeated use of the floor function identity givesThus the filtration satisfies ${\mathcal{F}}_n=\sigma (X_n)$. Each positive-probability atom of a sigma-algebra here has the formwith probability $2^{-n}$; $\{X=1\}$ is a possible additional null set atom. Averaging over each dyadic interval gives a versionFor a globally defined version of the right side, assign any value, for example zero, on $\{X=1\}$.

Indeed, the displayed random variable is ${\mathcal{F}}_n$-measurable and bounded by $\sup |h|$. On each $A_{n,k}$ its integral isby the uniform distribution. Every member of ${\mathcal{F}}_n$ is a union of the displayed sets and the possible zero-probability atom. Summing these identities therefore verifies the defining conditional expectation property on all of ${\mathcal{F}}_n$.

Each $Z_n$ is a bounded Borel measurable function of $X_n$, including the specified value at $X_n=1$. Therefore $(Z_n)$ is an adapted process for $({\mathcal{F}}_n)$ and consists of integrable random variables.

Fix an atom of a sigma-algebra in ${\mathcal{F}}_n$ with positive probability, corresponding to the dyadic interval $[u,u+\delta )$, with $\delta =2^{-n}$. By the uniform distribution, each half has conditional probability $1/2$. The conditional expectation of $Z_{n+1}$ on that atom is thereforeThe middle values cancel. On the zero-probability atom the conditional expectation can be chosen as zero, agreeing with our version of $Z_n$. Henceso $(Z_n)$ is a martingale. This is the dyadic slope martingale associated with the Lipschitz function $f$.

The uniformly integrable martingale convergence theorem states that a uniformly integrable martingale $(U_n)$ has an integrable terminal random variable $U_{\infty }$ such that $U_n\to U_{\infty }$ almost surely and in the L1 norm, andThe last identity follows by passing to the limit of a sequence in $\mathbb{E}[U_m{1}_A]=\mathbb{E}[U_n{1}_A]$ for $A\in {\mathcal{F}}_n$ and $m\ge n$, using convergence in L1.

Part (b)(iii) verifies uniform integrability for $(Z_n)$, soMoreover $|Z_{\infty }|\le L$ almost surely. In this particular problem the common bound also yields convergence in Lp for every finite $p\ge 1$, including convergence in L2: the dominated convergence theorem applies to $|Z_n-Z_{\infty }{|}^p\le (2L{)}^p$. General uniform integrability alone does not assert these higher-power conclusions.

Choose $Z_{\infty }$ as the pointwise limit of a sequence of $(Z_n)$ where it exists, and as zero otherwise. The convergence event and every $Z_n$ are $\sigma (X)$-measurable, so this is an exactly $\sigma (X)$-measurable version, bounded by $L$. Part (a)(ii), the Doob-Dynkin lemma, supplies a Borel measurable function $g$ on $[0,1]$ such that $Z_{\infty }=g(X)$. Applying scalar clipping to $g$ with bounds $[-L,L]$ preserves that equality and ensures $|g(u)|\le L$ everywhere.

Part (c)(ii) and the conditional expectation formula from part (b)(iv) now giveSince the indices $n$ form a countable family, these identities may be taken on one common full-probability event.

For fixed $n,k$, both the slope and the displayed average are constant on the atom $A_{n,k}$, whose probability is $2^{-n}>0$. An equality holding almost surely of these constants forces the deterministic equalitySum over $0\le k<j$. The telescoping sum givesThus the desired identity holds at every dyadic endpoint, including $1$, without evaluating the undefined slope at $X=1$.

Finally, given $x\in [0,1]$, take dyadic endpoints $x_n\to x$. The Lipschitz condition implies $|f(x_n)-f(x)|\le L|x_n-x|$, and the bound on the Borel measurable function $g$ givesPassing to the limit of a sequence provesThis is a martingale proof of the integral representation of a Lipschitz function. It constructs a bounded Lebesgue integrable function representing the increments of $f$, and in particular proves absolute continuity of $f$. No prior assumption that $f$ has a derivative is needed.

Write $N=a+b+c$ for the conserved total number of tokens. The main case has positive integer initial holdings. If an initial holding is zero, take $\tau =0$; the formulas below still hold when $N>0$. If $N=0$, the stochastic process is constant and $\mathbb{E}[\tau ]=0$.

A discrete-time stopping time for a filtration $({\mathcal{F}}_n)$ is a random variable $\tau$ taking values in $\{0,1,\dots \}\cup \{\infty \}$ such that $\{\tau \le n\}\in {\mathcal{F}}_n$ for every $n$. It means that whether stopping has occurred by time $n$ can be determined from the information available then.

For the first elimination time,Each event in this finite union belongs to ${\mathcal{F}}_j\subseteq {\mathcal{F}}_n$, by the definition of the natural filtration. Therefore $\tau$ is a stopping time. This verification does not require first knowing whether $\tau$ is finite almost surely.

Put $P_n=X_n{Y}_n{Z}_n$. Before $\tau$, all three players are active. Each unordered pair is selected with probability $1/3$, and each direction of transfer then has conditional probability $1/2$. Given the current holdings $(x,y,z)$, a transfer within the first pair has mean productFor transfers within the other two pairs the analogous values are $xyz-y$ and $xyz-x$. Averaging over pairs givesAt and after elimination the product is zero, since an eliminated player never re-enters. In particular the stopped process has incrementThe indicator function is ${\mathcal{F}}_n$-measurable, and the expression in parentheses has zero conditional expectation on its support. The stopped process is adapted and integrable: at fixed $n$, its absolute value is bounded by $N^3+nN/3$. HenceThis is the product martingale for three-player token exchange.

After $\tau$, the token product remains zero, whereas the deterministic term $nN/3$ continues to increase. Combining this with the pre-elimination calculation in part (ii),The stochastic process is adapted and integrable at each fixed time, and the displayed conditional expectation is nonnegative. Thus $(M_n)$ is a submartingale.

For $N>0$ it is neither a martingale nor a supermartingale. If $a,b,c>0$, there is positive probability that the first player transfers a token to the second in each of the next $a$ rounds. Until the last such round all three remain active, so this event has probability $6^{-a}>0$ and entails $\tau \le a$. At time $n=a$ the displayed conditional expectation is therefore strictly positive on an event of positive probability, ruling out both the zero drift required of a martingale and the nonpositive drift required of a supermartingale. If an initial holding is zero, $\tau =0$ and the same conclusion follows immediately. The degenerate case $N=0$ gives a constant martingale.

The bounded-time optional sampling theorem says that for an integrable discrete-time martingale $(U_n)$ and a bounded stopping time $S$, $\mathbb{E}[U_S]=\mathbb{E}[U_0]$. It requires no assumption about an eventual unbounded stopping time.

Apply this theorem with $S=n\wedge \tau$, or simply take the expectation of the stopped martingale in part (ii). For $N>0$ we obtainSince $P_{n\wedge \tau }\ge 0$,The monotone convergence theorem now yields $\mathbb{E}[\tau ]\le 3abc/N<\infty$. In particular $\tau <\infty$ almost surely, which has been established without assuming that optional stopping is valid at $\tau$.

For each sample path with finite $\tau$, $P_{n\wedge \tau }$ eventually equals $P_{\tau }=0$. Also $0\le P_{n\wedge \tau }\le N^3$. The dominated convergence theorem gives $\mathbb{E}[P_{n\wedge \tau }]\to 0$. Taking the limit of a sequence in the earlier identity therefore provesFor example, initial holdings $(1,1,1)$ give expectation one, as the first transfer must eliminate its giver. This computes the first elimination time, rather than the later time when one player owns all tokens.

Assume $X$ is square-integrable. Since $X$ and $Y$ have the same probability distribution, $Y$ is also square-integrable and $\mathbb{E}[Y^2]=\mathbb{E}[X^2]$. The product $XY$ is integrable by the Cauchy-Schwarz inequality.

We use the defining test-function identity for conditional expectation: for bounded $\mathcal{G}$-measurable $H$, $\mathbb{E}[XH]=\mathbb{E}[YH]$. Take $H=Y{1}_{\{|Y|\le m\}}$ and let $m\to \infty$. The dominated convergence theorem, with bounds $|XY|$ and $Y^2$, givesThis is the extension of the conditional expectation pull-out identity to this square-integrable multiplier. ConsequentlyA nonnegative random variable with zero expectation is zero almost surely. HenceGeometrically, this is the equality case in the L2 space orthogonal projection interpretation of conditional expectation.

The function ${\varphi }_a(t)=t\wedge a$ is a concave function, and $X\wedge a$ is integrable since $|X\wedge a|\le |X|+a$. The concave form of the conditional Jensen inequality givesThe random variables $X$ and $Y$ have the same probability distribution, so $\mathbb{E}[X\wedge a]=\mathbb{E}[Y\wedge a]$. Using the law of total expectation, the nonnegative difference between the right and left sides of the inequality has zero expectation. It must vanish almost surely. ThereforeThe equality comes from the distributional assumption as well as the conditional Jensen inequality.

We first establish the lower truncation identity as well. The pair $(-X,-Y)$ has the same hypotheses as $(X,Y)$, because conditional expectation is linear and negation preserves equality of probability distributions. Apply part (ii) to this pair and multiply by $-1$ to getFor every real $t$,Using this identity, part (ii), the lower truncation identity, and linearity of conditional expectation givesIn particular the argument does not assume that a function obtained by scalar clipping is a convex function or a concave function.

Write $C_a(t)=(t\wedge a)\vee (-a)$. The bounded random variables $C_a(X)$ and $C_a(Y)$ have the same probability distribution, and the displayed identity identifies the latter as the conditional expectation of the former. They are square-integrable, so part (i) gives $C_a(X)=C_a(Y)$ almost surely. Take $a=1,2,\dots$ and discard the countable union of exceptional null sets. At every remaining outcome, let $a\to \infty$ to obtainThus conditional expectation preserving a distribution forces equality even when only integrability is assumed.

Let $\mathcal{G}=T^{-1}(\mathcal{F})=\{T^{-1}(A):A\in \mathcal{F}\}$. Inverse images commute with complements and countable unions, so this is a sub-sigma-algebra of $\mathcal{F}$. The random variable $X\circ T$ is $\mathcal{G}$-measurable.

The assumption $\mathbb{P}\circ T^{-1}=\mathbb{P}$ says that $T$ is a measure-preserving transformation. Consequently $X\circ T$ has the same probability distribution as $X$ and is integrable. It also implies $\mathbb{E}[W\circ T]=\mathbb{E}[W]$ for every integrable random variable $W$, first for indicator functions, then for simple functions, and then by positive and negative approximation.

To identify a conditional expectation, take any $A\in \mathcal{F}$. The assumed identity with the bounded random variable $Z=1_A$ givesEvery member of $\mathcal{G}$ has the displayed form $T^{-1}(A)$, so this verifies all defining conditional expectation identities. ThereforeApply part (iii), since this conditional expectation has the same probability distribution as $X$. We concludeThis is invariance from integral duality for a measure-preserving transformation; neither invertibility of $T$ nor a second moment of $X$ is required.