\documentclass[twoside,12pt]{article}

\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\topmargin}{0 in}
\setlength{\headheight}{0.25 in}
\setlength{\headsep}{0.25 in}
\setlength{\evensidemargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\parskip}{1ex}

\newcommand{\heading}[1]{\vspace{3ex} {\Large {\em #1}}}
\newcommand{\subheading}[1]{\vspace{3ex} {\large {\em #1}}}

\usepackage{graphics}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}

\newenvironment{comment}[1]{}{}
\newenvironment{proof}{\noindent {\em Proof.}}{$\Box$}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\pr}[1]{\Pr\{#1\}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }

\begin{document}

\begin{center}
{\Large Notes for Tutorial 4} \\
6.042 - February 28 and March 3, 2003 \\
\bigskip
\end{center}

Students should come away knowing that the expectation of a product is
the product of the expectations for independent random variables.
They should also know that the expectation of a quotient is NOT the
quotient of the expectations.

Here are the topics covered here.

\begin{itemize}
\item Expectation of a product.
\item $k$ vs. $2k$ paradox.
\item Leader election.
\item 3-way birthdays.
\end{itemize}

I've appended the problems on separate pages so that you can easily
make photocopies to hand out, if you want to.

\section{Expectation of a Product}

We have seen that for all random variables $X$ and $Y$:

\beqn
\ex{X + Y} & = & \ex{X} + \ex{Y} \\
\ex{a X} & = & a \ex{X}
\eeqn

Now let's look at the expectation of a product of random variables.

\begin{theorem}
For all independent random variables $X$ and $Y$:

\beqn
\ex{X \cdot Y} & = & \ex{X} \cdot \ex{Y}
\eeqn
\end{theorem}

Emphasize the difference between the expectation of a sum (where
independence is NOT required) and the expectation of a product (where
independence IS required).

\begin{proof}
Let $S$ be the sample space.  We can argue as follows:

\beqn
\ex{X \cdot Y}
	& = &	\sum_{s \in S} X(s) Y(s) \pr{s} \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		\sum_{r_2 \in \text{Image}(Y)}
		\sum_{s \in S: X(s) = r_1 \text{ and } Y(s) = r_2}
		X(s) Y(s) \pr{s} \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		\sum_{r_2 \in \text{Image}(Y)} r_1 r_2 \cdot \left(
		\sum_{s \in S: X(s) = r_1 \text{ and } Y(s) = r_2}
		\pr{s} \right) \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		\sum_{r_2 \in \text{Image}(Y)}
		r_1 r_2 \pr{X = r_1 \cap Y = r_2} \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		\sum_{r_2 \in \text{Image}(Y)}
		r_1 r_2 \cdot \pr{X = r_1} \cdot \pr{Y = r_2} \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		r_1 \cdot \pr{X = r_1} \cdot
		\left(
		\sum_{r_2 \in \text{Image}(Y)}
		r_2 \cdot \pr{Y = r_2}
		\right) \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		r_1 \cdot \pr{X = r_1} \cdot \ex{Y} \\
	& = &	\ex{Y} \cdot \sum_{r_1 \in \text{Image}(X)}
		r_1 \cdot \pr{X = r_1} \\
	& = &	\ex{Y} \cdot \ex{X}
\eeqn

You might challenge the students to justify each step of this proof.
I've printed it on a second page that you can copy and hand out if you
like.

The first equation uses one definition of expectation.  Since we need
to write $X(s)$ and $Y(s)$ here, it might be a good time to remind
students that random variables are functions defined on the sample
space.

In the second step, we just reorganize the way we sum over outcomes in
the sample space.  It may be helpful to draw the sample space cut by
vertical lines into regions where $X$ is constant.  The outer sum runs
over these regions.  Then dice the first slab with horizontal lines
into small chunks where $Y$ is constant.  The second sum runs over
these chunks.  Then put some dots in a chunk to indicate outcomes.
The final sum runs over outcomes within a single chunk.

The third step uses the fact that in the inner sum, $X(s) = r_1$ and
$Y(s) = r_2$.  We also pull these values out of the inner sum.

In the fourth step, we use the definition of the probability of an
event as the sum of the probabilities of the outcomes it contains.

The fifth step uses independence.  Next, we pull out everything
related to $r_1$ out of the innermost sum.  The inner sum becomes the
definition of the expectation of $Y$.  Pulling out this constant,
we're left with the definition of the expectation of $X$.
\end{proof}

\section{$k$ vs $2k$}

I have two envelopes.  One envelope has $k$ dollars and the other has
$2k$ dollars.  (Make sure $k$ is even!)  Let a student pick an
envelope at random and open it.

Now give the student the option to switch to the other envelope.
Explain that this makes perfect sense.  Since the student sees $x$
dollars in his current envelope, his expected profit if he stays is
exactly $x$ dollars.

On the other hand, his expected wealth if he switches is:

\beqn
\ex{\text{switch wealth}}
	& = &	\frac{1}{2} \cdot (2x) + \frac{1}{2} \cdot \frac{x}{2} \\
	& = &	\frac{5}{4} x
\eeqn

There is half a chance that he gets double the money and half a chance
that he gets half the money.  So the equation above just uses the
definition of expected value.  Obviously, he should switch, right?!
Is this argument valid?  Give students plenty of time to argue over
this one.  (Be sure they realize that it wasn't necessary for him even
to open the first envelope; the argument above remains valid even if
he doesn't know how much money there is inside.)

The sample space in this experiment consists of two outcomes: either
the student picks $k$ or $2k$.  Here $k$ is not a random variable; it
is just a quantity unknown to the student.  Once a student picks an
envelope, the experiment is over.  The student still doesn't know how
much money is in the other envelope--- no more than he knows the 500th
digit of pi.  But it isn't a random variable whose value is to be
determined by some future experiment any more than the 500th digit of
pi is.  It's a random variable whose value is known, since we've
reached an outcome.  To make this point, pointed look in the
envelope.)

The expectation calculation above is of the correct form-- which makes
it tempting-- but is not relevant to this experiment.  It would be
appropriate if, after the player picked an envelope, I flipped a coin
to decide whether to put half as much money or twice as much money in
the other envelope.  But that is not the experiment at hand.

The expectation calculation has a second false appeal that makes it
even more enticing.  Let the random variable $P$ be the amount of
money in the envelope the student picks, and let $N$ be the amount in
the envelope not picked.  (These are legitimate random variables, but
their value is determine when he picks an envelope; at that point, the
experiment has an outcome.)

Now it is very tempting to compute:

\beqn
\ex{N / P}
	& = &	\frac{1}{2} \cdot 2 + \frac{1}{2} \cdot \frac{1}{2} \\
	& = &	\frac{5}{4}
\eeqn

In other words the expected ratio of money in the unpicked envelope to
the money in the picked envelope is $5/4$!  It looks like you should
switch!  But, then again:

\beqn
\ex{P / N}
	& = &	\frac{1}{2} \cdot 2 + \frac{1}{2} \cdot \frac{1}{2} \\
	& = &	\frac{5}{4}
\eeqn

Uh-oh.  Does this mean that we should switch back?  Then problem is
that we are assuming:

\beqn
\ex{N} & = & \ex{P} \cdot \ex{N / P}
\eeqn

But this is false!  The expectation of a quotient is not the
quotient of the expectations.  Even though the ratios we computed
above are greater than 1, switching doesn't help!  Switching {\em
would} be wise if $\ex{U} / \ex{P}$ were greater than 1.  But this is
not the case; the expected value of both $U$ and $P$ is simply
$\frac{3}{2} k$, and so the ratio of the expectations is $1$.  So
switching doesn't help.

\subsection{The expectation of a quotient}

If student come away a bit befuddled, they're in the same boat as me.
But they should come away knowing one fact: {\em the expectation of a
quotient is NOT the quotient of the expectations--- even for
independent random variables}.

This can be illustrated more clearly by a separate example.  I have a
coin labeled 1 on one side and 2 on the other.  I flip it twice.
Assume that the outcomes are independent.  Let $X$ be the value shown
on the first flip, and let $Y$ be the value shown on the second.

Now we have:

\beqn
\ex{X}	& = & \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 2 \\
	& = & \frac{3}{2} \\
\ex{Y}	& = & \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 2 \\
	& = & \frac{3}{2} \\
\frac{\ex{X}}{\ex{Y}} & = & 1 \\
\eeqn

But on the other hand:

\beqn
\ex{X / Y}
	& = & \frac{1}{4} \cdot \frac{1}{1} +
		\frac{1}{4} \cdot \frac{1}{2} + \\
	&   & \frac{1}{4} \cdot \frac{2}{1} +
		\frac{1}{4} \cdot \frac{2}{2} \\
	& = &	\frac{9}{8}
\eeqn

\section{Leader Election}

Suppose that a class of $n$ students wants to elect a leader by an
unusual process.  The class may select a coin with whatever bias they
like; that is, they can make the probability of flipping heads equal
to $p$ for whatever value of $p$ they choose.  Then everyone in the
class flips the coin.  If exactly one student flips heads, he or she
is declared the leader.  If no student flips heads or more than one
student flips heads, then then procedure is declared a failure.

How should the students choose $p$ so that the procedure is most
likely to succeed?  What is the probability of success if there are
$n$ students?  Give a good approximation for the probability of
success when the number of student is large.

The probability of success is:

\[
n p (1-p)^{n-1}
\]

Maximize this by setting the derivative with respect to $p$ equal to zero:

\beqn
n p \cdot (- (n-1) (1-p)^{n-2}) + n \cdot (1-p)^{n-1} & = & 0 \\
p (1 - n) + (1-p) & = & 0 \\
p n & = & 1 \\
p & = & 1 / n
\eeqn

With $p$ chosen in this way, the probability of success becomes:

\beqn
n (1/n) (1 - 1/n)^{n-1} & \rightarrow & \frac{1}{e}
\eeqn

\section{3-Way Birthdays}

A class has 100 students.  What is the expected number of subsets of
three students that share the same birthday?  Assume that all
birthdays are equally likely, students' birthdays are independent, and
no one was born on leap day.

The number of subsets of three students is:

\[
\frac{120 \cdot 119 \cdot 118}{3 \cdot 2 \cdot 1}
\]

Each set of three students has a common birthday with probability
$(1/365)^2$.  Therefore, by linearity of expectation, the expected
number of subsets of three students with the same birthday is:

\beqn
\frac{120 \cdot 119 \cdot 118}{3 \cdot 2 \cdot 1 \cdot 365^2}
	& = &	2.108\ldots
\eeqn

So in 6.042 this term, we should expect 2 such triples!

\newpage

\begin{theorem}
For all independent random variables $X$ and $Y$:

\beqn
\ex{X \cdot Y} & = & \ex{X} \cdot \ex{Y}
\eeqn
\end{theorem}

\begin{proof}
Let $S$ be the sample space.

\beqn
\ex{X \cdot Y}
	& = &	\sum_{s \in S} X(s) Y(s) \pr{s} \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		\sum_{r_2 \in \text{Image}(Y)}
		\sum_{s \in S: X(s) = r_1 \text{ and } Y(s) = r_2}
		X(s) Y(s) \pr{s} \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		\sum_{r_2 \in \text{Image}(Y)} r_1 r_2 \cdot \left(
		\sum_{s \in S: X(s) = r_1 \text{ and } Y(s) = r_2}
		\pr{s} \right) \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		\sum_{r_2 \in \text{Image}(Y)}
		r_1 r_2 \pr{X = r_1 \cap Y = r_2} \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		\sum_{r_2 \in \text{Image}(Y)}
		r_1 r_2 \cdot \pr{X = r_1} \cdot \pr{Y = r_2} \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		r_1 \cdot \pr{X = r_1} \cdot
		\left(
		\sum_{r_2 \in \text{Image}(Y)}
		r_2 \cdot \pr{Y = r_2}
		\right) \\
	& = &	\sum_{r_1 \in \text{Image}(X)}
		r_1 \cdot \pr{X = r_1} \cdot \ex{Y} \\
	& = &	\ex{Y} \cdot \sum_{r_1 \in \text{Image}(X)}
		r_1 \cdot \pr{X = r_1} \\
	& = &	\ex{Y} \cdot \ex{X}
\eeqn
\end{proof}

\bigskip

\centerline{Justify each step in this proof.}

\newpage

Suppose that a class of $n$ students wants to elect a leader by an
unusual process.  The class may select a coin with whatever bias they
like; that is, they can make the probability of flipping heads equal
to $p$ for whatever value of $p$ they choose.  Then everyone in the
class flips the coin.  If exactly one student flips heads, he or she
is declared the leader.  If no student flips heads or more than one
student flips heads, then then procedure is declared a failure.

How should the students choose $p$ so that the procedure is most
likely to succeed?  What is the probability of success if there are
$n$ students?  Give a good approximation for the probability of
success when the number of student is large.

\newpage

A class has 100 students.  What is the expected number of subsets of
three students that share the same birthday?  Assume that all
birthdays are equally likely, students' birthdays are independent, and
no one was born on leap day.

\end{document}
