Past exam of the probability course of the University of Oxford / 2014 (A8, 4327)

Original solutions to the 24 June 2014 Probability examination. Source: the released Mathematics archive, member FOI-20210708-1 - Data/4327.pdf. All three questions and their nineteen terminal parts are covered.

Convergence in distribution means that the cumulative distribution functions satisfyat every $x$ where the cumulative distribution function of $X$ is continuous. Values at its discontinuities need not converge. This definition uses only the probability distributions, so the random variables need not be defined on the same probability space.

Let $\mu =\mathbb{E}[X_1]$ and ${\sigma }^2=\mathrm{Var}(X_1)\in (0,\infty )$. For independent and identically distributed random variables, the central limit theorem statesThe limit is the standard normal distribution. If the variance is zero, then $X_i=\mu$ almost surely; the centered sums are zero, and division by $\sigma$ is not defined.

The implication convergence in probability implies convergence in distribution follows by comparing nearby events. Fix a continuity point $x$ of the cumulative distribution function $F_X$ and let $\epsilon >0$. If $X\le x-\epsilon$ and $|X_n-X|\le \epsilon$, then $X_n\le x$. Conversely, $X_n\le x$ and $|X_n-X|\le \epsilon$ imply $X\le x+\epsilon$. ThusThe error probability tends to zero by convergence in probability. Taking lower and upper limits and then letting $\epsilon \downarrow 0$, continuity at $x$ squeezes both bounds to $F_X(x)$. This is exactly convergence in distribution.

Subtract adjacent values of the cumulative distribution function. Its value at zero is zero, so the same calculation applies also to $k=1$:The probability mass function sums to one by a telescoping series.

For $x>0$, the event $M_n/n\le x$ says that each of the independent random variables is at most $\lfloor nx\rfloor$. Hence, for all sufficiently large $n$,Since $n/(\lfloor nx\rfloor +1)\to 1/x$ and $\log (1-u)=-u+o(u)$ as $u\to 0$, taking logarithms gives the limit $e^{-1/x}$. For $x\le 0$ the probability is zero. ThereforeThis is the Fréchet limit for a reciprocal integer tail, with a Fréchet distribution of shape one. Its cumulative distribution function is continuous even at zero, so the pointwise calculation establishes convergence in distribution.

Write $S_{n+1}=S_n+X_{n+1}$. The new random variable $X_{n+1}$ is independent of the entire history generated by $X_1,\dots ,X_n$, hence of $(S_1,\dots ,S_n)$. This is a Markov chain obtained from independent innovations: conditional on the past, only the current sum enters the next state. Its time-homogeneous transition probabilities areEvery jump is a positive integer, and each row sums to one by the probability mass function from part (b).

Now $M_{n+1}=\max (M_n,X_{n+1})$. Again $X_{n+1}$ is independent of the whole previous history, so the recursion is a Markov chain obtained from independent innovations. To remain at $s$, the new observation must be at most $s$; to jump to $t>s$, it must equal $t$. Thus the transition probabilities areThe upper tail sums to $1/(s+1)$, complementing the holding probability $s/(s+1)$.

Integrating $e^{tx}$ against the Gamma density gives the moment-generating function of a gamma distribution:The change of variables $y=(\lambda -t)x$ reduces the integral to $\Gamma (r)=(r-1)!$ using the gamma function. For $t\ge \lambda$ the defining integral is infinite. In particular the moment-generating function is finite on a neighbourhood of zero.

Independence makes the moment-generating function of the sum the product of the two moment-generating functions. For $t<\lambda$,The expectations are finite on, for example, $(-\lambda /2,\lambda /2)$, as is the moment-generating function of the candidate Gamma distribution. The uniqueness theorem for moment-generating functions therefore applies, provingThis is additivity of independent gamma distributions with a common rate; a common rate is essential to this specific formula.

An exponential distribution of rate $\lambda$ is a Gamma distribution with shape one. Repeated additivity of independent gamma distributions with a common rate therefore givesWith integer shape this is also called an Erlang distribution.

The Poisson interarrival times of a homogeneous Poisson process are independent and identically distributed with the exponential distribution of rate $\lambda$. Consequently $Y_1,Y_2$ are independent random variables and their joint probability density isHere $Y_2$ is the second interarrival duration, rather than the time of the second arrival.

The inverse change of variables is $y_1=uv$, $y_2=(1-u)v$, on $0<u<1$, $v>0$. Its absolute Jacobian determinant isThe change of variables for probability densities therefore givesThis factorizes on a product domain into a unit uniform density in $u$ and a shape-two Gamma density in $v$. Thus $U$ and $V$ are independent, with $U\sim \mathrm{Uniform}(0,1)$ and $V\sim \mathrm{Gamma}(2,\lambda )$. This is the shape-$(1,1)$ case of beta-gamma independence.

By part (c) with $\lambda =1$, let $T_n=E_1+\cdots +E_n\sim \mathrm{Gamma}(n,1)$ for independent and identically distributed exponential random variables. The requested integral is $\mathbb{P}(T_n\le n)$. Each summand has expectation one and variance one, so the central limit theorem givesZero is a continuity point of the standard normal distribution, and consequently

Write the stationary distribution as a row vector $\pi =(a,b,c,d)$. For the first transition matrix, $\pi P=\pi$ gives $a=a/2+d$, $b=a/2+b/2$, $c=b/2$ and $d=c$. Hence $b=a$ and $c=d=a/2$. Normalization yieldsBy the stated common-stationary distribution property, this is also the answer for the second transition matrix.

The first Markov chain is a finite irreducible Markov chain: its positive-probability directed cycle reaches all four states. The self-loop at state 1 makes it an aperiodic Markov chain. Convergence to an invariant distribution therefore givesThe second chain alternates between the sets $\{1,3\}$ and $\{2,4\}$. It is a periodic Markov chain with period two, so $p_{11}^{(2m+1)}=0$. From either state 2 or state 4 the next-step probability of entering state 1 is $2/3$. Therefore $p_{11}^{(2m)}=2/3$ for every $m\ge 1$. The subsequences have different limits, so the second return-probability sequence does not converge.

Start the Markov chain at a state $i$ and define the strictly positive first return time $T_i^{+}=\inf \{n\ge 1:X_n=i\}$. A recurrent state satisfies ${\mathbb{P}}_i(T_i^{+}<\infty )=1$; a transient state has this probability strictly below one. Equivalently a recurrent state is visited infinitely often almost surely when started there, whereas a transient state receives finitely many visits almost surely. The recurrence criterion by return probabilities gives the equivalent testStates in a communicating class share this classification. In an irreducible Markov chain all states communicate, so the chain is called a recurrent Markov chain if all its states are recurrent and a transient Markov chain if all are transient.

Represent the simple random walk by $X_n={\xi }_1+\cdots +{\xi }_n$, where the increments are independent and identically distributed and satisfy $\mathbb{P}({\xi }_k=1)=p$, $\mathbb{P}({\xi }_k=-1)=1-p$. They are integrable and have expectation $2p-1$, so the strong law of large numbers givesIf $p\ne 1/2$, this nonzero drift implies that $X_n$ eventually leaves every fixed finite interval and tends to the appropriate infinity. Hence it visits zero only finitely many times almost surely, so zero is a transient state. By translation of the starting state, every state is transient: the chain is transient for $p\ne 1/2$. This also covers the deterministic endpoint cases $p=0,1$, without assuming Markov chain irreducibility at those endpoints.

For the symmetric simple random walk on the integer line, odd return times are impossible. A return after $2m$ steps requires exactly $m$ positive increments, soby Stirling's approximation. The resulting sum diverges by the p-series criterion. The recurrence criterion by return probabilities therefore makes zero a recurrent state. The simple random walk is an irreducible Markov chain on $\mathbb{Z}$, so the symmetric chain is recurrent.

This is the synchronous product of simple symmetric random walks, rather than a walk that changes only one coordinate at a time. Independence of the three coordinate processes givesOdd-time return probabilities vanish. The p-series with exponent $3/2$ converges, so the sum of all return probabilities is finite. By the recurrence criterion by return probabilities, the origin is a transient state: the three-dimensional process is transient. From the origin its communicating class consists of integer triples whose coordinates have the same parity; translation gives the same classification for every other class.