\Question \textbf{Pokemon Again}\\
Nintendo comes out with a set of reprinted original Pokemon cards,
one for each of the original 150 Pokemon. Naturally nothing will do,
but that you collect them all. Suppose that these cards are sold as
individually wrapped random cards and all cards are equally common.
You can't see what a card is until after you buy it.
\begin{enumerate}
\item Approximately how many cards would you expect to need to buy before
you have all 150?
\item Now suppose you have a nice older brother who still has 25 of his
original cards (all unique). If he gives those cards to you, what
is the expected number of cards you need to buy now?
\item Your older brother isn't that nice; he won't give you his cards for
free but he will sell them. If new cards go for \$2.50 a piece, how
much would you be willing to pay your brother for his cards? Is the
per-card price greater or less than \$2.50? Why?
\end{enumerate}
\Question \textbf{Quadruply-repeated ones}\\
We say that a string of bits has $k$ \emph{quadruply-repeated ones}
if there are $k$ positions where four consecutive 1's appear in a row.
For example, the string $0100111110$ has two quadruply-repeated ones.
What is the expected number of quadruply-repeated ones
in a random $n$-bit string, when $n \ge 3$ and all $n$-bit
strings are equally likely?
\Question \textbf{Ball in Bins}%
You are throwing $k$ balls into $n$ bins. Let $X_i$ be the number of balls thrown into bin $i$.
\begin{enumerate}
\item What is $E[X_i]$?
\item Compute $E[X_i^2]$. Show that it is at most $2$ when $k = n$.
\item What is the expected number of empty locations?
\item What is the expected number of collisions?
\end{enumerate}
\Question \textbf{How Many Aces?}
After you solve this question, you should understand why indicators are so useful! Suppose that you draw 3 cards from a standard deck. Let $X$ denote the number of aces you draw.
\begin{enumerate}
\item What is $\Pr(X = 0)$?
\item What is $\Pr(X = 1)$?
\item What is $\Pr(X = 2)$?
\item What is $\Pr(X = 3)$?
\item Check your answers to make sure they add up to 1.
\item Using your previous answers, compute $E(X)$ from the definition.
\item Define indicators $X_i$, $1 \leq i \leq 3$, where $X_i$ is the indicator that the $i$th card is an ace. Compute $E(X)$ using linearity of expectation.
\item Are the $X_i$ indicators independent? How does this affect your answer to part (g)?
\end{enumerate}
\Question \textbf{More Aces in a Deck}
There are four aces in a deck. Suppose you shuffle the deck; define the random variables
\begin{align*}
X_1 &= \text{number of non-ace cards before the first ace} \\
X_2 &= \text{number of non-ace cards between the first and second ace} \\
X_3 &= \text{number of non-ace cards between the second and third ace} \\
X_4 &= \text{number of non-ace cards between the third and fourth ace} \\
X_5 &= \text{number of non-ace cards after the fourth ace}
\end{align*}
\begin{enumerate}
\item What is $X_1 + X_2 + X_3 + X_4 + X_5$?
\item Argue that the $X_i$ random variables all have the same distribution.
\item Use the results of the previous parts to compute $E(X_1)$.
\end{enumerate}
\Question \textbf{Poisson Distribution}
\begin{enumerate}
\item It is fairly reasonable to model the number of customers entering a shop during a particular hour as a Poisson random variable. Assume that this Poisson random variable $X$ has mean $\lambda$. Suppose that whenever a customer enters the shop they leave the shop without buying anything with probability $p$. Assume that customers act independently, i.e.~you can assume that they each simply flip a biased coin to decide whether to buy anything at all. Let us denote the number of customers that buy something as $Y$ and the number of them that do not buy anything as $Z$ (so $X = Y+Z$).
What is the probability that $Y=k$ for a given $k$? How about $\Pr[Z=k]$? Prove that $Y$ and $Z$ are Poisson random variables themselves.
Hint: you can use the identity $e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}$.
\item Assume that you were given two independent Poisson random variables $X_1, X_2$. Assume that the first has mean $\lambda_1$ and the second has mean $\lambda_2$. Prove that $X_1+X_2$ is a Poisson random variable with mean $\lambda_1+\lambda_2$. Hint: use the results from the previous parts.
\end{enumerate}
\Question \textbf{Geometric Distribution}
Two faulty machines, $M_1$ and $M_2$, are repeatedly run synchronously in parallel (i.e., both machines execute one run, then both execute a second run, and so on). On each run, $M_1$ fails with probability $p_1$ and $M_2$ fails with probability $p_2$, all failure events being independent. Let the random variables $X_1$, $X_2$ denote the number of runs until the first failure of $M_1$, $M_2$ respectively; thus $X_1$, $X_2$ have geometric distributions with parameters $p_1$, $p_2$ respectively. Let $X$ denote the number of runs until the first failure of \emph{either} machine. Show that $X$ also has a geometric distribution, with parameter $p_1+p_2-p_1p_2$.