\documentclass[11pt]{article}	
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightyear}{2002}
\renewcommand{\coursecopyrightnames}{Prof. Albert~R.~Meyer}

\begin{document}
\inclassproblems{14, Mon}

%generalized weak law
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance22.tex}
% FA 2001, tutorial 13

\begin{problem}
The Weak Law of Large Numbers in \href{
http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln13-14.pdf}
{Notes 13-14} was given for a sequence $G_1, G_2, \dots$ of pairwise
independent random variables with the same mean and variance.  We can
generalize the Law to sequences of pairwise independent random variables,
possibly with \emph{different} means and variances, as long as their
variances are bounded by some constant.

\begin{theorem*}[Generalized Pairwise Independent Sampling]
Let $X_1, X_2, \dots$ be a sequence of pairwise independent random
variables such that $\variance{X_i} \leq b$ for some $b\geq 0$ and all
$i\geq 1$.  Let
\begin{align*}
A_n & \eqdef \frac{X_1 + X_2 + \cdots + X_n}{n},\\
\mu_n & \eqdef \expect{A_n}.
\end{align*}
Then for every $\epsilon > 0$,
\begin{equation}\label{gpis}
\pr{\abs{A_n - \mu_n} > \epsilon} \leq \frac{b}{\epsilon^2} \cdot \frac{1}{n}.
\end{equation}
\end{theorem*}

\begin{problemparts}
\problempart  Prove the Generalized Pairwise Independent Sampling Theorem. 
\hint The proof of the Pairwise Independent Sampling Theorem from
the Notes is repeated in the Appendix.

\solution{Essentially identical to the proof attached, except that
$\variance{G_i}$ gets replaced by $b$, and the equality becomes $\leq$
where the $b$ is first used.}

\problempart Conclude
\begin{corollary*}[Generalized Weak Law of Large Numbers]

For every $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty}
        \pr{\abs{A_n - \mu_n}  \leq \epsilon} = 1.
\]
\end{corollary*}

\solution{
\begin{align*}
\pr{\abs{A_n - \mu_n}  > \epsilon} = & 1- \pr{\abs{A_n - \mu_n}  \leq
 \epsilon}\\
   \geq & 1- b/(n\epsilon^2) & \text{(by~(\ref{gpis}))},
\end{align*}
and for any fixed $\epsilon$, this last term approaches 1 as $n$
approaches infinity.}

\end{problemparts}
\end{problem}


% pset12 fall 01; spring 02 cp12M
\begin{problem} {\bf Attack of the Clones}

We want to determine the percentage, $r$, of people who intend to watch
the {\em Episode II: Attack of the Clones}.  Since we are still working on
our jedi mind tricks, we decide to conduct a poll.

%\begin{problemparts}

%\problempart

Suppose that we poll 800 people.  Use the Pairwise Sampling Theorem to
bound the confidence level that our estimated value is within $\pm0.04$ of
the actual value $r$.

\solution{
The Pairwise Sampling Theorem gives us a bound on the
probability that the average of a sum of independent, identically
distributed random variables differs from their mean by more than a
certain amount $\epsilon$.  Call this probability $\delta$.  Our
confidence level, $c = 1 - \delta$. From the theorem we find,
\[
\pr{\abs{\frac{S_n}{n} - r} \geq \epsilon}
\leq 
\frac{\sigma^2}{n\epsilon^2}
\]

Recall that $\sigma^2$ is the variance of the random variables we are
summing.  In this case, these are Bernoulli random variables, so the
variance is $pq$, where $q \eqdef 1-p$.  Unfortunately, $p$ is also the
value we are trying to compute!  However, we can take advantage of the
fact that the variance is maximized when $p=1/2$.  This gives us the
following bound on $\delta$.

\begin{eqnarray*}
\delta
& \leq & \frac{p(p-1)}{n\epsilon^2} \\
& \leq & \frac{0.5(0.5-1)}{n\epsilon^2} \\
& \leq & \frac{1}{4n\epsilon^2}.
\end{eqnarray*}

Plugging in 800 for $n$, and $0.04$ for $\epsilon$ we find $\delta
\leq 0.195$.  Our confidence level is $1-\delta$, so $c \geq 1 -
0.195$, or 80\%.
}

\iffalse

\problempart Again using the Sampling Theorem, find the number of
people we would need to poll to if we wanted to be 95\% confident that
our estimated value was within 0.04 of the actual value $r$.

\solution{ 
In order to be at least 95\% confident in our measurement, we need the
probability that our measurement is outside the error margin to be
less than 0.05.  Using our formula from part \textbf{a}, it is easy to
see that $\delta \leq 0.05$ when the bound is less than 0.05.
\[
\delta \leq \frac{1}{4n\epsilon^2}  \leq  0.05
\]
Solving for $n$, we find, that in order to achieve this bound we have
to poll at least $3125$ people:
\begin{eqnarray*}
0.05 & \geq & \frac{1}{4n \cdot 0.04^2}\\
n & \geq & \frac{1}{4 \cdot 0.05 \cdot 0.04^2}\\
n & \geq & 3125
\end{eqnarray*}
}


\problempart Do you think it is reasonable to model people as
independent coin tosses? Why does the number of people chosen in this
poll not depend on the population size?

\solution{

%revised by ARM Nov 2002

This was intended to be a thought provoking question.  The polling
theorems we have been using are based on the assumption that all people
are equally likely to be polled.  For example, polling only people in
California probably would not give results corresponding to the entire
United States, because people's voting behavior is often strongly
correlated with the region they are in.  So it would be important that the
people sampled in a poll were equally likely to be in each region of the
country.

The poll doesn't depend on population size.  It may be helpful to think of
the people polled as being colored balls in a (giant) box that we are
sampling from.  Regardless of the number of balls in the box, the
probability that we draw a red ball is just the fraction of balls in the
box that are red.}



\end{problemparts}
\fi

\end{problem}


\begin{problem} \textbf{Explaining Sampling to a Jury}

You just calculated the confidence level, based on a poll of 800 people,
of an estimate being within $\pm0.04$ of the fraction of people in the US
who intend to watch \emph{Star Wars Episode II: The Attack of the Clones}.
The lecture showed that to achieve a 95\% confidence level for such an
estimate, a poll of 3125 randomly selected people is sufficient.

Suppose you were going to serve as an expert witness in a trial.  How
would you explain to a jury why it is reasonable to model people as
independent coin tosses?  How would you explain why the number of people
necessary to poll \emph{does not depend on the population size}?

\solution{This was intended to be a thought-provoking, conceptual
question, and it was.  In fact, it became apparent from the extended
discussions at nearly all tables that, although most of the class had
cranked through the formulas for poll size and confidence levels last
week, they couldn't articulate, and indeed didn't really understand the
answers to the questions raised.

Here's a way to explain why we model polling people about Star Wars as
independent coin tosses that a jury might be able to follow:

\begin{quote}
Of the approximately 250,000,000 people in the US, there are some unknown
number, say 100,000,000, who plan to see Star Wars.  So in this case, the
\emph{fraction} of people planning to see Star Wars would be
100,000,000/250,000,000 = 0.4.

To estimate this unknown fraction, we randomly select one person from the
250,000,000 in such a way that \emph{everyone has an equal chance of being
picked}.  For example, we might get computer files from the Census Bureau
listing all 250,000,000 people in the US.  Then we would generate a number
between 1 and 250,000,000 by some physical or computational process that
generated each number with equal probability, and then we would interview
the person whose number came up.  In this way, we can be sure that the
probability that a person we select will be planning to see the movie is
exactly the unknown fraction who plan to see the movie.

After we have picked a person and learned their movie plans, we perform
the procedure again, making sure that everyone is equally likely to be
picked the second time, and so on, for picking a third, fourth, \etc
person.  On each pick the probability of getting a person who plans to see
the movie is the same fraction, so we describe picking a person in this
way as ``flipping a coin'' that has this fraction as probability of coming
up ``Heads''---meaning that the person selected plans to see the movie.

Now we all understand that if we keep flipping a coin with a certain
probability of coming up Heads, then the more we flip, the closer the
fraction of Heads flipped will be to that probability.  Mathematical
theory lets us calculate us how many time to flip coins to make the
fraction of Heads very likely close to the right fraction, but we won't go
into those details.

It's also clear, that if two different coins have the same probability of
coming up Heads, it makes no difference in our experiments which coin we
use: the number of flips we need for the fraction of Heads flipped very
likely to be close to the probability of a Head will be the same for
either coin.  So whether the coin had probability of heads, say, 0.4,
because 100,000,000 out of 250,000,000 people intended to see Star Wars,
or 10,000 out of 25,000, or 2 out of 5---the same number of flips will
allow us to estimate the probability of Heads, and hence to estimate the
fraction of the population aiming to see the movie.  So the \emph{number
of people we need to poll is the same}, whether we are selecting from a
large population or a small population, as long as the fraction planning
to see the movie is the same in the small population as in the large one.
\end{quote}
}
\end{problem}


\textbf{NOTE:} We didn't get to either of the following two problems.

\begin{problem}
Let $X,Y$ be independent Binomial random variables with parameters $(n,p)$
and $(m,p)$, respectively.

\bparts
\ppart
What is $\pr{X+Y = k}$?

\solution{
The pdf of $X$ is the probability of tossing $k$ Heads out of
$n$ independent flips of a coin with bias $p$.  Likewise for $Y$ and $m$
flips.  Since, $X$ and $Y$ are independent, the pdf of $X+Y$ corresponds
to $n+m$ independent flips, \ie, $X+Y$ is a Binomial variable with
parameters $(n+m, p)$.  Hence,
\[
\binom{m+n}{k}p^k(1-p)^{m+n-k}.
\]
}

\ppart  Prove that if $p=1/2$ and $n$ is even, then

\begin{equation}
\pr{X = \frac{n}{2}} \sim \sqrt{\frac{2}{n \pi}}\label{n/2heads}.
\end{equation}

\hint Use Stirling's approximation (in the appendix).

\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}

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}}
\pr{X = \frac{n}{2}}= 
 =\frac{\dbinom{n}{\ceil{n/2}}}{2^n} \sim \sqrt{\frac{2}{n \pi}},
\end{equation}
proving~(\ref{n/2heads}).

If $n$ is odd, the same asymptotic bound also holds (with $n/2$ replaced
by $\ceil{n/2}$).  }

\ppart Estimate the probability that the number of heads in 400 flips of a
fair coin will be between 195 and 205, and likewise that in 10,000 flips
it will be between 4980 and 5020.

Also, discuss writing a program to calculate the exact answer.

\solution{The numbers are all too large to calculate exactly 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 typically overflows when computing 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\footnote{Though on machines with
enough RAM and a gigahertz+ processor, Scheme actually can handle exact
calculations with 40,000 digit integers.}.  But there are no applications
that require anywhere near such accuracy.

So we aim for an approximate solution using Stirling'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; even using this
version, the calculation of the powers of $n/m$ and $n/(n-m)$ must be
properly interleaved with divisions by powers of 2 to avoid overflow.  But
since floating point is usually good for 8 to 10 places on most machines,
getting six place accuracy should be manageable.

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.}

\eparts

\end{problem}

\iffalse

\begin{problem}
A new political journal announces as part of its editorial policy that
only poll results identifying a candidate with a 51\% lead with 95\%
confidence level will be acceptable for publication (and conversely any
such poll with this confidence level is acceptable).  The editors reason
that by doing so, their readership can have the confidence that at most 5\%
of the identifications of leading candidates they publish will be
incorrect.

Hearing about this new policy, 200 Republican campaign managers of
\emph{trailing} candidates in \emph{close} two-candidate contests are
instructed by their National Committee to poll voters to see if the poll
shows that their candidates have a 51\% lead.  The committee plans to
submit to the journal only the results of legitimate polls that show the
Republican candidate leading with $51\pm 1/2\%$ at the 95\% confidence
level.  The Committee figures these results will all published and will
suggest a Republican landslide.

Will this strategy by the National Committee work?  If not explain why.
If so, discuss the fallacy in the editors' reasoning.

\solution{Yes, the strategy will work.

Even though all 200 Republican candidates are somewhat behind in their
campaigns, 10 of the polls on average would find them to be leading by
0.5--1.5\% at the 95\% confidence level.

The editors have confused the nature of statistical confidence levels with
probability: confidence at the 95\% level does \textbf{not} mean that
there is only 1 chance in 20 that a poll is right.  It doesn't even make
sense to talk about the probability of a real-world fact such as which
candidate is leading.  We can only say that our prediction based on a
random sample has probability 0.95 of being right.  This means that if we
took many samples and made predictions based on each sample, there is a
high probability that 95\% of our predictions would be right.  But when
the National Committee selects just those sample results it likes, the
confidence level we assign to those results is no longer relevant.

There really is no clear alternative policy the journal editors could
adopt that would overcome this kind of problem, even if there wasn't a
National Committee trying to mislead readers.  For example, in medical
trials, there are many more than 200 ``alternative'' therapies being
evaluated by proponents who may be gullible, but are genuinely honest.
Nevertheless, at the 95\% confidence level, we can expect 10 of the 200
evaluations of useless or even damaging alternative therapies to yield
positive results.  The remaining 190 medical trials would not be submitted
for publication by honest proponents because the trials did not show
positive results at the 95\% level.  But the 10 that did would be
submitted by honest medical testers with no intention to mislead.

This is why, unless there is a explanation of \emph{why} a therapy works,
scientists and doctors usually doubt results claiming to confirm the
efficacy of some mysterious therapy at a high confidence level.}

\end{problem}



%infinite variance
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance24.tex}
%carried over from 12F, with slight revision

\begin{problem}

\bparts

\ppart Describe an \emph{integer} valued random variable, $R_1$, such that
$\expect{R_1}=0$, but $\variance{R_1}$ is infinite.

\solution{Let
\begin{align*}
\pr{R_1 = 2^n} & \eqdef \frac{1}{2^{n+1}},\\
\pr{R_1 = -2^n} & \eqdef \frac{1}{2^{n+1}},\\
\pr{R_1 = \text{ a nonpower of 2 }} & \eqdef 0.
\end{align*}
}

\ppart Describe a \emph{natural number} valued random variable, $R_2$,
such that $\expect{R_2}$ is finite, but $\variance{R_2}$ is infinite.
\hint $\sum_{i=0}^\infty i/i^3 < \infty$, but $\sum_{i=0}^\infty i^2/i^3 =
\infty$.

\solution{
We know $\sum_{i=1}^\infty 1/i^3$ converges.  Say it converges to
the value $d>0$.  Define $\pr{R=i} \eqdef 1/di^3$ for $i>0$ and
$\pr{R=0} \eqdef 0$.  This ensures $\sum_{i=0}^\infty \pr{R=i} = 1$ as
required by the definition of random variable.
So
\[
\expect{R} = \sum_{i=0}^\infty i \pr{R = i} = \sum_{i=1}^\infty
\frac{i}{di^3} = \frac{1}{d}\sum_{i=1}^\infty \frac{1}{i^2} = c
\]
for some constant $c$, because we know that $\sum_{i=1}^\infty 1/i^2$ also
converges to some positive value.  But
\[
\variance{R} = \expect{R^2}-\expectsq{R} = 
(\sum_{i=0}^\infty i^2 \pr{R = i}) - c^2 =
(\sum_{i=1}^\infty \frac{i^2}{di^3}) - c^2 =
\frac{1}{d}\sum_{i=1}^\infty \frac{1}{i} - c^2 = \infty,
\]
because $\sum_{i=1}^\infty 1/i$ is the Harmonic Series which we
know diverges.
}

\iffalse

\ppart Find such an $R$ where $\expect{R} =1$.

\solution{
Let $d = \sum_{i=1}^\infty \frac{1}{i^3}$.  Revise the
definition of $R$ above so that $\pr{R=i} = \eqdef 1/di^3$ for $i>0$ and
$\pr{R=0} \eqdef 0$.

Let $c = \sum_{i=1}^\infty \frac{1}{i^2}$.

 then we would have
\[
\expect{R} = \sum_{i=0}^\infty i \pr{R = i} =
\sum_{i=1}^\infty\frac{1}{ci^2} = 1.
\]
Because $c>1$, the number  }
\fi

\eparts
\end{problem}
\fi

\instatements{
\appendix

\section{Appendix}
\setcounter{secnumdepth}{0}

\begin{lemma*}
[Stirling's Approximation]
\[
n! \sim \sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n
\]

\end{lemma*}

The \emph{probability density function (pdf)} for a random variable, $R$, is
the function $f_R : \range{R} \to [0,1]$ defined by:
\[
f_R(x) \eqdef \pr{R = x}.
\]

Random variables $R_1, R_2, \dots$ are \emph{mutually independent} iff
\[
\pr{\lgintersect_{i} [R_i = x_i]} = \prod_{i} \pr{R_i = x_i},
\]
for all $x_1, x_2, \dots \in \reals$.  They are \emph{$k$-wise
independent} iff $\set{R_i \suchthat i\in J}$ are mutually independent for
all subsets $J \subset \naturals$ with $\card{J} = k$.

The Binomial Distribution with parameters $n,p$ is the distribution of the
sum $B_{n,p} \eqdef \sum_{i=1}^n X_i$ where $X_1,\dots,X_n$ are mutually
independent Bernoulli (indicator) variables with $\pr{X_i = 1} = p$.  It
has pdf
\[
f_{n,p}(k) \eqdef \binom{n}{k} p^k q^{n-k}
\]
where $q \eqdef 1-p$.
\begin{align*}
\expect{B_{n,p}} = & np,\\
\variance{B_{n,p}}  = & npq.
\end{align*}


\begin{theorem*} [Expectation of a Product]
If  $R_1, R_2, \dots, R_n$ are mutually independent, then
\[
\expect{R_1 \cdot R_2 \cdots R_n} = 
\expect{R_1} \cdot \expect{R_2} \cdots \expect{R_n}.
\]
\end{theorem*}


%%%%%%%%%%%%%%%%%%%%%%%%% VARIANCE %%%%%%%%%%%%%%%%%%%%%%%%%%%%
The \emph{variance}, $\variance{R}$, of a random variable, $R$, is:
\[
\variance{R} \eqdef \expect{(R - \expect{R})^2}.
\]
Variance can also be equivalently defined as:
\[
\variance{R}\eqdef \expect{R^2} - \expectsq{R},
\]

\begin{lemma*}
For $a,b \in \reals$,
\begin{equation}\label{a2v}
\variance{aR+b} = a^2\variance{R}
\end{equation}
\end{lemma*}

\begin{theorem}\label{th:varsum}
If $R_1, R_2, \ldots, R_n$ are \emph{pairwise} independent random
variables, then
\[
\variance{R_1 + R_2 + \cdots + R_n} = \variance{R_1} + \variance{R_2} +
  \cdots + \variance{R_n}.
\]
\end{theorem}


%%%%%%%%%%%%%%%%%%%%%%%%%% MARKOV %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem*}[Markov's Theorem]
  If R is a nonnegative random variable, then for all $x > 0$
  \begin{displaymath}
    \pr{R \geq x} \leq \frac{\expect{R}}{x}.
  \end{displaymath}
\end{theorem*}
An alternative formulation is
\[
\pr{R \geq x\expect{R}} \leq \frac{1}{x}.
\]


%%%%%%%%%%%%%%%%%%%%%%%% Chebyshev %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem*}[Chebyshev]
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\begin{equation}\label{Chb}
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\end{equation}
\end{theorem*}
An alternative formulation is
\[
\pr{\abs{R - \expect{R}} \geq x\sigma_R} \leq \frac{1}{x^2},
\]
where $\sigma_R \eqdef \sqrt{\variance{R}}$ is the standard deviation of
$R$.


\begin{theorem*}[Pairwise Independent Sampling]
Let
\[
A_n \eqdef \frac{\sum_{i=1}^n G_i}{n}
\]
where $G_1, \dots, G_n$ are pairwise independent random variables with the
same mean, $\mu$, and deviation, $\sigma$.  Then
\begin{equation}\label{Sndev}
\pr{\abs{A_n - \mu} > x} \leq 
\paren{\frac{\sigma}{x}}^2 \cdot \frac{1}{n}.
\end{equation}
\end{theorem*}

\begin{proof}
By linearity of expectation,
\[
\expect{A_n} = \frac{\expect{\sum_{i=1}^n G_i}}{n}
   = \frac{\sum_{i=1}^n \expect{G_i}}{n}
   = \frac{n\mu}{n} = \mu.
\]

Since the $G_i$'s are pairwise independent, their variances will also add,
so
\begin{align*}
\variance{A_n}  = & \paren{\frac{1}{n}}^2 \variance{\sum_{i=1}^n G_i}
                        & \text{(by~(\ref{a2v}))}\\
 = & \paren{\frac{1}{n}}^2 \sum_{i=1}^n \variance{G_i}
                        & \text{(by Theorem~\ref{th:varsum})}\\
 = & \paren{\frac{1}{n}}^2 n\sigma^2\\
 = & \frac{\sigma^2}{n}.
\end{align*}

Now letting $R$ be $A_n$ in Chebyshev's Bound~(\ref{Chb})
yields~(\ref{Sndev}), as required.

\end{proof}



\iffalse

We have the approximation:
\[
f_{n,p}(\alpha n)  =  2^{-n(H(\alpha,p) - H(\alpha))}
\overbrace{e^{a_n - a_{\alpha n} - a_{(1-\alpha) n}}}^{\sim 1}/
\sqrt{2 \pi \alpha (1 - \alpha) n}
\]
where $0 < \alpha < 1$, $1/(12k+1) \leq a_k \leq 1/(12k)$, and
\begin{eqnarray*}
H(\alpha,p) & \eqdef & - (\alpha \log_2 p + (1 - \alpha) \log_2 (1 - p)),\\
H(\alpha) & \eqdef & H(\alpha,\alpha) = - (\alpha\log_2 \alpha + (1-\alpha)\log_2 (1-\alpha)).
\end{eqnarray*}
Also,
\[
F_{n, p}(\alpha n) \leq \frac{1 - \alpha}{1 - \alpha/p} f_{n, p}(\alpha n)
\]
where $0 < \alpha < p$.
}
\fi

\end{document}


\iffalse

%%%% FRI %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%spring 02 cp12M

\begin{problem}
We really would like to poll fewer people.  Since we know that the
distribution of polled answers is binomial, we can recalculate confidence
levels and required poll sizes people using approximations to the binomial
distribution.

Let $\delta$ be the probability that the experiment deviates more than
$\epsilon$ from the expected value, then from
\href{
http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln11-12.pdf}
{Notes 11-12}, \S4, we have
\begin{equation*}
\delta \leq 2 F_{n,1/2} ((1/2 - \epsilon) n).
\end{equation*}

\begin{problemparts} 

\problempart Suppose that we poll 800 people.  Using the bounds on the
binomial pdf, how confident can we now be that our estimated value is
within $\pm0.04$ of the actual value, $r$?

\solution {Coming Soon.}

\problempart Using the estimates for the binomial pdf, find the number of
people we would need to poll to if we wanted to be 95\% confident that our
estimated value was within 0.04 of the actual value, $r$.

\problempart Find the number of people we would need to poll to if we
wanted to be 95\% confident that our estimated value was within 0.02
of the actual value $r$.

\solution{

\begin{equation}\label{delta bound}
\delta \leq F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n) +
   F_{n,1-\frac{1}{2}}((1-\frac{1}{2}-\epsilon) n)
 = 2 F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n).
\end{equation}

Now plugging in $\epsilon = 0.02$ into~(\ref{delta bound}) gives:
\begin{align*}
\delta \leq  2 F_{n,\frac{1}{2}}(0.48 n)
    & \leq 2 \cdot  \frac{1 - \alpha}{1 - 2\cdot\alpha} f_{n,1/2}(0.48 n)\\
    &  \approx 2 \cdot 0.6842 \cdot 2^{-n(1 - H(0.48))}/\sqrt{2\pi \cdot 0.48(1-0.48)n}\\
    & = 2 \cdot 0.6842 \cdot \frac{2^{-0.00115 n}}{1.2523 \sqrt{n}}.
\end{align*}

We want to poll enough people so that $\delta$ is less than $0.05$.
The easiest way is to plug in values for $n$, the number of people
polled:
\[
\begin{array}{c|l}
\mbox{$n$ = people polled} & \begin{array}{cc}
\mbox{upper bound on} \\
\mbox{probability poll is wrong}
\end{array} \\
\hline
1000 &  29.4\% \\
2000 &  9.3\% \\
3000 &  3.4\% \\
2500 &  5.6\% \\
2750 &  4.4\%\\
2616 &  5.004\%\\
2617 &  4.999\%
\end{array}
\]

So polling 2617 people is sufficient to determine public opinion to within
2\% with confidence of 95\%.  Again, the remarkable point is that the
population of the country has no effect on the poll size.  Whether there
are ten thousand people or a billion in a country, polling 2617 people
is sufficient!
}

\end{problemparts}
\end{problem}
\fi
