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

%\hidesolutions
%\showsolutions

\begin{document}

\renewcommand{\reading}{Course Notes 12.}

\problemset{10}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem} In a carnival game, the player picks a number between 1
and~6.  The game operator then rolls three dice.  The outcome of the
game is determined as follows:

\begin{itemize}

\item If the player's number comes up once, she wins one dollar.

\item If the player's number comes up twice, she wins two dollars.

\item If the player's number comes up three times, she wins $k$
dollars.

\item If the players's number does not come up at all, she loses a
dollar.

\end{itemize}

\bparts

\ppart What is the player's expected profit as a function of $k$?


\solution{
There are $6^3 = 216$ equally likely outcomes.  In particular:

\begin{itemize}

\item There are $3 \cdot 5^2 = 75$ outcomes where the player's number
comes up just once.  (The die with the player's number can be chosen
in 3 ways, and the other two dice can come up 5 ways each.)

\item There are $3 \cdot 5 = 15$ outcomes where the player's number
comes up twice.  (The two dice with the player's number can be chosen
in 3 ways, and the other die can come up 5 ways.)

\item There is only 1 outcome where the player's number comes up on
all three dice.

\item There are $5^3$ outcomes where the player's number does not come
up at all.  (Each die can show any of the other 5 numbers.)

\end{itemize}

Therefore, the expected profit is:

\begin{eqnarray*}
\exp{\text{profit}}
	& = &	\frac{75}{216} \cdot 1 +
		\frac{15}{216} \cdot 2 +
		\frac{1}{216} \cdot k +
		\frac{125}{216} \cdot -1 \\
	& = &	\frac{k - 20}{216}
\end{eqnarray*}
}

\ppart For what value of $k$ is the game fair?

\solution{The expected payoff is zero for $k = 20$.  The player must
be paid \$20 when all three dice match in order to make the game
fair.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem} Each 6.042 final exam will be graded according to a
rigorous procedure:

\begin{itemize}

\item With probability $\frac{4}{7}$ the exam is graded by a {\em TA},
with probability $\frac{2}{7}$ it is graded by a {\em lecturer}, and
with probability $\frac{1}{7}$, it is accidentally dropped behind the
radiator and arbitrarily given a score of 84.

\item {\em TAs} score an exam by scoring each problem individually and
then taking the sum.

\begin{itemize}

\item There are ten true/false questions worth 2 points each.  For
each, full credit is given with probability $\frac{3}{4}$, and no
credit is given with probability $\frac{1}{4}$.

\item There are four questions worth 15 points each.  For each, the
score is determined by rolling two fair dice, summing the results, and
adding 3.

\item The single 20 point question is awarded either 12 or 18 points
with equal probability.

\end{itemize}

\item {\em Lecturers} score an exam by rolling a fair die twice,
multiplying the results, and then adding a ``general impression''
score.

\begin{itemize}

\item With probability $\frac{4}{10}$, the general impression score is 40.

\item With probability $\frac{3}{10}$, the general impression score is 50.

\item With probability $\frac{3}{10}$, the general impression score is 60.

\end{itemize}

\end{itemize}

Assume all random choices during the grading process are mutually
independent.

\bparts

\ppart What is the expected score on an exam graded by a TA?

\solution{ Let the random variable $T$ denote the score a TA would
give.  By linearity of expectation, the expected sum of the problem
scores is the sum of the expected problem scores.  Therefore, we have:
\begin{eqnarray*}
\expect{T}	& = &	10 \cdot \expect{\text{T/F score}} +
		4 \cdot \expect{\text{15pt prob score}} +
		\expect{\text{20pt prob score}} \\
	& = &
	10 \cdot \left(\frac{3}{4} \cdot 2 + \frac{1}{4} \cdot 0 \right)
	+ 4 \cdot \left( 2 \cdot \frac{7}{2} + 3 \right)
	+ \left(\frac{1}{2} \cdot 12 + \frac{1}{2} \cdot 18 \right) \\
	& = &	10 \cdot \frac{3}{2} + 4 \cdot 10 + 15 \\
	& = & 	70
\end{eqnarray*}
}

\ppart What is the expected score on an exam graded by a
lecturer?

\solution{
Now we find the expected value of $L$, the score a lecturer would
give.  Employing linearity again, we have:
\begin{eqnarray*}
\expect{L}	& = &	\expect{\text{product of dice}} + \expect{\text{general impression}} \\
	& = &	\left(\frac{7}{2}\right)^2 + \left(
		\frac{4}{10} \cdot 40 + 
		\frac{3}{10} \cdot 50 + 
		\frac{3}{10} \cdot 60 \right) \\
	& = &	\frac{49}{4} + 49 \\
	& = &	61 \frac{1}{4}
\end{eqnarray*}
}

\ppart What is the expected score on a 6.042 final exam?

\solution{Let $X$ equal the true exam score.  The total expectation
law implies:
\begin{eqnarray*}
\expect{X}	& = &	\frac{4}{7} \cdot \expect{T} +
		\frac{2}{7} \cdot \expect{L} +
		\frac{1}{7} \cdot 84 \\
	& = &	\frac{4}{7} \cdot 70 +
		\frac{2}{7} \cdot \left(\frac{49}{4} + 49\right) +
		\frac{1}{7} \cdot 84 \\
	& = &	40 + \frac{7}{2} + 14 + 12 \\
	& = &	69 \frac{1}{2}
\end{eqnarray*}
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem} In a certain card game, each card has a point value.

\begin{itemize}

\item Numbered cards in the range 2 to 9 are worth five points each.

\item The card numbered 10 and the face cards (jack, queen, king) are
worth ten points each.

\item Aces are worth fifteen points each.

\end{itemize}

\bparts

\ppart Suppose that you shuffle a 52-card deck.  What is the expected
total point value of the top three cards?

\solution{Let the random variable $X$ be the total point value of the
top three cards.  Then we can write:
\[
X  =  X_1 + X_2 + X_3
\]
where the random variables $X_1$, $X_2$, and $X_3$ are the point values
of the first, second, and third cards.  By the definition of
expectation:
\begin{eqnarray*}
\expect{X_i}
	& = &	\sum_{r \in X_i(S)} r \cdot \pr{X_i = r} \\
	& = &	5 \cdot \frac{8}{13} + 10 \cdot \frac{4}{13} +
		15 \cdot \frac{1}{13} \\
	& = &	\frac{95}{13}
\end{eqnarray*}

Now we can solve the problem by taking the expected value of both
sides of our original equation and then using linearity of
expectation:
\begin{eqnarray*}
\expect{X}	& = &	\expect{X_1 + X_2 + X_3} \\
	& = &	\expect{X_1} + \expect{X_2} + \expect{X_3} \\
	& = &	\frac{95}{13} + \frac{95}{13} + \frac{95}{13} \\
	& = &	\frac{285}{13}
\end{eqnarray*}
}

\ppart Suppose that you throw out all the red cards and shuffle the
remaining 26-card, all-black deck.  Now what is the expected total
point value of the top three cards?  (Note that drawing three aces,
for example, is now impossible!)

\solution{The expected point value is the same as before, since
expected point value of a single card is unchanged.  Nothing in our
solution assumed a 52 card deck.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem} A classroom has sixteen desks arranged as shown below.

\[
\begin{array}{cccc}
\fbox{ } & \fbox{ } & \fbox{ } & \fbox{ } \\
\fbox{ } & \fbox{ } & \fbox{ } & \fbox{ } \\
\fbox{ } & \fbox{ } & \fbox{ } & \fbox{ } \\
\fbox{ } & \fbox{ } & \fbox{ } & \fbox{ }
\end{array}
\]

If there is a girl in front, behind, to the left, or to the right of a
boy, then the two of them {\em flirt}.  One student may be in multiple
flirting couples; for example, a student in a corner of the classroom
can flirt with up to two others, while a student in the center can
flirt with as many as four others.

Suppose that desks are occupied by boys and girls with equal
probability and mutually independently.  What is the expected number
of flirting couples?  Justify your answer.

\end{problem}

\solution{First, let's count the number of pairs of adjacent desks.
There are three in each row and three in each column.  Since there are
four rows and four columns, there are $3 \cdot 4 + 3 \cdot 4 = 24$
pairs of adjacent desks.

Number these pairs of adjacent desks from 1 to 24.  Let $F_i$ be an
indicator for the event that occupants of the desks in the $i$-th pair
are flirting.  The probability we want is then:
\begin{eqnarray*}
\expect{\sum_{i=1}^{24} F_i}
	& = &	\sum_{i=1}^{24} \expect{F_i} \\
	& = &	\sum_{i=1}^{24} \pr{F_i = 1}
\end{eqnarray*}

The first step uses linearity of expectation, and the second step uses
the fact that the expecatation of an indicator is equal to the
probability that it is 1.

The occupants of adjacent desks are flirting if the first holds a girl
and the second a boy or vice versa.  Each of these events happens with
probability $\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$, and so the
probability that the occupants flirt is $\pr{F_i = 1} = \frac{1}{4} +
\frac{1}{4} = \frac{1}{2}$.  Plugging this into the previous
expression gives:
\begin{eqnarray*}
\expect{\sum_{i=1}^{24} F_i}
	& = &	\sum_{i=1}^{24} \pr{F_i = 1} \\
	& = &	24 \cdot \frac{1}{2} \\
	& = &	12
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
There are about 250,000,000 people in the United States who might use
a phone.  Assume that each person is on the phone during each minute
mutually independently with probability $p = 0.01$.

(To keep the problem simple, we are putting aside the fact that people
are on the phone more often at certain times of day and on certain
days of the year.)

\bparts

\ppart What is the expected number of people on the phone at a given
moment?

\solution{Let $I_i$ be an indicator for the event that the $i$-th
person is one the phone.  The number of people on the phone is then:

\[
\sum_{i=1}^{250,000,000} I_i
\]

The expectation of this sum is $250,000,000 \cdot 0.01 = 2,500,00$ by
linearity of expectation.
}

\ppart Suppose that we construct a phone network whose capacity is a
mere \textbf{one percent} above the expectation.  Upper bound the
probability that the network is overloaded in a given minute.  (Use
the approximation formula given in the notes.  You may need to
evaluate this expression in a clever way because of the size of
numbers involved.  For example, you could first evaluate the {\em
logarithm} of the given expression.)

\solution{The network is overloaded if the fraction of people calling
is greater than $1.01 \cdot 0.01 = 0.0101$.  In complementary terms,
the network is overloaded if the fraction of people {\em not} calling
is less than $1 - 0.0101 = 0.9899$.  Define the following variables:
\begin{eqnarray*}
n & \eqdef & 250,000,000 \quad \text{people in the US} \\
p & \eqdef & 0.99 \quad \text{prob. not on phone} \\
\alpha & \eqdef & 0.9899 \quad \text{min. allowable fraction not on phone}
\end{eqnarray*}

In these terms, the solution to the problem is $F_{n,p}(\alpha n)$.
We can upper bound this approximately using the formula from the
notes:
\[
F_{n,p}(\alpha n) \approx
	\frac{1 - \alpha}{1 - \alpha / p} \cdot
	\frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}} 
	\cdot p^{\alpha n} (1-p)^{(1 - \alpha) n} \\
\]

By first evaluating the logarithm of this expression, we find that
this is about $e^{-120}$.}

\ppart What is the expected number of minutes (approximately) until
the system is overloaded for the first time?

\solution{Applying the ``expected time to failure'' formula with
probability $p = e^{-120}$ gives $1 / p = e^{120}$.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
The Queen of Neverwas\footnote{The alter-ego of Nancy Plimpton, age 7,
of Ames, Iowa.} wants there to be more girls than boys in her
``Queendom''.  She plans to implement whichever of the following
policies most effectively skews the gender ratio:

\begin{enumerate}

\item A couple must have children until either they have more girls
than boys or they have a total of three children, whichever comes
first.  (This means that couples ``quit while they're ahead''.)

\item A couple must have children until they have one girl and then
stop having children.  (This ensures that every family has at least
one girl, while there is no comparable assurance for boys.)

\end{enumerate}

For each policy, compute the expected number of girls in a family and
the expected number of boys.  Which policy do you recommend to the
Queen?

\solution{The possible outcomes for the first policy are listed in the
table below.

\[
\begin{array}{lccc}
\text{family} & \text{prob.} & \text{\# girls} & \text{\# boys} \\
G	& 1/2	& 1	& 0 \\
BGG	& 1/8	& 2	& 1 \\
BBG	& 1/8	& 1	& 2 \\
BGB	& 1/8	& 1	& 2 \\
BBB	& 1/8	& 0	& 3
\end{array}
\]

Therefore, the expected number of girls is:

\begin{eqnarray*}
\expect{\text{\# girls}}
	& = &	\frac{1}{2} \cdot 1 + \frac{1}{8} \cdot 2 +
		\frac{1}{8} \cdot 1 + \frac{1}{8} \cdot 1 +
		\frac{1}{8} \cdot 0 \\
	& = &	1
\end{eqnarray*}

The expected number of boys is:

\begin{eqnarray*}
\expect{\text{\# boys}}
	& = &	\frac{1}{2} \cdot 0 + \frac{1}{8} \cdot 1 +
		\frac{1}{8} \cdot 2 + \frac{1}{8} \cdot 2 +
		\frac{1}{8} \cdot 3 \\
	& = &	1
\end{eqnarray*}

The expected number of girls in a family is equal to the expected
number of boys, so the first policy doesn't work.

For the second policy, we can regard having a child as a trial, where
having a girl is a ``failure''.  Then, according to the ``mean time to
failure'' formula, the expected number of children in a family is:

\begin{eqnarray*}
\expect{\text{\# children}}
	& = &	\frac{1}{1/2} \\
	& = &	2
\end{eqnarray*}

Since every family has exactly 1 girl, the expected number of girls is
1.  Therefore, by linearity of expectation, the expected number of
boys is also 1.  Thus, the second policy doesn't work either!  Queen
Nancy is out of luck!}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
