Let $X$ denote number of success in $n$ independent Bernoulli trials with probability of success $p$ in each trial. Show that, $$\mathbb{P}[X\ge r] \le \frac{r(1-p)}{(r-np)^2}, \quad if \quad r>np$$.

Comments- It looks like a standard problem, but I don't have enough ideas on how to proceed after opening the probability expression as sum of different combinations.


1 Answer 1



\begin{align} P(X \ge r) &= P(X- np \ge r-np) \\ &\le P(|X-np| \ge r-np) \\ \end{align}

  • Try to use a famous inequality. Notice that there is a square in the upperbound, it should suggest an appropriate inequality to use.
  • Also, note that $r > np$.
  • $\begingroup$ I wonder if this trick works for a similar upper bound of $P(X\le r)$, namely $\frac{(n-r)p}{(np-k)^2}$ when $r<np$. $\endgroup$ Mar 2, 2018 at 19:56
  • $\begingroup$ Let $Y$ be $X+Y=n$, then $P( X \le r) = P(Y \ge n-r)$ then we can apply the result. $\endgroup$ Mar 2, 2018 at 20:10
  • $\begingroup$ Indeed, yes. But if I work out $P(Y \ge n-r)$ from scratch as you hinted in the original post, I end up with $P(Y \ge n-r)<\frac{npq}{(np-k)^2}$ when $np>k$. That is, by using Chebyshev's inequality. $\endgroup$ Mar 2, 2018 at 20:50
  • $\begingroup$ $Y \sim Bin(n, 1-p)$, so I shall just replace $r$ with $n-r$ and $p$ with $1-p$ right? $\endgroup$ Mar 2, 2018 at 20:57
  • $\begingroup$ Right. But what happens when you do the proof itself as you suggested in your original post? $\endgroup$ Mar 2, 2018 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.