Past exam of the options II course of the University of Oxford / 2011 / M / M4

The moment-generating function is $M_X(t)=\mathbb{E}(e^{tX})$ at real $t$ for which this expectation is finite. The characteristic function isUnlike the moment-generating function, the characteristic function always exists, because $|e^{itX}|=1$.

Use the characteristic function to establish convergence in distribution by the Lévy continuity theorem, especially when exponential moments do not exist; a Cauchy distribution, for example, has a characteristic function but no finite moment-generating function on a neighborhood of zero.

Use the moment-generating function for an exponential-tail estimate: for $t>0$ with $M_X(t)<\infty$, Markov inequality givesOptimizing over $t$ produces a Chernoff bound. The modulus-one characteristic function does not directly give this positive exponential bound.

The binomial series gives, for $|z|<14/5$,All coefficients are nonnegative, and $g(1)=2/3+1/3=1$. Thus defineThese numbers sum to $1$, so they define a probability distribution on the nonnegative integers with the desired probability generating function.

Differentiate the probability generating function:ThereforeUsing the relation between the second factorial moment and variance,

For a nonnegative random variable $Z$ and $u>0$, Markov inequality statesIt follows by taking expectations in $Z\ge u{1}_{\{Z\ge u\}}$. A finite expectation makes the bound informative.

Since $2$ lies inside the radius $14/5$ of the probability generating function, its nonnegative series converges at $2$, and

Apply Markov inequality to the nonnegative random variable $2^T$. On $\{T\ge 5\}$ it is at least $32$, soThis exponential bound is substantially stronger here than applying Markov inequality directly to $T$.

At a fixed index, independence and uniformity giveThe match indicators are independent Bernoulli trials. Thus the waiting times between successive matches are independent geometric variables on $\{1,2,\dots \}$ with success probability $p$. Their moment-generating function isprovided $(1-p)e^t<1$. Since $S_m$ is the sum of $m$ such waiting times,For $k>1$, the finite domain is $t<\log (k/(k-1))$. For $k=1$, every index is a match, so $S_m=m$ deterministically and the moment-generating function is $e^{mt}$ for every real $t$.

For $x\ge 0$, the geometric distribution tail givesFor $x<0$, $P(T_k\le x)=0$. The limiting cumulative distribution function is therefore $0$ for negative $x$ and $1-e^{-x}$ for nonnegative $x$, and it is continuous everywhere. This proveswith rate parameter $1$ and mean $1$.