Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 34 (Advanced Probability)

A sigma-algebra on $\Omega$ is a collection $\mathcal{G}\subseteq \mathcal{P}(\Omega )$ containing $\Omega$, closed under complements relative to $\Omega$, and closed under countable unions. These properties also give closure under countable intersections by De Morgan laws.

Let $\mathcal{G}={\bigcap }_{r\in R}{\mathcal{F}}_r$. Every constituent sigma-algebra contains $\Omega$, so $\Omega \in \mathcal{G}$. If $A\in \mathcal{G}$, its complement belongs to every ${\mathcal{F}}_r$, hence to $\mathcal{G}$. Likewise, if $A_j\in \mathcal{G}$ for all $j$, then ${\bigcup }_j{A}_j$ belongs to every ${\mathcal{F}}_r$. Thus $\mathcal{G}$ is a sigma-algebra. For an empty indexing set, the usual intersection convention gives $\mathcal{G}=\mathcal{P}(\Omega )$, which is also a sigma-algebra.

A union need not work. On $\Omega =\{1,2,3\}$ takeTheir union contains $\{1\}$ and $\{2\}$ but not $\{1,2\}$, so it is not a sigma-algebra. Put $\mathcal{A}={\bigcup }_r{\mathcal{F}}_r$ and let $\mathfrak{C}$ be the collection of all sigma-algebras on $\Omega$ containing $\mathcal{A}$. This collection is nonempty because it contains the power set $\mathcal{P}(\Omega )$. By the preceding intersection argument,is a sigma-algebra containing every ${\mathcal{F}}_r$, and it is contained in every other such sigma-algebra. This proves existence and minimality.

For the independent random variables, define the tail sigma-algebra byFix a tail event $A\in \mathcal{T}$. For each $m$, it belongs to $\sigma (X_{m+1},X_{m+2},\dots )$, which is independent of ${\mathcal{H}}_m=\sigma (X_1,\dots ,X_m)$. To justify independence of the generated sigma-algebras, first use independence of finite collections on cylinder events, then extend twice by the pi-lambda theorem. In particular, $\mathbb{P}(A\cap C)=\mathbb{P}(A)\mathbb{P}(C)$ for every $C\in {\mathcal{H}}_m$ and every $m$.

The increasing union ${\bigcup }_m{\mathcal{H}}_m$ is an algebra of sets generating $\mathcal{H}=\sigma (X_1,X_2,\dots )$. The collection of $C\in \mathcal{H}$ satisfying this factorization is a Dynkin system: it contains $\Omega$, is closed under complements, and under countable disjoint unions. The pi-lambda theorem therefore extends the factorization to all $C\in \mathcal{H}$. Since $A\in \mathcal{H}$, taking $C=A$ gives $\mathbb{P}(A)=\mathbb{P}(A{)}^2$. Consequently,This is the Kolmogorov zero-one law, proved here directly.

For each fixed $m$, write $S_n=S_{m-1}+{\sum }_{j=m}^n{X}_j$ for $n\ge m$, with $S_0=0$. The random variable $S_{m-1}$ is finite, so $S_{m-1}/\sqrt{n}\to 0$. Adding a real sequence tending to zero changes neither the extended-real limit inferior nor the extended-real limit superior. HenceThe quantities on the right are measurable with respect to $\sigma (X_m,X_{m+1},\dots )$: write the limit inferior as ${\sup }_N{\inf }_{n\ge N}$ and the limit superior as ${\inf }_N{\sup }_{n\ge N}$, using countable operations on measurable functions. Therefore both threshold events belong to every such sigma-algebra, and hence are tail events, for every real threshold, including when either limit is infinite.

The final recurrence claim is false under the printed hypotheses. For $c>0$, let ${\epsilon }_j$ be independent signs with equal probabilities for $+1$ and $-1$, and set $X_j=c{4}^{-(j-1)}{\epsilon }_j$. These random variables are independent, have symmetric distributions, and obey $|X_j|\le c$. Nevertheless, the geometric series gives, on every sample path,Thus the proposed repeated-return event has probability zero, even though none of the increments is degenerate. The Kolmogorov zero-one law does not determine which of zero and one occurs.

An additional identical-distribution hypothesis makes the intended conclusion true. Here is a full proof of that qualified version, using the oscillation of a bounded centered iid random walk. Symmetry and integrability give $\mathbb{E}{X}_j=0$, so $S_n$ is a martingale for its natural filtration. If the common probability distribution is concentrated at zero, every $S_n$ is zero and the conclusion is immediate. Otherwise choose $\delta >0$ with $\mathbb{P}(|X_1|>\delta )>0$. The Borel-Cantelli lemmas then give $|X_n|>\delta$ infinitely often almost surely; thus $S_n$ cannot converge to a finite limit.

For $a>0$, let $T_a=\inf \{n:S_n\ge a\}$. Before $T_a$ the sum is below $a$, and at $T_a$ it is at most $a+c$. The stopped martingale $a+c-S_{n\wedge T_a}$ is therefore nonnegative. A stopped integrable martingale remains a martingale at these bounded times, and a nonnegative martingale converges finitely almost surely by the martingale convergence theorem. On $\{T_a=\infty \}$ this would force $S_n$ to converge finitely, which has just been ruled out. Hence $T_a<\infty$ almost surely. Apply the same argument to $-S_n$ and take a countable intersection over positive integer $a$. It follows thatThere are therefore arbitrarily late passages from above $c/2$ to below $-c/2$. A path with bounded increments of magnitude at most $c$ cannot make such a passage without visiting $[-c/2,c/2]$: jumping directly between its two open complementary half-lines would require an increment larger than $c$. There are infinitely many such visits. Thus with the added identical-distribution hypothesis, the intended answer is

For events $A_n$, define their limit superior byIt is the event that infinitely many $A_n$ occur. The two Borel-Cantelli lemmas are as follows: if ${\sum }_n\mathbb{P}(A_n)<\infty$, then $\mathbb{P}(A_{\infty })=0$, without any independence assumption; if the $A_n$ are independent and ${\sum }_n\mathbb{P}(A_n)=\infty$, then $\mathbb{P}(A_{\infty })=1$.

For the first assertion, the union bound gives, for every $N$,The tail of a convergent nonnegative series tends to zero, proving the first Borel-Cantelli lemma.

For the second assertion, independence and $1-u\le e^{-u}$ for $0\le u\le 1$ giveBy continuity of probability, $\mathbb{P}({\bigcap }_{n\ge N}{A}_n^c)=0$. The event that only finitely many $A_n$ occur is the countable union of these zero-probability events over $N$. Its probability is zero. This proves the second Borel-Cantelli lemma, and hence both requested assertions:

Write $Q(x)=1-\Phi (x)={\int }_x^{\infty }\varphi (t)dt$, where $\varphi (t)=(2\pi {)}^{-1/2}{e}^{-t^2/2}$ is the standard normal density. For $x>0$, ${\varphi }^{\prime }(t)=-t\varphi (t)$ and integration by parts yieldThe boundary term at infinity vanishes. The remainder is nonnegative and is at most $Q(x)/x^2$, soDividing by the positive quantity $\varphi (x)/x$ gives lower and upper bounds $x^2/(x^2+1)$ and $1$. The squeeze theorem proves the Mills ratio asymptotic

For $a>0$ and $n\ge 2$, let $A_n(a)=\{X_n^2>a\log n\}$. Symmetry of the standard normal distribution and the Mills ratio asymptotic just proved giveFor $a>2$ the series of these probabilities converges, since its terms are eventually bounded by a constant times the convergent p-series $n^{-a/2}$. For $0<a<2$ it diverges: choose $r$ strictly between $a/2$ and one, and use $(\log n{)}^{-1/2}\ge n^{-(r-a/2)}$ for sufficiently large $n$, reducing to the divergent p-series $n^{-r}$. At $a=2$ it still diverges, as the integral test givesFor $a>2$, the first Borel-Cantelli lemma makes $A_n(a)$ occur only finitely often. For $0<a\le 2$, independence of the random variables makes the events $A_n(a)$ independent, so the second Borel-Cantelli lemma makes them occur infinitely often almost surely. Apply these conclusions simultaneously at $a=2+1/k$ for positive integers $k$, and at $a=2$. On the resulting probability-one event, the limit superior is at most every $2+1/k$ and at least two. Therefore the Gaussian sample limsup at logarithmic scale is

The real L2 space on a probability space consists of equivalence classes of measurable functions $X:\Omega \to \mathbb{R}$ satisfying $\mathbb{E}[X^2]<\infty$, where two random variables represent the same element if they are equal almost surely. Its norm isPassing to equivalence classes makes this a genuine norm: $\Vert X{\Vert }_2=0$ exactly when $X=0$ almost surely. The Minkowski inequality gives the triangle inequality.

Let $(X_n)$ be a Cauchy sequence in this norm. Choose an increasing sequence of indices $n_k$ such thatThis is possible by choosing $n_k$ beyond a Cauchy threshold for tolerance $2^{-k}$. Set $D_k=X_{n_{k+1}}-X_{n_k}$. The Cauchy-Schwarz inequality on a probability space gives $\mathbb{E}|D_k|\le \Vert D_k{\Vert }_2$. By Tonelli theorem,Thus the series of absolute differences is finite almost surely. Define $X=X_{n_1}+{\sum }_{k\ge 1}{D}_k$ on this probability-one event, and give it the value zero on its complement. It is a measurable function, and $X_{n_k}\to X$ almost surely.

For $l>k$, the Minkowski inequality givesApply the Fatou lemma to the squared difference as $l\to \infty$. It follows thatIn particular $X-X_{n_1}\in L^2$, and therefore $X\in L^2$ by the Minkowski inequality. This proves convergence in L2 of the subsequence. To recover the entire sequence, for a prescribed $\epsilon >0$ choose a Cauchy threshold $N$ for $\epsilon /2$, then choose $k$ with $n_k\ge N$ and $\Vert X-X_{n_k}{\Vert }_2<\epsilon /2$. For every $n\ge N$,Hence $\boxed{X_n\to X\text{ in }{L}^2}$, proving completeness of Lp spaces for $p=2$ without assuming the desired completeness in the argument.

A filtration $({\mathcal{F}}_n{)}_{n\ge 0}$ on a probability space is an increasing sequence of sigma-algebras contained in $\mathcal{F}$: ${\mathcal{F}}_n\subseteq {\mathcal{F}}_{n+1}$. A real stochastic process $(X_n)$ is a martingale for this filtration if $X_n$ is ${\mathcal{F}}_n$-measurable, $\mathbb{E}|X_n|<\infty$, andThe first condition is adaptedness; the tower property of conditional expectation then gives $\mathbb{E}[X_n\mid {\mathcal{F}}_m]=X_m$ whenever $m\le n$.

The almost-sure martingale convergence theorem states that if a real martingale satisfies ${\sup }_n\mathbb{E}|X_n|<\infty$, then some integrable random variable $X_{\infty }$ satisfies $X_n\to X_{\infty }$ almost surely. The more general almost sure submartingale convergence theorem needs only ${\sup }_n\mathbb{E}[X_n^{+}]<\infty$ for a submartingale. In particular, a nonnegative martingale converges to a finite integrable limit almost surely, because its expected value is constant. Mere boundedness in the L1 norm does not imply convergence in L1. The stronger uniformly integrable martingale convergence theorem gives both almost-sure convergence and convergence in L1 when the martingale is uniformly integrable.

The martingale property gives $\mathbb{E}[X_n\mid {\mathcal{F}}_m]=X_m$. Both $X_m$ and $X_n$ are square-integrable, so their product is integrable by the Cauchy-Schwarz inequality. Using the ${\mathcal{F}}_m$-measurability of $X_m$ in conditional expectation givesThe pull-out step for the possibly unbounded $X_m$ can be justified by first truncating it, then passing to the limit in the L2 norm and using the Cauchy-Schwarz inequality. Expanding the square now yieldsThe left side is nonnegative. Thus $a_n=\mathbb{E}[X_n^2]$ is nondecreasing and bounded above by $M$, and so $a_n\to a\le M$. For $m\le n$,By symmetry of the norm difference this proves that $(X_n)$ is a Cauchy sequence in the L2 space. The completeness established in part (a) gives an $X_{\infty }\in L^2$ withThis is the L2-bounded martingale convergence theorem, derived from martingale-difference orthogonality and completeness. The same sequence also converges almost surely by part (b), since $\mathbb{E}|X_n|\le \sqrt{M}$; uniqueness of a limit in probability identifies that limit with this $X_{\infty }$.

Put $S_0=0$ and take ${\mathcal{F}}_0$ to be the trivial sigma-algebra. Each $S_n$ is measurable with respect to the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$, andIndependence of $X_{n+1}$ from ${\mathcal{F}}_n$ makes its conditional expectation equal to its expected value, which is zero. HenceThe measurability, integrability and conditional expectation conditions are all verified, so $\boxed{(S_n)\text{ is a martingale for }({\mathcal{F}}_n).}$

Here $X_1\le 1$, so for every $\tau >0$,The Jensen inequality for the strictly convex exponential function givesIn fact the inequality is strict: $\mathbb{P}(X_1=1)>0$ and $\mathbb{E}{X}_1=0$ exclude a constant random variable. In particular, $\boxed{1\le M(\tau )<\infty }$ as required.

For $Z_n=e^{\tau S_n}/M(\tau {)}^n$, independence and identical distribution giveThus $Z_n$ is positive, integrable with mean one, and adapted to the natural filtration. Conditioning on the next increment givesConsequently $\boxed{(Z_n)\text{ is a martingale}.}$ This is the exponential martingale of a random walk.

The hitting time $T$ is a stopping time for the natural filtration, because $\{T\le n\}={\bigcup }_{k\le n}\{S_k=b\}$. The integer-valued increments are at most one. A path started at zero therefore cannot reach or exceed $b$ without first visiting $b$, soDefine $Y_n=b-S_{n\wedge T}$. It is nonnegative and integrable: $|S_{n\wedge T}|\le {\sum }_{j\le n}|X_j|$. Moreover,The indicator function is ${\mathcal{F}}_n$-measurable, and $X_{n+1}$ is independent of ${\mathcal{F}}_n$ with zero expected value. Taking conditional expectation therefore proves directly that $(Y_n)$ is a nonnegative martingale.

The general result used here is that a nonnegative discrete-time martingale has a finite almost-sure limit; this is the martingale convergence theorem, since $\mathbb{E}{Y}_n=\mathbb{E}{Y}_0=b$ bounds its L1 norm. On $\{T=\infty \}$ it follows that $S_n=b-Y_n$ converges finitely. A convergent sequence of integers is eventually constant, so $X_n=S_n-S_{n-1}$ would eventually be zero on this event.

However, the independent events $\{X_n=1\}$ all have the same strictly positive probability. The second Borel-Cantelli lemma says that they occur infinitely often almost surely. This contradicts eventual constancy on any positive-probability subset of $\{T=\infty \}$. ThusNotice that no lower bound on the negative increments was needed.

The stopped martingale $Z_{n\wedge T}$ is a martingale. For completeness, the bounded-time stopping rule follows directly fromwhose conditional expectation given ${\mathcal{F}}_n$ is zero. Integrability at each fixed $n$ follows by expressing the stopped value as a finite sum of the integrable $Z_j$ restricted to disjoint events. Therefore $\mathbb{E}{Z}_{n\wedge T}=\mathbb{E}{Z}_0=1$.

The crucial bound is deterministic. Since $S_{n\wedge T}\le b$ and $M(\tau )\ge 1$,A bounded family is uniformly integrable: for $K>e^{\tau b}$ all its quantities $\mathbb{E}[|Z_{n\wedge T}|1_{\{|Z_{n\wedge T}|>K\}}]$ vanish. Part (c) gives $T<\infty$ almost surely, and then $S_T=b$. HenceThe general result for passing to expectations is the dominated convergence theorem: almost-sure convergence under one integrable bound implies convergence in L1 and convergence of expectations. Applying it with the bound $e^{\tau b}$ givesThis is the exponential first-passage transform for an upward skip-free random walk; it avoids an unjustified use of optional stopping at an unbounded stopping time.

For the simple symmetric random walk, the moment-generating function isFor a given $\alpha >0$, choose the unique $\tau >0$ satisfying $\cosh \tau =e^{\alpha }$. The transform in part (d) becomes $\mathbb{E}{e}^{-\alpha T}=e^{-b\tau }$. To express this in terms of $\alpha$, put $r=e^{-\tau }\in (0,1)$. The equation $(r+r^{-1})/2=e^{\alpha }$ gives $r^2-2e^{\alpha }r+1=0$. Its smaller root is the one in $(0,1)$, soThe second expression follows by rationalizing the first root. As $\alpha \downarrow 0$ the transform tends to one, consistent with the almost-sure finiteness proved in part (c).

A family $(Y_i{)}_{i\in I}$ of integrable random variables is uniformly integrable ifThis controls the contributions of large values uniformly over the family, rather than merely bounding its L1 norms.

Put $X_n=\mathbb{E}[Z\mid {\mathcal{F}}_n]$ and $A_n(K)=\{|X_n|>K\}\in {\mathcal{F}}_n$. The conditional Jensen inequality gives $|X_n|\le \mathbb{E}[|Z|\mid {\mathcal{F}}_n]$, hence $\mathbb{E}|X_n|\le \mathbb{E}|Z|$. The Markov inequality therefore givesUsing the measurability of $A_n(K)$ in the defining integral identity for conditional expectation, for every $R>0$ we getThe first term tends to zero as $R\to \infty$ because $Z$ is integrable, by the dominated convergence theorem. Given $\epsilon >0$, first choose $R$ to make it less than $\epsilon /2$, then choose $K$ to make the second term less than $\epsilon /2$. These choices work for every $n$. This proves uniform integrability of conditional expectations:In fact the argument works for an arbitrary family of sigma-algebras; nesting is not needed for this conclusion.

Values at the endpoint one do not affect any of the conclusions, since $\mathbb{P}(U=1)=0$. Set $b_n(1)=1$ to define each random variable everywhere, and choose a Borel measurable function agreeing with $f$ almost everywhere if necessary. These choices leave all integrals and almost-sure assertions unchanged.

Every dyadic interval at level $n+1$ lies in a dyadic interval at level $n$. Equivalently, $b_n(U)$ is a measurable function of $b_{n+1}(U)$, so ${\mathcal{F}}_n\subseteq {\mathcal{F}}_{n+1}$: these sigma-algebras form a filtration. Since the uniform distribution of $U$ gives $\mathbb{E}|f(U)|={\int }_0^1|f(u)|du<\infty$, the conditional expectations $X_n=\mathbb{E}[f(U)\mid {\mathcal{F}}_n]$ are integrable and adapted. The tower property of conditional expectation givesThus $(X_n)$ is a martingale, and part (a) proves that it is uniformly integrable.

For $I_{n,k}=[k{2}^{-n},(k+1)2^{-n})$, the event $\{U\in I_{n,k}\}$ is an atom of a sigma-algebra ${\mathcal{F}}_n$, with probability $2^{-n}$. The value of the conditional expectation there is thereforeConsequently $\boxed{X_n=f_n(U)\text{ almost surely}.}$ This also shows directly that ${\int }_0^1|f_n|\le {\int }_0^1|f|$.

By the uniformly integrable martingale convergence theorem, there is an integrable $Y$ such that $X_n\to Y$ almost surely and in the L1 norm. To identify this limit, put ${\mathcal{F}}_{\infty }=\sigma ({\bigcup }_n{\mathcal{F}}_n)$. Since $0\le U-b_n(U)<2^{-n}$ away from the harmless endpoint, $U={\lim }_n{b}_n(U)$, and $U$ is ${\mathcal{F}}_{\infty }$-measurable. Conversely every $b_n(U)$ is a measurable function of $U$. Thus ${\mathcal{F}}_{\infty }=\sigma (U)$, and both $Y$ and $f(U)$ have ${\mathcal{F}}_{\infty }$-measurable versions.

For $A\in {\mathcal{F}}_m$, the defining property of conditional expectation gives $\mathbb{E}[X_n{1}_A]=\mathbb{E}[f(U)1_A]$ whenever $n\ge m$. Passing to the limit in the L1 norm yieldsThe increasing union ${\bigcup }_m{\mathcal{F}}_m$ is an algebra of sets generating ${\mathcal{F}}_{\infty }$. The class of events for which this integral identity holds is a Dynkin system, so the pi-lambda theorem extends the identity to every $A\in {\mathcal{F}}_{\infty }$. Since both random variables are measurable there, uniqueness of conditional expectation gives $Y=f(U)$ almost surely. We have proved that the dyadic conditional averages recover integrable functions:because a probability-one assertion for $U$ is a full-Lebesgue measure assertion for $x$. Likewise, the uniform distribution of $U$ turns convergence in L1 intoNo pointwise continuity of $f$ is required.

A standard Brownian motion is a real stochastic process $(B_t{)}_{t\ge 0}$ with $B_0=0$ almost surely, continuous sample paths almost surely, and independent increments such that $B_t-B_s$ has normal distribution $N(0,t-s)$ whenever $0\le s<t$. With its completed, right-continuous natural filtration $({\mathcal{F}}_t)$, its Strong Markov property is the following: for every almost-surely finite stopping time $T$, the processis a standard Brownian motion independent of ${\mathcal{F}}_T$. Here the stopping-time sigma-algebra isIn particular, for every bounded ${\mathcal{F}}_T$-measurable random variable $H$ and bounded Borel functional $G$ on the continuous path space,Thus the independence is from the entire stopped past, not only from $B_T$, and is a statement about the whole future path, not just a single increment.

To prove the Brownian reflection principle without assuming that a level is hit in finite time, fix $t>0$, $m>0$, and set $T_m=\inf \{s\ge 0:B_s\ge m\}$ and $R=T_m\wedge t$. Continuity of the sample paths makes $T_m$ a stopping time and gives $B_{T_m}=m$ whenever $T_m<\infty$. The stopping time $R$ is bounded. Reflect the path after $R$:By the Strong Markov property, the future increments after $R$ are an independent Brownian motion. Negating them preserves their probability distribution, by symmetry of their joint normal distributions. Hence the reflected process $\hat{B}$ has the same path law as $B$.

If $T_m>t$, reflection changes nothing on $[0,t]$ and ${\hat{B}}_t=B_t<m$. If $T_m\le t$, both paths first hit $m$ at the same time and ${\hat{B}}_t=2m-B_t$. Therefore, for $x\le m$, the following events agree path by path:Indeed, the right-hand endpoint is at least $m$, so the reflected path must have hit $m$ before or at $t$; this also forces the original path to have done so. The reflection relation then makes the endpoint inequality equivalent to $B_t\le x$. Equality cases at $T_m=t$ satisfy the same relation. Since ${\hat{B}}_t$ and $B_t$ have the same probability distribution,For $t=0$, both sides are zero, because $B_0=M_0=0$ and $2m-x\ge m>0$.

For $t>0$, set $x=m$ in this identity. Continuity implies $\{B_t>m\}\subseteq \{M_t\ge m\}$, and the normal distribution of $B_t$ has no atom at $m$. Splitting according to whether $B_t\le m$ givesBoth random variables are nonnegative. Their tails agree for all $m>0$, which determines their probability distributions, including the mass at zero. Thus the Brownian running maximum satisfies

For $x>0$ and $t>0$, continuity again gives $\{T_x\le t\}=\{M_t\ge x\}$. Since $B_t/\sqrt{t}$ is a standard normal random variable, the distribution function of the Brownian first-passage time isIt tends to one as $t\to \infty$ and to zero as $t\downarrow 0$, proving almost-sure finiteness and absence of an atom at zero. For the standard normal random variable $B_1$,The value of this ratio on the zero-probability event $\{B_1=0\}$ may be defined arbitrarily. Matching the distribution functions provesFinally, differentiate the distribution function on $t>0$, using ${\Phi }^{\prime }=\varphi$ and $\frac{d}{dt}(x/\sqrt{t})=-x/(2t^{3/2})$. The first-passage-time density isand is zero for $t\le 0$. Its integral is one by the endpoint limits of $F_{T_x}$, so no missing mass at an infinite hitting time is present.