% Variants of this problem appeared in:
% SP 2000, PS 10.5
% FA 2001, TUT 12
\begin{problem}%source: spring00 ps10-5
We have two coins: one is a fair coin and the other is a coin
that produces heads with probability 3/4.  One of the two coins is picked,
and this coin is tossed $n$ times.

\begin{problemparts}

\problempart
Does the Weak Law of Large Numbers allow us to \emph{predict} what limit, if any,
is approached by the expected proportion of heads that turn up as $n$
approaches infinity?  Briefly explain.

\solution{
The Weak Law of Large Numbers tells us that the proportion 
of heads will approach $1/2$ if the fair coin was picked, 
and it will approach $3/4$ if the other coin was picked. 
But it does not tell us anything about which of these two numbers 
it will approach, 
as we have no information about which coin is picked. 
}

\problempart
How many tosses suffice to make us 95\% confident which coin was chosen?
Explain.

\solution{
To guess which coin was picked, 
set a threshold $t$ between $1/2$ and $3/4$. 
If the proportion of heads is less than the threshold, 
guess it was the fair coin; 
otherwise, guess the biased coin. 
Let the random variable $H_n$ be the number of heads in the 
first $n$ flips. 
We need to flip the coin enough times 
so that $\Pr(H_n/n > t) \leq 0.05$ if the fair coin was picked, 
and $\Pr(H_n/n < t) \leq 0.05$ if the biased coin was picked. 
A natural threshold to choose is $5/8$, 
exactly in the middle of $1/2$ and $3/4$. 

$H_n$ is the sum of independent Bernoulli variables, 
which each have variance $1/4$ for the fair coin 
and $3/16$ for the biased coin. 
Using Chebyshev's Inequality for the fair coin, 
\begin{align*}
\Pr\left(\frac{H_n}{n} > \frac{5}{8} \right) 
        & = \Pr\left(\frac{H_n}{n} - \frac{1}{2} > \frac{5}{8} - \frac{1}{2}\right) 
          = \Pr\left(H_n - \frac{n}{2} > \frac{n}{8} \right) \\
        & = \Pr\left(H_n - \expect{H_n} > \frac{n}{8} \right) 
          \leq \Pr\left(|H_n - \expect{H_n}| > \frac{n}{8} \right) \\
        & \leq \frac{\variance{H_n}}{(n/8)^2} 
          = \frac{n/4}{n^2/64} 
          = \frac{16}{n}
\end{align*}
For the biased coin, we have
\begin{align*}
\Pr\left(\frac{H_n}{n} < \frac{5}{8} \right) 
        & = \Pr\left(\frac{3}{4} - \frac{H_n}{n} > \frac{3}{4} - \frac{5}{8}\right) 
          = \Pr\left(\frac{3n}{4} - H_n > \frac{n}{8} \right) \\
        & = \Pr\left(\expect{H_n} - H_n > \frac{n}{8} \right) 
          \leq \Pr\left(|H_n - \expect{H_n}| > \frac{n}{8} \right) \\
        & \leq \frac{\variance{H_n}}{(n/8)^2} 
          = \frac{3n/16}{n^2/64} 
          = \frac{12}{n}
\end{align*}
We are 95\% confident if these are at most $0.05$, 
which is satisfied if $n \geq 320$. 

Because the variance of the biased coin is less that of the fair coin, 
we can do slightly better if make our threshold 
a bit bigger, to about $0.634$, 
which gives 95\% confidence with 279 coin flips. 

Because $H_n$ has a binomial distribution, 
we can get a much better bound using the estimates 
from Lecture 21, 
giving 95\% confidence when $n > 42$. 
}

\end{problemparts}
\end{problem}

%
%\begin{problem}
%This is a problem fragment. that produces heads with probability 3/4.  One of the two coins is picked,
%and this coin is tossed $n$ times.

%\begin{problemparts}

%\problempart

%Does the Weak Law of Large Numbers allow us to \emph{predict} what limit, if any,
%is approached by the expected proportion of heads that turn up as $n$
%approaches infinity?  Briefly explain.

%
%\solution{

%There is no way to predict the proportion of heads in the long run, since
%this will depend upon which of the two coins is picked, and we have no
%information about which coin is picked or how it is picked.  So while the
%Law of Large Numbers implies that the proportion of heads will, with
%probability appraoching one, be near either 1/2 or 3/4, it does not, and
%cannot, say anything about which of these numbers is the expected limit.

%}

%\problempart

%How many tosses suffice to make us 95\% confident which coin was chosen?
%Explain.

%
%\solution{

%To be 95 percent sure which coin was picked, bet that the fair coin was
%chosen if the proportion of heads is less than the average of 1/2 and 3/4,
%namely 5/8; otherwise bet that the biased coin was chosen.  You will win
%the bet if the proportion of heads does not deviate from the probability
%of heads by more than 1/8.  A quick calculation using Chebyshev's bound
%and the fact that the variance of a Bernoulli variable is at most 1/4,
%implies that the probability of a deviation this large is at most
%$1/(4n(1/8)^2)$.  This will be less than or equal to .05 if $n > 320$.

%In this problem, the number of heads in $n$ flips will be a Bernoulli
%distribution, and the estimates from Lecture Notes 21 could also be
%applied to yield a tighter bound: $n > 42$.

%}

%\end{problemparts}
%\end{problem}

