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

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$.

Given $X_n=k>0$, the number remaining next time is uniform on $\{0,\dots ,k-1\}$ and is independent of earlier choices; given $X_n=0$, the next state is $0$. Thus the conditional law of $X_{n+1}$ depends only on $X_n$, which is the Markov property.

By contrast, observing only the last number removed generally loses information about the remaining stock. For $N\ge 3$, compare the two positive-probability historiesBoth have $Y_2=1$, but the first leaves $N-2>0$ stickers, so $P(Y_3>0\mid Y_1=1,Y_2=1)=1$, whereas the second leaves none, so $P(Y_3>0\mid Y_1=N-1,Y_2=1)=0$. Hence $(Y_n)$ fails the Markov property.

The qualification $N\ge 3$ is necessary if a Markov chain is allowed to have time-dependent transitions. For $N=1$, the removal sequence is the deterministic, time-homogeneous Markov chain $1,0,0,\dots$. For $N=2$, it is a time-inhomogeneous Markov chain, although it is not time-homogeneous on its observed removal states: a removal of $1$ at the first step forces another removal of $1$, whereas a removal of $1$ at the second step forces $0$ next. The blanket non-Markov claim should therefore be understood in the generic, nondegenerate setting.

The state space is $\{0,1,\dots ,N\}$, with initial state $X_1=N$. With rows indexed by the current state and columns by the next state, the transition matrix isThe state strictly decreases at each step until absorption at $0$.

For a Markov chain started at state $i$, let ${\tau }_i^{+}=\inf \{n\ge 1:X_n=i\}$ denote the first positive return time, using time $0$ for the starting state. A recurrent state has $P_i({\tau }_i^{+}<\infty )=1$; a transient state has return probability strictly less than $1$. An absorbing state satisfies $P_{ii}=1$, so the chain remains there forever after arrival and it is necessarily a recurrent state.

State $0$ is an absorbing state and a recurrent state. From every positive state, the stock decreases strictly at the next step and can never increase, so a return to that positive state is impossible. Thus all positive states are transient, with return probability zero. Starting from $N$, absorption occurs within at most $N$ sticker-taking children.

Let $e_k$ be the expected number of children receiving a sticker when $k$ remain. A first-step decomposition givesSubtracting the equations for $k{e}_k$ and $(k-1)e_{k-1}$ gives $e_k-e_{k-1}=1/k$. Hence $e_k=H_k$, the $k$th harmonic number. In particularEvery visit before absorption counts exactly one child who receives at least one sticker.

The same first-step argument applies to the uniform depletion Markov chain at every initial stock size.

After the first child, $X_2$ is uniform on $\{0,\dots ,N-1\}$. Conditional on $X_2=k\ge 1$, the mean number removed is $(k+1)/2$; conditional on $X_2=0$, it is zero. The law of total expectation therefore givesFor $N=1$, the sum is empty and the same formula gives zero.

Use the state space $\{1,\dots ,N\}$, since an empty box is refilled immediately. The probability that formerly led from $i$ to $0$ now leads to $N$. Thus the transition matrix isFor $i=N$, the second line includes the self-loop obtained when all stickers are taken. When $N=1$, this is simply the one-state Markov chain.

Let $Q=H_N$ and defineThe probabilities sum to $Q^{-1}(1+{\sum }_{k=1}^{N-1}(k+1{)}^{-1})=1$. For $k<N$, the incoming probability isusing a telescoping sum. Similarly,Thus $\pi$ is a stationary distribution. Every state can reach $N$ in one step, and $N$ can reach every lower positive state in one step, so the chain is irreducible. The self-loop at $N$ has probability $1/N>0$, hence the chain is aperiodic. The convergence theorem for a finite irreducible aperiodic Markov chain now givesFor $N=1$, the conclusion follows directly from the single absorbing/refilled state.

This is the limiting law of the uniform depletion and refill Markov chain.