\documentclass[12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\recitation{21}{December 1, 2004}

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

\begin{problem}
A couple decides to have children until they have both a boy and a
girl.  What is the expected number of children that they'll end up
with?  Assume that each child is equally likely to be a boy or a girl
and genders are mutually independent.
\end{problem}

\solution{There are many ways to solve this problem.  We'll do it from
first principles.

Suppose that a couple has children until they have both a boy and a girl.
A tree diagram for this experiment is shown below.
%
\begin{center}
\includegraphics{boygirl-tree}
\end{center}
%
Let the random variable $R$ be the number of children the couple has.
From the definition of expectation, we have:
%
\begin{align}
\ex{R}
    & = \sum_{w \in S} R(w) \cdot \pr{w} \notag\\
    & = \left(2 \cdot \frac{1}{4} + 3 \cdot \frac{1}{8} + 4 \cdot \frac{1}{16} + \ldots\right) + \left(2 \cdot \frac{1}{4} + 3 \cdot \frac{1}{8} + 4 \cdot \frac{1}{16} + \ldots\right) \notag\\
    & = 2 \left(2 \cdot \frac{1}{4} + 3 \cdot \frac{1}{8} + 4 \cdot \frac{1}{16} + \ldots\right).\label{2s}
\end{align}
%
The only difficulty is evaluating the sum.  We can use the general
formula
%
\[
1 + 2 r + 3 r^2 + 4 r^3 + \ldots = \frac{1}{(1-r)^2}
\]
%
which is obtained by differentiating the formula for the sum of an
infinite geometric series.  Setting $r = 1/2$ gives:
%
\[
1 + 2 \cdot \frac{1}{2} + 3 \cdot \frac{1}{4} + 4 \cdot \frac{1}{8} + \ldots
    = 4
\]
%
We have to tweak this a little to get the sum we're interested in.
Subtracting 1 from each side and then dividing both sides by 2 does
the trick:
%
\[
2 \cdot \frac{1}{4} + 3 \cdot \frac{1}{8} + 4 \cdot \frac{1}{16} + \ldots
    = \frac{4 - 1}{2} = \frac{3}{2}
\]
So from~\eqref{2s} we have
\[
\ex{R} = 2\paren{\frac{3}{2}} = 3.
\]

A much simpler approach uses the fact that the ``mean time to failure'' is
$1/p$ where $p$ is the probability of failure in one step.  If we consider
having a child of opposite sex to the first a ``failure'' of that child,
then the mean time to failure is the expected number of children after the
first until the couple has both a boy and a girl.  But the probability of
a failure at the $k$th child after the first is 1/2 for all $k\geq 1$.  So
the expected number of children after the first is 1/(1/2) = 2, and the
expected number of children including the first is 1+2 =3.
}

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

\newpage

\begin{problem} A classroom has sixteen desks arranged as shown below.
%
\begin{center}
\begin{picture}(270,198)
% \put(0,0){\dashbox(270,198){}} % bounding box
\multiput(0,0)(72,0){4}{\framebox(54,36){}}
\multiput(0,54)(72,0){4}{\framebox(54,36){}}
\multiput(0,108)(72,0){4}{\framebox(54,36){}}
\multiput(0,162)(72,0){4}{\framebox(54,36){}}
\end{picture}
\end{center}
%
If there is a girl in front, behind, to the left, or to the right of a
boy, then the two of them \textit{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?
\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{align*}
\ex{\sum_{i=1}^{24} F_i}
	& = \sum_{i=1}^{24} \ex{F_i} \\
	& = \sum_{i=1}^{24} \pr{F_i = 1}
\end{align*}
%
The first step uses linearity of expectation, and the second 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{align*}
\ex{\sum_{i=1}^{24} F_i}
	& = \sum_{i=1}^{24} \pr{F_i = 1} \\
	& = 24 \cdot \frac{1}{2} \\
	& = 12
\end{align*}
}

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

\newpage

\begin{problem}
There is a nice formula for the expected value of a random variable
$R$ that takes on only nonnegative integer values:
%
\[
\ex{R} = \sum_{k=0}^{\infty} \pr{R > k}
\]

\insolutions{
\begin{proof}
\iffalse
We will begin with the right-hand expression and transform it into
$\ex{R}$.  Because $R$ is natural number valued, we can expand $\pr{R
> i}$ into a series:
\[
\pr{R > i} = \pr{R = i+1} + \pr{R = i+2} + \pr{R = i+3} + \cdots
\]
So,\fi

\begin{eqnarray*}
\sum_{i=0}^{\infty} \pr{R > i}
        & = & \underbrace{\pr{R = 1} +  \pr{R = 2} + \pr{R = 3} + \cdots}_{\pr{R > 0}} \\
        &   & \qquad\qquad\quad
              +\underbrace{\pr{R = 2} + \pr{R = 3} + \cdots}_{\pr{R > 1}} \notag\\
        &   & \qquad\qquad\qquad\qquad\quad\ \ \ \quad
	      +\underbrace{\pr{R = 3} + \cdots}_{\pr{R > 2}} \notag \\
        &   & \qquad\qquad\qquad\qquad\qquad\qquad\qquad \vdots\\
        & = &  \pr{R = 1} + 2 \cdot \pr{R = 2} + 3 \cdot \pr{R = 3} + \cdots \\
        & = &  \ex{R}.
\end{eqnarray*}

\end{proof}
}

%
Suppose we roll 6 fair, independent dice.  Let $R$ be the
\textit{largest} number that comes up.  Use the formula above to
compute $\ex{R}$.
\end{problem}

\solution{The first task is to compute $\pr{R > k}$; that is, the
probability that \textit{some} die is greater than $k$.  Let's switch
to computing the probability of the complementary event:
%
\[
\pr{R > k} = 1 - \pr{R \leq k}
\]
%
Now $\pr{R \leq k}$ is the probability that all the dice show numbers
in the set $\set{1, \ldots k}$.  If $k \geq 6$, then this probability
is 1.  For smaller $k$, the probability that \textit{one} die shows a
value in this range is $k / 6$.  Since the dice are independent, the
probability that \textit{all 6} dice are in this range is $(k/6)^6$.
Thus, we have:
%
\begin{align*}
\ex{R}
    & = \sum_{k=0}^{\infty} \pr{R > k} \\
    & = 1+ \paren{1 - \paren{\frac{1}{6}}^6} + 
        \paren{1 - \paren{\frac{2}{6}}^6} + \ldots +
        \paren{1 - \paren{\frac{6}{6}}^6} \\
    & = 7 - \frac{1^6 + 2^6 + 3^6 + 4^6 + 5^6 + 6^6}{6^6}
\end{align*}
}

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

\newpage

\begin{problem}
Here are seven propositions:
%
\[
\begin{array}{rcrcr}
x_1 & \vee & x_3 & \vee & \neg x_7 \\
\neg x_5 & \vee & x_6 & \vee & x_7 \\
x_2 & \vee & \neg x_4 & \vee & x_6 \\
\neg x_4 & \vee & x_5 & \vee & \neg x_7 \\
x_3 & \vee & \neg x_5 & \vee & \neg x_8 \\
x_9 & \vee & \neg x_8 & \vee & x_2 \\
\neg x_3 & \vee & x_9 & \vee & x_4
\end{array}
\]
%
Note that:

\begin{enumerate}

\item Each proposition is the OR of three terms of the form $x_i$ or
the form $\neg x_i$.

\item The variables in the three terms in each proposition are all
different.

\end{enumerate}

\noindent Suppose that we assign true/false values to the variables
$x_1, \ldots, x_9$ independently and with equal probability.

\bparts

\ppart What is the expected number of true propositions?

\solution[\vspace{3in}]{
Each proposition is true unless all three of its terms are false.
Thus, each proposition is true with probability:
%
\[
1 - \paren{\frac{1}{2}}^3 = \frac{7}{8}
\]

Let $T_i$ be an indicator for the event that the $i$-th proposition is
true.  Then the number of true propositions is $T_1 +
\ldots + T_7$ and the expected number is:
%
\begin{align*}
\ex{T_1 + \ldots + T_7}
    & = \ex{T_1} + \ldots + \ex{T_7} \\
    & = 7/8 + \ldots + 7/8 \\
    & = 49/8 = 6 \frac{1}{8}
\end{align*}}

\ppart Use your answer to prove that there exists an assignment to the
variables that makes \textit{all} of the propositions true.

\solution{A random variable can not always be less than its
expectation, so there must be some assignment such that:
%
\[
T_1 + \ldots T_7 \geq 6 \frac{1}{8}
\]
%
This implies that $T_1 + \ldots + T_7 = 7$ for at least one outcome.
This outcome is an assignment to the variables such that all of the
propositions are true.}

\eparts

\end{problem}

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

\end{document}
