Past exam of the probability course of the University of Oxford / 2017 (A13764W1, A8)

Source paper: released examination archive, member 2016/T/a13764w1.pdf. The printed cover dates this examination to 15 June 2017.

By independence of random variables, the joint probability density is the product of the two probability density functions of the rate-one exponential distributions:Its values on the boundary are immaterial, because the boundary has zero area.

Use the inverse change of variables for probability densitiesIts absolute Jacobian determinant isThereforeSince ${\int }_0^{\infty }w{e}^{-w}dw=1$, its marginal densities are $f_V(v)=1_{(0,1)}(v)$ and $f_W(w)=w{e}^{-w}{1}_{(0,\infty )}(w)$. The joint density factorizes as $f_V{f}_W$, so $V$ and $W$ are independent random variables, with $V$ uniform on $[0,1]$ and $W\sim \mathrm{Gamma}(2,1)$ in the shape-rate convention. This is beta-gamma independence with both shape parameters equal to one.

Put $W=X+Y$. The independent pair $(U,W)$ has the same joint distribution as $(V,W)$ from part (ii), because both first coordinates are uniform and independent of the same sum law. HenceConsequentlyThe rate is one. This multiplication identity is the mechanism behind the exponential invariant law of a random affine recursion.

The answer isIt holds initially by construction. If it holds at step $n-1$, then $X_{n-1}$ is a function of $E_0,\dots ,E_{n-1},U_1,\dots ,U_{n-1}$, so it is independent of the fresh inputs $E_n,U_n$. Part (a)(iii) therefore gives $U_n(X_{n-1}+E_n)\sim \mathrm{Exp}(1)$. This completes the mathematical induction and identifies the stationary distribution of the recursion.

The two recursions use a synchronous coupling: they receive exactly the same fresh inputs. Subtraction cancels the additive term:The variable $U_n$ is independent of the preceding difference and has expected value $1/2$. Thus expectation of a product of independent random variables givesBy Markov's inequality, for every $\epsilon >0$,This proves the requested convergence in probability; in fact the difference has L1 convergence. It is synchronous contraction of a random affine recursion, and the estimate holds for every real $c$.

Every $X_n$ has the same exponential distribution, so $X_n\stackrel{d}{\to }X$ for $X\sim \mathrm{Exp}(1)$. Part (ii) gives $Z_n-X_n\stackrel{p}{\to }0$. Applying Slutsky's theorem to $Z_n=X_n+(Z_n-X_n)$ yieldsThe limiting probability distribution does not depend on $c$. This is precisely the attraction to the exponential invariant law of a random affine recursion.

The update defines a time-homogeneous Markov process: given its present value, the next value depends only on independent fresh input. Part (b)(i) identifies an invariant law: initializing with the rate-one exponential distribution preserves that distribution at every time. Part (b)(iii) shows convergence of the one-time laws to this invariant law from every deterministic initial value.

For a countable state space, the analogous countable-state Markov chain convergence theorem says that an irreducible Markov chain that is aperiodic and positive recurrent converges to its unique stationary distribution from every initial state. Here the state space is continuous, so that countable-state theorem does not directly supply the proof; the explicit coupling does. The two conclusions have the same equilibrium interpretation.

The moment-generating function of a real random variable $X$ isfor real $t$ where the expectation is finite. One may regard it as an extended nonnegative function elsewhere. In particular $M_X(0)=1$; finiteness on a neighborhood of zero is the usual hypothesis for recovering moments and using its local expansion.

Differentiating the moment-generating function at zero givesThe second derivative is the second raw moment, so the variance is $M_X^{\prime \prime }(0)-(M_X^{\prime }(0){)}^2$. The assumed exponential integrability justifies these derivatives.

Integrate against the standard normal density by completing the square:Thus the moment-generating function of a standard normal variable is

Let $Y_1,Y_2,\dots$ be real independent and identically distributed random variables with finite expected value $\mu$ and variance $0<{\sigma }^2<\infty$. The central limit theorem statesEquivalently, the cumulative distribution functions of these normalized sums converge at every real point to the standard normal distribution function. The theorem itself does not require a finite moment-generating function.

The given expected value and variance imply $M_X(0)=1$, $M_X^{\prime }(0)=0$ and $M_X^{\prime \prime }(0)=1$. The Taylor expansion therefore givesSince $\log (1+u)=u+o(u)$ as $u\to 0$, it follows thatThis is the quadratic expansion of a cumulant-generating function for a centered variable of variance one.

Write $S_n=n^{-1/2}{\sum }_{k=1}^n{X}_k$. By independence of random variables, its moment-generating function isFor each fixed real $t$, the expansion in part (i) yieldsFor $t=0$ the equality is immediate. Exponentiation gives $M_{S_n}(t)\to e^{t^2/2}$, the moment-generating function of a standard normal variable. The functions are finite on a common neighborhood of zero, so the convergence theorem for moment-generating functions provesThis proves the central limit theorem under the exponential-moment hypothesis of this part.

Use the deterministic weights $a_{n,k}=\sqrt{k}/n$. Their squared sum and maximum areTo apply the quadratic expansion of a cumulant-generating function rigorously, write $\log M_X(u)=u^2/2+r(u)$, with $r(u)=o(u^2)$. Fix $t\ne 0$ and letAll arguments $t\sqrt{k}/n$ lie in this shrinking interval. ConsequentlyTaking logs of the moment-generating function and using independence of random variables now givesThe case $t=0$ is immediate. Since $e^{t^2/4}$ is the moment-generating function of a normal distribution of variance $1/2$, the convergence theorem for moment-generating functions givesThis is a weighted central limit theorem with negligible maximum weight. Its limit variance also agrees with the exact value $\mathrm{Var}(T_n)=(n+1)/(2n)$ from variance additivity for independent random variables.

A transition matrix $P$ defines an irreducible Markov chain if every state is accessible from every other state:Equivalently, all states belong to one communicating class. When $i\ne j$, a positive number of steps is necessarily used.

A stationary distribution is a nonnegative row vector $\pi =({\pi }_i{)}_{i\in S}$ with total mass one that is preserved by one transition:In matrix notation, $\pi P=\pi$. If the initial state has distribution $\pi$, so does the state at each later time.

For an irreducible Markov chain on a countable state space, the set has either zero or one element. By uniqueness of stationary distributions for an irreducible countable chain, a stationary probability distribution exists exactly in the positive recurrent case, and thenfor the first return time $T_i^{+}$. The right-hand side fixes every entry, proving uniqueness.

For a finite state space, existence is guaranteed, so there is exactly one. A countably infinite state space can have none: the simple symmetric random walk on the integers is irreducible and null recurrent. Periodicity does not affect this existence-and-uniqueness statement.

The difference process $D_n$ is a Markov chain. If the columns are equal, the next block creates a height difference of one. If the difference is $k\ge 1$, landing in the taller column increases it to $k+1$, while landing in the shorter column makes it zero. Therefore its only nonzero transition probabilities areThese probabilities depend only on the present difference, not on the absolute heights or their history. This is the reset-or-increment Markov chain with $p=1/2$.

For its stationary distribution, the incoming-flow equations give ${\pi }_1={\pi }_0$ and ${\pi }_k={\pi }_{k-1}/2$ for $k\ge 2$. Normalization uses a geometric series:ThusThe remaining balance equation is also satisfied: the flow into zero is $(1-{\pi }_0)/2=1/3$. Every state can reach zero and every positive state can be reached from zero, so it is an irreducible Markov chain. Its invariant probability distribution makes it positive recurrent, and that distribution is unique.

The maximum-height process $H_n$ is not Markov. Starting empty, condition first on the positive-probability history $(H_1,H_2,H_3)=(1,1,2)$. After two blocks the columns were equal, so after three their difference is one. Hence $\mathbb{P}(H_4=3\mid H_1=1,H_2=1,H_3=2)=1/2$.

For the history $(1,2,2)$, the first two blocks built one column and the third caught the other column up, leaving equal heights. Hence $\mathbb{P}(H_4=3\mid H_1=1,H_2=2,H_3=2)=1$. Both histories have the same time and present height $H_3=2$, but different predictions. This violates the Markov property and illustrates why a function of a Markov chain need not be Markov.

The precise conclusion isTo prove it, observe that the maximum rises exactly when the new height difference is positive:A block landing in a shorter column produces $D_m=0$ and no rise; every other case raises the maximum and leaves $D_m>0$. Starting from $H_0=0$, telescoping givesThe difference chain is irreducible and positive recurrent by part (i). Apply the countable-state Markov chain ergodic theorem to the bounded indicator function $g(k)=1_{\{k>0\}}$. Its stationary mean is ${\sum }_{k\ge 1}{\pi }_k=1-{\pi }_0=2/3$, giving the asserted almost sure convergence. No aperiodicity assumption is needed for this time average. This establishes the growth rate of two-column sticky deposition.