Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 33 (Advanced Probability)

Use the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$ of the simple symmetric random walk. The event $\{T_1\le n\}={\bigcup }_{k=0}^n\{S_k=1\}$ belongs to ${\mathcal{F}}_n$, so $T_1$ is a stopping time.

For a positive integer $m$, set ${\tau }_m=T_1\wedge T_{-m}$. This exit time from the finite interval is integrable: in each block of $m+1$ steps there is a probability at least $2^{-(m+1)}$ of all steps being positive, which forces exit if it has not already occurred. Consequently the survival probabilities have a geometric upper bound.

We use the bounded-time optional stopping theorem: if $M$ is a martingale and $\sigma$ a bounded stopping time, then $\mathbb{E}{M}_{\sigma }=\mathbb{E}{M}_0$. Apply it at ${\tau }_m\wedge n$ to $S_n$ and to the square-minus-time martingale of a simple symmetric random walk $S_n^2-n$. The stopped positions lie in $[-m,1]$, so dominated convergence and monotone convergence giveWriting $p_m=\mathbb{P}(T_1<T_{-m})$, the first equation becomes $p_m-m(1-p_m)=0$, hence $p_m=m/(m+1)$. The second gives $\mathbb{E}{\tau }_m=p_m+m^2(1-p_m)=m$. Since ${\tau }_m\le T_1$, its expectation satisfies $\mathbb{E}{T}_1\ge m$ for every $m$. ThereforeNevertheless $\mathbb{P}(T_1<\infty )\ge p_m\to 1$. Thus the infinite mean first passage of a simple symmetric random walk occurs despite almost sure finiteness; using unrestricted optional stopping directly at $T_1$ would be unjustified.

Define the stopped martingaleIt is nonnegative: before the first visit to $1$, the nearest-neighbour random walk is at most $0$, and afterwards the stopped position is $1$. Each $M_n$ is integrable, with $|M_n|\le n+1$. MoreoverThe indicator is ${\mathcal{F}}_n$-measurable and the increment has conditional mean zero, so $M_n$ is a martingale with $\mathbb{E}{M}_n=M_0=1$.

Part (a) shows $T_1<\infty$ almost surely, so every such path eventually has $M_n=0$. Thus $M_n\to 0$ almost surely. But $\mathbb{E}|M_n-0|=1$ for every $n$, so there is no convergence in L1. Any possible L1 convergence limit would agree with the almost sure limit. This is a nonnegative martingale with almost sure convergence but no convergence in L1, and hence it is not uniformly integrable.

Because each increment is $\pm 1$, the event at time $k$ defining $T$ is exactly $\{X_{k-1}=X_k=1\}$. Therefore, for $n\ge 2$,and for $n<2$ this event is empty. Thus $T$ is a stopping time for the natural filtration.

On the other hand, $\{U\le 0\}=\{T=2\}=\{X_1=X_2=1\}$. This event has probability $1/4$, whereas the initial sigma-algebra ${\mathcal{F}}_0$ is trivial, even after completion up to null sets. It therefore cannot belong to ${\mathcal{F}}_0$. Hence $U=T-2$ is not a stopping time. Subtracting a deterministic delay from a stopping time can require information from the future.

The time $T$ is the waiting time for two consecutive successes in independent fair trials. First note its integrability: if any one of the disjoint pairs $(X_1,X_2),\dots ,(X_{2k-1},X_{2k})$ is $++$, then $T\le 2k$. Thus $\mathbb{P}(T>2k)\le (3/4{)}^k$.

Let $e_0$ be the expected additional waiting time with no trailing positive step, and let $e_1$ be the expected additional time when the preceding step was positive. Conditioning on the next independent increment givesA negative step returns either state to state $0$; a positive step moves state $0$ to state $1$ and completes the pattern from state $1$. Substitution yields $e_0=2+e_1=3+e_0/2$, so $e_0=6$. The original process starts in state $0$, and thereforeOverlapping pairs are dependent, so regarding each successive pair as a fresh trial of success probability $1/4$ would give the wrong expectation.

Let $Y_i$ be independent and identically distributed random variables with moment-generating function finite on an open interval about $0$. Putallowing $\Lambda =+\infty$ outside its finite domain. The Cramér theorem states that ${\bar{Y}}_n=n^{-1}{\sum }_{i=1}^n{Y}_i$ satisfies a large deviation principle with speed $n$ and good rate function $I$, the Legendre transform of a cumulant-generating function. Explicitly, for every closed set $F$ and open set $O$,Here $\log 0=-\infty$ and $\inf \varnothing =+\infty$. The rate function is lower semicontinuous and its finite sublevel sets are compact. The exponential-moment hypothesis is essential for this form of the Cramér theorem.

For the unit-rate exponential distribution, direct integration givesFor $x>0$, maximizing $\theta x+\log (1-\theta )$ gives $\theta =1-1/x$, and therefore $I(x)=x-1-\log x$. For $x\le 0$ the supremum is infinite, as seen by taking $\theta \to -\infty$.

For $a>1$, $I$ is increasing on $[a,\infty )$, and its continuity gives ${\inf }_{[a,\infty )}I={\inf }_{(a,\infty )}I=I(a)$. The closed-set upper bound and open-set lower bound of the Cramér theorem squeeze the desired limit to $-I(a)$. For $a=1$, both infima are $0$, because $I(1)=0$ and $I(x)\to 0$ as $x\downarrow 1$. For $0\le a<1$, the strong law of large numbers gives $S_n/n\to 1$ almost surely, so the tail probability tends to $1$; at $a=0$ it is identically $1$.

Consequently the exponential sample-mean upper-tail rate isThe threshold case uses the rate-function lower bound on the open half-line, rather than applying the law of large numbers at equality.

The transformation of the uniform distribution gives, for $x\ge 1$,Thus $X_1$ has a Pareto distribution with lower endpoint $1$ and shape $2$. It has mean $2$, but no positive exponential moments, so the preceding version of the Cramér theorem is unavailable.

At $a=0$, the event in question is certain. For every fixed $a>0$ and all sufficiently large $n$, positivity of the summands gives the one-big-jump polynomial lower boundTaking logarithms and dividing by $n$ gives an upper bound $0$ and a lower bound $-2\log (na)/n\to 0$. HenceThis covers thresholds below, at and above the mean. Above the mean it means decay is slower than exponential speed $n$, not that the tail probability tends to $1$.

On a measurable space $(E,\mathcal{E})$ with a sigma-finite measure $\mu$, a Poisson random measure $N$ is a random counting measure such that $N(A)$ has the Poisson distribution with parameter $\mu (A)$ for every measurable $A$ of finite intensity, and the counts on finitely many pairwise disjoint measurable sets are independent. The sample measures are countably additive; repeated atoms are allowed if the intensity has atoms.

When $\mu (A)=\infty$, exhaustion by finite-intensity subsets gives $N(A)=\infty$ almost surely. Indeed their counts increase, and the Poisson distribution probability of a count at most any fixed integer tends to zero as the parameter tends to infinity. Independent Poisson counts on disjoint sets, with means prescribed by $\mu$, characterize the Poisson random measure.

For a measurable $A$ with $(\mu +\nu )(A)<\infty$, independence of the two Poisson random measures givesThus its count has the Poisson distribution with the summed parameter. If $A_1,\dots ,A_m$ are disjoint, the variables within each family of counts are independent, and independence of $\Phi$ and $\Psi$ makes the two families independent of each other. Hence the pairs $(\Phi (A_j),\Psi (A_j))$, and therefore their sums, are independent over $j$.

Adding sample counting measures preserves countable additivity. The definition in (a) therefore provesThis proves the required Superposition theorem for Poisson point processes directly from count distributions.

Interpret the second process as an independent copy of the unit-rate Poisson process. First, the sums are finite almost surely. On $[0,1]$ there are finitely many arrivals, none at $0$, so their inverse-square contributions are finite. On $[1,\infty )$,For completeness, this expectation identity follows first for nonnegative simple functions from $\mathbb{E}N(A)=|A|$, and then for all nonnegative measurable functions by monotone convergence. Thus no unproved Poisson-integral formula is needed, and the tail sum is finite almost surely.

By (b), merging the two processes produces a rate-$2$ Poisson process with arrival times $V_i$. Its rescaled arrivals $2V_i$ form a unit-rate Poisson process: for a measurable set $A$, their count is the merged count on $A/2$, with parameter $2|A/2|=|A|$, and disjoint-set independence is preserved. ConsequentlyTherefore $\boxed{c=4}$. This is the scaling of an inverse-power sum over Poisson arrivals with exponent $2$.

The PDF does not explicitly repeat the second process's rate. If that rate were $\rho$ rather than $1$, the same count argument would give $X+Y\stackrel{d}{=}(1+\rho {)}^{2}X$. The numerical value $4$ uses the intended independent-unit-rate-copy interpretation.

Use the independent-mark interpretation: the Brownian motions attached to the atoms are independent of one another and of the initial Poisson random measure. Fix $t$ and defineConditionally on the initial atoms, each atom is retained as a dangerous atom if its own path meets the target by time $t$. These tests are independent, with position-dependent retention probability $p_t(x)$. The permitted Poisson thinning property makes the dangerous atoms a Poisson random measure of intensity $p_t(x)dx$.

Its total intensity is computed without invoking a marking or displacement theorem. The event in the definition of $p_t(x)$ says that $x$ belongs toBy the Tonelli theorem,Symmetry of Brownian motion gives $-\xi \stackrel{d}{=}\xi$ as processes. It therefore identifies the last expectation with $\mathbb{E}\mathrm{vol}(W(t))$, where the sign of the deterministic path $f$ is unchanged. This swept set is a Wiener sausage with an added deterministic path.

The total intensity is finite on each bounded time interval. To see this explicitly, write $K_t=1+{\sup }_{s\le t}|f(s)|$ and $R_t={\sup }_{s\le t}|\xi (s)|$. The sausage is contained in a ball of radius $K_t+R_t$. On a finite time grid, splitting according to the first crossing of a positive level $u$ by a one-dimensional Brownian motion shows that the chance of ending above $u$, conditional on the crossing, is at least $1/2$: the remaining independent increment is symmetric. Thus the grid maximum exceeds $u$ with probability at most twice the final Gaussian upper tail. Dense grids and continuity give the same bound for the path maximum. Applying this to each coordinate and its negative givesThe last inequality follows from $\mathbb{E}{e}^{\theta N(0,t)}=e^{{\theta }^{2}t/2}$ and minimizing the exponential Markov bound. Integration of this tail gives finite moments of $R_t$ of every positive order, so $\mathbb{E}\mathrm{vol}(W(t))<\infty$.

There are consequently only finitely many dangerous atoms on each compact time interval, almost surely. For closed balls, continuity of the paths makes each finite hitting-time infimum attained. The event $T>t$ is therefore the absence of dangerous atoms up to time $t$.

The open-ball convention has the same survival probability at each fixed $t$. Indeed for any compact path range $K$, the difference between its closed and open radius-one neighborhoods is the shell $\{x:\mathrm{dist}(x,K)=1\}$, which has zero Lebesgue measure. To see this, choose a nearest $y\in K$ for a shell point $x$. For every sufficiently small $\epsilon >0$, the ball of radius $\epsilon /2$ centered at $x-\epsilon (x-y)$ lies in the open neighborhood and inside the ball of radius $3\epsilon /2$ about $x$. Thus the shell has a fixed proportional hole at every scale; the Lebesgue density theorem forces its measure to be zero. By the Tonelli theorem, closed-touch and open-entry retention probabilities have equal integrals. Independent thinning therefore gives no atom that touches only the boundary before this fixed horizon, almost surely. This also excludes a difference at an open-entry infimum equal to $t$.

The zero-count probability of a Poisson distribution is $e^{-\lambda }$, and henceThis survival among independently moving Poisson traps formula has been derived using only independent thinning and the defining Poisson zero-count probability, with the expectation/volume step supplied by Tonelli's theorem.

For a nonnegative submartingale $(M_k{)}_{0\le k\le n}$ and $M_n^{\ast }={\max }_{0\le k\le n}{M}_k$, the weak form of the Doob maximal inequality isTo prove it, let $A_k$ be the event that $k$ is the first index with $M_k\ge u$. These events are disjoint, $A_k\in {\mathcal{F}}_k$, and their union is $A=\{M_n^{\ast }\ge u\}$. The submartingale property gives $\mathbb{E}[M_n\mid {\mathcal{F}}_k]\ge M_k$. Multiplying by $1_{A_k}$, taking expectations and summing yields $\mathbb{E}[M_n{1}_A]\ge {\sum }_k\mathbb{E}[M_k{1}_{A_k}]\ge u\mathbb{P}(A)$. Nonnegativity gives the second inequality.

The associated Doob Lp maximal inequality, for $p>1$ and $M_n\in L^p$, isIndeed $M_k\le \mathbb{E}[M_n\mid {\mathcal{F}}_k]$, so conditional Jensen inequality first ensures finite $p$th moments for all $M_k$ and hence for the finite maximum. Integrating the weak inequality against $p{u}^{p-2}du$ and using the Tonelli theorem givesThe last step is Holder inequality. Dividing, unless the maximum is zero, proves the stated norm bound. For an arbitrary martingale, its absolute value is a nonnegative submartingale by conditional Jensen inequality, so both corresponding absolute-maximum bounds follow.

The moment-generating function of a normal distribution givesIndependence of $X_{n+1}$ from ${\mathcal{F}}_n$ impliesEvery exponential here is integrable. Thus the process is a martingale exactly when $-\lambda +{\lambda }^2/2=0$. Its two roots are $0$ and $2$, and the unique positive root isThe resulting exponential martingale of a random walk is nonnegative and has expectation $1$ at every finite time.

The strong law of large numbers gives $S_n/n\to -1$ almost surely, so $S_n\to -\infty$. Therefore the infinite-horizon maximum $Z$ is finite and attained almost surely; also $Z\ge 0$ because $S_0=0$.

Apply the Doob maximal inequality to $M_k=e^{2S_k}$ through time $n$. Since $\mathbb{E}{M}_n=1$,These finite-horizon events increase to $\{Z>t\}$. Continuity of probability under increasing unions givesFor $t<0$ the same bound is trivial, because its right side exceeds $1$. Only bounded-horizon maximal inequalities were used before passing to the limit; no unjustified stopping at an infinite-horizon crossing time is needed.

For $0<b<\lambda =2$, integrate the identity $e^{bz}-1={\int }_0^{z}b{e}^{bt}dt$ for $z\ge 0$. The Tonelli theorem and the tail bound in (c) giveFor $b=0$ the expectation is $1$, and for $b<0$ the fact $Z\ge 0$ gives $0<e^{bZ}\le 1$. ThereforeThis is an exponential moment bound for a Gaussian random-walk maximum. The upper-tail bound proves the requested sufficient range; it alone does not establish a converse at the endpoint.

Put $\tau =T_r\wedge T_R$. First establish almost sure finiteness. The Itô formula gives the martingale $|B_t{|}^2-2t$ for planar Brownian motion. Stop it at $t\wedge T_R$. The stopped path has norm at most $R$, soBy monotone convergence, $\mathbb{E}{T}_R<\infty$, and hence $\tau <\infty$ almost surely.

The function $h(y)=\log |y|$ is a harmonic function away from $0$: in polar coordinates its Laplacian is $h^{\prime \prime }(\rho )+h^{\prime }(\rho )/\rho =-{\rho }^{-2}+{\rho }^{-2}=0$. The Itô formula shows $h(B_{t\wedge \tau })$ is a local martingale. It is bounded between $\log r$ and $\log R$, so it is a true martingale and passage to $\tau$ is justified by dominated convergence. Writing $p={\mathbb{P}}_x(T_r<T_R)$ and using continuity at exit givesSolving yields the planar Brownian annulus hitting probabilityThe stopping argument stays away from the singularity of the logarithm until the calculation is complete.

First fix a deterministic point $y$ different from the initial point. By translation, work with $y=0$ and $B_0=x\ne 0$. For $R>|x|$, hitting $0$ before $T_R$ requires hitting every circle of radius $r\in (0,|x|)$ before $T_R$. Part (a) givesAny finite-time hit of $0$ lies before exit from some sufficiently large integer-radius circle, since a continuous path on a finite interval is bounded. A countable union over such radii therefore shows that this fixed point is never hit. This is the polar point for planar Brownian motion property; it is a statement about each fixed point, not about avoiding all points simultaneously.

For the initial point $x$, fix a deterministic $\epsilon >0$. The Gaussian distribution of $B_{\epsilon }$ has a density, so $B_{\epsilon }\ne x$ almost surely. Conditional on ${\mathcal{F}}_{\epsilon }$, the future is Brownian motion starting from $B_{\epsilon }$, and the preceding fixed-point result shows that it never hits $x$. Taking $\epsilon =1/m$ and a countable union proves there is no return to the starting point at any positive time.

In contrast, neighborhoods are revisited arbitrarily late. Choose $r>0$ so that the closed disk centered at $x$ of radius $r$ lies in the given open set $U$. From any point $z$ outside this disk, let $R\to \infty$ in part (a), centered at $x$. It givesAt each deterministic integer time $n$, condition on $B_n$. If it is in the disk there is already a visit to $U$ at time $n$; if it is outside, the Markov property and the last calculation ensure a later visit to that disk, hence to $U$. With probability one this holds for all $n$ simultaneously. Thus the set of visits to $U$ is unbounded. The recurrence of planar Brownian motion concerns neighborhoods even though every fixed point is polar.

Let $L$ be the fixed line and choose $y\in L$. Take orthonormal vectors $e_1,e_2$ spanning the plane perpendicular to $L$. The processis standard planar Brownian motion starting from $Y_0\ne 0$. Indeed the projected increments are centered Gaussian random vectors with covariance $(t-s)I_2$, are independent on disjoint intervals, and have continuous paths.

The event $B_t\in L$ is exactly $Y_t=0$. The polar point for planar Brownian motion result in (b) therefore givesThis is a projection criterion for Brownian avoidance of affine subspaces: avoiding a fixed point in a two-dimensional projection excludes hitting the original line.

Let $M_t={\max }_{0\le s\le t}{B}_s$. The Brownian reflection principle givesHere is the reflection argument: on paths that hit $1$ before $t$, reflect all increments after their first hitting time. The Strong Markov property gives independent Brownian motion after that time, whose sign can be reversed without changing its law. This exchanges paths ending below $1$ with paths ending above $1$. The latter have necessarily hit $1$, and the endpoint has no atom at $1$, giving the displayed equality. It also shows that $M_t$ has a continuous distribution at every positive level.

Writing $\Phi$ for the standard normal distribution function, the probability of staying below the barrier is thereforeSince $\Phi (h)-\Phi (0)\sim h/\sqrt{2\pi }$ as $h\downarrow 0$, the Brownian barrier survival asymptotic isAny smaller exponent gives a zero limit and any larger exponent gives an infinite limit, so this is the unique exponent producing a finite positive constant.

Let $X_i$ be independent and identically distributed random variables with mean $0$ and variance ${\sigma }^2\in (0,\infty )$, and put $S_0=0$, $S_k={\sum }_{i=1}^k{X}_i$. Define the polygonal interpolationwith the endpoint $W_n(1)=S_n/(\sigma \sqrt{n})$. The Donsker invariance principle stateswhere $B$ is standard one-dimensional Brownian motion and the arrow denotes weak convergence of probability measures on this path space. Equivalently, the step interpolation converges in the Skorokhod space with its $J_1$ topology. The continuous interpolation version is sufficient for the maximum in part (c).

For the simple symmetric random walk, the increments have mean $0$ and variance $1$. Use the polygonal interpolation from (b). The maximum functional is Lipschitz in the supremum norm, sinceEach interpolating segment is linear, so its maximum occurs at a grid endpoint. The continuous mapping theorem applied to the Donsker invariance principle givesThe limiting maximum has no atom at $a>0$ by the Brownian reflection principle, so the closed-tail probabilities converge at this threshold. Including $j=0$ does not change the event because $a>0$. Therefore the random-walk maximum limit from Donsker invariance isHere $\Phi$ is the standard normal distribution function. The normalization and the positive-threshold condition are those in the PDF; the TeX aid's $\sqrt{t}$ is not the printed expression.