\Question{Markov's Inequality and Chebyshev's Inequality}
A random variable $X$ has variance $\Var{X} = 9$ and expectation $\Ex{X}=2$. Furthermore, the value of $X$ is never greater than $10$. Given this information, provide either a proof or a counterexample for the following statements.
\begin{Parts}
\Part $\Ex{X^2} = 13$.\label{markov-chebyshev-part-a}
\nosolspace{1cm}
\Part $\Pr[X = 2] > 0$.
\nosolspace{1cm}
\Part $\Pr[X \geq 2] = \Pr[X \leq 2]$.
\nosolspace{1cm}
\Part $\Pr[X \leq 1] \leq 8/9$.
\nosolspace{1cm}
\Part $\Pr[X \geq 6] \leq 9/16$.
\nosolspace{1cm}
\Part $\Pr[X \geq 6] \leq 9/32$.
\nosolspace{1cm}
\end{Parts}
\Question{Subset Card Game}
Jonathan and Yiming are playing a card game. Jonathan has $k > 2$ cards, and each card has a real number written on it. Jonathan tells Yiming (truthfully), that the sum of the card values is $0$, and that the sum of squares of the values on the cards is $1$. Specifically, if the card values are $c_1, c_2, \ldots, c_k$, then we have $\sum_{i=1}^k c_i = 0$ and $\sum_{i=1}^k c_i^2 = 1$. Jonathan and Yiming also agree on a positive target value of $\alpha$.
The cards are then going to be dealt randomly in the following fashion: for each card in the deck, a fair coin is flipped. If the coin lands heads, then the card goes to Yiming, and if the coin lands tails, the card goes to Jonathan. Note that it is possible for either player to end up with no cards/all the cards.
A player wins the game if the sum of the card values in their hand is at least $\alpha$, otherwise it is a tie.
\begin{Parts}
\Part Prove that the probability that Yiming wins is at most $\frac{1}{8\alpha^2}$.
\Part Find a deck of $k$ cards and target value $\alpha$ where the probability that Yiming wins is exactly $\frac{1}{8\alpha^2}$.
\end{Parts}
\Question{Sampling a Gaussian With Uniform}
In this question, we will see one way to generate a normal random variable
if we have access to a random number generator that outputs numbers
between $0$ and $1$ uniformly at random.
As a general comment, remember that showing two random variables
have the same CDF or PDF is sufficient for showing that they have the
same distribution.
\begin{Parts}
\Part First, let us see how to generate an exponential random variable
with a uniform random variable. Let $U_1 \sim Uniform(0, 1)$. Prove
that $-\ln U_1 \sim Expo(1)$.
\Part Let $N_1, N_2 \sim \mathcal{N}(0, 1)$, where $N_1$ and $N_2$ are
independent. Prove that $N_1^2 + N_2^2 \sim Expo(1/2)$.
\textit{Hint:} You may use the fact that over a region $R$, if
we convert to polar coordinates $(x, y) \rightarrow (r, \theta)$,
then the double integral over the region $R$ will be
$$\iint_R f(x, y) \, dx \, dy = \iint_R f(r \cos \theta, r \sin \theta) \cdot r \, dr \, d\theta.$$
\Part Suppose we have two uniform random variables, $U_1$ and $U_2$.
How would you transform these two random variables into a normal random
variable with mean $0$ and variance $1$?
\textit{Hint:} What part (b) tells us is that the point $(N_1, N_2)$
will have a distance from the origin that is distributed as the
square root of an exponential distribution. Try to use $U_1$ to sample
the radius, and then use $U_2$ to sample the angle.
\end{Parts}
\Question{Optimal Gambling}
Jonathan has a coin that may be biased, but he doesn't think so. You disagree with him though, and he challenges you to a bet. You start off with $X_0$ dollars. You and Jonathan then play
multiple rounds, and each round, you bet an amount of money of your choosing, and then coin is tossed. Jonathan will match your bet, no matter what, and if the coin comes up heads,
you win and you take both yours and Jonathan's bet, and if it comes up tails, then you lose your bet.
\begin{Parts}
\Part Now suppose you actually secretly know that the bias of the coin is $\frac{1}{2} < p < 1$! You use the following strategy: on each round, you will bet a fraction $q$ of the money you have at the start of the round. Let $X_n$ denote the amount of money you have on round $n$. $X_0$ represents your initial assets and is a constant value. What is $\E[X_n]$ in terms of $X_0, p$, and $q$?
\Part What value of $q$ will maximize $\E[X_n]$? For this value of $q$, what is the distribution of $X_n$? Can you predict what will happen as $n \to \infty$? [\textit{Hint}: Under this betting strategy, what happens if you ever lose a round?]
\Part The problem with the previous approach is that we were too concerned about expected value, so our gambling strategy was too extreme. Let's start over: again we will use a gambling strategy in which we bet a fraction $q$ of our money at each round. Express $X_n$ in terms of $n$, $q$, $X_0$, and $W_n$, where $W_n$ is the number of rounds you have won up until round $n$. [\textit{Hint}: Does the order in which you win the games affect your profit?]
\Part By the law of large numbers, $W_n/n \to p$ as $n \to \infty$. Using this fact, what does $(\ln X_n)/n$ converge to as $n \to \infty$?
\Part The rationale behind $(\ln X_n)/n$ is that if $(\ln X_n)/n \to c$, where $c$ is a constant, then that means for large $n$, $X_n$ is roughly $e^{cn}$. Therefore, $c$ is the asymptotic growth rate of your fortune! Find the value of $q$ that maximizes your asymptotic growth rate.
\Part Using the value of $q$ you found in the previous part, compute $\E[X_n]$.
\Part Now, Jonathan is not going to always believe that the coin is fair. What he will do is play $100$ rounds with you, and observe how many times the coin comes up heads. Jonathan will then construct a $95\%$ confidence interval for the true bias of the coin, $p$. True or false, the probability that Jonathan's interval captures $p$ is at least $95\%$.
\Part Let's say after playing $100$ rounds, Jonathan observes that $74$ heads have appeared. Help Jonathan construct a $95\%$ confidence interval using the CLT. Also, answer true or false: the probability that this interval contains the true bias $p$ of the coin is $95\%$. You may assume that $\Phi(2) - \Phi(-2) \approx 0.95$, where $\Phi$ is the CDF of the standard Gaussian.
\end{Parts}
\Question{Boba in a Straw}
Imagine that Jonathan is drinking milk tea and he has a very short straw: it has enough room to fit two boba (see figure).
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1.5]
\draw (-0.5, 1) -- (-0.5, -1);
\draw (0.5, 1) -- (0.5, -1);
\draw[dashed] (-0.5, 0) -- (0.5, 0);
\draw (-0.5, 1) -- (0.5, 1);
\draw (-0.5, -1) -- (0.5, -1);
\draw node[fill, circle, scale=3] at (0, 0.5) {};
\end{tikzpicture}
\caption{A straw with one boba currently inside. The straw only has enough room to fit two boba.}
\label{fig:straw}
\end{figure}
Here is a formal description of the drinking process: We model the straw as having two ``components'' (the top component and the bottom component). At any given time, a component can contain nothing, or one boba. As Jonathan drinks from the straw, the following happens every second:
\begin{enumerate}
\item The contents of the top component enter Jonathan's mouth.
\item The contents of the bottom component move to the top component.
\item With probability $p$, a new boba enters the bottom component; otherwise the bottom component is now empty.
\end{enumerate}
Help Jonathan evaluate the consequences of his incessant drinking!
\begin{Parts}
\Part At the very start, the straw starts off completely empty. What is the expected number of seconds that elapse before the straw is completely filled with boba for the first time? [Write down the equations; you do not have to solve them.]
\Part Consider a slight variant of the previous part: now the straw is narrower at the bottom than at the top. This affects the drinking speed: if either (i) a new boba is about to enter the bottom component or (ii) a boba from the bottom component is about to move to the top component, then the action takes two seconds. If both (i) and (ii) are about to happen, then the action takes three seconds. Otherwise, the action takes one second. Under these conditions, answer the previous part again. [Write down the equations; you do not have to solve them.]
\Part Jonathan was annoyed by the straw so he bought a fresh new straw (the straw is no longer narrow at the bottom). What is the long-run average rate of Jonathan's calorie consumption? (Each boba is roughly $10$ calories.)
\Part What is the long-run average number of boba which can be found inside the straw? [Maybe you should first think about the long-run distribution of the number of boba.]
\end{Parts}