\Question{Buffon's Needle on a Grid}
In this problem, we will consider Buffon's Needle, but with a catch. We now drop
a needle at random onto a large grid, and example of which is shown below.
\begin{center}
\begin{tikzpicture}
\draw[step=0.5cm,color=gray] (.75,.75) grid (3.75,3.75);
\draw[thick,color=black] (2.25, 2.45) -- (2.603553, 2.803553);
\end{tikzpicture}
\end{center}
The length of the needle is $1$, and the space between the grid lines is $1$ as well.
Recall from class that a random throw means that
the position of the center of the needle and its orientation
are independent and uniformly distributed.
\begin{Parts}
\Part Given that the angle between the needle and the horizontal lines is $\theta$,
what is the probability that the needle does not intersect any grid lines?
Justify your answer.
\Part Continue part (a) to find the probability that the needle, when dropped onto the
grid at random (with the angle chosen uniformly at random), intersects a grid line.
Justify your answer.
\textit{Hint:} You may use the fact that
$\sin \theta \cos \theta = \frac{1}{2} \sin (2\theta)$
without proof.
\Part Let $X$ be the number of times the needle intersects a gridline (so, in the example shown
above, $X = 2$). Find $\mathbb{E}[X]$. Justify your answer.
\textit{Hint:} Can you do this without using your answer from part (b)?
\Part Combine the previous parts to figure out the probability that $X = 1$, i.e. the needle
will only intersects one gridline. Justify your answer.
\Part We will fold the needle into an equilateral triangle, where each side is length
$\frac{1}{3}$. What is the expected number of intersections that this triangle will have
with the gridlines, when dropped onto the grid? Justify your answer.
\end{Parts}
\Question{Variance of the Minimum of Uniform Random Variables}
Let $n$ be a positive integer and let $X_1,\dotsc,X_n \overset{\text{i.i.d.}}{\sim} \Unif[0, 1]$.
Find $\var Y$, where
$$Y := \min\{X_1,\dotsc,X_n\}.$$
\textit{Hint}: You may need to perform integration by parts.
\Question{Erasures, Bounds, and Probabilities}
%You may want to use a calculator for this problem. Better yet, use a
%computer running MATLAB or Python to calculate things like erf functions.
%Or you can just type stuff like \texttt{erf(0.25)} into Wolfram Alpha
%(\url{http://www.wolframalpha.com}).
%
Alice is sending $1000$ bits to Bob. The probability that a bit gets erased is
$p$, and the erasure of each bit is independent of the others.
Alice is using a scheme that can tolerate up to one-fifth of the bits being
erased. That is, as long as Bob receives at least $801$ of the $1000$ bits
correctly, he can decode Alice's message.
In other words, Bob becomes unable to decode Alice's message only if $200$ or
more bits are erased. We call this a ``communication breakdown'', and we want
the probability of a communication breakdown to be at most $10^{-6}$.
\begin{enumerate}
\item{Use Markov's inequality to upper bound $p$ such that the probability
of a communications breakdown is at most $10^{-6}$.}
\item{Use Chebyshev's inequality to upper bound $p$ such that the
probability of a communications breakdown is at most $10^{-6}$.}
% \item{Use the following Chernoff bound (which is valid for all $\epsilon > 0$)
% to upper bound $p$ such that the
% probability of a communications breakdown is at most $10^{-6}$.
%
% $$\textnormal{Pr }(\textnormal{No. of erasures }\geq\ (1+\epsilon)1000p) \leq e^{-\frac{\epsilon^{2}}{2+\epsilon}1000p}\ \ \ \ \textnormal{(Chernoff Bound)}$$}
\item{As the CLT would suggest, approximate the fraction of erasures by a
Gaussian random variable
%\footnote{A Gaussian random variable is an
% example of a continuous random variable, which you have not seen too
% much of in this course. Basically, the random variable can be any real
% number, instead of being confined to take only one of a discrete set of
% values. For continuous random variables like the Gaussian random
% variable, it does not make much sense to ask ``what is the probability
% of the variable assuming a particular value, like $0$ or $0.5$'' (since
% this probability is always $0$ for any such single point). Instead, one
% asks ``what is the probability that the variable takes a value in a
% given range, like for example, $[-1,1)$ or $(5, \infty)$. What the CLT
% says is that when you average a large number of discrete i.i.d Bernoulli
% random variables, even though the average is still a discrete random
% variable, the distribution of the average begins to
% look more and more like that of a continuous (Gaussian) random variable.}
(with suitable mean and variance). Use this to
find an approximate bound for $p$ such that the probability of a
communications breakdown is at most $10^{-6}$.
% You can use the fact
% that if $Y$ is a Gaussian random variable with mean $\mu$ and variance
% $\sigma^{2}$, then:
% $$\textnormal{Pr }(Y \geq y) = \frac{1}{2} \left(1-\textnormal{erf}\left(\frac{y - \mu}{\sigma\sqrt{2}}\right)\right)$$
}
\end{enumerate}
\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}
% written Spr 16
\Question{Markov Chain Terminology}
In this question, we will walk you through terms related to Markov chains.
\begin{enumerate}
\item (Irreducibility) A Markov chain is irreducible if, starting from any state $i$, the chain can transition to any other state $j$, possibly in multiple steps.
\item (Periodicity) $d(i) := \gcd\{n > 0 \mid P^n(i, i) = \Pr[X_n = i \mid X_0 = i] > 0 \}$, $i \in {\cal X}$. If $d(i) = 1 \; \forall i \in \mc{X}$, then the Markov chain is aperiodic; otherwise it is periodic.
\item (Matrix Representation) Define the transition probability matrix $P$ by filling entry $(i, j)$ with probability $P(i, j)$.
\item (Invariance) A distribution $\pi$ is invariant for the transition probability matrix $P$ if it satisfies the following balance equations: $\pi = \pi P$.
\end{enumerate}
\begin{figure}[H]
\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
semithick]
\tikzstyle{every state}=[fill=white,draw=black,thick,text=black,scale=1]
\node[state] (A) {$0$};
\node[state] (B) [right of=A] {$1$};
\path (B) edge [bend right] node[above] {$a$} (A);
\path (A) edge [bend right] node[below] {$b$} (B);
\path (A) edge [loop left] node {$1-b$} (A);
\path (B) edge [loop right] node {$1-a$} (B);
\end{tikzpicture}
\end{figure}
\begin{Parts}
\Part For what values of $a$ and $b$ is the above Markov chain irreducible? Reducible?
\nosolspace{1cm}
\Part For $a=1$, $b=1$, prove that the above Markov chain is periodic.
\nosolspace{1cm}
\Part For $0 < a < 1$, $0 < b < 1$, prove that the above Markov chain is aperiodic.
\nosolspace{1cm}
\Part Construct a transition probability matrix using the above Markov chain.
\nosolspace{3cm}
\Part Write down the balance equations for this Markov chain and solve them. Assume that the Markov chain is irreducible.
\nosolspace{4cm}
\end{Parts}
\Question{Analyze a Markov Chain}
Consider the Markov chain $X(n)$ with the state diagram shown below where $a, b \in (0, 1)$.
\begin{center}
\includegraphics[width=2in]{src/problems/markovchains/resources/figures/analyze-markov-chain-fig}
\end{center}
\begin{Parts}
\Part Show that this Markov chain is aperiodic;
\Part Calculate $\Pr[X(1) = 1, X(2) = 0, X(3) = 0, X(4) = 1 \mid X(0) = 0]$;
\Part Calculate the invariant distribution;
\Part Let $T_i = \min\{n \geq 0 \mid X(n) = i\}$, $T_i$ is the number of steps until we transit to state $i$ for the first time. Calculate $\E[T_2 \mid X(0) = 1]$.
\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}