Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 31 (Advanced Probability)

For $a<b$, let $U_N[a,b]$ be the number of completed upcrossings by the observations $X_1,\dots ,X_N$: buy when the value is at most $a$, sell at the first subsequent value at least $b$, and repeat. With $z^{-}=\max \{-z,0\}$, one form of the Doob upcrossing inequality for a martingale isFor completeness, hold either zero or one unit according to this rule. The holding at each step is measurable before the next martingale increment, so the total gain $G_N$ has expected value zero. Completed trades earn at least $b-a$ each; an unfinished trade loses at most $(X_N-a{)}^{-}$. Thus $G_N\ge (b-a)U_N[a,b]-(X_N-a{)}^{-}$, proving the inequality.

Suppose $C={\sup }_n\mathbb{E}|X_n|<\infty$. For each rational pair $a<b$ the inequality and monotone convergence giveEvery rational interval therefore has only finitely many upcrossings, simultaneously outside a countable union of null sets. If $\mathrm{liminf}{X}_n<\mathrm{limsup}{X}_n$, there is a rational interval strictly between them and infinitely many upcrossings, a contradiction. Thus the limit $X_{\infty }$ exists in the extended real line almost surely. Fatou's lemma now givesThe limit is finite almost surely and integrable. This proves the martingale convergence theorem rather than using it as the deduction.

The exact extra condition for convergence in L1 is uniform integrability:To see sufficiency, first discard the tails of $X_n$ uniformly and the tail of the integrable $X_{\infty }$. On the set where both absolute values are at most $K$, their difference is bounded by $2K$ and tends to zero almost surely; dominated convergence finishes the proof. Conversely, if $X_n\to X_{\infty }$ in $L^1$, thenMake the first term uniformly small for all sufficiently large $n$, then control the finitely many remaining integrable variables by increasing $K$. Hence uniform integrability is necessary too. In this case the conditional expectation identity $X_n=\mathbb{E}[X_{\infty }\mid {\mathcal{F}}_n]$ follows by taking the $L^1$ limit in $X_n=\mathbb{E}[X_m\mid {\mathcal{F}}_n]$ for $m\ge n$.

The coin-doubling martingale shows why an $L^1$ bound is not enough. Let ${\xi }_1,{\xi }_2,\dots$ be independent fair coin indicators and setConditional on the first $n$ coins, the next value is either $2X_n$ or zero with equal probabilities, so this is a nonnegative martingale. Its expected value is always $1$, while a first failure occurs almost surely, giving $X_n\to 0$ almost surely. Yet $\mathbb{E}|X_n-0|=1$ for every $n$. Indeed, whenever $2^n>K$, its tail expected value above $K$ is still $1$. Thus convergence in L1 fails because uniform integrability fails.

A Lévy measure $K$ on the real line is a nonnegative Borel measure satisfyingIt records the intensity per unit time of jumps of a Lévy process. Under the additional small-jump first-moment condition, the uncompensated Lévy–Khintchine formula iswhere $b\in \mathbb{R}$ and ${\sigma }^2\ge 0$. The integral is absolutely convergent: near zero its integrand has absolute value at most $|u||y|$, while outside a neighborhood of zero it is at most $2$ and $K$ has finite mass. If the usual compensated Lévy–Khintchine formula uses drift $\gamma$, this convention has $b=\gamma -{\int }_{|y|\le 1}yK(dy)$.

A Lévy process starts at zero and has stationary independent increments and stochastic continuity. Its characteristic function at time $t$ is $e^{t\psi (u)}$, with $\psi (0)=0$ and $\psi$ continuous. The given time-one characteristic function is strictly positive. It therefore has the unique continuous logarithm vanishing at zero,Any other continuous exponent would differ by an integer multiple of $2\pi i$; continuity on the real line and the value at zero make that integer identically zero. This determines all increment laws. More explicitly, for $0=t_0<t_1<\cdots <t_m$,Thus it determines every finite-dimensional distribution. For the standard càdlàg version of a Lévy process, coordinates at rational times determine the path, so these laws determine the entire process law on its canonical path space as well.

To find the Lévy measure, try the symmetric density $e^{-\alpha |y|}/|y|$. Its jump exponent isDifferentiation under the integral is justified by the integrable bound $2e^{-\alpha y}$. The elementary Fourier sine transform givesSince $J_{\alpha }(0)=0$, integration in $u$ yields $J_{\alpha }(u)=-\log (1+u^2/{\alpha }^2)$. Choosing $\alpha =\sqrt{2}$ matches the prescribed exponent exactly. This is the Lévy measure of a symmetric Laplace time-one law:The candidate satisfies the Lévy measure condition because its density is of order $1/|y|$ near zero and decays exponentially at infinity; moreover ${\int }_{|y|\le 1}|y|K(dy)=2{\int }_0^1{e}^{-\sqrt{2}y}dy<\infty$. Uniqueness of the triplet in the Lévy–Khintchine formula proves that these are the required coefficients. The infinite mass near zero means infinitely many small jumps, not a Gaussian component; their total variation is finite on bounded time intervals because $\int (1\wedge |y|)K(dy)<\infty$.

On the real line, Prohorov's theorem states that a sequence of probability measures is uniformly tight if and only if every subsequence has a further subsequence converging weakly to a probability measure. Here uniformly tight means that, for every $\epsilon >0$, some compact interval contains mass at least $1-\epsilon$ for every measure in the sequence. This is relative sequential compactness for weak convergence of probability measures, not merely the existence of one convergent subsequence.

We first prove the characteristic-function tail bound. Put $c_0=1-\sin 1>0$. For $y\ne 0$,At $y=0$ the expression is zero by continuity. If $|y|\ge \lambda$, the supplied elementary bound, with $t=|y|/\lambda$, makes it at least $c_0$. The integrand is nonnegative, so Tonelli's theorem yieldsThus one valid universal constant isThe estimate controls spatial tails using only the characteristic function near zero.

Apply it to each ${\mu }_n$. For fixed $\lambda$, pointwise convergence of the characteristic functions and the bound $|{\varphi }_n|\le 1$ allow dominated convergence on the finite integration interval, givingContinuity of a characteristic function and $\varphi (0)=1$ make the last expression tend to zero as $\lambda \to \infty$. Given $\epsilon >0$, choose $\lambda$ making it less than $\epsilon /2$; then for all sufficiently large $n$, the preceding tail is less than $\epsilon$. Enlarge the compact interval to handle the finitely many remaining probability measures. This proves uniform tightness of the whole sequence.

By Prohorov's theorem, every subsequence has a further weakly convergent subsequence, say with limit $\nu$. The real and imaginary parts of $e^{iuy}$ are bounded continuous functions, so along that subsequenceThe uniqueness theorem for characteristic functions implies $\nu =\mu$. All subsequential weak limits are therefore $\mu$. If the original sequence failed to converge weakly to $\mu$, a bounded continuous test function and a subsequence would keep its integrals a fixed distance from the limiting integral; a further weakly convergent subsequence would contradict that. HenceThis supplies the required proof of the Lévy continuity theorem in the stated case.

For the final request, the printed $Q$ is not defined; the intended function is $\varphi$, the characteristic function of a summand. We prove that ${\varphi }^{\prime }(0)=ia$ without assuming integrability. Write $Y_n=S_n/n$. Independence gives $\mathbb{E}{e}^{iu{Y}_n}=\varphi (u/n{)}^n$. Moreover convergence in probability to $a$ implies uniform convergence of these characteristic functions on each bounded frequency interval: for $|u|\le T$ and $\delta >0$,First let $n\to \infty$, then $\delta \downarrow 0$.

The potential logarithm-branch ambiguity needs to be resolved, not discarded. By continuity of $\varphi$ near zero, its principal complex logarithm is defined at $u/n$ for all $|u|\le 1$ and all large $n$, with value zero at $u=0$. Alsouniformly on $[-1,1]$, so $\mathrm{Log}{\Psi }_n(u)\to 0$ uniformly there. The two continuous logarithms differ by an integer multiple of $2\pi i$:That integer is continuous in $u$ and zero at zero, hence identically zero. ConsequentlyFor arbitrary nonzero $h\to 0$, take $n=\lfloor 1/|h|\rfloor$ and $u=nh$. Eventually $1/2\le |u|\le 1$, so dividing the preceding error by $u$ shows $\mathrm{Log}\varphi (h)/h\to ia$. Exponentiating at zero proves the derivative forced by the weak law:This is the weak law forces a characteristic-function derivative argument. Its estimates use bounded exponentials, not $\mathbb{E}|X_1|$. If $X_1$ is integrable, dominated convergence permits differentiation inside the expectation and gives ${\varphi }^{\prime }(0)=i\mathbb{E}{X}_1$, so then $a=\mathbb{E}{X}_1$.

Absolute integrability is genuinely unnecessary. For an explicit weak law without an absolute first moment, take a symmetric variable withwith mass $1-1/e$ at zero and no mass with $0<|X|<e$. This is a valid law: the specified tail decreases from $1/e$ to zero, and its derivative defines the continuous part beyond $e$. Its absolute first moment is infinite because ${\int }_e^{\infty }dx/(x\log x)=\infty$. For independent copies, set $Y_{n,j}=X_j{1}_{\{|X_j|\le n\}}$. Symmetry gives $\mathbb{E}{Y}_{n,j}=0$, and integration of the tail givesFor the last estimate, split the integral at $\sqrt{n}$; the initial part is $O(\sqrt{n})$ and the remainder is at most $2n/\log n$, apart from a fixed initial constant. Chebyshev's inequality now gives $n^{-1}{\sum }_{j\le n}{Y}_{n,j}\to 0$ in probability. The probability that any truncation changes a summand is at most $n\mathbb{P}(|X|>n)=1/\log n\to 0$, so $S_n/n\to 0$ in probability although $\mathbb{E}|X|=\infty$. The derivative is zero, but the usual expectation of $X$ does not exist.

If either the positive or negative part is integrable, the finite weak-law limit does force full integrability. For example, if $\mathbb{E}{X}^{-}<\infty$, then $X\wedge A$ is integrable and its sample averages have the weak law of large numbers limit $\mathbb{E}(X\wedge A)$. Since they are bounded above by the original averages, $\mathbb{E}(X\wedge A)\le a$ for every $A$. Letting $A\to \infty$ shows $\mathbb{E}{X}^{+}<\infty$. The symmetric argument handles the other one-sided hypothesis. The nonintegrable example necessarily has both one-sided expectations infinite.

For $f(x)=x$, the continuous martingale is $M_t^f=B_t$. Since $B_t$ has the centered normal distribution of variance $t$,For $f(x)=x^2$, the continuous martingale is $B_t^2-t$. The Gaussian fourth moment givesThis verifies both cases. The time integral in the printed identity is understood with its omitted $ds$.

Write $M^{(n)}=M^{f_n}$. The derivatives of the approximations areThus $|g_n|\le 1$. The Itô formula gives $M_t^{(n)}={\int }_0^t{g}_n(B_s)d{B}_s$. This use of the formula is valid despite the two second-derivative discontinuities: mollify the $C^1$ function $f_n$, whose derivative is Lipschitz. Its smooth derivatives converge boundedly, while the second derivatives are bounded by $n$ and converge except at $\pm 1/n$. For every $s>0$, the normal distribution of $B_s$ assigns those points zero probability. Dominated convergence for the drift integral and the Itô isometry for the stochastic integral pass the smooth formula to $f_n$. Equivalently, this identifies the martingale in the assumed decomposition and permits its cross-covariances to be calculated.

If $m\ge n$, then $|g_m-g_n|\le 1_{\{|x|<1/n\}}$. The Itô isometry and Doob L2 maximal inequality therefore give, for every fixed $T$,The Gaussian density is bounded by $(2\pi s{)}^{-1/2}$, soConsequently the processes are Cauchy in the complete space of continuous random paths with norm $(\mathbb{E}{\sup }_{s\le T}|Z_s{|}^2{)}^{1/2}$. They have a continuous-path limit $M$ there. Limits obtained for different integer horizons agree on overlaps; choose these versions consistently. Each $M_t$ is adapted, and passing to the $L^2$ limit in $\mathbb{E}[M_t^{(n)}\mid {\mathcal{F}}_s]=M_s^{(n)}$ shows that $M$ is a continuous martingale. Letting $m\to \infty$ in the preceding bound proves the requested convergence, with an explicit rate:The same Itô isometry identifies $M_t={\int }_0^t\mathrm{sgn}(B_s)d{B}_s$, with $\mathrm{sgn}(0)=0$.

There is a genuine factor-of-two error in the last printed conclusion. The stated $f_n$ has second derivative $n{1}_{\{|x|<1/n\}}$ almost everywhere, and the generator in the decomposition is one half of the second derivative. Hence the exact identity isBecause ${\sup }_x|f_n(x)-|x||\le 1/(2n)$ and $f_n(0)=1/(2n)$, this already proves uniform $L^2$ convergence on bounded intervals to $L_t=|B_t|-M_t$. It does not by itself prove almost-sure convergence of the full sequence, so we supply that additional step.

Take $n_k=k^2$. For each fixed integer $T$ and each $\epsilon >0$, the maximal-error bound and Markov's inequality implyThe first Borel-Cantelli lemma, applied to rational positive $\epsilon$ and integer $T$, gives uniform almost-sure convergence of this subsequence on every bounded interval. Therefore $L_{k^2}\to L$ uniformly there almost surely.

For $k^2\le n\le (k+1{)}^2$, the indicator windows are nested. The ratio-one interpolation for shrinking-window occupation integrals givesBoth ratios tend uniformly to one as $k\to \infty$. The two bounds converge uniformly to the continuous nonnegative process $L$, so the entire sequence does too. Thus the correct normalized conclusion isand with the factor actually printed in the question the limit isThese are the occupation approximations for Brownian local time. In the Tanaka formula convention, $L_t$ is the local time of a semimartingale at zero. It is not identically zero: $\mathbb{E}{L}_t=\mathbb{E}|B_t|=\sqrt{2t/\pi }>0$ for $t>0$, since $M$ starts at zero and is a martingale. Thus the discrepancy cannot be removed by treating the two limits as equal. The standard normalization is also given in Lalley's notes on the Itô calculus and local time.

A martingale describes an observable after its predictable drift has been removed. For a Markov chain the drift is the change produced by its transition operator; for Brownian motion it is one half of the Laplacian. Requiring the resulting processes to be martingales for a sufficiently rich class of observables determines the transition law itself. The same identities, combined with optional stopping, determine hitting probabilities, expected exit times and recurrence or transience. The duplicated Q5 paragraph in the PDF is a repeated printing of this one essay request.

For a finite or countable-state Markov chain with transition matrix $P$, define $(Pf)(x)={\sum }_{y}P(x,y)f(y)$ for a bounded test function $f$. The Markov property says $\mathbb{E}[f(X_{n+1})\mid {\mathcal{F}}_n]=(Pf)(X_n)$. Consequentlyis a martingale, since each increment has conditional expected value zero. Conversely, if these processes are martingales for every bounded $f$, taking the conditional expectation of an increment recovers that identity. With $f=1_{\{y\}}$ it gives $\mathbb{P}(X_{n+1}=y\mid {\mathcal{F}}_n)=P(X_n,y)$ for every state $y$. Thus, given the initial law, these identities characterize the Markov chain, not merely a few of its moments. This is the discrete-time Markov chain martingale characterization.

The drift operator is $P-I$. If $(P-I)h=0$ away from a target set, $h(X_{n\wedge T})$ is a stopped martingale, where $T$ is the first hit of that set. Under boundedness or suitable uniform integrability, the optional stopping theorem expresses $h$ in terms of boundary hitting probabilities. Similarly, if $(P-I)v=-1$ away from the target and $v=0$ on it, then $v(X_{n\wedge T})+(n\wedge T)$ is a martingale, giving $v(x)={\mathbb{E}}_{x}T$ when the terminal limit is justified.

For a concrete calculation, take a simple symmetric random walk on $\{0,1,\dots ,N\}$ stopped at $T$, its first hit of $0$ or $N$. In the interior, $h(i)=i$ has zero drift, while $v(i)=i(N-i)$ satisfiesThe stopped identity gives ${\mathbb{E}}_i(T\wedge n)=v(i)-{\mathbb{E}}_{i}v(X_{T\wedge n})\le v(i)$, proving $T$ finite with finite mean. Bounded convergence in both stopped identities now yields the gambler's ruin answersThis illustrates why the integrability justification is part of using a martingale, rather than an automatic consequence of writing an equation.

For a finite-state continuous-time Markov chain with generator matrix $Q=(q_{ij})$, the corresponding martingale problem for a continuous-time Markov chain usesThese are martingales. Conversely, suppose an adapted càdlàg finite-state process satisfies these identities. Let $P_t=e^{tQ}$, fix $T$, and set $g(s,i)=(P_{T-s}f)(i)$. Then ${\partial }_{s}g+Qg=0$. Apply deterministic integration by parts to the finite collection of indicator martingales to obtain the time-dependent Dynkin formula: $g(s,X_s)-g(0,X_0)-{\int }_0^s({\partial }_{r}g+Qg)(r,X_r)dr$ is a martingale. ThereforeThis recovers the Markov property and the entire semigroup, proving the characterization. On countable spaces one uses nonexplosion and localization to justify the analogous unbounded-rate formulas.

For $d$-dimensional Brownian motion, the Itô formula shows that, for $f\in C_c^{\infty }({\mathbb{R}}^d)$,is a true martingale, since its bounded derivatives make the integral square-integrable on each bounded horizon. This is the martingale problem for Brownian motion with generator $L=\frac{1}{2}\Delta$.

Here is why it also characterizes Brownian motion. Suppose a continuous adapted process $X$, with $X_0=x$, satisfies that martingale problem. Use smooth cutoff test functions equal to $x_i$ and $x_i{x}_j$ inside successively larger balls, and stop before leaving those balls. The coordinate tests show that $X^i-x_i$ are continuous local martingales; the product tests show that $X^i{X}^j-x_i{x}_j-{\delta }_{ij}t$ are local martingales. The Itô product rule consequently givesthe difference between the two proposed compensators is a continuous finite-variation local martingale, hence constant and zero at time zero. For each $u\in {\mathbb{R}}^d$, another application of the Itô formula gives the exponential local martingaleIts modulus is the deterministic quantity $e^{|u{|}^{2}t/2}$, so it is a true martingale on every bounded time interval. Taking its conditional expectation and dividing by its known value at time $s$ givesThe conditional characteristic function identifies a centered multivariate normal distribution of covariance $(t-s)I$, independent of the past. Together with continuity, this is the defining law of Brownian motion. This proves the Lévy characterization of multidimensional Brownian motion in the form needed for the generator characterization.

The analytic use of these martingales parallels the chain case. A harmonic function $h$ satisfies $\Delta h=0$, so it yields a stopped local martingale until the process leaves its domain of harmonicity. Bounded stopped observables permit optional stopping and solve boundary hitting problems. A solution of $\frac{1}{2}\Delta v=-1$ with zero boundary values gives an expected exit time. For example, in the ball of radius $R$, $v(x)=(R^2-|x{|}^2)/d$ gives ${\mathbb{E}}_x{T}_R=(R^2-|x{|}^2)/d$; stopping $|B_t{|}^2-dt$ first at $T_R\wedge n$ proves finiteness and justifies the limiting calculation. The Brownian local time construction in Q4 is another example: the predictable compensators of approximations to $|B_t|$ recover its increasing occupation term.

We now prove the required three-dimensional transience of Brownian motion in dimension at least three, in the strong sense $|B_t|\to \infty$ almost surely. Start first at a point $x$ with $r<|x|<R$, and let $T$ be the first exit from this annulus. The radial Laplacian in dimension three givesThus $|B_{t\wedge T}{|}^{-1}$ is a bounded martingale. The exit time is finite: stopping $|B_t{|}^2-3t$ gives $3\mathbb{E}(t\wedge T)\le R^2-|x{|}^2$. At exit, continuity puts $|B_T|$ at either $r$ or $R$. The optional stopping theorem therefore yieldsand hence the Brownian sphere-hitting probability in dimension threeAs $R\to \infty$, the events $\{{\tau }_r<{\tau }_R\}$ increase to $\{{\tau }_r<\infty \}$: a continuous path is bounded on the finite interval preceding any finite inner hit. This argument assumes no transience. ConsequentlyTo pass from a positive escape probability to almost-sure eventual escape, take Brownian motion started at zero. Let ${\sigma }_R$ be its first hit of the sphere of radius $R$. Stopping the squared-norm martingale proves $\mathbb{E}{\sigma }_R=R^2/3<\infty$. At ${\sigma }_R$, the Strong Markov property and the preceding hitting formula giveThe Strong Markov property here follows from independent Brownian increments by approximating a stopping time from above with dyadic-valued stopping times and using path continuity. Choose $R_m=2^{m}r$. The exit times ${\sigma }_{R_m}$ increase to infinity, since a continuous path is bounded on every compact time interval. The events of a return to the closed ball of radius $r$ after ${\sigma }_{R_m}$ decrease and have probabilities $2^{-m}$. Their intersection has probability zero. Thus almost surely there is some finite exit time after which the path never again enters that ball. Apply this simultaneously to all positive integer $r$. This proves the last visit to a bounded ball for three-dimensional Brownian motion conclusion and therefore