Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics, and probability / Probability

Assume finite second moments and set $Y_i=X_i-\mathbb{E}{X}_i$. By linearity of expectation, centring $X_1+X_2$ gives $Y_1+Y_2$. Expanding its square and using the definitions of variance and covariance,No independence assumption is required for this variance of a sum identity.

For finite second moments, the variance of a sum is

In the uniform balls-in-bins allocation, each ball enters box 1 independently with probability $1/n$. Thus $M_1$ has the binomial distribution $\mathrm{Bin}(n,1/n)$, with probability mass functionand zero outside that range.

For both boxes to be empty, each ball must avoid two specified boxes. The individual avoidance probability is $(n-2)/n$, and the choices of different balls are independent. ThereforeThis also covers $n=2$, when the answer is zero.

Write $p_n=(1-1/n{)}^n$, the probability that all balls avoid a specified box. Each of the empty-box indicators in uniform allocation is an indicator random variable with success probability $p_n$. Since $I_i^2=I_i$, its expectation and variance are

Let $q_n=(1-2/n{)}^n$. The product of two distinct empty-box indicators in uniform allocation is the indicator random variable of both boxes being empty, so $\mathbb{E}(I_i{I}_j)=q_n$. ThusIndeed $0\le 1-2/n<(1-1/n{)}^2$ for $n\ge 2$, and taking the positive integer power $n$ preserves this strict inequality. This proves the negative covariance directly.

By linearity of expectation, $\mathbb{E}{N}_n=n{p}_n$. The variance of a sum and the negative covariance just proved giveApply Chebyshev's inequality to the empty-box indicators in uniform allocation:This proves the required concentration of the empty-box fraction. Since $p_n\to e^{-1}$, it also yields convergence in probability of $N_n/n$ to $e^{-1}$.

For a nonnegative integer-valued random variable, its probability generating function isThe series converges absolutely at least for $|s|\le 1$, with $0^0=1$ in the $k=0$ term; it may converge on a larger domain.

This is the geometric distribution on $\{0,1,2,\dots \}$ with success parameter $1/2$. Its probability generating function is a geometric series:

The ancestor contributes one individual. Given its offspring count $N$, the descendant family rooted at each child is an independent branching process with the same offspring distribution as the original one. Its total progeny therefore has the same distribution as $Z$. The independent reproduction choices let these descendant total progeny variables be represented by independent copies $Z_1,Z_2,\dots$, independent of $N$. Hence, on this family-tree construction,where the sum is zero when $N=0$.

For $0\le s\le 1$, condition on $N=k$. Independence of the descendant total progeny variables givesincluding the empty product $1$ when $k=0$. Taking expectation over $N$ proves the probability generating function of an independent random sum formulaThe same identity holds for complex $|s|<1$ by absolute convergence.

The extra ancestor multiplies the probability generating function by $s$. The preceding probability generating function of an independent random sum formula therefore yieldsFor $0\le s<1$ the two roots are $1\pm \sqrt{1-s}$. A probability generating function lies in $[0,1]$ there, so the plus root is impossible. Also $Z\ge 1$ gives $G_Z(0)=0$. Consequently the total progeny with critical geometric offspring hasAt $s=1$ the value is $1$, consistent with almost-sure finiteness. For complex $|s|<1$, the same expression uses the analytic square root that equals $1$ at $s=0$.

The cumulative distribution function is $F_X(x)=\mathbb{P}(X\le x)$. In the absolutely continuous setting of a probability density function, the probability density function is a nonnegative integrable function $f_X$ satisfyingThus $\mathbb{P}(a<X\le b)={\int }_a^b{f}_X(t)dt$ and $F_X^{\prime }=f_X$ almost everywhere. A merely continuous cumulative distribution function need not possess a probability density function; the density assumption means absolute continuity.

Every cumulative distribution function is nondecreasing, right-continuous, valued in $[0,1]$, and has limits $0$ at $-\infty$ and $1$ at $+\infty$. For a continuous random variable it is continuous. When a probability density function exists, it is in fact absolutely continuous, with nonnegative derivative almost everywhere.

The proposed cumulative distribution function satisfies $0<F(x)<1$ and is smooth. Its derivative isso it is increasing and continuous, hence right-continuous. As $x\to -\infty$, $e^{-x}\to \infty$ and $F(x)\to 0$; as $x\to \infty$, $e^{-x}\to 0$ and $F(x)\to 1$. Thus it has all the required cumulative distribution function properties, and defines the standard Gumbel distribution.

Because $Z=e^{-Y}>0$, its cumulative distribution function is zero for $z\le 0$. For $z>0$, the transformation is decreasing, and $Y$ has a continuous cumulative distribution function, soThus the exponential transform of a standard Gumbel variable givesThis is the exponential distribution with rate $1$.

Write $M_n={\max }_i{E}_i$. Each exponential distribution has cumulative distribution function $1-e^{-x}$ for $x\ge 0$. Independence therefore gives the maximum of independent exponential random variables formulaFor any fixed $y$, the threshold $y+\ln n$ is nonnegative for all sufficiently large $n$. ThenThis is convergence in distribution to the standard Gumbel distribution.

First $0\le M_n\le {\sum }_i{E}_i$, so linearity of expectation gives $\mathbb{E}{M}_n\le n<\infty$. The tail integral formula for expectation, followed by the finite binomial theorem expansion, givesThe exchange involves only a finite sum. As a useful check, substitution $t=e^{-x}$ rewrites the integral as ${\int }_0^1[1-(1-t{)}^n]/tdt={\sum }_{j=0}^{n-1}{\int }_0^1(1-t{)}^{j}dt={\sum }_{k=1}^{n}1/k$, the harmonic number $H_n$.