\documentclass[12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\newcommand{\pdf}{\textsc{PDF}}
\newcommand{\cdf}{\textsc{CDF}}

\begin{document}

\recitation{20}{November 24, 2004}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\insolutions{
\section{Philosophy of Polling}

Polling involves not only some tricky mathematics, but also some
philosophical issues.

The difficulty is that polling tries to apply probabilty theory to
resolve a question of fact.  Let's first consider a slightly different
problem where the issue is more stark.  What is the probability that
%
\[
N = 2^{6972607} - 1
\]
%
is a prime number?  One might guess $1/10$ or $1/100$.  Or one might
get sophisticated and point out that the Prime Number Theorem implies
that only about $1$ in 5 million numbers in this range are prime.  But
these answers are all wrong.  There is no random process here.  The
number $N$ is either prime or composite.  You can conduct as many
``repeated trials'' as you like; the answer will always be the same.
Thus, it seems probability does not touch upon this question.

However, there is a probabilistic primality test due to Rabin and
Miller.  If $N$ is composite, there is at least a $3/4$ chance that
the test will discover this.  (In the remaining $1/4$ of the time, the
test is inconclusive; it never produces a wrong answer.)  Moreover,
the test can be run again and again and the results are independent.
So if $N$ actually is composite, then the probability that $k = 100$
repetitions of the Rabin-Miller do not discover this is at most:
%
\[
\left(\frac{1}{4}\right)^{100}
\]
%
So 100 consecutive inconclusive answers would be extremely convincing
evidence that $N$ is prime!  But we still couldn't say anything about
the \textit{probability} that $N$ is prime: that is still either 0 or
1 and we don't know which.

A similar situation arises in the context of polling: we can make a
convincing argument that a statement about public opinion is true, but
can not actually say that the statement is true with any particular
probability.  Suppose we're conducting a yes/no poll on some question.
Then we assume that some fraction $p$ of the population would answer
``yes'' to the question and the remaining $1 - p$ fraction would
answer ``no''.  (Let's forget about the people who hang up on
pollsters or launch into long stories about their little dog Fi-Fi---
real pollsters have no such luxury!)  Now, $p$ is a fixed number, not
a randomly-determined quantity.  So trying to determine $p$ by a
random experiment is analogous to trying to determine whether $N$ is
prime or composite using a probabilistic primality test.

Probability slips into a poll since the pollster samples the opinions
of a people selected uniformly and independently at random.  The
results are qualified by saying something like this:
%
\begin{quotation}
``One can say with 95\% confidence that the maximum margin of sampling
error is $\pm 3$ percentage points.''
\end{quotation}
%
This means that either the number, $q$, reported in the poll is within
0.03 of the actual fraction, $p$, or else an unlucky 1-in-20 event
happened during the polling process; specifically, the pollster's random
sample was not representative of the population at large.  This is
\textit{not} the same thing as saying that there is a 95\% chance that $q$
is within 0.03 of $p$; it either is or it isn't, just as $N$ is either
prime or composite regardless of the Rabin-Miller test results.

\newpage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Suppose that a coin that comes up heads with probability $p$ is
flipped $n$ times.  Then for all $\alpha < p$
%
\begin{align*}
\pr{\text{\# heads} \leq \alpha n}
    & \leq \frac{1 - \alpha}{1 - \alpha / p} \cdot
           \frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}} 
           \cdot p^{\alpha n} (1-p)^{(1 - \alpha) n}
\end{align*}
%
where:
%
\[
H(\alpha) = \alpha \log_2 \frac{1}{\alpha} +
		(1 - \alpha) \log_2 \frac{1}{1 - \alpha}
\]

\vspace{0.5in}

\begin{problem}
A coin that comes up heads with probability $p$ is flipped $n$ times.
Find an upper bound on
%
\[
\pr{\text{\# heads} \geq \beta n}
\]
%
where $\beta > p$.  Think about the number of tails and plug into the
monster formula above.
\end{problem}

\solution{
\begin{align*}
\pr{\text{\# heads} \geq \beta n}
    & = \pr{\text{\# tails} \leq (1 - \beta) n}
\end{align*}
%
Now tails comes up with probability $1 - p$.  So the answer is the
same as above with $\alpha$ replaced by $1 - \beta$ and $p$ replaced
by $1 - p$:
%
\begin{align*}
\pr{\text{\# heads} > \beta n}
    & \leq \frac{\beta}{1 - \frac{1 - \beta}{1 - p}} \cdot
           \frac{2^{n H(\beta)}}{\sqrt{2 \pi \beta (1 - \beta) n}} 
           \cdot p^{\beta n} (1-p)^{(1 - \beta) n}
\end{align*}
%
Here we're using the fact that $H(1 - \beta) = H(\beta)$.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem} A Gallup poll in November 2004 found that 35\% of the
adult population of the United States believes that the theory of
evolution is ``well-supported by the evidence''.  Gallup polled 1016
people and claims a margin of error of 3 percentage points.

Let's check Gallup's claim.  Suppose that there are $m$ adult
Americans, of whom $pm$ believe evolution is well-supported and
$(1-p)m$ do not.  Gallup polls $n$ Americans selected uniformly and
independently at random.  Of these, $qn$ believe that evolution is
well-supported and $(1-q)n$ do not.  Gallup then estimates that the
fraction of Americans who believe evolution is well-supported is $q$.

Note that the only randomization in this experiment is in who Gallup
chooses to poll.  So the sample space is all sequences of $n$ adult
Americans.  The response of the $i$-th person polled is ``yes'' with
probability $p$ and ``no'' with probability $1 - p$ since the person
is selected uniformly at random.  Furthermore, the $n$ responses are
mutually independent.

\bparts

\ppart Give an upper bound on the probability that the poll's estimate
will be 0.03 or more too low.  Just write the expression; don't evaluate
yet!

\solution[\vspace{2in}]{We can regard each response as a coin flip
that is heads with probability $p$.  In these terms, $qn$ is the total
number of heads flipped.  So we have:
%
\begin{align*}
\lefteqn{\pr{qn \leq (p - 0.03)n}} \qquad \\
    & \leq \frac{1 - (p-0.03)}{1 - (p-0.03) / p} \cdot
           \frac{2^{n H(p-0.03)}}{\sqrt{2 \pi (p-0.03) (1 - (p-0.03)) n}} 
           \cdot p^{(p-0.03) n} (1-p)^{(1 - (p-0.03)) n}
\end{align*}}

\ppart Give an upper bound on the probability that the poll's estimate
will be 0.03 or more too high.  Again, just write the expression.

\solution[\newpage]{Reasoning as before and using the answer to the
preceding problem gives:
%
\begin{align*}
\lefteqn{\pr{qn > (p + 0.03)n}} \qquad \\
    & \leq \frac{p+0.03}{1 - \frac{1 - (p+0.03)}{1 - p}} \cdot
           \frac{2^{n H(p+0.03)}}{\sqrt{2 \pi (p+0.03) (1 - (p+0.03)) n}} 
           \cdot p^{(p+0.03) n} (1-p)^{(1 - (p+0.03)) n}
\end{align*}
}

\ppart The sum of these two answers is the probability that Gallup's poll
will be off by 3 percentage points or more, one way or the other.
Unfortunately, these expressions both depend on $p$--- the unknown
fraction of evolution-believers that Gallup is trying to estimate!

However, the sum of these two expressions is maximized when $p = 0.5$.  So
evaluate the sum with $p = 0.5$ and $n = 1016$ to upper bound the
probability that Gallup's error is 0.03 or more.  Pollsters usually try to
ensure that there is a 95\% chance that the actual percentage $p$ lies
within the poll's error range, which is $q \pm 0.03$ in this case.  Is
Gallup's evolution poll properly designed?

\solution[\vspace{3in}]{The probability that the error is 0.03 or more is
about 0.07, which means that $p$ will lie within the error range of a
polled fraction with probability 0.93.  So our estimates suggest Gallup's
poll is not quite large enough to meet the claimed 0.95 probability.
Since Gallup is a professional, we expect he's got the poll size right, by
by using a more accurate numerical estimation formula -- or he may have
considered it legitimate to round a very slightly larger margin of error
down to 0.03.}

\ppart If we accept all of Gallup's polling data and calculations, can we
conclude that there is a high probability that the number of adult
Americans who believe evolution is well-supported by the facts is $35 \pm
3$ percent?

\solution{No.  This is an question of fact, which is either true or
false.  We \textit{can} say that either the statement above is true or
else a 1-in-20 event occurred during the poll; specifically, Gallup
chose an unrepresentative sample.  This may convince you that $p$ is
``probably'' in the range $0.35 \pm 0.03$, but there is no way to convert
that informal ``probably'' to a mathematical probability.}

%ERIC: this solution needs more explanation (as I presume you realize). 

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem}
Let's play a game!  I have two envelopes.  One contains an integer $S$
and the other contains an integer $L$, where $S < L$.  To win the
game, you must determine which envelope contains the larger number.
To give you a fighting chance, I'll let you peek at the number in one
envelope selected at random.  Your job is to devise a strategy that
gives you a better than 50\% chance of winning, regardless of how $S$
and $L$ are chosen.

\bparts

\ppart Define a probability density function on the half integers
%
\[
\set{\ldots,\ -\frac{7}{2},\ -\frac{5}{2},\ -\frac{3}{2},\ -\frac{1}{2},\ \frac{1}{2},\ \frac{3}{2},\ \frac{5}{2},\ \frac{7}{2},\ \ldots}
\]
%
such that every half-integer has positive probability.  (Why can't you
use the uniform distribution?)

\solution[\vspace{2in}]{
Many solutions are possible.  Here is one:
%
\[
\begin{array}{rcccccccccc}
\# & \ldots & -\frac{7}{2} & -\frac{5}{2} & -\frac{3}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{3}{2} & \frac{5}{2} & \frac{7}{2} & \ldots \\[1ex]
\text{probability} & \ldots & \frac{1}{32} & \frac{1}{16} & \frac{1}{8} & \frac{1}{4} & \frac{1}{4} & \frac{1}{8} & \frac{1}{16} & \frac{1}{32} & \ldots
\end{array}
\]
%
The sum of the probabilities of all outcomes is
%
\[
2 \cdot \left(\frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \frac{1}{32} + \ldots\right) = 2 \cdot \frac{1}{2} = 1
\]
%
as required.}

\ppart Now supose you select a half-integer $X$ according to the
probability density function that you defined above.  Let $P$ be the
number you see by peeking into a randomly-selected envlope.  If $P >
X$, guess you're looking at the larger number.  If $P < X$, guess that
the other number is larger.  Prove that this strategy works with
probability greater than 50\%.

\solution{A tree diagram for this experiment is shown below.
%
\begin{center}
\includegraphics{integer-game}
\end{center}
%
The edge probabilities $a$, $b$, and $c$ depend on the numbers I
choose, $S$ and $L$, as well as your probability distribution.
However, these probabilities need only satisfy two requirements:
%
\begin{enumerate}
\item $a + b + c = 1$
\item $b > 0$
\end{enumerate}
%
The first is ensured because exactly one of the events $X < S$, $S < X
< L$, and $L < X$ must occur.  The second holds because your
probability distribution assigned positive probability to every
half-integer.  Assuming these facts, the probablity that you win the
game is:
%
\begin{align*}
\pr{\text{you win}}
    & = \frac{a}{2} + \frac{b}{2} + \frac{c}{2} + \frac{b}{2} \\
    & = \frac{a + b + c}{2} + \frac{b}{2} \\
    & = \frac{1}{2} + \frac{b}{2} \\
    & > \frac{1}{2}
\end{align*}
%
Thus, you win with probability greater than $1/2$.
}

\eparts

\end{problem}

\end{document}
