Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 201 (Advanced Probability)

Work on a filtered probability space $(\Omega ,\mathcal{F},({\mathcal{F}}_n{)}_{n\ge 0},\mathbb{P})$. A submartingale is a real-valued stochastic process satisfying the following three conditions: $Y_n$ is ${\mathcal{F}}_n$-measurable, $\mathbb{E}|Y_n|<\infty$, andThus it is adapted, has integrable random variables at every time, and its conditional expected next value is at least its current value. Repeated conditioning gives $\mathbb{E}[Y_m\mid {\mathcal{F}}_n]\ge Y_n$ for every $m\ge n$. The inequality concerns conditional expectation; individual sample paths need not increase. If no filtration is specified, the definition can be applied to the natural filtration generated by the process.

The almost sure submartingale convergence theorem says that if a submartingale $(Y_n)$ satisfiesthen there is an integrable random variable $Y_{\infty }$ such thatIndeed the positive-part bound also bounds the negative parts, since $\mathbb{E}{Y}_n\ge \mathbb{E}{Y}_0$; the theorem gives a finite limit. In particular, the martingale convergence theorem applies to any martingale with ${\sup }_n\mathbb{E}|M_n|<\infty$.

For a nonnegative martingale, $\mathbb{E}{M}_n=\mathbb{E}{M}_0$ supplies this bound automatically. Its limit obeys $\mathbb{E}{M}_{\infty }\le \mathbb{E}{M}_0$ by the Fatou lemma. Almost sure convergence alone need not preserve the expectation or give convergence in L1. Uniform integrability is the additional condition that supplies convergence in L1 and the identity $M_n=\mathbb{E}[M_{\infty }\mid {\mathcal{F}}_n]$.

Take independent and identically distributed random variables ${\xi }_k$ with the Bernoulli distribution of parameter $1/2$, and their natural filtration. SetThe event at $n=0$ is the whole sample space. Independence givesso this is a nonnegative martingale; it is integrable with $\mathbb{E}{M}_n=1$. The first zero among the ${\xi }_k$ is almost surely finite, since the probability of having only ones through time $n$ is $2^{-n}\to 0$. After that first zero, every $M_n$ is zero. Hence the almost sure limit is zero:This fair-coin doubling martingale also exhibits failure of uniform integrability: convergence in L1 would force the expectations to converge to zero.

Let $({\mathcal{F}}_n)$ be the natural filtration of the random walk on a graph. For a bounded harmonic function on a graph, the transition rule and the Markov property giveThus $h(X_n)$ is a bounded martingale. The martingale convergence theorem gives a finite almost sure limit $L$.

On the probability-one recurrence event, every vertex $v$ is visited along a sequence $n_k\to \infty$. Along that sequence $h(X_{n_k})=h(v)$, while convergence of the whole sequence forces $h(v)=L$. Therefore every pair of vertices has the same value. This is the bounded harmonic function theorem on a recurrent graph:Recurrence makes each vertex value a subsequential limit of the same convergent martingale. A connected locally finite graph is countable, since it is the union of its finite distance balls, so these almost sure assertions can also be combined by a countable intersection. The one-vertex case is immediate.

Write $D_k=M_k-M_{k-1}$ for the martingale difference sequence. Bounded increments mean that one deterministic $C<\infty$ satisfies $|D_k|\le C$ for every $k$, almost surely. Then $\mathbb{E}{D}_k=0$ and, for $j<k$,The increments are uncorrelated random variables, uniformly bounded in $L^2$. Applying the supplied strong law for uniformly L2-bounded uncorrelated random variables gives $n^{-1}{\sum }_{k=1}^n{D}_k\to 0$ almost surely. Also $M_0/n\to 0$, because $M_0$ is finite almost surely. Therefore a martingale with bounded increments has zero linear growth:This is the strong law for martingales with bounded increments.

For the submartingale, let $\Delta Y_k=Y_k-Y_{k-1}$ and define its predictable drift and compensator byThis is the Doob decomposition in discrete time. The process $N_n$ is a martingale. Since $|\Delta Y_k|\le C$, we have $0\le a_k\le C$, so $|N_k-N_{k-1}|\le 2C$. The result just proved gives $N_n/n\to 0$ almost surely, and $A_n\ge 0$. Consequently the strong law for submartingales with bounded increments isThe compensator may grow, so the conclusion is a lower bound rather than a claim of convergence to zero.

For each deterministic $n$, use the nonnegativity and the martingale property to obtainA nonnegative random variable with zero expectation is zero almost surely. Hence $M_{n+1}=0$ almost surely on $\{M_n=0\}$. Intersecting these probability-one statements over all $n$ makes them hold simultaneously, and induction givesZero is absorbing for a nonnegative martingale. This is the absorption at zero of a nonnegative martingale. On $\{T=\infty \}$ the assertion has no finite-time requirement. No unbounded-time use of the optional stopping theorem is needed.

The time $T_R$ is a stopping time, because $\{T_R\le n\}={\bigcup }_{k\le n}\{M_k\ge R\}\in {\mathcal{F}}_n$. Apply the optional stopping theorem to the bounded time $T_R\wedge n$:On $\{T_R\le n\}$ the stopped value is at least $R$, and elsewhere it is nonnegative. Letting $n\to \infty$ gives the maximal bound for a nonnegative martingale:Stop at a bounded time first, then pass to the increasing event. This avoids assuming uniform integrability of the original process. For $0<R\le 1$, $T_R=0$ and the bound simply says $1\le 1/R$.

The overshoot hypothesis as printed cannot hold for every $R>0$. For $R\le 1$, $T_R=0$ and $M_{T_R}=1$; choosing $R<1/\tau$ contradicts $M_{T_R}\le \tau R$. The intended and sufficient assumption is the overshoot bound for $R\ge 1$, on the event $\{T_R<\infty \}$. We use those thresholds below; when $R\le 1$, the requested stopped-time bound is trivial because $T\wedge T_R=0$.

Fix $R\ge 1$ and set $S=T\wedge T_R$. By part (a), the stopped martingale satisfies $0\le M_{S\wedge n}\le \tau R$: before stopping it is below $R$, at $T$ it is zero, and at $T_R$ the assumed overshoot bound applies. Thus the square of this stopped process is integrable. For $\Delta M_n=M_{n+1}-M_n$,The event $\{S>n\}$ is ${\mathcal{F}}_n$-measurable and contained in $\{T>n\}$. Conditional expectation of the linear term is zero, while the variance assumption makes the remaining conditional expectation nonnegative. The stopped increments here are bounded by the stopping and overshoot bounds, so all conditional expectations are legitimate. ConsequentlySince $X_0=1$, we have ${\sigma }^2\mathbb{E}(S\wedge n)\le \mathbb{E}{M}_{S\wedge n}^2-1$. Bounded-time optional stopping theorem also gives $\mathbb{E}{M}_{S\wedge n}=1$, soApply the monotone convergence theorem to $S\wedge n$. This proves the stronger estimate $(\tau R-1)/{\sigma }^2$ and hence the requested absorption-time bound from conditional variance and overshoot:In particular this stopping time is finite almost surely. For $0<R\le 1$, $S=0$ and $X_n=1$ is a constant submartingale, while the stopping-time expectation is zero.

If $T>n$, either $T_R\le n$, or both stopping times exceed $n$. Therefore the maximal bound for a nonnegative martingale and the Markov inequality give, for $R\ge 1$,The right-hand side is minimized at $R=\sigma \sqrt{n}/\tau$. Whenever the claimed bound is nontrivial, $2\tau /(\sigma \sqrt{n})<1$, this choice has $R>2$ and is allowed under the corrected overshoot hypothesis. Substituting gives the square-root tail bound for martingale absorption:When the displayed upper bound is at least one, the inequality follows from $\mathbb{P}(T>n)\le 1$. This handles every $n$ without using the impossible small-threshold hypothesis.

Let $\mu =\mathbb{E}{X}_1$ and let the cumulant-generating function and its Legendre transform beUnder the permitted assumption that $\psi$ is finite everywhere, the right-tail form of the Cramér theorem is, for $a\ge \mu$,Use $\log 0=-\infty$. The restriction to nonnegative parameters is valid on this side of the mean: convexity gives $\psi (\theta )\ge \mu \theta$, so negative parameters cannot improve the value zero available at $\theta =0$. For $a<\mu$, the right-tail probability tends to one by the strong law of large numbers, so its logarithmic rate is zero; it is not generally $-I(a)$.

The full large deviation principle bounds probabilities of closed sets from above and open sets from below with rate $I$. For the displayed tail equality, a possible finite upper endpoint also needs attention. If $b=\mathrm{esssup}{X}_1<\infty$, then at $a=b$ the event requires every summand to equal $b$; its probability is $\mathbb{P}(X_1=b{)}^n$, and $I(b)=-\log \mathbb{P}(X_1=b)$. The identity follows by taking $\theta \to \infty$ in $\mathbb{E}{e}^{\theta (X_1-b)}$. Above $b$, both sides have infinite rate. The theorem describes exponential decay, including endpoints and impossible events.

For every $\theta \ge 0$, the Markov inequality and independence give the Chernoff boundOptimize over nonnegative $\theta$. For $a\ge \mu$, part (a) identifies this supremum with $I(a)$, yielding the finite-$n$ estimateIf $I(a)=\infty$, use parameters with arbitrarily large $\theta a-\psi (\theta )$; the probability must then be zero. Taking the logarithmic upper limit proves the upper bound in the Cramér theorem:For $a<\mu$, the nonnegative-parameter supremum is zero, giving the correct trivial tail-rate upper bound. Exponential Markov bounds and the product moment-generating function supply the entire upper-bound argument.

Write $b=\mathrm{esssup}{X}_1$. The hypothesis $\mathbb{P}(X_1>a)>0$ implies $a<b$ and rules out a constant random variable. In particular $I(a)<\infty$. The cumulant-generating function is strictly convex, since its second derivative is the positive variance under exponential tilting, and ${\psi }^{\prime }(0)=\mu$, ${\psi }^{\prime }(\theta )\to b$ as $\theta \to \infty$.

If $a>\mu$, there is a unique ${\theta }_a>0$ with ${\psi }^{\prime }({\theta }_a)=a$, and the Legendre transform gives $I(a)={\theta }_{a}a-\psi ({\theta }_a)$. ThusIf $a=\mu$, use differentiability at zero: $\psi (\theta )=\mu \theta +o(\theta )$, so for some sufficiently small $\theta >0$,In either case choose a parameter $\theta \ge 0$ with $J=\theta (a+\epsilon )-\psi (\theta )>I(a)$, and choose $0<\eta <J-I(a)$. The Cramér theorem gives, for all sufficiently large $n$,The Chernoff bound at the chosen parameter gives $\mathbb{P}(S_n/n\ge a+\epsilon )\le e^{-nJ}$. The conditioning event has positive probability for every $n$, since all summands can simultaneously exceed $a$. ThereforeTaking the complement within the conditioning event proves the conditional concentration at a large-deviation threshold:The farther tail has a strictly larger exponential cost. The argument also works when $a+\epsilon$ reaches or exceeds the upper support endpoint, without requiring an interior maximizer there.

A standard real Brownian motion relative to a filtration $({\mathcal{F}}_t)$ is an adapted stochastic process with $B_0=0$ almost surely, continuous paths almost surely, andEquivalently, it has independent increments and stationary increments, each with a normal distribution of mean zero and variance equal to the elapsed time, together with continuous paths and the stated initial value. The filtration may be its natural filtration. A Brownian motion started at $z$ is $z+W_t$ for a standard process $W$; multidimensional standard Brownian motion has independent standard real coordinate processes. The normalization is variance $t$ at time $t$.

The $2^n$ increments are independent normal random variables, each distributed as $2^{-n/2}{B}_1$. Their squared means are $2^{-n}$ and, using the permitted variance, their squared variances are $2\cdot 2^{-2n}$. Independence therefore givesConsequently the dyadic quadratic variation converges to one:This is dyadic quadratic variation of Brownian motion on the time interval of length one. The calculation requires independence only within each partition; increments from different resolutions need not be independent.

For every $w\in C^{\alpha }[0,1]$, its finite Hölder seminorm gives the deterministic boundWhen $\alpha >1/2$, the right-hand side tends to zero. Thus under any probability measure on the stated coordinate sigma-algebra, these measurable finite-coordinate sums converge to zero on every path, and hence almost surely.

If the coordinate process were a Brownian motion, part (b) would make the same sums converge to one in $L^2$, and hence in probability. Almost sure convergence to zero also implies convergence in probability to zero. Uniqueness of a limit in probability is a contradiction. Therefore no such Brownian measure exists:This is the quadratic variation obstruction to Hölder regularity. It does not address the critical exponent $\alpha =1/2$, where the displayed deterministic bound does not tend to zero.

Let $\mu$ be the given Brownian motion law on $C[0,1]$. Choose $\alpha <\beta <1/2$ and an integer $p$ with $p(1/2-\beta )>1$. For the largest adjacent level-$n$ increment $A_n$, Brownian scaling and the Markov inequality givewhere $c_p=\mathbb{E}|\mathcal{N}(0,1){|}^p<\infty$. These probabilities are summable, so the Borel-Cantelli lemma gives a finite random $K$ such that $A_n\le K{2}^{-n\beta }$ for every $n$, after absorbing the finitely many exceptional levels.

For $s<t$, choose $m$ with $2^{-m}\le t-s<2^{1-m}$. Their left dyadic approximations at level $m$ differ by at most two grid steps; each finer approximation adds at most one adjacent increment. Continuity and dyadic increment chaining therefore giveThus paths are $\beta$-Hölder and hence $\alpha$-Hölder on $[0,1]$. This direct proof supplies the relevant Brownian Hölder regularity, also obtainable from the Kolmogorov continuity theorem.

The full-measure subset $E_{\alpha }=C^{\alpha }[0,1]$ is measurable in $C[0,1]$, because continuity identifies its seminorm with a countable supremum:Its finiteness event is a countable union of countable intersections of coordinate-measurable events. The sigma-algebra specified on $E_{\alpha }$ is precisely the trace of the coordinate sigma-algebra on $C[0,1]$. Define $\nu (A)=\mu (A)$ for trace-measurable $A\subseteq E_{\alpha }$; equivalently restrict the Brownian law to its full-measure subset. Since $\mu (E_{\alpha })=1$, no renormalization is needed, and all finite-dimensional coordinate laws are unchanged. This is the required probability measure:The construction uses the requested coordinate sigma-algebra and makes no assumption about a separable Hölder-norm topology.

First take finite endpoints $\ell <r$ and a starting point $z\in (\ell ,r)$. For the Brownian exit time $H=\inf \{t:B_t\notin (\ell ,r)\}$, the stopped path stays in $[\ell ,r]$. The process $(B_t-z{)}^2-t$ is a martingale. Bounded-time optional stopping theorem givesBy the monotone convergence theorem, $\mathbb{E}H<\infty$, so exit from every bounded interval is almost sure:For completeness, a proper unbounded interval also has almost sure exit. Applying optional stopping theorem to $B_{H\wedge t}$ and then bounded convergence theorem gives the endpoint probabilitiesFor a fixed lower level $\ell$, let $r\to \infty$. Hitting $\ell$ before $r$ is a subset of ever hitting $\ell$, and its probability tends to one. Similarly every fixed higher level is hit almost surely. After a level is reached, the same argument from that level shows that a level strictly outside a given proper interval is eventually reached. This proves exit even when endpoints are included. A starting point already outside needs no argument. The whole real line has no exit, so the phrase “every interval” is understood to exclude that trivial exception. Countably many rational levels make the exit conclusion simultaneous for all proper intervals. The bounded-interval assertion is the one used below.

Translate the centre of the ball to zero. Choose an inner radius $\rho$ strictly smaller than the ball's radius. If the starting point already lies in the ball there is nothing to prove; otherwise write $d=|z|>\rho$ and choose $R>d$. Let $H_{\rho },H_R$ be the first hits of the two circles.

The Brownian exit time from the annulus $\rho <|z|<R$ is finite almost surely: it is no later than exit of the first coordinate from $(-R,R)$, which is finite by part (a). The function $\log |z|$ is harmonic on this annulus. The Itô formula and optional stopping theorem apply to its bounded stopped values, yieldingSolving gives the planar Brownian annulus hitting probabilityAs $R\to \infty$ this tends to one, while the event in the formula is contained in $\{H_{\rho }<\infty \}$. Thus the inner circle is hit almost surely. That circle lies strictly inside the original open ball, proving the recurrence of planar Brownian motion in the form requested:A probability-one intersection over balls with rational centres and positive rational radii makes this conclusion simultaneous for all nonempty open balls, since every such ball contains one from that countable family.

The domain is the union of the horizontal and vertical strips. The four connected components of its boundary carry the constants $a,b,c,d$ in the northeast, northwest, southwest and southeast, respectively.

First justify finiteness of $T$. A small open ball around $(2,2)$ lies outside the domain. By part (b), planar Brownian motion visits that ball almost surely in finite time. A continuous path from $z\in D$ to that ball must meet $\partial D$ first. Hence $T<\infty$ almost surely, and $B_T\in \partial D$ by continuity.

The harmonic function $u$ is smooth inside $D$. The Itô formula, localized on relatively compact subdomains, makes $u(B_{t\wedge T})$ a local martingale. Its boundary definition uses the continuous extension of $u$. Since $u$ is bounded, this stopped process is a true martingale with uniform integrability: pass through the compact exhaustion using bounded convergence theorem. In particular ${\mathbb{E}}_{z}u(B_{t\wedge T})=u(z)$.

Now $B_{t\wedge T}\to B_T$ almost surely as $t\to \infty$. The dominated convergence theorem, boundedness of $u$, and its continuous boundary values give the bounded harmonic representation with almost sure Brownian exit:Almost sure exit and boundedness of the harmonic function are both used. The domain's unboundedness causes no loss of expectation here because the stopped function values are uniformly bounded.

Fix $x\in (-1,1)$ and start at $(x,y)$ with $y>1$. Write the independent Brownian coordinates as $x+W_t^1$ and $y+W_t^2$. LetOn $\{H<L_y\}$ the path has stayed in the upper strip and first exits the cross-shaped domain at its right or left side. The boundary value is $a$ or $b$, respectively. Let $V=a$ if $x+W_H^1=1$ and $V=b$ if $x+W_H^1=-1$. The Brownian exit from an interval probabilities giveCouple all heights $y$ using the same two Brownian paths. By part (a), $H<\infty$ almost surely, and continuity makes ${\min }_{0\le t\le H}{W}_t^2$ finite. ThusLet $K=\max \{|a|,|b|,|c|,|d|\}$. On the complement of this exceptional event, $f(B_T)=V$; on the event itself, $|f(B_T)-V|\le 2K$. The representation in part (c) therefore yieldsThis proves the harmonic limit along an infinite strip arm:Far up the arm, the bottom is reached with vanishing probability before the horizontal coordinate exits. The limit is consequently determined by the two side values alone.

A real Lévy process is a stochastic process $(X_t{)}_{t\ge 0}$ with $X_0=0$ almost surely, independent increments, stationary increments, and stochastic continuity. The latter means $X_t-X_s\to 0$ in probability as $t\to s$. Its usual path convention is càdlàg: paths are right-continuous and have left limits. Equivalently one starts with the increment and continuity-in-probability conditions and then chooses the càdlàg version.

The Lévy characteristic exponent is specified here bySome conventions use $e^{t\tilde{\psi }(\theta )}$ instead, with $\tilde{\psi }=-\psi$. The sign convention must be fixed before computing the exponent. The zero process satisfies this definition; excluding it requires an additional nondegeneracy condition.

Both Poisson processes start at zero and have càdlàg paths. On disjoint time intervals their increments are independent, and independence of the two processes makes the difference increments independent as well. Their increment laws depend only on interval length, so $X$ has stationary increments. For a time interval of length $h$, the probability that either Poisson process has a jump is $1-e^{-h}\to 0$. This proves stochastic continuity. Consequently the difference is a Lévy process, equivalently a continuous-time symmetric simple random walk with total jump rate one and jumps $+1$ and $-1$ each chosen with probability $1/2$.

The characteristic function of a Poisson variable of mean $\lambda$ is $\exp \{\lambda (e^{i\theta }-1)\}$. Independence therefore givesThus, in the negative-exponent convention of part (a),In the positive-exponent convention the answer is $\tilde{\psi }(\theta )=\cos \theta -1$. The Compound Poisson process has mean zero and variance $t$, consistent with the expansion $\psi (\theta )={\theta }^2/2+O({\theta }^4)$.

The printed uniqueness claim omits nondegeneracy of the limit. The zero process is a Lévy process, and every $\alpha >1/2$ yields that limit. We first classify all possibilities under the stated assumptions, then identify the unique nonzero one.

For $t>0$, part (b) givesfor each fixed $\theta \ne 0$. If $\alpha <1/2$, the characteristic functions tend to zero for every nonzero parameter and remain one at zero. This discontinuous function cannot be the characteristic function of a probability law. The characteristic-function convergence theorem therefore rules out even one-dimensional weak convergence of random variables at a positive time.

For joint convergence, take $0=t_0<t_1<\cdots <t_m$ and write $q_k={\sum }_{j=k}^m{\theta }_j$. Independent increments giveAt $\alpha =1/2$, this tends to $\exp \{-\frac{1}{2}{\sum }_k(t_k-t_{k-1})q_k^2\}$. These are exactly the joint laws of standard Brownian motion: increments are independent centred normals with variances $t_k-t_{k-1}$. The assumed limiting Lévy process thus has the Brownian law.

For $\alpha >1/2$, the same joint characteristic functions tend to one. Every limiting vector is zero. The càdlàg path convention then makes the limiting process identically zero almost surely: first intersect the zero-value events at rational times, then use right continuity. The complete scaling classification of a continuous-time symmetric simple random walk isIn particular, if a nonzero limiting Lévy process is intended, the unique exponent is $\alpha =1/2$, andThe finite-dimensional Brownian law, together with the Lévy càdlàg convention, determines the process law and its continuous version. No assertion of path-space convergence of the approximating walks is needed here.