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

By linearity of expectation and independence,For $\sigma >0$, apply Chebyshev's inequality at threshold $h\sigma$ and take the complementary event:If $\sigma =0$, every $X_i=\mu$ almost surely, so $W=\mu$ almost surely and the bound holds directly. This handles the zero-threshold case without applying Chebyshev's inequality at an inadmissible threshold.

Let $X_i$ be the head indicator random variable for toss $i$. These are independent and identically distributed random variables with a Bernoulli distribution of parameter $1/2$, so $\mu =1/2$, $\sigma =1/2$, and $W=N/n$. Taking $h=1/5$ makes $h\sigma =1/10$. The preceding Chebyshev's inequality bound givesThe endpoints are included because this event is exactly $|W-1/2|\le 1/10$.