Estimating the Lower Bound of A Summation Related to Probability

Question

I am working on a probability problem which requires me to find a lower bound of a sum. The sum is $$\sum_{i=n}^{100}{100\choose i}\left(\frac{80}{100}\right)^i\left(\frac{20}{100}\right)^{100-i}\geq 0.9$$

How do I find $n$ here in order to satisfy the inequality? Wolfram Alpha cannot calculate it, but can we perhaps give an estimate?

Answer 1

Use Newton's Binomial Theorem! It says that:

$$(x+y)^k=\sum_{i=0}^k\binom{k}{i}x^iy^{k-i}$$

If $n$ were $0$, using $x=\frac{80}{100}$, $y=\frac{20}{100}$ and $k=100$ we'd have $(x+y)^k=1^{100}=1$, which already satisfies your desired inequality, $\geq 0.9$.

---

With the observation above, your sum may be rewritten as:

$$1-\sum_{i=0}^{n-1}\binom{100}{i}{\left(\frac{80}{100}\right)}^i{\left(\frac{20}{100}\right)}^{100-i}$$

so an equivalent problem is trying to find $n$ for which:

$$\sum_{i=0}^{n-1}\binom{100}{i}{\left(\frac{80}{100}\right)}^i{\left(\frac{20}{100}\right)}^{100-i}\leq 0.1$$

Perhaps this is easier to deal with for computers? An easy algorithm off the top of my head is to keep adding successive terms until the sum is higher than $0.1$, then stop and use the previous value of $n$.

Answer 2

I wrote a Python script to calculate this:

import math def combination(n,m): return math.factorial(n)/math.factorial(m)/math.factorial(n-m) def helper(i): return combination(100,i)*0.8i*0.2(100-i) def cumulative_prob(n): ans = 0 for i in range(n,101): ans += helper(i) return ans

Testing some values out, we see that cumulative_prob(75) = 0.9125 and cumulative_prob(76) = 0.8686.

Answer 3

Let $X \sim \text{Bin}(100, 0.8)$. By the question, $$ \Pr(X \geq n) = \sum_{i=n}^{100} {100 \choose i}0.8^i0.2^{100-i} \geq 0.9 \tag{$\clubsuit$} $$ Put $Y = 100 - X$. Then $$ \Pr(X \geq n) \geq 0.9 \Leftrightarrow \Pr(100 - Y \leq n - 1)\leq 0.1 \Leftrightarrow\Pr(Y \geq 101 - n) \leq 0.1 $$ Because $\mathbb{E}[Y] = 20$ and $Var[Y] = 16$, using one-sided Chebyshev's inequality, we have $$ \Pr(Y \geq 101 - n) = \Pr(Y - 20 \geq 81 - n) \leq \frac{16}{16 + (81 - n)^2} \tag{$\spadesuit$} $$ if $81 - n > 0$. By letting $$ \frac{16}{16 + (81 - n)^2} \leq 0.1 $$ we get $$ n \leq 69 $$ In other words, by letting $n \leq 69$, $(\clubsuit)$ holds. However, note that it is still possible to find some $n > 69$ such that the inequality holds since we use Chebyshev's inequality to upper bound the tail probability, which is not exact. A tighter bound than $(\spadesuit)$ would make $n$ more precise.