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

Markov's inequality: if $X\ge 0$ and $a>0$, then $\mathbb{P}(X\ge a)\le \mathbb{E}[X]/a$. Pointwise,Taking expected values, using their monotonicity and the identity $\mathbb{E}[1_E]=\mathbb{P}(E)$, gives $\mathbb{E}[X]\ge a\mathbb{P}(X\ge a)$. Division by the positive threshold proves the inequality. If the expectation is infinite, the extended-valued bound remains true but uninformative.

**Chebyshev's inequality: if $X$ has finite mean $\mu$ and variance ${\sigma }^2$, then for $a>0$,Apply Markov's inequality to the nonnegative random variable $Y=(X-\mu {)}^2$ with threshold $a^2$. Since $\mathbb{E}[Y]={\sigma }^2$ and $\{|X-\mu |\ge a\}=\{Y\ge a^2\}$, the desired statement follows immediately.

By linearity of expectation, $\mathbb{E}[Z]={\sum }_i\mathbb{E}[X_i]=0$. Expanding the square and again using linearity of expectation givesHere the zero means imply $\mathbb{E}[X_i^2]={\sigma }_i^2$ and $\mathbb{E}[X_i{X}_j]=\mathrm{Cov}(X_i,X_j)$. The covariance expansion itself does not require independence. Under the additional independence stated here, $\mathbb{E}[X_i{X}_j]=\mathbb{E}[X_i]\mathbb{E}[X_j]=0$, so it simplifies further to $\mathrm{Var}(Z)={\sum }_i{\sigma }_i^2$.

Write the card values as $a_1,\dots ,a_{1000}$. Uniform selection givesThus $\mathbb{E}[X]=0$ and $\mathrm{Var}(X)=1$, by the variance identity $\mathrm{Var}(X)=\mathbb{E}[X^2]-\mathbb{E}[X{]}^2$.

Every particular card is second with probabilityHence $X$ and $Y$ have the same distribution, with means zero and variances one. They are not independent, since a card cannot be drawn twice.

Every ordered pair of distinct cards has probability $1/(1000\cdot 999)$. ThereforeThis negative covariance is the effect of sampling without replacement, not a contradiction of their identical marginals.

Represent the removed half as the first $m=500$ cards in a uniformly random ordering. Every unordered half is then equally likely. Let $X_1,\dots ,X_{500}$ be their values. Each has mean zero and variance one, and every distinct pair has covariance $-1/999$ by the same ordered-pair argument as in (ii).

The general covariance expansion from (b), applied without imposing independence, givesThis is the finite population correction for a half-sample; treating the draws as independent would give the wrong variance.

Finally $\{Z\ge 50\}\subseteq \{|Z|\ge 50\}$, so Chebyshev's inequality yieldsThe cards returned before this sampling step restore the original population; no conditioning on the earlier two observed values is imposed.