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

The $X_i$ are independent Bernoulli random variables with success parameter $p$. Their sum has the binomial distribution $S_n\sim \mathrm{Bin}(n,p)$, whose probability mass function isChoose the $k$ successful events in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways; independence gives the same product probability for each choice. At $p=0$ or $p=1$, interpret the formula by its degenerate distribution or by continuity.

An indicator random variable equals $1$ with probability $p$ and $0$ with probability $1-p$, so $\mathbb{E}(X_i)=1\cdot p+0\cdot (1-p)=p$. Also $X_i^2=X_i$ pointwise, whence

By linearity of expectation, $\mathbb{E}(S_n)={\sum }_{i=1}^{n}p=np$. Part (ii) gives $\mathrm{Var}(X_i)=\mathbb{E}(X_i^2)-[\mathbb{E}(X_i){]}^2=p-p^2$. Independent random variables have zero pairwise covariance, so the variance of their sum is the sum of their variances. Therefore

For $0<p<1$, independence of the remaining indicators givesBecause $0<k<n$, the latter probability is positive for interior $p$. The two events are independent events exactly when their joint probability equals $p\mathbb{P}(S_n=k)$, which is equivalent to $p=k/n$.

At $p=0$ or $p=1$, the event $\{S_n=k\}$ is null, and a null event is independent of every event. Therefore the full answer, including the degenerate endpoints, is

Summing the probability mass function of the binomial distribution up to the largest permitted integer givesThe floor is implicit in the original integer-indexed sum.

The weak law of large numbers gives $S_n/n\to p$ in probability. If $\alpha <p$, the event $S_n/n\le \alpha$ implies $|S_n/n-p|\ge p-\alpha$, whose probability tends to zero. If $\alpha >p$, its complement $S_n/n>\alpha$ implies $|S_n/n-p|>\alpha -p$, whose probability also tends to zero. ThusFor an explicit independent bound, Chebyshev's inequality bounds either unwanted probability by $p(1-p)/[n(\alpha -p{)}^2]$. The boundary $\alpha =p$ is outside the two requested cases and is not decided by the weak law of large numbers alone.