\Question{Trick or Treat}
Ryan and Suraj are trick or treating together, and are each trying to collect all $n$ flavors of Laffy Taffy. At each house, they each receive a Laffy Taffy, chosen uniformly at random from all flavors. However, Suraj will throw a tantrum if Ryan gets a flavor he doesn't, so they agree that if they receive different flavors, they'll both politely return the candy they got, and move on to the next house. What is the expected number of houses they need to visit until they get a full set of Laffy Taffy?
\nosolspace{2in}
\Question{Coupon Collection}
Suppose you take a deck of $n$ cards and repeatedly perform the following step: take the current top card and put it back in the deck at a uniformly random position (the probability that the card is placed in any of the $n$ possible positions in the deck --- including back on top --- is $1/n$).
Consider the card that starts off on the bottom of the deck. What is the expected number of steps until this card rises to the top of the deck? (For large $n$, you may use the approximation $\sum_{i=1}^n \frac{1}{i} \approx \ln{n}$)
[\textit{Hint}: Let $T$ be the number of steps until the card rises to the top. We have $T=T_n+T_{n-1}+\cdots+T_2$, where the random variable $T_i$ is the number of steps until the bottom card rises from position $i$ to position $i-1$. Thus, for example, $T_n$ is the number of steps until the bottom card rises off the bottom of the deck, and $T_2$ is the number of steps until the bottom card rises from second position to top position. What is the distribution of $T_i$?]
\nosolspace{3cm}
\Question {Diversify Your Hand}
You are dealt 5 cards from a standard 52 card deck. Let $X$ be the number of distinct values in your hand. For instance, the hand (A, A, A, 2, 3) has 3 distinct values.
\begin{Parts}
\Part
Calculate $E[X]$.
\nosolspace{2cm}
\Part Calculate $Var[X]$.
\nosolspace{2cm}
\end{Parts}
\Question{Balls and Bins}
Throw $n$ balls into $m$ bins, where $m$ and $n$ are positive integers. Let $X$ be the number of bins with exactly one ball. Compute $\var X$.
\Question{Practical Confidence Intervals}
\begin{enumerate}[(a)]
\item It's New Year's Eve, and you're re-evaluating your finances for the next year. Based on previous spending patterns, you know that you spend \$1500 per month on average, with a standard deviation of \$500, and each month's expenditure is independently and identically distributed. As a poor college student, you also don't have any income. How much should you have in your bank account if you don't want to go broke this year, with probability at least 95\%?
\item As a UC Berkeley CS student, you're always thinking about ways to become the next billionaire in Silicon Valley. After hours of brainstorming, you've finally cut your list of ideas down to 10, all of which you want to implement at the same time. A venture capitalist has agreed to back all 10 ideas, as long as your net return from implementing the ideas is positive with at least 95\% probability.
Suppose that implementing an idea requires $50$ thousand dollars, and your start-up then succeeds with probability $p$, generating $150$ thousand dollars in revenue (for a net gain of $100$ thousand dollars), or fails with probability $1 - p$ (for a net loss of $50$ thousand dollars). The success of each idea is independent of every other. What is the condition on $p$ that you need to satisfy to secure the venture capitalist's funding?
\item One of your start-ups uses error-correcting codes, which can recover the original message as long as at least $1000$ packets are received (not erased). Each packet gets erased independently with probability $0.8$. How many packets should you send such that you can recover the message with probability at least 99\%?
\end{enumerate}
\Question{Law of Large Numbers}
Recall that the {\em Law of Large Numbers} holds if, for every $\epsilon > 0$,
$$ \lim_{n \rightarrow \infty} \Pr\p*{\left|\frac{1}{n} S_n
- \Ex{\frac{1}{n} S_n}\right| > \epsilon} = 0.$$
In class, we saw that the Law of Large Numbers holds for
$ S_n = X_1+\dots +X_n$,
where the $X_i$'s are i.i.d.\ random variables.
This problem explores if the Law of Large Numbers holds under other circumstances.
Packets are sent from a source to a destination node over the Internet. Each packet is sent on a certain route, and the routes are disjoint. Each route has a failure probability of $p \in (0, 1)$ and different routes fail independently.
If a route fails, all packets sent along that route are lost.
You can assume that the routing protocol has no knowledge of which route fails.
For each of the following routing protocols, determine whether the Law of Large Numbers holds when $S_n$ is defined as the total number of received packets out of $n$ packets sent.
Answer \textbf{Yes} if the Law of Large Number holds, or \textbf{No} if not, and give a brief justification of your answer. (Whenever convenient, you can assume that $n$ is even.)
\begin{Parts}
\Part \textbf{Yes} or \textbf{No}:
Each packet is sent on a completely different route.
\Part \textbf{Yes} or \textbf{No}:
The packets are split into $n/2$ pairs of packets.
Each pair is sent together on its own route (i.e., different pairs are sent on different routes).
\Part \textbf{Yes} or \textbf{No}:
The packets are split into $2$ groups of $n/2$ packets.
All the packets in each group are sent on the same route, and the two groups are sent on different routes.
\Part \textbf{Yes} or \textbf{No}:
All the packets are sent on one route.
\end{Parts}