\Question
\textbf{Calculate these... or else}
\begin{enumerate}
\item
What is the probability of drawing a straight (your hand's card values can be arranged in consecutive ascending order, i.e. $\{8,9,10,J,Q\}$ is a straight. Values do not loop around, so $\{Q, K, A, 2, 3\}$ is not a straight) from a standard 52-card deck?
\item
What is the probability of drawing at least one card from each suit (still a 5 card hand)?
\item
Two squares are chosen at random on $8\times 8$ chessboard. What is
the probability that they share a side?
\item
8 rooks are placed randomly on an $8\times 8$ chessboard. What is the probability none of them are attacking each other? (Two rooks attack each other if they are in the same row, or in the same column).
\item A bag has two quarters and a penny. If someone removes a coin, the Coin-Replenisher will come and drop in 1 of the coin that was just removed with 3/4 probability and with 1/4 probability drop in 1 of the opposite coin. Someone removes one of the coins at random. The Coin-Replenisher drops in a penny. You randomly take a coin from the bag. What is the probability you take a quarter?
\end{enumerate}
\Question
\textbf{Friendly Independence} \\
Let's start with the basics. You have two friends, Olivia and Fitz. We're interested in the things they do. Specifically, we're interested in whether Olivia eats popcorn and whether Fitz retires to Vermont on any given day. For the purposes of this question, we can assume these events are independent.
\begin{enumerate}
\item Show that Olivia not eating popcorn and Fitz retiring to Vermont are independent. That is, $\bar O$ and $F$ are independent.
\item Show that Olivia eating popcorn and Fitz not retiring to Vermont are independent. That is, $O$ and $\bar F$ are independent.
\item Show that Olivia not eating popcorn and Fitz not retiring to Vermont are independent. That is, $\bar O$ and $\bar F$ are independent.
\item You've made a new friend Cyrus, who sometimes yells passionately at people. Olivia eating popcorn, Fitz retiring to Vermont, and Cyrus yelling are mutually independent events. Show that Olivia eating popcorn and Fitz retiring to Vermont $\cap$ Cyrus yelling are independent. That is, $O$ and $(F \cap C)$ are independent.
\item Show that Olivia eating popcorn and Fitz retiring to Vermont $\Delta$ Cyrus yelling are independent. That is, $O$ and $(F \Delta C)$ are independent. Recall that $\Delta$ is the symmetric difference of two sets. $A \Delta B = (B-A) \cup (A-B)$.
\item More generally, let $\{A_j, j \in J\}$ be mutually independent. Show that $\{\cap_{j \in J_k} A_j, k \in K\}$ are mutually independent if the subsets $J_k$ of $J$ are pairwise disjoint.
\end{enumerate}
\Question \textbf{ Throwing balls into a depth-limited bin} \\Say you want to throw $n$ balls into $n$ bins with depth $k-1$ (they can fit $k-1$ balls, after that the bins overflow). Suppose that $n$ is a large number and $k=0.1n$. You throw the balls randomly into the bins, but you would like it if they don't overflow. You feel that you might expect not too many balls to land in each bin, but you're not sure, so you decide to investigate the probability of a bin overflowing. \textit{Hint: use union bound for parts c), d)}
\begin{enumerate}
\item Focus on the first bin. Get an upper bound the number of ways that you can throw the balls into the bins such that this bin overflows. Try giving an argument about the following strategy: select $k$ balls to put in the first bin, and then throw the remaining balls randomly.
\item Calculate an upper bound on the probability that the first bin will overflow:
\item Upper bound the probability that some bin will overflow.
\item How does the above probability scale as $n$ gets really large?
\end{enumerate}
\Question
\textbf{Student Request Collector} \\After a long night of debugging, Alvin has just perfected the new homework party/office hour queue system. CS 70 students sign themselves up for the queue, and TAs go through the queue, resolving requests one by one. Unfortunately, our newest TA (let's call him TA Bob) does not understand how to use the new queue: instead of resolving the requests in order, he always uses the Random Student button, which (as the name suggests) chooses a random student in the queue for him. To make matters worse, after helping the student, Bob forgets to click the Resolve button, so the student still remains in the queue! For this problem, assume that there are $n$ total students in the queue.
\begin{enumerate}
\item Suppose that Bob has already helped $k$ students. What is the probability that the Random Student button will take him to a student who has not already been helped?
\item Let $X_i^r$ be the event that TA Bob has not helped student $i$ after pressing the Random Student button a total of $r$ times. What is $\Pr[X_i^r]$? Assume that the results of the Random Student button are independent of each other. Now approximate the answer using the inequality $1-x \leq e^{-x}$.
\item Let $T_r$ represent the event that TA Bob presses the Random Student button $r$ times, but still has not been able to help all $n$ students. (In other words, it takes TA Bob longer than $r$ Random Student button presses before he manages to help every student). What is $T_r$ in terms of the events $X_i^r$? (Hint: Events are subsets of the probability space $\Omega$, so you should be thinking of set operations...)
\item Using your answer for the previous part, what is an upper bound for $\Pr[T_r]$? (You may leave your answer in terms of $\Pr[X_i^r]$. Use the inequality $1-x \leq e^{-x}$ from before.)
\item Now let $r = \alpha n \ln n$. What is $\Pr[X_i^r]$?
\item Calculate an upper bound for $\Pr[T_r]$ using the same value of $r$ as before. (This is more formally known as a bound on the tail probability of the distribution of button presses required to help every student. This distribution will be explored in more detail later, in the context of random variables.)
\item What value of $r$ do you need to bound the tail probability by $1/n^2$? In other words, how many button presses are needed so that the probability that TA Bob has not helped every student is at most $1/n^2$?
\end{enumerate}