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

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/fall03/handouts/lectures/ln13.pdf}
{Week 13 Notes}}


\begin{document}
\problemset{11}

\begin{problem}
If a couple continues to have children until they have a boy, then we have
seen that the expected number, $N$, of children the will have is $1/(1/2) =
2$, assuming boys and girls are equally likely to be born.  What is the
variance of the number of children they will have?  \hint There is a closed
form for the series that $\expect{N^2}$ equals by definition.


\solution{
We can compute the variance as follows:
\[
\variance{N}
         = \expect{N^2} - \expect{N}^2 
         = \sum_{k=1}^{\infty} k^2 \cdot \left(\frac{1}{2}\right)^k - 2^2 
         = \frac{\frac{1}{2} + (\frac{1}{2})^2}{(1 - \frac{1}{2})^3} - 4 
         = 6 - 4
         = 2
\]
The formula for the series was derived in Rosen and previous Notes.
}
\end{problem}



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

\bparts

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

\ppart How many tosses suffice to make us 95\% confident which coin was
chosen?  Any sufficient number of tosses that does not depend on $n$ is
acceptable as an answer, but you should explain your answer.

\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{\frac{H_n}{n} > \frac{5}{8} } 
        & = \pr{\frac{H_n}{n} - \frac{1}{2} > \frac{5}{8} - \frac{1}{2}} 
          = \pr{H_n - \frac{n}{2} > \frac{n}{8} } \\
        & = \pr{H_n - \expect{H_n} > \frac{n}{8} } 
          \leq \pr{|H_n - \expect{H_n}| > \frac{n}{8} } \\
        & \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{\frac{H_n}{n} < \frac{5}{8} } 
        & = \pr{\frac{3}{4} - \frac{H_n}{n} > \frac{3}{4} - \frac{5}{8}} 
          = \pr{\frac{3n}{4} - H_n > \frac{n}{8} } \\
        & = \pr{\expect{H_n} - H_n > \frac{n}{8} } 
          \leq \pr{|H_n - \expect{H_n}| > \frac{n}{8} } \\
        & \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 of the binomial distribution, which give 95\%
confidence when $n > 42$.}

\eparts

\end{problem}


% Problem: Hearts
          % Topics: Variance, Expectation
% Variants of this problem appeared in:
% SP 2000, PS 10.5, problem 3
% FA 2000, PS 11.5

\begin{problem}
Suppose you are playing the game ``Hearts'' with three of your friends.
In Hearts, all the cards are dealt to the players, in this case the four
of you will each have 13 cards.

\begin{problemparts}

\problempart
What is the expectation of the number of hearts in your hand?

\solution{
Let $H$ be the number of hearts in your hand, and let $X_i$ be the
indicator random variable for the event that the $i$th card in your
hand is a heart.  Then $H = \sum_{i=1}^{13} X_i$.  So
\[
\expect{H}  = \sum_{i=1}^{13} \expect{X_i}
        = \sum_{i=1}^{13} \Pr(\text{$i$th card is a heart}) 
        = \sum_{i=1}^{13} \frac{1}{4} = \frac{13}{4}.
\]
}

\problempart
What is the variance of the number of hearts in your hand?

\solution{
To compute variance, 
we first compute $\expect{H^2}$, 
following the solution to the Random Hat Check Problem.
\[
\expect{H^2} = \expectsq{\sum_{i=1}^{13} X_i}
        = \sum_i \expect{X_i} + \sum_i \sum_{j \neq i} \expect{X_i X_j} 
\]
Note that $X_i^2 = X_i$, so $\expect{X_i^2} = 1/4$.  
When $i \neq j$,
$X_i X_j = 1$ if cards $i$ and $j$ are both hearts, and 0 otherwise.  The
probability that both cards are hearts is $\binom{13}{2}/\binom{52}{2}$, 
so 
$\expect{X_iX_j} = \binom{13}{2}/\binom{52}{2} = 3/51$.  
In the summation above, there
are 13 $\expect{X_i^2}$ terms, and $13 \cdot 12 = 156$ terms of the
form $\expect{X_i X_j}$ with $i \neq j$.  Thus,
\[
\variance{H} = \expect{H^2} - \expectsq{H}
        = 13 \cdot \frac{1}{4} + 156 \cdot \frac{3}{51} - (\frac{13}{4})^2 
        \approx 1.864. 
\]
}

\problempart What is the expectation of the number of suits in your
hand?

\solution{ Let $N$ denote the number of suits in a hand.  Let $X_s$ be
the indicator random variable for the event that there is a spade in
the hand.  Define $X_h, X_d, X_c$ analogously for the three remaining
suits: hearts, diamonds, and clubs.  Then $N = X_s + X_h + X_d + X_c$.

The expectation of each of the indicator variables is the probability
that a hand contains the corresponding suit.  Thus, for $i \in \set{s,h,d,c}$
\[
\expect{X_i} = 1 -  \frac{\binom{52-13}{13}}{\binom{52}{13}} \approx 0.9872,
\]
because $\binom{52-13}{13}$ is the number of hands that are missing the
particular suit, and $\binom{52}{13}$ is the total number of hands.
\[
\expect{N}=\expect{X_s + X_h + X_d + X_c} = \expect{X_s} + \expect{X_h} +
\expect{X_d} + \expect{X_c} \approx 4 \cdot 0.9872 = 3.9488.
\]

}

\problempart What is the variance of the number of suits in your hand?

\solution{

To compute variance, we compute $\expect{N^2}$ directly, and then
$\variance{N} = \expect{N^2} - \expectsq{N}$.  We first calculate
$\Pr(N=i)$ for $i = 1,2,3,4$.
\[
\Pr(N=1) = \frac{4} {\binom{52}{13}} \approx 6.299 \times 10^{-12},
\]
because there are four possible hands of all one suit out of
$\binom{52}{13}$ possible hands of 13 cards.
\[
\Pr(N=2) = \frac{\binom{4}{2}\left[\binom{26}{13} - 2\right]}{\binom{52}{13}}
         \approx 9.827 \times 10^{-5},
\] 
because there are $\binom{4}{2}$ ways to choose which two suits.
There are $\binom{26}{13}$ ways to choose 13 cards from the 26
possible cards of those two suits.  Two of those $\binom{26}{13}$
hands actually contain only one suit.
\[
\Pr(N=3) = \frac{\binom{4}{3}
                    \left[\binom{39}{13} - \binom{3}{2}\binom{26}{13} 
                                + 3\right]}
                {\binom{52}{13}} \approx 0.05097,
\]
because there are $\binom{4}{3}$ ways to choose the three suits, and
$\binom{39}{13}$ ways to choose $13$ cards from the $39$ cards of
those three suits.  But that includes hands with only one or two
suits.  So, using Inclusion-Exclusion, we subtract the
$\binom{3}{2}\binom{26}{13}$ ways to choose two of the three suits and
then choose $13$ cards from the $26$ cards of those suits.  This
subtracts out the three hands with only one suit twice, so we add
these back.

Of course, 
\[
\Pr(N=4) = 1 - (\Pr(N=1) +\Pr(N=2) + \Pr(N=3)) \approx 0.9489.
\]
Thus, 
\begin{align*}
\expect{N^2} & = 1 \cdot \Pr(N=1) + 4 \cdot \Pr(N=2) 
                + 9 \cdot \Pr(N=3) + 16 \cdot \Pr(N=4) \\
        & \approx 0 + 0.0004 + 0.4587 + 15.1824 = 15.6415
\end{align*}
This allows us to complete the calculation of the variance:
\[
\variance{N} \approx 15.6415 - (3.9488)^2 \approx 0.0485.
\]
}

\end{problemparts}

\end{problem}


\begin{problem}%{\bf fall96 }

For each of the following, bound the probability using (i) Markov's Theorem,
(ii) Chebyshev's Theorem, and (iii) Binomial Approximation (Lecture Notes
10, Section 4.2)

\begin{problemparts}

\problempart
In 1000 independent coin flips, what is the probability of getting 
at least 600 heads?

\solution{ REDO SOLUTIONS AND CHECK BINOMIAL APPROX
ANSWERS. $\prob{\geq 600} = 1-\prob{< 600}(n=1000,\alpha=3/5)\leq 1 -
2^{-1000}{\binom{1000}{600}}{\frac{1-3/5}{1-6/5}}$}


\problempart
In a noisy communication channel with $10\%$ error rate, what is the
probability that out of 1000 transmitted bits, at least 200 bits are 
wrongly transmitted ({\em i.e.}, {\tt 1} is received as {\tt 0} and 
vice versa)? Assume that errors in each of the bits are independent.

\solution{
$\pr{\geq 200} = 1-\pr{< 200}(n=1000,\alpha=1/5)\leq 1 - 
2^{-1000}{\binom{1000}{200}}{\frac{1-1/5}{1-2/5}}$
}

\end{problemparts}
\end{problem}

%Rosen 4.5 50,51

\begin{problem}
The covariance of two random variables X and Y on a sample space S, denoted
by Cov(X,Y), is defined to be the expected value of the random variable
(X-E(X))(Y-E(Y)).  That is , Cov(X,Y) = E((X - E(X))(Y- E(Y))).

\begin{problemparts}
\problempart
Show that Cov(X,Y) = E(XY) - E(X)E(Y), and use this result to conclude that 
Cov(X, Y) = 0 if X and Y are independent random variables.
\solution{
Cov(X,Y) = E((X-E(X))*(Y-E(Y))) = E(XY-Y*E(X) - X*E(Y) + E(X)*E(Y)) =
E(XY) - E(Y)*E(X) - E(X)*E(Y) + E(X) * E(Y) = E(XY) - E(X)*E(Y).

If X and Y are independent, then the last two terms are equal, 
so their difference is 0.
}

\problempart

Show that $\variance{X + Y} = \variance{X} + \variance{Y}$ + 2Cov(X,Y).
  
\solution{
V(X+Y) 

= E((X+Y)^2)-E(X+Y)^2

= E(X^2+2XY+Y^2)-(E(X)+E(Y))^2

= E(X^2)+2E(XY)+E(Y^2) - E(X)^2 - 2E(X)E(Y) - E(Y)^2 

= E(X^2) - E(X)^2 + 2(E(XY) - E(X)E(Y)) + E(Y^2) - E(Y)^2 

= V(X) + 2Cov(X,Y) + V(Y)

}
\end{problemparts}
\end{problem}




\end{document}                            
