\Question{Function of a Markov Chain}
Let $X_n$ be a Markov chain on the state space $\mc{X}$ and let $f : \mc{X} \to \mc{X}$ be a function on the state space. Give an example to show that $f(X_n)$ may not be a Markov chain. [\textit{Hint}: A sequence $Y_n$ is not a Markov chain if it does not satisfy the Markov property
\begin{align*}
\Pr(Y_{n+1} = j \mid Y_{n} = i, Y_{n-1} = i_{n-1}, \dotsc, Y_0 = i_0) = \Pr(Y_{n+1} = j \mid Y_{n} = i)
\end{align*}
for all $i_0, \dotsc, i_{n-1}, i, j \in \mc{X}$ and $n \in \N$.]
\Question{Reflecting Random Walk}
Alice starts at vertex 0 and wishes to get to vertex $n$. When she is at vertex 0 she has a probability of 1 of transitioning to vertex 1. For any other vertex $i$, there is a probability of $1/2$ of transitioning to $i+1$ and a probability of $1/2$ of transitioning to $i-1$.
\begin{Parts}
\Part What is the expected number of steps Alice takes to reach vertex $n$? Write down the hitting-time equations, but do not solve them yet.
\Part Solve the hitting-time equations. [\textit{Hint}: Let $R_i$ denote the expected number of steps to reach vertex $n$ starting from vertex $i$. As a suggestion, try writing $R_0$ in terms of $R_1$; then, use this to express $R_1$ in terms of $R_2$; and then use this to express $R_2$ in terms of $R_3$, and so on. See if you can notice a pattern.]
\end{Parts}
\Question{Boba in a Straw}
Imagine that Wan Fung is drinking milk tea and he has a very short straw: it has enough room to fit two boba (see Figure \ref{fig:straw}).
\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 Wan Fung drinks from the straw, the following happens every second:
\begin{enumerate}
\item The contents of the top component enter Wan Fung'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 Wan Fung 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 Wan Fung 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 Wan Fung'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}
\Question{Online Product Sampling}
Suppose you are manufacturing bags of coffee beans. You want to guarantee that your product tastes amazing. In fact, the manufacturing process is not perfect, and a fraction $p$ of your bags do not taste amazing. In the industry, it is crucial for you to perform inspections.
One strategy for performing inspections is the following:
\begin{enumerate}
\item \textbf{High Sampling}: Inspect every bag of coffee until $m$ consecutive bags taste amazing; then switch to low sampling.
\item \textbf{Low Sampling}: Sample one bag out of every $k$ bags uniformly at random (in other words, for each bag, sample it with probability $1/k$); if the sample does not taste amazing, then switch to high sampling.
\end{enumerate}
[As a side-note: why do we not simply inspect every bag? The answer is that an inspected bag of coffee can no longer be sold.]
We will use a Markov chain model on $\mc{X} = \{0, \dotsc, m\}$. The state $i \in \{0, \dotsc, m-1\}$ represents the \textbf{High Sampling} state where we have tasted $i$ consecutive amazing bags. The state $m$ represents the \textbf{Low Sampling} state.
\begin{Parts}
\Part Write down the balance equations, but do not solve them.
\Part For the rest of this problem, you may assume that $m = 2$ (so we have a three-state Markov chain). Compute the stationary distribution $\pi$.
\Part Under this inspection strategy, what is the long-run fraction of bags which are inspected?
\Part Under this inspection strategy, what is the long-run fraction of bags of coffee which are sold (i.e.\ not inspected) and don't taste amazing?
\end{Parts}
\Question{Continuous LLSE}
Suppose that $X$ and $Y$ are uniformly distributed on the shaded region in Figure \ref{fig:continuous-llse}.
\begin{figure}[h]
\centering
\begin{tikzpicture}[scale=3]
\draw[fill, gray!50] (0, 0) -- (1, 0) -- (1, 1) -- (0, 1) -- (0, 0);
\draw[fill, gray!50] (1, 1) -- (2, 1) -- (2, 2) -- (1, 2) -- (1, 1);
\draw[thick, ->] (0, 0) -- (0, 2.5);
\draw[thick, ->] (0, 0) -- (2.5, 0);
\node[below] at (2.5, 0) {$x$};
\node[left] at (0, 2.5) {$y$};
\node[left] at (0, 2) {$2$};
\node[left] at (0, 1) {$1$};
\node[below left] at (0, 0) {$0$};
\node[below] at (1, 0) {$1$};
\node[below] at (2, 0) {$2$};
\end{tikzpicture}
\caption{The joint density of $(X, Y)$ is uniform over the shaded region.}
\label{fig:continuous-llse}
\end{figure}
That is, $X$ and $Y$ have the joint distribution:
\begin{align*}
f_{X, Y}(x, y) &= \begin{cases}
1/2, & 0 \leq x \leq 1, 0 \leq y \leq 1 \\
1/2, & 1 \leq x \leq 2, 1 \leq y \leq 2
\end{cases}
\end{align*}
\begin{Parts}
\Part Do you expect $X$ and $Y$ to be positively correlated, negatively correlated, or neither?
\Part Compute the marginal distribution of $X$.
\Part Compute $L[Y \mid X]$.
\Part What is $\E[Y \mid X]$?
\end{Parts}
\Question{First Exponential to Die}
Let $X$ and $Y$ be $\operatorname{Expo}(\lambda_1)$ and $\operatorname{Expo}(\lambda_2)$ respectively. What is $\Pr(\min(X, Y) = X)$, the probability that the first of the two to die is $X$?
[\textit{Hint}: consider the ideas in Midterm 2, Problem 5, Part 11. Note that in continuous probability, integrals are analagous to sums in discrete probabilty.]