# Quick ways for approximating $\sum_{k=a_1}^{k=a_2}C_{100}^k(\frac{1}{2})^k(\frac{1}{2})^{100-k}$?

Consider the following problem:

A fair coin is to be tossed 100 times, with each toss resulting in a head or a tail. Let $$H:=\textrm{the total number of heads}$$ and $$T:=\textrm{the total number of tails},$$ which of the following events has the greatest probability?

A. $H=50$

B. $T\geq 60$

C. $51\leq H\leq 55$

D. $H\geq 48$ and $T\geq 48$

E. $H\leq 5$ or $H\geq 95$

What I can think is the direct calculation: $$P(a_1\leq H\leq a_2)=\sum_{k=a_1}^{k=a_2}C_{100}^k(\frac{1}{2})^k(\frac{1}{2})^{100-k}$$

Here is my question:

Is there any quick way to solve this problem except the direct calculation?

-

Here is a very elementary way of estimating these probabilities. Observe that the distribution of $H$ is very similar to a normal distribution with mean $50$ and standard deviation $\sigma = 5$. In particular, we should have

$$P (|H-50| \leq \sigma) \;\approx\; 68\% \qquad\text{and}\qquad P(|H-50| \leq 2\sigma) \;\approx\; 95\%$$

As mixedmath pointed out, the only viable answers are B, D, and E. We can estimate the probabilities of these events as follows:

B. $P(H \geq 60) \;=\; P(H \geq 50 + 2\sigma)$, which should be on the order of 2.5%.

D. $P(48\leq H \leq 52) \;=\; P(|H-50| \leq \sigma/2)$, so this should be something like 40%.

E. $P(H\leq 5\text{ or }H \geq 95) \;=\; P(|H-50| \geq 9\sigma)$, so this should be really small.

Thus (D) is the correct answer.

-
The normal approximation is used here. So one is supposed to have the table of the pdf of normal distribution, right? – Jack Jun 6 '11 at 5:06
@Jack: Everyone in the whole world should memorize the following two facts: (1) a normal distribution is within $\sigma$ of the mean about 68% of the time (2) a normal distribution is within $2\sigma$ of the mean about 95% of the time. All of my calculations here follow from these. – Jim Belk Jun 6 '11 at 9:16
Hmm, I think you are talking about the 68-95-99.7 rule. It's enough to get B and E. But I don't think I can convince myself that I can get D unless I use the picture. – Jack Jun 6 '11 at 14:43
+1 I was going to answer exactly this. – leonbloy Jun 6 '11 at 14:58
@Jack: I agree that getting D also requires knowing what the normal distribution looks like. The 40% isn't very exact: I divided 68% by two and then rounded up a bit. – Jim Belk Jun 6 '11 at 17:15

Chebyshev's inequality, combined with mixedmath's and some other observations, shows that the answer has to be D without doing the direct calculations.

First, rewrite D as $48 \leq H \leq 52$. A is a subset of D, and because the binomial distribution with $n = 100$ and $p = 0.5$ is symmetric about $50$, C is less likely than D. So, as mixedmath notes, A and C can be ruled out.

Now, estimate the probability of D. We have $P(H = 48) = \binom{100}{48} 2^{-100} > 0.07$. Since $H = 48$ and $H=52$ are equally probable and are the least likely outcomes in D, $P(D) > 5(0.07) = 0.35$.

Finally, $\sigma_H = \sqrt{100(0.5)(0.5)} = 5$. So the two-sided version of Chebyshev says that $P(E) \leq \frac{1}{9^2} = \frac{1}{81}$, since E asks for the probability that $H$ takes on a value 9 standard deviations away from the mean. The one-sided version of Chebyshev says that $P(B) \leq \frac{1}{1+2^2} = \frac{1}{5}$, since B asks for the probability that $H$ takes on a value 2 standard deviations smaller than the mean.

So D must be the most probable event.

Added: OP asks for more on why $P(C) < P(D)$. Since the binomial($100,50$) distribution is symmetric about $50$, $P(H = i) > P(H = j)$ when $i$ is closer to $50$ than $j$ is. Thus $$P(C) = P(H = 51) + P(H = 52) + P(H = 53) + P(H = 54) + P(H = 55)$$ $$< P(H = 50) + P(H=51) + P(H = 49) + P(H = 52) + P(H = 48) = P(D),$$ by directly comparing probabilities.

-
Why C is less likely than D? – Jack Jun 6 '11 at 4:05
@Jack: I added to my answer. Does that help? – Mike Spivey Jun 6 '11 at 5:17
Fair enough. Thanks. – Jack Jun 6 '11 at 5:23

Yes. In the following, which uses (almost) nothing beyond what is already in the problem statement, the calculations involve only simple arithmetic with one-digit numbers (and $10$) and easy estimates involving fractions of two-digit numbers: the stuff of mental arithmetic.

Let $P(k)$ represent the probability of $k$ heads. From the (intuitively obvious) facts that (i) $P(k) \gt 0$ for $0 \le k \le 100$, (ii) $P(k)$ increases from $k=0$ to $k=50$ and then decreases from $k=50$ to $k=100$, and (iii) $P(k) = P(100-k)$, we easily establish the inequalities

$$D \gt C, D \gt A, B \gt E.$$

I claim that actually $A \gt B$ (i.e., the chance of exactly 50 heads exceeds the chance of 60 or more tails), which establishes $D$ as the answer. To see this, look at the relative probabilities. They all have a common factor of $100!/2^{100}$ which we can ignore, focusing on the binomial coefficients that are left. Now a series of simple estimates establishes

$$P(40) / P(50) = \frac{50}{60} \frac{49}{59} \cdots \frac{41}{51} \lt \left(\frac{5}{6}\right)^{10} \lt \frac{1}{1 + 10(1/5)} = \frac{1}{3}.$$

(The ratio actually is less than $1/7$.) Moreover,

$$P(39) / P(50) = \frac{40}{61} P(40)/P(50) \lt \frac{2}{3} P(40)/P(50).$$

Continuing in like vein we see that the chance of $A$ relative to that of $B$, $\left(P(0) + P(1) + \cdots + P(40)\right)/P(50)$, is dominated by a geometric series with starting term $P(40)/P(50)$ and common ratio $2/3$. Therefore its sum is less than $1/3 (1 - 2/3)^{-1} = 1.$ This proves the claim.

-
+1: I like this. I don't follow the step $(5/6)^{10} < 1/(1+10(1/5))$, though. Am I missing something obvious? – Mike Spivey Jun 7 '11 at 3:22
@Mike $(6/5)^{10} = (1 + 1/5)^{10} = 1 + 10/5 + |O(1/5^2)| \gt 3$. Take the reciprocal. – whuber Jun 7 '11 at 13:09
Got it. Thanks. – Mike Spivey Jun 7 '11 at 15:31

In short: no. But you can cut a few things out immediately. For example, A is nonsense. A is eaten by C. And C is eaten by D.

So you need only to check B, D, and E. Of course, depending on your intuition, you might have a 'feel' for how unlikely E is as well. But that isn't as certain.

-
Actually, in my intuition D feels less likely than E. – gfes Jun 6 '11 at 1:39
It is perhaps more obvious that A is less than D, since it is a subset. – Henry Jun 6 '11 at 9:41
@gfes: the point is that extremely unbalanced results, as in E, are extremely unlikely. So even though you have 12 choices in E and 5 in D, D will be much more likely. – Ross Millikan Jun 6 '11 at 12:45
I know. Intuition can be a tricky thing in probability. – gfes Jun 6 '11 at 16:13