Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 101 (Introduction to Probability)

For the central limit theorem, let $X_1,X_2,\dots$ be independent and identically distributed random variables with expectation $\mu$ and finite positive variance ${\sigma }^2$. ThenThus the centered, normalized sum has convergence in distribution to the standard normal distribution. The positive-variance assumption is needed for this normalization; if ${\sigma }^2=0$, each summand equals $\mu$ almost surely and the centered sum is identically zero.

Here is a characteristic function proof using only the finite second moment. Put $U=(X_1-\mu )/\sigma$, so $\mathbb{E}U=0$ and $\mathbb{E}{U}^2=1$. The elementary integral remainder identity gives $|e^{iz}-1-iz|\le z^2/2$ for real $z$. ConsequentlyBy the dominated convergence theorem, the characteristic function satisfies ${\phi }_U(t)=1-t^2/2+o(t^2)$ as $t\to 0$. For a fixed real $t$, independence therefore givesThe allowed complex-number limit makes this tend to $e^{-t^2/2}$, the characteristic function of the standard normal distribution. It is continuous at zero, so the Lévy continuity theorem proves the asserted convergence in distribution. No third moment or boundedness of the summands was used.

For $t\ge 0$, independence factors the survival function of the minimum:The minimum is nonnegative, and this is exactly the survival function of an exponential distribution. HenceThe parameter here is the rate, rather than the mean. The calculation is the simplest example of competing exponential clocks.

The exponential distribution has no atoms, so all sample values are distinct almost surely, and $M_i$ is the $i$th order statistic. Set $M_0=0$ and $D_i=M_i-M_{i-1}$. Part (b) gives $D_1\sim \mathrm{Exp}(n\lambda )$.

To justify induction and the required independence, let $J$ be the label attaining the minimum. Conditional on its time and label, the remaining clocks are fresh independent rate-$\lambda$ exponential random variables, by the memoryless property. This conditional claim can be checked directly: for a specified label $j$, first ringing time $u$, and residual lifetimes $y_k>0$ for $k\ne j$, the joint probability density isThus the first minimum, its uniform winning label and the surviving residual clocks are independent. Repeat this argument after each minimum. At the $i$th step there are $n-i+1$ clocks, so the independent exponential order-statistic spacings satisfySince $Y_k/k$ has rate $k\lambda$ whenever $Y_k\sim \mathrm{Exp}(\lambda )$, summing the gaps provesIn particular the maximum is $M^{\ast }=M_n$. By variance additivity for independent random variables and the Laplace transform of an exponential distribution, its requested quantities areThe product follows from independence of the gaps, not merely from their marginal probability distributions.

This is the simple symmetric random walk on the integers, starting at zero. It is recurrent: it returns to zero infinitely often almost surely, and in fact visits every integer infinitely often. To see the two-sided unboundedness explicitly, gambler's ruin gives, for positive integers $a,b$,Letting $a\to \infty$ shows that $b$ is hit with probability one; the analogous argument hits every negative integer. From any state the same argument gives return to zero with probability one. Repeated use of the Strong Markov property then gives infinitely many returns and visits. ThereforeIn particular $X_n$ has no limit almost surely, and $|X_n|$ does not tend to infinity because of the returns to zero. In contrast, the strong law of large numbers gives $X_n/n\to 0$ almost surely, while the central limit theorem gives $X_n/\sqrt{n}\stackrel{d}{\to }N(0,1)$. These distinguish oscillation of the path from scaling limits of its probability distribution.

Every $X_n$ is integrable: induction gives $|X_n|\le a^n|x|+{\sum }_{j=0}^{n-1}{a}^j$. Since the innovation has expectation zero, the recursion impliesStarting from $\mathbb{E}{X}_0=x$, induction therefore givesThis holds for every $a>0$, including $a=1$. The independence of the signs also identifies this as an autoregressive process of order one, although zero mean of each sign already suffices for the displayed expectation recursion.

Write $c=1/(a-1)$. If $X_0=x>c$, then for either possible sign,as long as $X_n>c$. Thus the process stays above $c$, is strictly increasing, and induction gives $X_n\ge c+a^n(x-c)\to \infty$. If $x<-c$, the symmetric argument makes the process strictly decreasing to $-\infty$. This proves the first assertion pathwise, with the strict sufficient threshold $|x|>c$.

For an arbitrary starting point, a proof is needed that the process actually reaches such a region. Fix $L>c$ and choose an integer $m$ soAt a block starting at time $km$, if $X_{km}\ge 0$, the next $m$ signs all equal to $+1$ give $X_{(k+1)m}>L$. If $X_{km}<0$, all $-1$ signs instead give $X_{(k+1)m}<-L$. Conditional on the current natural filtration, the selected block has probability $\epsilon =2^{-m}$, by independence of future signs. If $\tau =\inf \{n:|X_n|>L\}$, iterated conditional expectation givesThis is a geometric tail bound from a uniform escape probability, so $\tau <\infty$ almost surely. Once outside, the sign is preserved and, for every future noise sequence,Consequently the explosive affine recursion with symmetric bounded noise hasThe block argument closes the gap between escape from a large initial value and escape from an arbitrary one; no assertion about the absence of atoms in an infinite random series is necessary.

A discrete-time martingale relative to a filtration $({\mathcal{F}}_n)$ is an adapted process $(M_n)$ with $\mathbb{E}|M_n|<\infty$ andIterating conditional expectation also gives $\mathbb{E}[M_m\mid {\mathcal{F}}_n]=M_n$ for $m\ge n$. It is bounded in $L^2$ when each $M_n$ is square integrable andThis is a uniform bound on the second moments, not a pathwise bound on all sample values.

The optional stopping theorem for bounded stopping times says that, if $\sigma \le \tau \le K$ for a deterministic finite $K$, thenHere ${\mathcal{F}}_{\sigma }$ is the stopping-time sigma-algebra. The second assertion follows by taking $\sigma =0$ and then expectations. An $L^2$ bound is not needed: integrability at the finitely many deterministic times suffices.

For a proof, both stopped values are integrable since $|M_{\tau }|,|M_{\sigma }|\le {\sum }_{j=0}^K|M_j|$. ExpandIf $A\in {\mathcal{F}}_{\sigma }$, then $A\cap \{\sigma \le k\}\in {\mathcal{F}}_k$ by the definition of the stopping-time sigma-algebra, and $\{\tau >k\}\in {\mathcal{F}}_k$ because $\tau$ is a stopping time. Thus the indicator of $A\cap \{\sigma \le k<\tau \}$ is ${\mathcal{F}}_k$-measurable. Multiplying the sum by $1_A$, taking expectations, and conditioning each summand on ${\mathcal{F}}_k$ gives zero, by the martingale increment property. Therefore $\mathbb{E}[1_A{M}_{\tau }]=\mathbb{E}[1_A{M}_{\sigma }]$ for every $A\in {\mathcal{F}}_{\sigma }$. Since $M_{\sigma }$ is ${\mathcal{F}}_{\sigma }$-measurable, this is exactly the claimed conditional expectation identity.

The global drift hypothesis as printed is impossible on a finite state space. Indeed, let $x_{\ast }$ minimize $f$. Every possible value of $f(X_{n+1})$ is at least $f(x_{\ast })$, socontradicting a decrease by $\delta >0$. Equivalently, its formal iteration would give ${\mathbb{E}}_{x}f(X_n)=f(x)-n\delta$, whereas $f$ is bounded on the finite state space. This is the constant nonzero drift is impossible on a finite Markov chain obstruction. Thus there is no genuine chain satisfying all the literal premises.

The meaningful intended version imposes the drift only on $S\setminus D$, and stops at $D$. In the natural filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, the Markov property then gives, on $\{T>n\}$,The correct stopped martingale isIt is adapted and integrable, since $f$ is bounded and $n\wedge T\le n$. Its increment equalswhose conditional expectation is zero. Taking expectations yieldsSince $T<\infty$ almost surely and $f(X_T)=0$, the bounded convergence theorem gives ${\mathbb{E}}_{x}f(X_{n\wedge T})\to 0$. The monotone convergence theorem gives ${\mathbb{E}}_x(n\wedge T)\uparrow {\mathbb{E}}_{x}T$, without presupposing its finiteness. Consequently the constant-drift hitting-time identity isFor $x\in D$, both sides are zero. Under the repaired hypothesis the unstopped $f(X_n)+n\delta$ need not be a martingale after hitting $D$; it is the displayed stopped martingale that proves the result.

The printed hitting-time formula is false for the stated transition probabilities. For example, take $N=2$ and $q=3/4$, put $p=1-q$, and write $m_i={\mathbb{E}}_{i}T$. A first step givesso $m_2=2/q=8/3$. The printed expression gives $3$, not $8/3$. This discrepancy is present in the original PDF, not just in its converted text. The quantifier mentioning every positive integer must also be restricted to positive starting states $1,\dots ,N$; states larger than $N$ are not in $S$.

Here is the exact solution for the chain as specified. Until $T$, only $\{1,\dots ,N\}$ is visited. From any such state, a sequence of downward steps reaches zero within $N$ steps with probability at least $q^N>0$; the forced step at $N$ only increases that probability. The Markov property therefore givesThus $T$ is finite almost surely and has finite expectation, without needing the supplied transience assumption. Set $m_0=0$. The first-step analysis givesPut $d=q-p=2q-1>0$, $r=p/q$, and $D_i=m_i-m_{i-1}$. The equations becomeBackward iteration, or substitution into this recursion, givesSumming from $1$ to $i$ gives the corrected hitting time of a downward-biased walk reflected at an upper barrier:and in particularThese values also supply the appropriate test function for part (b): $f(i)=m_i$, $f(0)=0$, and $Pf=f-1$ at every state before absorption. The finite-state stopped argument is applied on $\{0,\dots ,N\}$, with zero made absorbing.

For $N\ge 3$, the printed hint cannot produce constant drift by choosing its single constant $c$. With $f(i)=i$ for $i<N$ and $f(N)=N+c$, the expected downward drift is $d$ at ordinary interior states, $d-pc$ at $N-1$, and $1+c$ at $N$. Making the top drift $d$ requires $c=-2p$, but then the drift at $N-1$ is $d+2p^2$, not $d$. For $N=2$ there is no ordinary interior state; a different constant drift can be arranged, but still gives $2/q$ rather than the printed formula. This identifies precisely the missing correction at the neighboring state for the intended drift $d$; the geometric term in the correct test function repairs it throughout the interval.

Let $\tau =T_{-a}\wedge T_b$ for the simple symmetric random walk. From any interior point, $a+b$ successive $+1$ increments force exit through $b$. The conditional probability of this block is $2^{-(a+b)}$, so a blockwise geometric tail bound from a uniform escape probability gives $\tau <\infty$ almost surely.

Apply the bounded optional stopping theorem to $\tau \wedge n$. Since $S_n$ is a martingale, ${\mathbb{E}}_0{S}_{\tau \wedge n}=0$. The stopped positions lie in $[-a,b]$, so the bounded convergence theorem gives ${\mathbb{E}}_0{S}_{\tau }=0$. If $h={\mathbb{P}}_0(T_{-a}<T_b)$, nearest-neighbor jumps ensure $S_{\tau }=-a$ on that event and $S_{\tau }=b$ otherwise. ThusNext apply the bounded optional stopping theorem to the square-minus-time martingale of a simple symmetric random walk:Again the right side converges by the bounded convergence theorem, while the left side increases to ${\mathbb{E}}_0\tau$ by the monotone convergence theorem. ThereforeThis argument justifies passage to the unbounded stopping time rather than applying optional stopping without an integrability check.

For $0<i<N$, the total rate out of $i$ is ${\lambda }_i$. The holding time of the continuous-time Markov chain and its next state satisfyThe holding time is independent of the direction of this jump: the conditional probability of destination $j$ is the rate $q_{ij}$ divided by the total rate ${\lambda }_i$, independently of the elapsed holding duration. This is the exponential-clock construction of a continuous-time Markov chain with the given infinitesimal generator matrix.

At $i=0$ or $i=N$, all rates out are zero. These are absorbing states; the path remains at its initial endpoint and $J_i=\infty$ almost surely. There is no next visited state, so $X_{J_i}$ is not a finite-time jump value at either endpoint. If one separately uses $X_{\infty }$ for the limiting state, that limit is the same endpoint.

The embedded jump chain in the interior is a simple symmetric random walk on $\{0,\dots ,N\}$, stopped at the endpoints. From any interior state it has probability at least $2^{-N}$ of hitting a boundary in the next $N$ jumps, by following successive leftward choices. Thus its number of jumps before absorption is finite almost surely. Each of this finite number of holding times is finite almost surely, so absorption also occurs in finite continuous time. The finite set of positive interior rates causes no explosion; in particular their maximum bounds the total jump rate. When $N=1$, the chain starts at an already absorbing endpoint.

The rates alter the clock but not the sequence of visited states. The gambler's ruin calculation from part (a), translated to an initial state $i$ between endpoints $0,N$, therefore givesThis includes probability one at zero and probability zero at $N$.

Use the positive-integer convention for the geometric distribution:Conditional on $K=k$, independence gives $\mathbb{E}[S\mid K=k]=k/\lambda$. Taking expectations givesThis is the convention required below because a chain starting at $i$ makes at least one visit to $i$. If instead $K$ counts failures on $\{0,1,\dots \}$, its mean is $(1-p)/p$, and the corresponding answer for that different random sum is $(1-p)/(p\lambda )$.

For the chain of part (b), let $K_i$ count visits to $i$, including the initial visit, before absorption. After a departure to $i-1$, gambler's ruin on $\{0,\dots ,i\}$ gives probability $1/i$ of reaching zero before returning to $i$. After a departure to $i+1$, the analogous probability of reaching $N$ before returning is $1/(N-i)$. The departure is equally likely in either direction, so the probability of absorption before a return isAt every return to $i$, the Strong Markov property resets these alternatives. Hence the geometric return count before absorption gives $K_i\sim \mathrm{Geom}(p_i)$ on positive integers. One may construct the chain from its embedded jump chain and a separate sequence of fresh independent exponential clocks. Then its successive holding times at $i$ are independent and identically distributed rate-${\lambda }_i$ exponential random variables, independently of $K_i$, andUsing the first calculation gives the occupation time at an interior state of a variable-rate symmetric walk:For $N=2,i=1$, $p_i=1$ and the only visit is the initial one; the degenerate positive-integer geometric distribution at one handles this case. Other states' rates affect the time of each excursion, but not its probability of return, which explains why only ${\lambda }_i$ appears in this expectation.

From the masses of the Poisson distribution, its probability generating function isAt $z=0$, the term $z^0$ is interpreted as one, so this also gives $\mathbb{P}(Z=0)=e^{-\lambda }$.

One constructive definition of a rate-$\lambda$ Poisson process uses independent and identically distributed exponential random variables $E_j$ of rate $\lambda$. Set $T_0=0$, $T_k={\sum }_{j=1}^k{E}_j$ andThe strong law of large numbers gives $T_k/k\to 1/\lambda$ almost surely, so the maximum is finite at every finite $t$. The process starts at zero, has right-continuous nondecreasing integer paths, and jumps by one at the arrival times.

For $k\ge 1$, exactly $k$ arrivals by $t$ means $T_k\le t<T_{k+1}$. Integrating the first $k$ exponential gaps and the survival probability of the next gap givesThe last factor is the volume of the $k$-dimensional simplex, obtained for example by iterated integration. For $k=0$, directly $\mathbb{P}(N_t=0)=\mathbb{P}(E_1>t)=e^{-\lambda t}$. ThusAt a fixed time $s$, conditional on the counting history, the residual time until the next arrival has rate-$\lambda$ exponential distribution, independently of that history, by the memoryless property. After that arrival all subsequent gaps are fresh independent exponentials. Thus the process of future counts $N_{s+u}-N_s$ has the same law as $N_u$ and is independent of the past. This proves stationary independent increments, the equivalent usual defining properties of the Poisson process, and gives

Conditional on $Z=k$, the summands are independent with the common Laplace transform of a nonnegative random variable $\varphi (q)$. The empty sum for $k=0$ is zero. Therefore the compound Poisson distribution hasand applying the probability generating function from part (a) givesIf $m=\mathbb{E}{X}_1<\infty$, differentiating at zero from the right gives ${\varphi }^{\prime }(0+)=-m$ and $L_Y^{\prime }(0+)=-\lambda m$. HenceThe differentiation is justified by $(1-e^{-q{X}_1})/q\le X_1$ and the dominated convergence theorem. No finite moment was assumed in the question, so the formula must also be interpreted when $m=\infty$. For any nonnegative random variable $V$, the monotone convergence theorem givesApply this to $X_1$ and $Y$, and use $1-e^{-\lambda h}\sim \lambda h$ as $h\downarrow 0$, with $h=1-\varphi (q)$; it yields the same formula with value $+\infty$ when $m=\infty$. If $m=0$, nonnegativity makes all marks zero almost surely and the result is immediate.

For the second method, condition on the count rather than differentiating a transform. For finite $m$, the tower property of conditional expectation gives $\mathbb{E}[Y\mid Z]=Zm$, and $\mathbb{E}Z=\lambda$ gives $\mathbb{E}Y=\lambda m$. More generally, Tonelli's theorem and independence giveFor $m=\infty$, already the term $j=1$ is infinite since $\mathbb{P}(Z\ge 1)>0$. Thus the two methods agree, including in the extended-valued case.

As in the intended independent-mark construction, take the entire sequence $(X_j)$ independent of the Poisson process, not merely independent of one fixed count. Then $Y$ is a Compound Poisson process. For deterministic $s<t$, its increment $Y_t-Y_s$ is independent of ${\mathcal{F}}_s=\sigma (Y_u:0\le u\le s)$. To justify this carefully, first condition on $N_s=k$. The past of $Y$ uses only the counting history up to $s$ and marks among $X_1,\dots ,X_k$. The future count has independent rate-$\lambda$ Poisson process increments, and future marks $X_{k+1},X_{k+2},\dots$ are fresh with the common law. Their joint conditional law is the same for every $k$ and every past history, so the increment is independent even of this larger marked history, hence of ${\mathcal{F}}_s$. Marks equal to zero do not cause a problem: ${\mathcal{F}}_s$ may then reveal less than the full counting history.

By part (b), with Poisson parameter $\lambda (t-s)$,The proposed process is adapted to ${\mathcal{F}}_t$, nonnegative, andIn particular, no finite expectation of a mark is required. Also $Z_s>0$, andis independent of ${\mathcal{F}}_s$ and has mean one. Therefore the exponential Laplace martingale of a compound Poisson process satisfiesThis proves every condition for a continuous-time martingale in the requested filtration. When $q=0$, $\varphi (0)=1$ and the same conclusion reduces to the constant martingale $Z_t=1$.