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

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{10}                    % !! start the paper

% Gambling Game from the lecture notes
\begin{problem}

Consider the following two gambling games.

Game A: We win \$2 with probability $2/3$ and lose \$1 with probability
$1/3$.

Game B: We win \$1002 with probability $2/3$ and lose \$2001 with
probability $1/3$.

\begin{problemparts}
\problempart What is the expected win in each case?

\solution{From the Notes: Let random variables $A$ and $B$ be the
payoffs for the two games.  For example, $A$ is 2 with probability 2/3
and -1 with probability 1/3.  We can compute the expected payoff for
each game as follows:

\begin{eqnarray*}
\expect{A} = 2 \cdot \frac{2}{3} + (-1) \cdot \frac{1}{3} = 1, \\
\expect{B} = 1002 \cdot \frac{2}{3} + (-2001) \cdot \frac{1}{3} = 1.
\end{eqnarray*}

We have the same probability, 2/3, of winning each game and the same
expected return for each game.
}

\problempart What is the variance in each case?  

%\insolutions{\bf NOTE to TAs: the point of this problem is to make sure
%they understand what calculating variance means by doing a concrete
%example - they should be able to use BOTH formulas of variance to do
%this.}
%
\solution{The variances of the two games are very different. We can
compute the $\variance{A}$ by working ``from the inside out'' as
follows:

\begin{eqnarray*}
A - \expect{A}
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        -2 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(A - \expect{A})^2
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        4 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\expect{(A - \expect{A})^2}
        & = &   1 \cdot \frac{2}{3} + 4 \cdot \frac{1}{3} \\
\variance{A} & = & 2.
\end{eqnarray*}

Similarly, we have for $\variance{B}$:
\begin{eqnarray*}
B - \expect{B}
        & = &   \left\{
                \begin{array}{cl}
                        1001 & \text{ with probability } \frac{2}{3} \\
                        -2002 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(B - \expect{B})^2
        & = &   \left\{
                \begin{array}{cl}
                        1,002,001 & \text{ with probability } \frac{2}{3} \\
                        4,008,004 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\expect{(B - \expect{B})^2}
        & = &   1,002,001 \cdot \frac{2}{3} + 4,008,004 \cdot \frac{1}{3} \\
\variance{B} & = & 2,004,002.
\end{eqnarray*}

The variance of Game A is 2 and the variance of Game B is more than
two million!  Intuitively, this means that the payoff in Game A is
usually close to the expected value of \$1, but the payoff in Game B
can deviate very far from this expected value.

High variance is often associated with high risk.  For example, in ten
rounds of Game A, we expect to make \$10, but could conceivably lose
\$10 instead.  On the other hand, in ten rounds of game B, we also
expect to make \$10, but could actually lose more than
\$20,000!
}
\end{problemparts}
\end{problem}

%%---------------------------------------------------------------%%

\begin{problem}
A gambler plays 120 hands of draw poker, 60 hands of black jack,
and 20 hands of stud poker per day.  He wins a hand of draw poker with
probability 1/6, a hand of black jack with probability 1/2, and a hand of
stud poker with probability 1/5.  Assume the outcomes of the card games are
mutually independent.  %He hopes to win 108 hands per day.

\bparts

\ppart What is the expected number of hands the gambler wins in a day?

\solution{
$120(1/6)+60(1/2)+20(1/5)=54$.
}

\ppart What is the variance in the number of hands won per day?

\solution{
The variance can also be calculated using linearity of
variance.  For an individual hand the variance is $p(1-p)$ where $p$ is
the probability of winning.  Therefore the variance is
\[
120(1/6)(5/6) + 60(1/2)(1/2) + 20(1/5)(4/5) = 50/3 + 15 + 16/5 = 250/15 +
225/15 + 48/15 = 523/15 = 34\ 13/15.
\]
}

\ppart What would the Markov bound be on the probability that the
gambler will win 108 hands on a given day?

\solution{
The expected number of ganes won is 54, so
by Markov, $\pr{R \geq 108} \leq 54/108 = 1/2$.
}

\ppart What would the Chebyshev bound be on the probability that the
gambler will win 108 hands on a given day?  You may answer with a
numerical expression that is not completely evaluated.

\solution{
\[
\pr{R - 54 \geq 54} \leq \pr{\abs{R - 54} \geq 54} \leq
\frac{V}{54^2} = \frac{523}{15(54)^2} \approx 0.0196.
\]

A very slightly better bound comes from using the one-sided Chebyshev
bound from Problem Set 11:
\[
\pr{R - 54 \geq 54} \leq \frac{V}{V + 54^2}
= \frac{523}{523 + 15(54)^2} \approx 0.0182.
\]
}
\eparts
\end{problem}


\begin{problem}
Prove that $\variance{X+Y+Z} = \variance{X} + \variance{Y} +
\variance{Z}$, if $X,Y,Z$ are pairwise independent. Explain why
pairwise independence is sufficient.

{\em Reminder:} If two random variable are independent, then $\expect{X_i
X_j} = \expect{X_i} \expect{X_j}$.  Given a set of random variables,
pairwise independence implies that every possible pair of random variables
is independent.

\solution{
Let $R = X + Y + Z$.  We can compute $\expectsq{R}$ as follows:
\begin{eqnarray*}
\expectsq{R}
& = & \left(\expect{X+Y+Z}\right)^2 \\
& = & (\expect{X} + \expect{Y} + \expect{Z})^2 \\
& = & \expectsq{X} + \expectsq{Y} + \expectsq{Z} + 2\expect{X}\expect{Y} + 
       2\expect{X}\expect{Z} + 2\expect{Y}\expect{Z}
\end{eqnarray*}

Computing $\expect{R^2}$ we get:
\begin{eqnarray*}
\expect{R^2} 
& = & \expect{(X+Y+Z)^2}\\
& = & \expect{X^2 + Y^2 + Z^2 + 2XY + 2XZ + 2YZ} \\
& = & \expect{X^2} + \expect{Y^2} + \expect{Z^2} + 2\expect{XY}
      + 2\expect{XZ} + 2\expect{YZ}\\
& = & \expect{X^2}  + \expect{Y^2} + \expect{Z^2} + 2\expect{X}\expect{Y} + 
       2\expect{X}\expect{Z} + 2\expect{Y}\expect{Z}
\end{eqnarray*}

Notice that the last step is only valid because the random variables are
pairwise independent. Finally, we can compute $\variance{R}$.  We can
begin immediately by cancelling out the cross terms leaving us with:

\begin{eqnarray*}
\variance{R}
& = & \expect{R^2} - \expectsq{R}\\
& = & \expect{X^2} + \expect{Y^2} + \expect{Z^2}
        - (\expectsq{X} + \expectsq{Y} + \expectsq{Z}) \\
& = & \expect{X^2} - \expectsq{X} + \expect{Y^2}
      - \expectsq{Y} + \expect{Z^2} - \expectsq{Z} \\
& = & \variance{X} + \variance{Y} + \variance{Z},
\end{eqnarray*}
thus concluding the proof.
}
\end{problem}


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

Notes 13 used the Chebyshev bound to conclude that if a random sample of
3,125 voters is taken, then the fraction of voters in the sample who favor
Gore will, with probability 95/100, be within 0.04 of the actual fraction
who favor Gore among the whole voting population of millions.  Then, using
tighter bounds available for the binomial distribution, it was shown that
a smaller sample -- merely 662 voters -- would actually suffice.  In each
of these calculations, the actual size of the voting population was never
considered because it did not matter.

Suppose you were going to serve as an expert witness in a trial.  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 Gore as
independent coin tosses that a jury might be able to follow:

\begin{quote}
Of the approximately 100,000,000 voters in the US, there are some
\emph{unknown} number, say 51,000,000, who favor Gore.  So in this case,
the \emph{fraction} of voters favoring Gore would be
51,000,000/100,000,000 = 0.51.

To estimate this unknown fraction, we randomly select one person from the
100,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 100,000,000 voters in the US.  Then we would generate a number
between 1 and 100,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.  Picking a person this way amounts to
flipping a coin that had a chance of coming up ``Gore'' that was equal to
the unknown fraction.  In our example, there would be a 51\% chance of the
``coin'' coming up ``Gore'' and a 49\% chance of coming up ``Bush.''  

After we have picked a person and learned their voting preference, 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.  Each pick is like flipping a coin whose probability of coming up
``Gore'' is the same unknown fraction.

Now we all understand that if we keep flipping a coin with a 51\% chance
of coming up Heads, then the more we flip, the closer the fraction of
Heads flipped will be to 51\%.  Mathematical theory lets us calculate us
how many times to flip coins to make the fraction of Heads very likely
close to 51\%, but we need't go into the details of the calculation.

Now suppose we had two coins, say a penny and a nickel, which had the same
51\% probability of coming up Heads.  Then it's not going to make any
difference which coin we use in our coin flips: the number of flips we
need to get the fraction of Heads flipped being very likely close to 51\%
will be the same whether we flip pennies or nickels.

Different size populations correspond to different coins: the nickel might
correspond to selecting a voter from a population 100,000,000 people, and
the dime might correspond to selecting one from a population of 100.  The
same number of flips of pennies or nickels will allow us to estimate the
probability of ``Heads,'' and hence to estimate the fraction of voters
favoring Gore.  All that mattered is that the ``penny'' population had the
same probability of Heads, namely, 51,000,000 out of a population of
100,000,000, as the ``nickel'' population, namely, 51 out of 100.

So the number of ``flips'' needed does not depend on whether we're
flipping a ``51\% penny'' or a ``51\% nickel.''  That is, if two
populations have the same fraction of voters favoring Gore, then \emph{the
number of people we need to poll is the same}, even if the populations are
of very different sizes.
\end{quote}
}
\end{problem}




\iffalse

\begin{problem}
We can generalize the Pairwise Independent Sampling Theorem (\cf the
Appendix) to averages of random variables 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.}

\ppart  Describe some of the applications of such Sampling Theorems.
\eparts
\end{problem}
\fi

\appendix
\section{Appendix}
\setcounter{secnumdepth}{0}
%%%%%%%%%%%%%%%%%%%%%%%% EXPECTATION %%%%%%%%%%%%%%%%%%%%%%%%%%%
The \emph{expectation} of random variable, $R$, is:
\begin{equation*}
\expect{R} \eqdef \sum_{r \in \range{R}} r \cdot \pr{R = r}
\end{equation*}

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

\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
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
\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$.

\iffalse

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


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

