Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / M (Probability)

The moment-generating function is $M_X(t)=\mathbb{E}[e^{tX}]$ for real $t$ where this expectation is finite. Usually one requires finiteness on a neighbourhood of zero when using it to characterize a distribution. The characteristic function isIt always exists because the integrand has absolute value one. In both definitions the expectation is taken with respect to the distribution of $X$.

A characteristic function is useful for proving convergence in distribution, including for laws without a finite moment-generating function: the continuity theorem says that pointwise convergence of characteristic functions to a characteristic function continuous at zero implies convergence in distribution to its law. For example, the Cauchy distribution has a characteristic function although its moment-generating function is not finite on any neighbourhood of zero.

A moment-generating function is especially useful for exponential tail bounds: for $t>0$ where it is finite, Markov's inequality givesOptimizing over $t$ yields a Chernoff bound. The positive real exponential in this argument permits the inequality; a unit-modulus complex exponential does not give the corresponding tail bound.

Expand the analytic factor around zero by the binomial series:Every coefficient is nonnegative. Adding $2/3$ to the constant coefficient gives probabilities $p_j$ with sum $g(1)=2/3+1/3=1$. Define $\mathrm{Pr}(T=j)=p_j$ for $j\ge 0$. This is a nonnegative integer-valued random variable and its probability generating function is exactly $g$. The power series has radius $14/5>1$, so the evaluations and derivatives used below are finite.

For a probability generating function, $\mathbb{E}T=g^{\prime }(1)$ and $\mathbb{E}[T(T-1)]=g^{\prime \prime }(1)$. HereThus $\mathbb{E}T=5/54$ and $\mathbb{E}[T(T-1)]=25/324$. Adding the first moment gives $\mathbb{E}{T}^2=55/324$, hence

Markov's inequality states that for a nonnegative random variable $Z$ and $a>0$,It follows immediately from $Z\ge a{1}_{\{Z\ge a\}}$ and monotonicity of expectation. A finite expectation makes the bound informative.

By the definition of the probability generating function,The evaluation at two is valid because two is inside the power-series radius $14/5$.

The event $T\ge 5$ is the same as $2^T\ge 32$. Apply Markov's inequality to the nonnegative random variable $2^T$ and use part (iv):The strict numerical comparison is enough even though the probabilistic inequality itself is non-strict.

At each index the two independent uniform symbols match with probability $p=k/k^2=1/k$. The match indicators are independent across indices. Consequently the waiting times between successive matches are independent geometric random variables on $1,2,\dots$ with success probability $p$, and $S_m$ is their sum.

For one waiting time $G$, summing the geometric series gives $\mathbb{E}{e}^{tG}=p{e}^t/[1-(1-p)e^t]$. Independence yieldsFor $k>1$ the moment-generating function is finite for $t<\log (k/(k-1))$. When $k=1$, every index matches, $S_m=m$ deterministically and the formula reduces to $e^{mt}$ for every real $t$.

For $t\ge 0$, the geometric survival probability givesFor $t<0$, the distribution functions are zero, as is the limiting exponential distribution function. Since that limiting distribution function is continuous everywhere, these limits proveThe parameter is rate one, so the limiting mean is one, consistent with $\mathbb{E}(S_1/k)=1$.

Given $X_n=k$, the next child takes a fresh uniform choice from $1,\dots ,k$, making $X_{n+1}$ uniform on $0,\dots ,k-1$. At zero the count stays zero. This conditional law depends only on the current count, so $X_n$ is a Markov chain.

The amounts taken do not generally retain that state information. For $N\ge 3$, compare two positive-probability histories with the same current value $Y_2=1$: if $Y_1=N-2$, exactly one sticker remains and $Y_3=1$; if $Y_1=N-1$, none remains and $Y_3=0$. Thus the next amount depends on earlier history even after conditioning on the current amount, violating the Markov property.

The non-Markov assertion needs this nondegenerate range of $N$. With $N=1$ the amount process is trivial; for $N=2$ it is also Markov if time-inhomogeneous transitions are permitted. The history counterexample establishes the intended failure for every $N\ge 3$.

The state space is $\{0,1,\dots ,N\}$. In this increasing ordering, the transition matrix is specified byFor each positive $k$, the $k$ possible amounts taken correspond bijectively to the $k$ possible remaining counts. Each positive-state row therefore sums to one.

A state is a recurrent state if the probability of a return at some positive time, starting there, is one. It is a transient state if that return probability is less than one. It is an absorbing state if its one-step probability of remaining there is one. An absorbing state is recurrent, since every subsequent time is a return.

State zero is absorbing and recurrent. Every positive state is transient: after leaving it, the sticker count strictly decreases until reaching zero and can never return to that positive value. In fact absorption occurs after at most $N$ children who take a positive amount. Hence

Let $e_k$ be the expected number of future children receiving stickers from a box containing $k$, with $e_0=0$. Conditioning on the first uniform remainder givesSubtract the corresponding identity for $k-1$ after multiplying each by its denominator. This gives $k{e}_k=k{e}_{k-1}+1$, so $e_k=e_{k-1}+1/k$. Therefore $e_N={\sum }_{j=1}^{N}1/j$, andThe recurrence counts the current positive recipient once and excludes all later children arriving after the box is empty.

The remainder after the first child, $X_2$, is uniform on $0,\dots ,N-1$. Given $X_2=j\ge 1$, the second child takes an average of $(j+1)/2$ stickers; when $j=0$ the amount is zero. Hence, for $N\ge 1$,The expression gives zero for $N=1$, as expected.

Since refilling is immediate, the observed arrival-state space becomes $\{1,\dots ,N\}$. A zero remainder is replaced by $N$, while all positive remainders are unchanged. ThusIn particular state one moves to $N$ with probability one, and state $N$ has a self-loop of probability $1/N$.

Write $Q={\sum }_{m=1}^{N}1/m$ and propose ${\pi }_N=1/Q$, ${\pi }_j=1/((j+1)Q)$ for $j<N$. These probabilities sum to one because $1+{\sum }_{j=1}^{N-1}1/(j+1)=Q$.

For $j<N$, the incoming stationary probability isusing the telescoping identity $1/(k(k+1))=1/k-1/(k+1)$. Similarly ${\sum }_{k=1}^N{\pi }_k/k=1/Q={\pi }_N$. Thus $\pi$ is stationary.

The finite chain is irreducible: every state can reach $N$, and from $N$ every state is reachable in one step. Its self-loop at $N$ makes it aperiodic. The finite-state convergence theorem therefore gives the claimed limit from any initial state:For $N=1$ this is the single absorbing refill state and the same formula gives probability one.