Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 27 (Advanced Probability)

Use the exponent convention $\mathbb{E}{e}^{iu{X}_t}=e^{t\psi (u)}$. A real Lévy process starts at $0$, has stationary increments and independent increments, is stochastically continuous, and is taken in its càdlàg version. Its characteristic exponent of a Lévy process satisfies $\psi (0)=0$ and is continuous. This convention has the opposite sign from the alternative $e^{-t\Psi (u)}$, so $\psi =-\Psi$.

For real $u$, the exponential martingale of a Lévy process is integrable because $|M_t^u|=e^{-t\mathrm{Re}\psi (u)}$ is deterministic and finite. For $s\le t$, its conditional expectation with respect to the natural filtration isThe second equality uses both independent increments and stationary increments. Thus this is a complex martingale, meaning that its real and imaginary parts are martingales.

A probability distribution is an infinitely divisible distribution when, for every positive integer $n$, it is the distribution of a sum of $n$ independent and identically distributed random variables. Their common distribution is allowed to depend on $n$. For a Lévy process,and these summands are independent with the common law of $X_{1/n}$. This proves the required infinite divisibility directly.

The Lévy–Khintchine theorem states that a real infinitely divisible distribution has characteristic function $e^{\psi (u)}$, where, for a unique triplet with the following fixed truncation,with $b\in \mathbb{R}$, $a\ge 0$, $K$ a positive measure, $K(\{0\})=0$, and $\int (1\wedge y^2)K(dy)<\infty$. Conversely every such triplet gives an infinitely divisible distribution and a Lévy process, unique in law, whose time-$t$ characteristic function is $e^{t\psi (u)}$. The Lévy measure $K$ need not be finite near zero. Taylor expansion makes the compensated integrand $O(y^2)$ there, while the measure is finite away from zero, so the integral is well defined. The drift parameter depends on the truncation: using $|y|\le 1$ instead can alter $b$ by the contribution of atoms at $\pm 1$. Here $a$ denotes Gaussian variance, not drift.

We now prove that continuity forces $K=0$, using the suggested truncation rather than merely quoting a path classification. For $\epsilon >0$, ${\lambda }_{\epsilon }=K(|y|\ge \epsilon )$ is finite. The truncated exponent is that of the Compound Poisson processwhere $N$ has rate ${\lambda }_{\epsilon }$ and the marks have law $K(dy)1_{\{|y|\ge \epsilon \}}/{\lambda }_{\epsilon }$ when the rate is positive. The remaining exponent $\psi -{\psi }_{\epsilon }$ also has an admissible Lévy–Khintchine formula triplet. Hence construct independently a Lévy process $Z^{\epsilon }$ with that exponent. The sum $Y^{\epsilon }+Z^{\epsilon }$ has the same finite-dimensional distributions as $X$, and hence the same law on càdlàg path space. Continuity is therefore an almost-sure property of the sum if it is one of $X$.

But independent compound Poisson jumps cannot cancel: conditional on the path of $Z^{\epsilon }$, its jump times are countable; the independent Poisson jump times have continuous distributions and avoid them almost surely. At each jump of $Y^{\epsilon }$, the sum has the same nonzero jump, of size at least $\epsilon$. If ${\lambda }_{\epsilon }>0$, there is positive probability of such a jump on any fixed positive-length time interval, contradicting almost-sure continuity. Thus $K(|y|\ge \epsilon )=0$ for every $\epsilon >0$, and taking $\epsilon =1/n$ gives $K=0$.

The characteristic function is now $\exp [t(ibu-a{u}^2/2)]$. If $a>0$, the process $B_t=(X_t-bt)/\sqrt{a}$ has continuous paths and independent centered normal increments of variance $t-s$, so it is standard Brownian motion on the original probability space. If $a=0$, the increments are deterministic, and continuity together with equality at all rational times gives $X_t=bt$ simultaneously for all $t$ almost surely. A Brownian motion on an enlarged space can be used in the zero-variance representation if necessary. Therefore

In discrete time, the bounded-time optional stopping theorem says that an integrable supermartingale $X$ and bounded stopping times $S\le T$ satisfy $\mathbb{E}[X_T\mid {\mathcal{F}}_S]\le X_S$. For a martingale there is equality. The assertion at a possibly unbounded, almost-surely finite stopping time $T$ also holds with $S=0$ if $\{X_{T\wedge n}:n\ge 0\}$ is uniformly integrable: then $X_T$ is integrable and $\mathbb{E}{X}_T\le \mathbb{E}{X}_0$, with equality for a martingale. Boundedness of $T$ or the stated integrability condition cannot in general be omitted.

For the increment hypothesis here, $\mathbb{E}T<\infty$ implies $T<\infty$ almost surely, and telescoping givesThe right-hand side is an integrable random variable. Applying bounded-time optional stopping to $T\wedge n$ and then the dominated convergence theorem provesThis is bounded-increment optional stopping with integrable time; the same reasoning gives equality for a martingale.

Put $q=1-p$ and first assume $0<p<1$. Let $\tau$ be the first occurrence time of the specified seven-letter word. Its probability in a prescribed block is $r=p^4{q}^3>0$. Disjoint seven-flip blocks are independent, and a match in one forces $\tau$ to have occurred by its end. Consequently $\mathbb{P}(\tau >7m)\le (1-r{)}^m$ and $\mathbb{E}\tau \le 7/r<\infty$; this establishes the integrability needed for stopping before computing its value.

Start a new gambler with unit capital immediately before each flip. A gambler bets all current capital on the next required letter of the word, receives capital divided by $p$ for a correct head or by $q$ for a correct tail, and receives zero on failure. After completing all seven bets, the gambler retains the winnings without further betting. Each individual bet preserves its conditional expected capital. If $C_n$ is the total capital of all gamblers who have entered through flip $n$, then $C_n-n$ is a martingale.

At any time at most seven gamblers are still betting, and each one's capital is at most $L=1/(p^4{q}^3)$, since probabilities of shorter prefixes are at least the full-word probability. Completed winnings do not change. Thus the increments of $C_n-n$ have a deterministic bound, for example $14L+1$. The preceding optional-stopping argument therefore gives $\mathbb{E}(C_{\tau }-\tau )=0$.

At the first full match, no earlier gambler has completed the word. A surviving gambler who has placed $k$ successful bets corresponds to a suffix of the completed word which is also its length-$k$ prefix, namely a border of a word. The only such lengths are $3$ and $7$: the shorter common string is HHT. Their capitals are $1/(p^{2}q)$ and $1/(p^4{q}^3)$, respectively. Hence $C_{\tau }$ is this deterministic sum andFor a fair coin this is 136 flips. This is a waiting time for a word in independent nonuniform symbols; the overlap contribution is essential. If $p=0$ or $p=1$, the word cannot occur because it contains both types of flip, so the expected waiting time is infinite.

For real $\lambda$, the normal moment-generating formula gives $\mathbb{E}{e}^{\lambda (B_t-B_s)}=e^{{\lambda }^2(t-s)/2}$. Using independent increments and conditioning on the Brownian filtration,All terms are integrable by the same normal formula. Thus the displayed process is an Exponential martingale for Brownian motion.

For the interval exit time, we first show both almost-sure finiteness and finite expectation. On $\{T>n\}$, the position at time $n$ lies in $(-b,a)$. If $X_{n+1}-X_n\ge a+b$, the continuous path must exit by time $n+1$. This increment is independent of ${\mathcal{F}}_n$ and has law $N(\mu ,1)$, so the conditional probability of this event is a fixed $c>0$. ThereforeThis geometric tail bound from a uniform escape probability implies $T<\infty$ almost surely and $\mathbb{E}T<\infty$.

Take $\lambda =-2\mu$. Then $e^{-2\mu X_t}=e^{-2\mu B_t-2{\mu }^{2}t}$ is the exponential martingale just proved. Its stopped values lie between $e^{-2\mu a}$ and $e^{2\mu b}$. The optional stopping theorem at $T\wedge t$, followed by bounded convergence, gives $\mathbb{E}{e}^{-2\mu X_T}=1$. With $v=\mathbb{P}(X_T=a)$ and the two possible boundary values,Solving yieldsNext apply bounded-time optional stopping to $B_t$. Since $B_{T\wedge t}=X_{T\wedge t}-\mu (T\wedge t)$, we obtain $\mathbb{E}{X}_{T\wedge t}=\mu \mathbb{E}(T\wedge t)$. The stopped position is bounded, and the stopped time increases to an integrable $T$. Passing to the limit gives $\mu \mathbb{E}T=av-b(1-v)$. ThereforeAs a check, letting $\mu \downarrow 0$ gives the driftless formulas $v\to b/(a+b)$ and $\mathbb{E}T\to ab$. The expectation calculation uses a justified stopping limit, rather than assuming that optional stopping holds at every unbounded time.

Standard one-dimensional Brownian motion is a real process with $B_0=0$, continuous paths almost surely, and increments $B_t-B_s\sim N(0,t-s)$ independent of the past at time $s$, for $0\le s<t$. These conditions determine its entire finite-dimensional distribution family.

The Wiener theorem asserts that such a process exists, equivalently that there is a unique Wiener measure on $C_0([0,\infty ),\mathbb{R})$ under which the coordinate process has these properties. To construct it, prescribe centered multivariate normal laws with covariance $\mathbb{E}{B}_s{B}_t=\min (s,t)$. This covariance is positive semidefinite becauseThe laws are consistent under removing coordinates, so the Kolmogorov extension theorem constructs the process. Normal increments have fourth moment $\mathbb{E}|B_t-B_s{|}^4=3|t-s{|}^2$. The Kolmogorov continuity theorem therefore supplies a continuous modification, retaining all the prescribed finite-dimensional laws and hence the independent normal increments. Apply this on every compact time interval, taking consistent versions; continuity and equality at rational times make them agree on overlaps. The resulting law on continuous-path space is unique because evaluations at rational times generate its Borel sigma-algebra. This is a proof sketch of the existence theorem, independent of the random-walk limit in Question 5.

For every positive real $r$, a centered normal variable of variance $t-s$ has absolute $r$th moment $c_r|t-s{|}^{r/2}$, where $c_r=\mathbb{E}|N(0,1){|}^r<\infty$. Fix $0<\alpha <1/2$ and choose $r$ large enough that $\alpha <1/2-1/r$. ThenThe Kolmogorov continuity theorem gives a modification with Hölder continuity of every exponent less than $(r/2-1)/r=1/2-1/r$, in particular exponent $\alpha$, on each compact interval. This modification and the given continuous Brownian motion agree almost surely at all rational times; continuity makes them agree everywhere simultaneously. Thus the property holds for the given trajectories, not just for another version.

Take a countable increasing sequence of positive exponents approaching $1/2$, and intersect their probability-one events for every integer time horizon. Hölder continuity of a larger exponent implies that of every smaller positive exponent on a compact interval, after adjusting the constant. We have therefore proved the simultaneous assertionThe compact-interval qualification matters: a single uniform Hölder constant on the entire half-line is not being asserted.

We use dyadic quadratic variation of Brownian motion. For fixed rational $0\le u<v$, set $\ell =v-u$ and let $Q_n$ be the sum of the squares of the $2^n$ Brownian increments on its equal-length partition. Independence and the normal fourth moment giveFor every $\eta >0$, Chebyshev's inequality bounds $\mathbb{P}(|Q_n-\ell |>\eta )$ by $2{\ell }^2{\eta }^{-2}{2}^{-n}$, a summable sequence. The Borel-Cantelli lemma implies $Q_n\to \ell$ almost surely. Intersect over positive rational $\eta$ and all rational intervals to obtain one probability-one event on which every such interval has this positive quadratic-variation limit.

If a path were Hölder of exponent $\alpha >1/2$ on a nonempty open interval, choose a compact rational subinterval $[u,v]$ within it and a finite Hölder constant $C$ there. Every partition increment would have absolute value at most $C(\ell 2^{-n}{)}^{\alpha }$, soThis contradicts $Q_n\to \ell >0$. The same pathwise event excludes every exponent greater than $1/2$, without needing an uncountable intersection of events. ThereforeThis is the quadratic variation obstruction to Hölder regularity. It rules out a continuously differentiable trajectory on any interval, since a continuous derivative is bounded on smaller compact intervals and gives a Lipschitz bound. By itself it does not rule out differentiability at an isolated point. The stronger nowhere differentiability of Brownian motion can also be seen directly as follows.

On a mesh of width $h=2^{-n}$ in $[0,M]$, the probability that any specified three consecutive increments all have absolute value at most $Kh$ is at most $C{K}^3{h}^{3/2}$: each increment is $N(0,h)$ and the three are independent. There are at most $M/h$ possible blocks, so the probability of any such block is at most $CM{K}^3{h}^{1/2}$, summable in $n$. By Borel-Cantelli lemma, for every pair of positive integers $M,K$ there are eventually no such blocks. But a finite derivative at some time $t<M$ would imply $|B_s-B_t|\le C_t|s-t|$ near $t$. The three mesh increments beginning at the mesh point immediately to the left of $t$ would then all be at most $6C_{t}h$ for all sufficiently fine meshes. Choosing an integer $K\ge 6C_t$ contradicts the preceding event. Thus finite derivatives do not exist anywhere almost surely, including a finite right derivative at $0$. The Hölder estimates below $1/2$ express continuity with a roughness scale; they do not imply differentiability.

Write $m_l=\lfloor N{t}_l\rfloor -\lfloor N{t}_{l-1}\rfloor$ and $\varphi (v)=\mathbb{E}{e}^{iv\xi }$. Since $\mathbb{E}\xi =0$ and $\mathbb{E}{\xi }^2=1$, the characteristic function expansion at zero is $\varphi (v)=1-v^2/2+o(v^2)$. Indeed, $|e^{ix}-1-ix|\le x^2/2$ for real $x$, and $(e^{iv\xi }-1-iv\xi )/v^2\to -{\xi }^2/2$. The dominated convergence theorem, with dominating variable ${\xi }^2/2$, proves the expansion after taking expectations. Initially omit the endpoint interpolation terms. The integer-time increments involve disjoint sets of independent steps, so their joint characteristic function isHere $m_l/N\to t_l-t_{l-1}$. Taking the logarithm near $1$ givesThis proves the claimed limit for the integer-time approximation.

At a fixed time $t$, the omitted endpoint term is $R_N(t)=N^{-1/2}(Nt-\lfloor Nt\rfloor ){\xi }_{\lfloor Nt\rfloor +1}$, and $\mathbb{E}|R_N(t){|}^2\le 1/N$. A fixed linear combination of the errors in the $k$ increments therefore tends to zero in $L^1$, by the triangle inequality and Cauchy-Schwarz inequality, even when two endpoint terms share a step. Since $|e^{ix}-e^{iy}|\le |x-y|$, restoring interpolation changes the joint characteristic function by a quantity tending to zero. HenceThe limit is the joint characteristic function of independent centered normal increments with the indicated variances. By Lévy continuity theorem, the increment vectors converge in distribution to Brownian increment vectors. The value vector is obtained by the fixed invertible triangular map of cumulative sums; thus the continuous mapping theorem gives convergence of $(S_{t_1}^N,\dots ,S_{t_k}^N)$ to $(B_{t_1},\dots ,B_{t_k})$. This proves every required finite-dimensional distribution limit. The finite fourth moment is not needed for this part; it will give tightness in part (b).

We prove fourth-moment tightness of polygonal random walks uniformly, including intervals shorter than a mesh cell or crossing a mesh boundary. For $s<t$, let $c_j$ be the length of the overlap of $(Ns,Nt)$ with $(j-1,j)$. The interpolated increment isPut $m_4=\mathbb{E}{\xi }^4<\infty$. Expanding the fourth power and using centered independent steps, only the terms with four equal indices or two equal pairs survive. ConsequentlyIf $m_4\le 3$, the last correction is nonpositive. If $m_4>3$, use $\sum c_j^4\le (\sum c_j^2{)}^2$. In either case the expression is at most $\max (3,m_4)N^{-2}(\sum c_j^2{)}^2$. Since $c_j^2\le c_j$,Also $S_0^N=0$ and the paths are continuous. The stated tightness criterion applies with $\gamma =4$, $\alpha =1$ and the displayed constant, so the laws ${\mu }_N$ are tight on $C_0([0,1],\mathbb{R})$ with its uniform topology. Part (a) established all the Brownian finite-dimensional distribution limits. The supplied implication from tightness plus those limits now yields the Donsker invariance principle:where $\mu$ is Wiener measure. No estimate restricted to grid endpoints would suffice by itself for the printed uniform criterion; the overlap coefficients handle every pair of times.

Write $Z_t=⟨{\kappa }_t⟩$, where the angle brackets average only over walk paths, and use $\mathbb{E}$ only for the environment. Every nearest-neighbor path of length $t$ has probability $(2d{)}^{-t}$, so the finite path sum is exactly the walk expectation. It depends only on environment layers through time $t$, and hence is ${\mathcal{F}}_t$-measurable. Its factors lie in $[1-\epsilon ,1+\epsilon ]$, so $Z_t$ is positive and integrable at each fixed time.

For any fixed path through time $t+1$, the environment variable $h(t+1,{\xi }_{t+1})$ is independent of ${\mathcal{F}}_t$ and has mean zero. Conditional expectation therefore removes its last factor. Summing over the $2d$ possible last steps of each length-$t$ path cancels the extra factor $2d$ in the path probability. ThusThis is the positive random-environment path-weight martingale. It is nonnegative and bounded in $L^1$, so the martingale convergence theorem gives a finite limit $\zeta \ge 0$ almost surely. At this stage one can conclude $\mathbb{E}\zeta \le 1$ by Fatou's lemma, but not yet equality; the second-moment bound in part (b) will prevent loss of mean.

For a fixed environment, use two independent copies of the walk to express $Z_t^2=⟨{\kappa }_t^{(1)}{\kappa }_t^{(2)}⟩$. The product is finite and nonnegative, so we can interchange the two expectations. At each time $j$, if the walks occupy different sites, the two environment signs are independent and their factors have product expectation $1$. If they coincide, both factors use the same sign andDifferent time layers are independent even when a site is visited again. Therefore, with the simultaneous collision count $I_t={\sum }_{j=1}^t{1}_{\{{\xi }_j^{(1)}={\xi }_j^{(2)}\}}$,This is the collision-count second moment for independent path weights. It involves equal-time intersections, not arbitrary intersections of the two spatial ranges.

The difference walk $D_j={\xi }_j^{(1)}-{\xi }_j^{(2)}$ has independent bounded increments symmetric about zero and a full-dimensional step distribution. It may hold at zero for one step; such a hold counts as a positive-time return. The allowed transience fact givesMoreover $\rho >0$ since the two first steps can be equal. Restarting the independent increments after every return to zero shows that the total positive-time return count $I_{\infty }$ has the zero-based geometric distributionIndeed the probability of at least $k$ returns is ${\rho }^k$, and subtracting successive tails gives this law. Consequently, whenever $\rho (1+{\epsilon }^2)<1$,A sufficient small-noise condition is $0<\epsilon <\min (1,\sqrt{(1-\rho )/\rho })$.

The L2 martingale convergence theorem now gives $Z_t\to \zeta$ in $L^2$ as well as almost surely. One can see the mean preservation directly: for $t\ge s$, the martingale identity gives $\mathbb{E}(Z_t-Z_s{)}^2=\mathbb{E}{Z}_t^2-\mathbb{E}{Z}_s^2$. The second moments are increasing and bounded, so the sequence is Cauchy in $L^2$ and its limit is the already identified almost-sure limit. Thus

For each fixed $m\ge 0$ and $T\ge m$, remove the first $m$ weight factors but retain the same walk law:This quantity is measurable with respect to ${\mathcal{G}}_{m+1}=\sigma (h(j,x):j\ge m+1,x\in {\mathbb{Z}}^d)$, since the averaging over all walk positions is deterministic and involves no earlier environment variables. The bounds on each deleted factor give, pointwise for every environment,Both constants are finite and strictly positive. Taking lower limits gives the exact identity of eventsThere is no exceptional-set issue in this comparison. Choose the version of $\zeta$ to equal ${\mathrm{liminf}}_T{Z}_T$ when this is finite and to equal $1$ otherwise; it agrees with the almost-sure martingale limit, and its zero event is precisely the left-hand event above. Since the identity holds for every $m$, $\{\zeta =0\}$ belongs to the printed tail sigma-algebra ${\bigcap }_{n\ge 1}{\mathcal{G}}_n$. This proves the tail event for a vanishing positive path-weight limit without pretending that the whole value of $\zeta$ is tail-measurable.

The independent time layers of the environment are independent random vectors, so the Kolmogorov zero-one law applies to their tail sigma-algebra. It yields $\mathbb{P}(\zeta =0)\in \{0,1\}$. Under the small-noise condition from part (b), $\mathbb{E}\zeta =1$ and $\zeta \ge 0$, so that probability cannot be $1$. HenceThe tail-event argument itself works for every $0<\epsilon <1$; the deduction of positivity here uses the mean-one conclusion supplied by part (b).