Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / B / 6 / a

First take $0<p<1$. For $X\sim \mathrm{Bin}(n,p)$, independence of the Bernoulli trials givesFor $x\ge p$ and $t>0$, Markov inequality yieldsDifferentiate the logarithm of the right-hand side to minimize it. The stationary point satisfieswhich is at least $1$ when $x\ge p$. Substitution givesWhen $x=p$, use the limit $t_{\ast }\to 0$, giving the trivial bound $1$.

For $x\le p$, take $t<0$. On $\{X\le nx\}$ we have $e^{tX}\ge e^{tnx}$, so the same Markov inequality gives the same expression. Its minimizing $t_{\ast }$ is now nonpositive, yielding the stated lower-tail bound. No rounding of $nx$ is needed, because the exponential event inclusion holds for real thresholds. The cases $p=0$ and $p=1$ are deterministic and follow directly, or by the corresponding limits.