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$ – StubbornAtom 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$ – Siong Thye Goh 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$ – StubbornAtom 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$ – Siong Thye Goh 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$ – StubbornAtom 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.