\Question \textbf{Three Tails}
You flip a fair coin until you see three tails in a row. What is the average number of heads that you'll see until getting $TTT$?
\Question \textbf{Aperiodicity}
In this problem, we explore the concept of aperiodicity.
\begin{enumerate}
\item Can you find a finite irreducible aperiodic Markov chain whose distribution does not converge?
\item Construct a finite Markov chain that is a sequence of i.i.d. random variables. Is it necessarily irreducible and aperiodic? What is its invariant distribution?
\end{enumerate}
\Question \textbf{Markov's Coupon Collecting}
Courtney is home for Thanksgiving and needs to make some trips to the Traitor Goes grocery store to prepare for the big turkey feast. Each time she goes to the store before the holiday, she receives one of the $n$ different coupons that are being given away. You may recall that we studied how to calculate the expected number of trips to the store needed to collect at least one of each coupon. Using geometric distributions and indicator variables, we determined that expected number of trips to be $n(\ln(n + \gamma))$.
Let's re-derive that, this time with a Markov chain model and first step equations.
\begin{enumerate}
\item Define the states and transition probabiltiies for each state (explain what states can be transitioned to, and what probabilities those transitions occur with).
\item Now set up first step equations and solve for the expected number of grocery store trips Courtney needs to make before Thanksgiving so that she can have at least one of each of the $n$ distinct coupons.
\end{enumerate}
\Question \textbf{Function of a Markov Chain}
Show that a function $Y(n) = g(X(n))$ of a Markov chain $X(n)$ may not be a Markov chain.
\Question \textbf{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{enumerate}
\item Show that this Markov chain is aperiodic;
\item Calculate $P[X(1) = 1, X(2) = 0, X(3) = 0, X(4) = 1 \mid X(0) = 0]$;
\item Calculate the invariant distribution;
\item Let $T_i = \min\{n \geq 0 \mid X(n) = i\}$. Calculate $E[T_2 \mid X(0) = 1]$.
\end{enumerate}
\Question \textbf{Continuous Computations}
Let $X$ be a continuous random variable whose pdf is $cx^3$ (for some constant $c$) in the range $0\le x\le 1$, and is $0$ outside this range.
\begin{enumerate}
\item Find $c$
\item Find $\Pr\big[\frac{1}{3}\le X\le\frac{2}{3}~~\big|~X\le\frac{1}{2}\big]$.
\item Find $\text{E}(X)$.
\item Find $\text{Var}(X)$.
\end{enumerate}
\Question \textbf{Uniform Means}
Let $X_1, X_2, \dots, X_n$ be $n$ indepdent and identically distributed uniform random variables on the interval $[0, 1]$.
\begin{enumerate}
\item Let $Y = \text{min}\{X_1, X_2, \dots, X_n\}$. Find $\text{E}(Y)$.
\item Let $Z = \text{max}\{X_1, X_2, \dots, X_n\}$. Find $\text{E}(Z)$.
\end{enumerate}
\textit{Hint: Find the cdf first.}