\documentclass[12pt,oneside]{article}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}

\begin{document}

%\examinitials{Quiz 1}{March 5, 2003}
%\newcommand{\solution}[1]{}
%\newcommand{\examonly}[1]{#1}

\exam{Quiz 1 Solutions}{March 7, 2003}
\newcommand{\solution}[1]{\bigskip \textbf{Solution.} #1}
\newcommand{\examonly}[1]{}

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

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

\examonly{

\setcounter{page}{0}

\vspace{0.5in}

{\bf Write your name here and on each page:} \underline{\hspace{2.5in}}

\vspace{0.2in}

Circle the name of your tutor:

\begin{center}
\begin{tabular}{ccccc}
\\
Sam Daitch & \hspace{0.5in} & Pedro Felzenszwalb & \hspace{0.5in}
	& Blaise Gassend \\ \\
Jon Jackson & & Attila Kondacs & & Min Wu
\end{tabular}
\end{center}

\vspace{0.25in}

\begin{itemize}
\item This exam is closed book.  Calculators and computers are not
allowed.

\item You may use one handwritten page of notes.  A photocopy of
handwritten notes is not acceptable.

\item Show your work as fully and as clearly as possible so that
partial credit may be given.

\item Write your solutions in the space provided.  If you run out of
space, use the back of the page.

\item Do not discuss this exam with students who have not yet taken
it.  Do not leave with a copy of the exam under any circumstances.
\end{itemize}

\vspace{0.5in}

\centerline{\textbf{Good luck!}}

\vspace{0.5in}

\[
\begin{array}{|c|c|c|} \hline
\text{Problem} & \text{Points} & \text{Score} \\
 \hline 1 & 20 & \\
 \hline 2 & 15 & \\
 \hline 3 & 15 & \\
 \hline 4 & 15 & \\
 \hline 5 & 20 & \\
 \hline 6 & 15 & \\
 \hline \text{TOTAL} & 100 & \\ \hline
\end{array}
\]

}

\begin{problems}

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

\examonly{\newpage}

\newcommand{\tf}[1]{
    \hspace{0.2in}
    \textbf{true}
    \hspace{0.2in}
    \textbf{false}
    \hspace{0.2in}
    \parbox[t]{4.6in}{#1}}

\problem {\bf [20 pts]\ } Next to each statement, circle either {\bf
true} or {\bf false}.

\begin{enumerate}

\item \tf{If $A$ and $B$ are events and $\pr{A \cap B} = 0$, then they
are necessarily independent.}

\item \tf{$1 + 3 + 3^2 + 3^3 + \ldots + 3^{99} \geq 3^{100} / 2$.}

\item \tf{For every pair of random variables $X$ and $Y$, $\ex{X - Y}
= \ex{X} - \ex{Y}$.}

\item \tf{If $X$ and $Y$ are independent random variables, then $\ex{X
\cdot Y} = \ex{X} \cdot \ex{Y}$.}

\item \tf{In five independent flips of a fair coin, the sequence of
results $TTHTH$ is more likely than the sequence $HHHHH$.}

\item \tf{For all independent random variables $X$ and $Y$ such that
$\pr{Y \neq 0} = 1$, $\ex{X/Y} = \ex{X} / \ex{Y}$.}

\item \tf{For all events $A$ and $B$, $\pr{A \cup B} + \pr{A \cap B} =
\pr{A} + \pr{B}$.}

\item \tf{For all events $A$ and $B$ such that $A \subseteq B$ and
$\pr{B} > 0$, $\pr{A} = \pr{A \mid B} \cdot \pr{B}$.}

\item \tf{For every random variable $A$ with expectation $x$, we have
$\pr{A = x} > 0$.}

\item \tf{For all random variables $A$, $B$, and $C$ (not necessarily
independent), if $\ex{A} > \ex{B}$ and $\ex{B} > \ex{C}$, then $\ex{A}
> \ex{C}$.}

\end{enumerate}

\solution{The correct answers are as follows:

\begin{tabular}{rlcrl}
1. & false &\quad& 6. & false \\
2. & false && 7. & true \\
3. & true  && 8. & true \\
4. & true  && 9. & false \\
5. & false && 10. & true
\end{tabular}
}

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

\examonly{\newpage}

\problem {\bf [15 pts]\ } A Barglesnort makes its lair in one of three
caves:

\vspace{0.25in}
\centerline{\resizebox{!}{1in}{\includegraphics{quiz1-caves.eps}}}
\vspace{0.25in}

\noindent The Barglesnort inhabits cave 1 with probability
$\frac{1}{2}$, cave 2 with probability $\frac{1}{4}$, and cave 3 with
probability $\frac{1}{4}$.  A rabbit subsequently moves into one of
the two unoccupied caves, selected uniformly at random.  With
probability $\frac{1}{3}$, the rabbit leaves tracks at the entrance to
its cave.  (Barglesnorts are much too clever to leave tracks.)  What
is the probability that the Barglesnort lives in cave 3, given that
there are no tracks in front of cave 2?

\bigskip

If you fail to draw a tree diagram, then no partial credit will be
awarded for an incorrect solution.

\solution{A tree diagram is given below.  Let $B_3$ be the event that
the Barglesnort inhabits cave 3, and let $T_2$ be the event that there
are tracks in front of cave 2.  Taking data from the tree diagram, we
can compute the desired probability as follows:

\beqn
\pr{B_3 \mid \overline{T_2}}
	& = &	\frac{\pr{B_3 \cap \overline{T_2}}}{\pr{\overline{T_2}}} \\
	& = &	\frac{\frac{1}{24} + \frac{1}{12} + \frac{1}{12}}
		{1 - \frac{1}{12} - \frac{1}{24}} \\
	& = & 	\frac{5}{21}
\eeqn

In the denominator, we apply the formula $\pr{\overline{T_2}} = 1 -
\pr{T_2}$ for convenience.

\bigskip
\centerline{\resizebox{!}{4in}{\includegraphics{quiz1-bargle.eps}}}
}


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

\examonly{\newpage}

\problem {\bf [15 pts]\ } Answer the following questions about
independence.

\begin{problemparts}

\problempart {\bf [5 pts]\ } Suppose that you roll a fair die that has
six sides, numbered $1$, $2$, $\ldots$, $6$.  Is the event that the
number on top is a multiple of 2 independent of the event that the
number on top is a multiple of 3?  Justify your answer.

\examonly{\vspace{3.5in}}

\solution{Let $A$ be the event that the number on top is a multiple of
2, and let $B$ be the event that the number on top is a multiple of 3.
We have:

\[
\pr{A} \cdot \pr{B} =
	\frac{3}{6} \cdot \frac{2}{6} =
	\frac{1}{6} = \pr{A \cap B}
\]

Therefore, these events are independent.
}

\problempart {\bf [5 pts]\ } Now suppose that you roll a fair die that
has {\em four} sides, numbered $1$, $2$, $3$, $4$.  Again, is the
event that the number on top is a multiple of 2 independent of the
event that the number on top is a multiple of 3?  Justify your answer.

\solution{As before, let $A$ be the event that the number on top is a
multiple of 2, and let $B$ be the event that the number on top is a
multiple of 3.  Now, however, we have:

\beqn
\pr{A} \cdot \pr{B}
	& = &	\frac{2}{4} \cdot \frac{1}{4} \\
	& = &	\frac{1}{8}
\eeqn

But:

\beqn
\pr{A \cap B} & = & 0
\eeqn

Since these results disagree, the events are not independent.
}

\examonly{\newpage}

\problempart {\bf [5 pts]\ } Finally, suppose that you roll a fair die
that has {\em eight} sides, numbered $1$, $2$, $\ldots$, $8$.  Let the
random variable $X$ be the remainder when the number on top is divided
by 2, and let the random variable $Y$ be the remainder when the number
on top is divided by 3.  Are the random variables $X$ and $Y$
independent?  Justify your answer.

\solution{First, let's tabulate the values of $X$ and $Y$:

\[
\begin{array}{ccc}
\text{die roll} & X & Y \\
1 & 1 & 1 \\
2 & 0 & 2 \\
3 & 1 & 0 \\
4 & 0 & 1 \\
5 & 1 & 2 \\
6 & 0 & 0 \\
7 & 1 & 1 \\
8 & 0 & 2 \\
\end{array}
\]

Working from the table, we have:

\beqn
\pr{X = 1 \cap Y = 1} & = & \frac{2}{8}
\eeqn

But:

\beqn
\pr{X = 1} \cap \pr{Y = 1}
	& = &	\frac{4}{8} \cdot \frac{3}{8} \\
	& = &	\frac{3}{16}
\eeqn

Since these results conflict, the random variables are not independent.
}

\end{problemparts}


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

\examonly{\newpage}

\problem {\bf [15 pts]\ } Each 6.042 quiz 1 is graded according to a
rigorous procedure:

\begin{itemize}

\item With probability $\frac{4}{7}$ the exam is graded by a {\em
tutor}, 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 Tutors} 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.

\begin{problemparts}
\problempart {\bf [5 pts]\ } What is the expected score on an exam
graded by a tutor?

\solution{
Let the random variable $T$ denote the score a tutor would give.  By
linearity of expectation, the expected sum of the problem scores is
the sum of the expected problem scores.  Therefore, we have:

\beqn
\ex{T}	& = &	10 \cdot \ex{\text{T/F score}} +
		4 \cdot \ex{\text{15pt prob score}} +
		\ex{\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
\eeqn
}

\examonly{\newpage}

\problempart {\bf [5 pts]\ } What is the expected score on an exam
graded by a lecturer?

\examonly{\vspace{4in}}

\solution{
Now we find the expected value of $L$, the score a lecturer would
give.  Employing linearity again, we have:

\beqn
\ex{L}	& = &	\ex{\text{product of dice}} + \ex{\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}
\eeqn
}

\problempart {\bf [5 pts]\ } What is the expected score on a 6.042
exam?

\solution{Let $X$ equal the true exam score.  The total expectation
law implies:

\beqn
\ex{X}	& = &	\frac{4}{7} \cdot \ex{T} +
		\frac{2}{7} \cdot \ex{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}
\eeqn
}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf [20 pts]\ } A spacecraft will be lost if and only if a
critical component fails.  The craft contains 400 critical components
that are ``highly reliable''.  Each of these components fails with
probability 1 in 1000.  The remaining 5,500 critical components on
board are ``extremely reliable''.  Each of these fails with
probability 1 in 10,000.  Let $p$ be the probability that the
spacecraft is lost.

\begin{problemparts}

\problempart {\bf [8 pts]\ } If component failures occur mutually
independently, what is the probability $p$ that the spacecraft is
lost?  Your answer may be an expression, instead of a number.

\examonly{\vspace{3.5in}}

\solution{Let $H_i$ be the event the that $i$-th highly-reliable
component fails, and let $X_j$ be the event that the $j$-th
extremely-reliable component fails.  Then we have:

\beqn
p	& = &	\pr{H_1 \cup H_2 \cup \ldots \cup H_{400} \cup
			X_1 \cup X_2 \cup \ldots \cup X_{5500}} \\
	& = &	1 - \pr{\overline{H_1 \cup H_2 \cup \ldots \cup H_{400} \cup
			X_1 \cup X_2 \cup \ldots \cup X_{5500}}} \\
	& = &	1 - \pr{\overline{H_1} \cap \overline{H_2} \cap \ldots
			\cap \overline{H_{400}} \cap
			\overline{X_1} \cap \overline{X_2} \cap \ldots
			\cap \overline{X_{5500}}} \\
	& = &	1 - \pr{\overline{H_1}} \cdot \pr{\overline{H_2}} \cdots
			\pr{\overline{H_{400}}} \cdot
			\pr{\overline{X_1}} \cdot \pr{\overline{X_2}}
			\cdots \pr{\overline{X_{5500}}} \\
	& = &	1 - \prod_{i=1}^{400} \pr{\overline{H_i}} \cdot
			\prod_{j=1}^{5500} \pr{\overline{X_j}} \\
	& = &	1 - \prod_{i=1}^{400} (1 - \pr{H_i}) \cdot
			\prod_{j=1}^{5500} (1 - \pr{X_j}) \\
	& = &	1 - \left(1 - \frac{1}{1000}\right)^{400} \cdot
		    \left(1 - \frac{1}{10000}\right)^{5500}
\eeqn

The first step uses the defintion of $p$.  In the second step, we
apply the identity $\pr{E} = 1 - \pr{overline{E}}$.  Then we apply
DeMorgan's law.  The fourth step uses the fact that component failures
are mutually independent.  In the fifth step, we simply switch to
product notation.  Then, once again, we apply the rule $\pr{E} = 1 -
\pr{overline{E}}$.  In the last step, we substitute in the component
failure probabilities.}

\problempart {\bf [6 pts]\ } Now do not assume that components fail
mutually independently.  Give the tightest upper bound you can on $p$.
Justify your answer.

\solution{Intuitively, if events are cover to as much of the sample
space as possible, then they ought not to overlap one another.  In
other worse, the events should be disjoint.  Formally, if the failures
are disjoint events, then the sum rule says:

\beqn
p	& = &	\pr{H_1 \cup H_2 \cup \ldots \cup H_{400} \cup
			X_1 \cup X_2 \cup \ldots \cup X_{5500}} \\
	& = &	\pr{H_1} + \pr{H_2} + \ldots + \pr{H_{400}} + \\
	&&	\quad \pr{X_1} + \pr{X_2} + \ldots + \pr{X_{5500}} \\
	& = &	400 \cdot \frac{1}{1000} + 5500 \cdot \frac{1}{10000} \\
	& = &	\frac{95}{100}
\eeqn

This is actally tight.  Boole's inequality says that the probability
of a union of events is at most the sum of the event probabilities.
}

\examonly{\newpage}

\problempart {\bf [6 pts]\ } Again, do not assume that components fail
mutually independently.  Give the tightest lower bound you can on $p$.
Justify your answer.

\solution{Certainly, the probability of failure is at least $1 /
1000$, since a single each highly reliable component fails with that
probability.  On the other hand, the probability could actually be no
higher than that, since all the other events could be a subset of that
one.}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf [15 pts]\ } A classroom has sixteen desks arranged as
shown below.

\vspace{0.25in}
\centerline{\resizebox{!}{1.5in}{\includegraphics{quiz1-desks.eps}}}
\vspace{0.25in}

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.

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

\beqn
\ex{\sum_{i=1}^{24} F_i}
	& = &	\sum_{i=1}^{24} \ex{F_i} \\
	& = &	\sum_{i=1}^{24} \pr{F_i = 1}
\eeqn

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:

\beqn
\ex{\sum_{i=1}^{24} F_i}
	& = &	\sum_{i=1}^{24} \pr{F_i = 1} \\
	& = &	24 \cdot \frac{1}{2} \\
	& = &	12
\eeqn
}

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

\end{problems}
\end{document}
