\documentclass[11pt,fleqn]{article}
\usepackage{fullpage}
\usepackage{latexsym,epsf,epsfig}
\usepackage{amsmath,amsthm,amsfonts}
\begin{document}
\def\E{\mathbb{E}}
\def\Var{\operatorname{Var}}
\newtheorem{thm}{Theorem}
\section*{CS 70 homework 12 solutions}
Your full name: PUT YOUR NAME HERE
\newline
Your login name: PUT YOUR LOGIN NAME HERE
\newline
Homework 12
\newline
Your section number: PUT YOUR SECTION NUMBER HERE
\newline
Your list of partners: LIST YOUR PARTNERS HERE
\newline
\begin{enumerate}
\item
\begin{enumerate}
\item Show that, for independent random variables $X,Y$, we have
$\E[XY] = \E[X] \times \E[Y]$.
YOUR ANSWER GOES HERE.
\item Give a simple example to show that the conclusion of
the previous part is not necessarily true when $X$ and $Y$ are not independent.
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
\begin{enumerate}
\item Compute the expectation $\E[B]$ and the variance $\Var[B]$.
YOUR ANSWER GOES HERE.
\item Use Chebyshev's inequality to compute an {\it upper bound\/}~$b$
on the probability that Buchanan receives at least 3407 votes, i.e.,
find a number~$b$ such that $$
\Pr[B\ge 3407] \le b. $$
Based on this result, do you think Buchanan's vote is significant?
YOUR ANSWER GOES HERE.
\item Now suppose that your bound~$b$ in part~(b) is in fact sharp, [\ldots]
What is the
probability that in {\it at least one\/} of the counties,
Buchanan receives at least 3407 votes? How would this affect your
judgement as to whether the Palm Beach tally is significant?
YOUR ANSWER GOES HERE.
\item ~ [\ldots] Suppose
then that 80\% of the voters in Palm Beach County vote deterministically
according to the state-wide proportions for Florida, while the remaining
20\% behave randomly as described earlier. Does your bound $b$
in part~(b) increase, decrease or remain the same under this model?
Justify your answer.
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
\begin{enumerate}
\item Take an ordinary deck of 52 playing cards, and add a single joker.
Shuffle it and turn up the cards one at a time until the joker appears.
On average, how many cards are required until you see the joker?
YOUR ANSWER GOES HERE.
\item Now take a deck of 52 playing cards, add two jokers, shuffle,
and turn up cards one at a time until the first time that a joker appears.
On average, how many cards are required until you see the first joker?
YOUR ANSWER GOES HERE.
\item Check your work by writing a program. Run it for some large number of
trials (say, a million trials) and compute the average number of cards
needed to see the first joker. What do you get?
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
Let the random variables $X$ and $Y$ be distributed independently and
uniformly at random in the set $\{0,1, \ldots, p-1\}$, where $p > 2$
is a prime.
\begin{enumerate}
\item What is the expectation $\E[X]$?
YOUR ANSWER GOES HERE.
\item Let $S = (X + Y) \bmod p$ and $T = XY \bmod p$. What are the
distributions of $S$ and $T$?
YOUR ANSWER GOES HERE.
\item What are the expectations $\E[S]$ and $\E[T]$?
YOUR ANSWER GOES HERE.
\item By linearity of expectation, we might expect that $\E[S] =
(\E[X] + \E[Y]) \bmod p$. Explain why this does not hold in the present
context; i.e., why does the value for $\E[S]$ obtained in part
(c) not contradict linearity of expectation?
YOUR ANSWER GOES HERE.
\item Since $X$ and $Y$ are independent, we might expect that $\E[T] =
\E[X] \E[Y] \bmod p$. Does this hold in this case? Explain why/why not.
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
James Bond is imprisoned [\ldots]
On the average, how long does it take before he realizes
that the door is unlocked and escapes?
YOUR ANSWER GOES HERE.
\end{enumerate}
\end{document}