\problemdata                                                             
        {probability-k-events-2} % latex-friendly label for the prob.
        {k-events; coin flipping} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S02 CP9M} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Suppose you repeatedly flip a fair coin (\emph{fair} means that heads and
tails are equally likely to appear).

\begin{problemparts}

\problempart What is the probability that you flip exactly 4 heads out of 8?
between 3 and 5 heads?

\solution{
The probability of exactly 4 heads is about 0.27.
\[
\frac{\binom{8}{4}}{2^8} = \frac{8 \cdot 7 \cdot 6 \cdot 5}{4 \cdot 3
\cdot 2 \cdot 1 \cdot 2 ^ 8} = \frac{35}{128} \approx 0.27.
\]
Similarly, there will be from 3 to 5 heads 60\% of the time:
\[
\frac{\binom{8}{3} + \binom{8}{4} + \binom{8}{5}}{2^8} \approx 0.60.
\]
}

\problempart Suppose you flip a fair coin $n$ times.  What is the probability
that you flip exactly $m$ heads?  Write a formula for the exact answer,
and write a closed-form formula for an approximate answer.

\solution{
The probability of $m$ heads is $\binom{n}{m}/2^n$.  Using Stirling for an
approximation:
\begin{eqnarray}
\binom{n}{m} & \sim &\frac{\sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n}
{\sqrt{2\pi m}\left(\dfrac{m}{e}\right)^m {\sqrt{2\pi
(n-m)}\left(\dfrac{n-m}{e}\right)^{n-m}}} \notag\\
& = & 
\frac{\sqrt{n}\left(\dfrac{n}{e}\right)^m\left(\dfrac{n}{e}\right)^{n-m}}
{\sqrt{2\pi m (n-m)}\left(\dfrac{m}{e}\right)^m
 {\left(\dfrac{n-m}{e}\right)^{n-m}}} \notag\\
& = & \sqrt{\dfrac{n}{2\pi m (n-m)}}\left(\dfrac{n}{m}\right)^m\left(\dfrac{n}{n-m}\right)^{n-m}.\label{stirsimp}
\end{eqnarray}
}

\problempart How would you actually calculate the probability that the number of
heads in 400 flips was between 195 and 205?\dots in 10,000 flips was
between 4980 and 5020?  Could you do it exactly by hand? \dots with a
calculator? with a computer program in some language (what language)?
What about approximately to two decimal places?...six decimal places?
This is intended as a discussion question.  You should be prepared to
defend your conclusions with appropriate technical arguments.

\solution{The numbers are all too large to calculate by hand.  Computing
400!, 190!, and 210!\ exactly will overflow on any calculator, so an exact
computation by calculator would also be impractical.  In fact, it will
cause numerical overflow errors in most programming languages.  Real
Scheme has infinite precision rational arithmetic and can handle 400!, but
\emph{not} 10,000!, so exact computation in the 10,000 case is unlikely to
work in any language: remember the answer will have around 40,000 digits.
(It's conceivable that the Scheme heap size could be set large enough to
hold a hash table with $10,000^2$ entries each of which might be up to
40,000 digits, though this is a stretch.  If so, you could use the Pascal
recursion
\[
\binom{n+1}{m} =  \binom{n}{m-1} + \binom{n}{m} 
\]
in a memoized computation to get an exact answer.)  But there are no
applications that require anywhere near such accuracy.

For the approximate case, we can use Stirliing's approximation for $n!$,
but there are still pitfalls: $(400/e)^{400}$ will overflow floating point
arithmetic on calculators and essentially all computers, so the simplified
version~(\ref{stirsimp}) would be needed.  Since floating point is usually
good for 8 to 10 places on most machines, getting six place accuracy
should be manageable.

In fact there's a rough approximation for the probability that's easy:
setting $m = n/2$ in~(\ref{stirsimp}) yields
\begin{equation}
\binom{n}{n/2} \sim \frac{2^n}{\sqrt{n \pi/2}}\label{n/2simp},
\end{equation}
so
\begin{equation}
\pr{\text{$n/2$ heads in $n$ flips}} =\frac{\dbinom{n}{n/2}}{2^n} \sim
\sqrt{\frac{2}{n \pi}}\label{n/2heads}.
\end{equation}
A calculator will yield the value of the righthand side of
equation~(\ref{n/2heads}) at $n=400$; it is $\approx 0.0399$.  But all the
probabilities for 195 to 205 heads are about the same, so an offhand
estimate would be $11 \times 0.0399 \approx 0.439$.  The actual answer is
0.418.

Similarly, for $n=10,000$, the value of~(\ref{n/2heads}) is about 0.00798,
and all the probabilities for 4980 to 5020 heads are about the same, so an
offhand estimate would be $41 \times 0.00798 \approx 0.327$.  The actual
answer is 0.318.}

\end{problemparts}

\end{problem}


                                 