Past exam of the probability, measure and martingales course of the University of Oxford / 2023 / 3 / a

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.