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

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

\renewcommand{\problemdata}[5]{}

\begin{document}
\inclassproblems{13M}

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

In last Friday's in-class problems, you 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}.  You also determined 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}


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

%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/fall01/lectures/l12.pdf}{Notes
12} 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{problemparts}
\problempart  Prove:
\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*}
\bar{X}_n & \eqdef (X_1 + X_2 + \cdots + X_n)/n,\\
\mu_n & \eqdef \expect{\bar{X}_n}.
\end{align*}
Then for every $\epsilon > 0$,
\[
\pr{\abs{\bar{X}_n - \mu_n} \geq \epsilon} \leq \frac{b}{n\epsilon^2}.
\]
\end{theorem*}
\hint The proof of the Pairwise Independent Sampling Theorem from
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l12.pdf}{Notes
12} is 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{\bar{X}_n - \mu_n}  \geq \epsilon} = 0.
\]
\end{corollary*}

\solution{For fixed $\epsilon$, the bound $b/(n\epsilon^2)
\rightarrow 0$ as $n \rightarrow \infty$.}

\end{problemparts}
\end{problem}


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

\begin{problem}
(carried over from Friday)

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


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

%\subsection{Bounds on Deviation from the Mean}

\begin{theorem*}[Markov's Theorem]
 If R is a nonnegative random variable, then for all $x > 0$
\begin{equation}\label{M}
\pr{R \geq x} \leq \frac{\expect{R}}{x}.
\end{equation}
\end{theorem*}

\begin{theorem*}[Chebyshev]
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\begin{equation}\label{Cheb}
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\end{equation}
\end{theorem*}

%\subsection{Weak Law of Large Numbers}

Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
independent variables with the same mean, $\mu$, and deviation, $\sigma$.

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

\begin{proof}
By linearity of expectation,
\[
\expect{\frac{S_n}{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{eqnarray*}
\variance{\frac{S_n}{n}} & = & \left(\frac{1}{n}\right)^2 \variance{S_n}\\
& = & \left(\frac{1}{n}\right)^2 \sum_{i=1}^n \variance{G_i}\\
& = & \left(\frac{1}{n}\right)^2 n\sigma^2\\
& = & \frac{\sigma^2}{n}.
\end{eqnarray*}

Now Chebyshev's Bound tells us that for any random variable, $R$,
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
So, letting $R$ be $S_n/n$ yields~(\ref{Sndev}), as required.

\end{proof}

\end{document}
