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.



\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 '18 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 '18 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 '18 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 '18 at 20:57
  • $\begingroup$ Right. But what happens when you do the proof itself as you suggested in your original post? $\endgroup$ Mar 2 '18 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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