\documentclass[11pt]{article}
% Problem set: do not define TEMPLATE or SOL
% LaTeX template: define TEMPLATE but not SOL
% Solution: define both TEMPLATE and SOL
%
%\def\sol{1}
\def\template{1}
% STUDENTS:
% You can enter your solutions into this template by just
% typing them right after it says "SOLUTION".
% Ignore the \ifdefined\sol blocks; you can delete them if you want.
% (Note that it won't compile if you try to uncomment the
% solution flag :))
%
\usepackage{fullpage,graphicx}
\usepackage{amsmath,amsfonts,amsthm,amssymb,multirow}
\usepackage{algorithmic,comment,url,enumerate}
\usepackage{tikz}
\usepackage{framed}
\usetikzlibrary{decorations.pathreplacing, shapes}
\usetikzlibrary{automata, positioning, arrows}
\usepackage[ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e}
\newcommand{\expecting}[1]{\noindent{[\textbf{We are expecting:} \em #1\em]}}
\newcommand{\hint}[1]{\noindent{[\textbf{HINT:} \em #1 \em]}}
\newcommand{\pts}[1]{\textbf{(#1 pt.)}}
\newcommand{\sgn}{\mathrm{sgn}}
\definecolor{shadecolor}{gray}{0.95}
\newcommand{\bE}{\mathbb{E}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\eps}{\epsilon}
\newtheorem{theorem}{Theorem}
\newtheorem{assumption}{Assumption}
\newtheorem{definition}{Definition}

\begin{document}
\noindent
\textbf{Problem Set 7 \ifdefined\sol Solution \fi} \hfill CS265/CME309, Winter 2026
\ifdefined\sol\else
\newline
Due: Friday 3/6, 11:59pm on Gradescope
\ifdefined\template
\newline 
Group members: INSERT NAMES HERE
\fi

\vspace{.4cm}\noindent
Please follow the homework policies on the course website.
\fi

\noindent
\rule{\linewidth}{0.4pt}

\noindent


\begin{enumerate}



\item \pts{7} \textbf{Coin Tossing Revisited}
\begin{enumerate}
    \item \pts{4} Consider the following Markov chain:    
    \begin{center}

\begin{tikzpicture}[->, >=stealth', auto, node distance=2.4cm, semithick]
    \tikzstyle{every state}=[fill=white,draw=black,minimum size=24pt]
    % Define the states on a horizontal line
    \node[state] (0) {0};
    \node[state, right of=0] (1) {1};
    \node[state, right of=1] (2) {2};
    \node[state, right of=2] (3) {3};
    \node[right of=3, xshift=-0.4cm] (dots) {\(\dots\)};
    \node[state, right of=dots, xshift=-0.4cm] (km1) {\(k-1\)};
    \node[state, right of=km1] (k) {\(k\)};

    % Forward transitions 
    \draw[->]
      (0) edge[bend right=30] node[below] {\(\tfrac{1}{2}\)} (1);
      \draw[->](1) edge[bend right=30] node[below] {\(\tfrac{1}{2}\)} (2);
      \draw[->](2) edge[bend right=30] node[below] {\(\tfrac{1}{2}\)} (3);
      \draw[->](km1) edge[bend right=30] node[below] {\(\tfrac{1}{2}\)} (k);
      \draw[->](3) edge[bend right=10] (8,-.3);
      \draw[->] (10.3,-.3) to (km1);

    % Backward transitions to state 0 
    \draw[->]
      (1) edge[bend right=30] node[below,pos=0.5] {\(\tfrac{1}{2}\)} (0);
      \draw[->]
      (2) edge[bend right=40] node[below,pos=0.2] {\(\tfrac{1}{2}\)} (0);
      \draw[->]
      (3) edge[bend right=50] node[below,pos=0.2] {\(\tfrac{1}{2}\)} (0);
\draw[->]
      (km1) edge[bend right=60] node[below,pos=0.2] {\(\tfrac{1}{2}\)} (0);

    % From state k back to 0 with probability 1
    \draw[->]
      (k) edge[bend right=70] node[below,pos=0.2] {\(1\)} (0);
    % self loop at 0
    \draw
      (0) edge[loop left] node {\(\tfrac{1}{2}\)} (0);

\end{tikzpicture}

    \end{center}
    Prove that this Markov chain has a unique stationary distribution $\pi$, and determine what it is.  

\hint{In case it's helpful, $\sum_{j=0}^k 2^{-j} = 2 - 2^{-k}$.}

\item \pts{3} Recall that, in HW1, you (optionally) showed that the expected number of fair coin flips until you see $k$ heads in a row is $2^{k+1}-2$.  Explain how to see this from the stationary distribution $\pi$ that you computed in part (a).  

\emph{Note: Your explanation should contain (i) the connection between that problem and the Markov chain in part (a); and (ii) a short but complete proof of the fact that the answer is $2^{k+1}-2$. }


\end{enumerate}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/coin2.tex}
\fi
\end{shaded}
\fi


\newpage
%%%%%%%%%% Random walks %%%%%%%%


\item \pts{7} \textbf{Random Walks on the Hypercube} 

Earlier this quarter, we studied randomized routing on the hypercube. In this problem, we examine random walks on the hypercube. Let $n > 2$, and consider the Markov chain $\{X_t\}$ defined on the states $\{0,1\}^n$ where at each step, the chain moves to a uniformly random neighboring state.  That is, $\{X_t\}$ is defined by the following transition probabilities: 
    \[\Pr[X_t = x^{(i)} \mid X_{t-1} = x] = \frac{1}{n},
    \]
    where \( x^{(i)} \) is the state that differs from \( x \) only in the \( i \)-th bit.
\begin{enumerate}


\item \pts{1} 
Is this chain periodic or aperiodic?   Is it irreducible?  
Justify your answers in one sentence each.

\item  \pts{1} Consider the ``lazy'' version of $\{X_t\}$ that, at every timestep, flips a fair coin and with probability $1/2$ stays in its current state, and with probability $1/2$ transitions as prescribed above.  Call this lazy version $\{\tilde{X}_t\}$. Show that $\{\tilde{X}_t\}$ has a unique stationary distribution. 

\item \pts{5} Show that the mixing time of $\{\tilde{X}_t\}$ is bounded by $O(n \log n)$.
\hint{Define a coupling.}
\end{enumerate}


\ifdefined\template
\begin{shaded} \textbf{SOLUTION:}
\ifdefined\sol
\input{solution/markov2}
\fi
\end{shaded}
\fi

%%%%%%%%%%% Umbrellas

\vspace{1cm}
\item \pts{6} Mary commutes back and forth between her home and her office (by walking).  At time $t=0$, she goes from home to office; at time $t=1$ she goes from office to home; at time $t=2$ she goes from home back to office; and so on.  Mary has four umbrellas, which are either at her home or at her office.  At each timestep, if it is raining and there is an umbrella in the location Mary is leaving, she takes an umbrella with her to the other location.  If it is not raining, she doesn't take an umbrella.  If it is raining and there is no umbrella in the location she is leaving, she walks in the rain without an umbrella and gets wet.

Suppose that it rains independently with probability $p$ at each time step, for $p \in (0,1)$.  Suppose also that this process goes on for a long time.  

\begin{enumerate}
    \item \pts{6} What is the probability that Mary is in danger of getting wet at time $t$, for large enough $t$?  That is, what is
\[ \lim_{t \to \infty} \Pr[ \text{Mary is in a location with zero umbrellas at time $t$} ]? \]

You should give an answer in terms of $p$.
Justify your answer.
    \item \pts{0} \textbf{[Optional: this part won't be graded.]}  What is the answer if Mary has $k$ umbrellas instead of $4$?  Suppose that Mary wants her odds of being umbrella-less to be most $0.05$; that is,
    \[ \lim_{t \to \infty} \Pr[ \text{Mary is in a location with zero umbrellas at time $t$} ] \leq 0.05, \]and suppose that $p = 0.1$ (at least, during the winter quarter).  How many umbrellas should she have?
\end{enumerate}

\ifdefined\template
\begin{shaded} \textbf{SOLUTION:}
\ifdefined\sol
\input{solution/umbrellas}
\fi
\end{shaded}
\fi


\newpage
%%%%%%%%%% Proof of fundamental thm of markov chains (special case)


\item \pts{0} \textbf{[Optional: this whole problem won't be graded]  Proving a Special Case of the Fundamental Theorem of Markov Chains}

\newcommand{\pmin}{p_{\mathrm{min}}}

Let $X_0, X_1, \ldots$ be a Markov chain over $n$ states (labeled $1, 2, \ldots, n$) with transition matrix $P \in \R^{n\times n}$, i.e., for any $t \ge 0$, $\Pr[X_{t+1} = j| X_t = i] = P_{ij}$. In addition, we assume that $P_{ij} > 0$ for all $i, j \in [n]$, and define $\pmin := \min_{i,j\in[n]}P_{ij} > 0$. In this problem, we will prove part of the fundamental theorem of Markov chains for this special case. In particular, we will show that there exists a unique stationary distribution $\pi$ such that for all $i, j \in [n]$,
\[
    \lim_{t\to+\infty}\Pr[X_t = j|X_0 = i] = \pi_j.
\]


\begin{enumerate}
    \item  As a warmup, show that the assumption $P_{ij} > 0$ for all $i, j \in [n]$ implies that the Markov chain is irreducible and aperiodic. Thus, the assumption that we made is not weaker than the one in the original theorem.




    \item\label{part:1-norm} \pts{2} Let $a = \begin{bmatrix}a_1 & a_2 & \cdots & a_n\end{bmatrix}$ be a row vector that satisfies $\sum_{i=1}^{n}a_i = 0$. Prove that $\|aP\|_1 \le (1 - n\pmin /2)\|a\|_1$.


    \hint{You can use the following fact: For vectors $a, b \in \R^n$ satisfying $\sum_{i=1}^{n}a_i = 0$ and $\min_{i\in[n]}b_i \ge \eps > 0$,  $\left|\sum_{i=1}^na_ib_i\right|\le \sum_{i=1}^{n}|a_i|b_i - \frac{\eps}{2}\sum_{i=1}^{n}|a_i|$.}




    \item\label{part:pi} Prove that there exists an $n$-dimensional row vector $\pi = \begin{bmatrix}\pi_1 & \pi_2 & \cdots & \pi_n\end{bmatrix}$ such that: (1) $\pi = \pi P$; (2) $\sum_{i=1}^{n}\pi_i = 1$.
    
    \hint{First prove the existence of a non-zero vector $\pi$ satisfying $\pi = \pi P$, and then show that the second condition can be satisfied by scaling $\pi$. For the first step, you may use the following fact without proof: if $\lambda$ is an eigenvalue of a square matrix $A$, $\lambda$ is also an eigenvalue of $A^T$. Part~\ref{part:1-norm} might be helpful for the second step.}


    \item  Let $v = \begin{bmatrix}v_1 & v_2 & \cdots & v_n\end{bmatrix}$ be a row vector that satisfies $\sum_{i=1}^nv_i = 1$. Let $\pi$ be a vector chosen as in Part~\ref{part:pi}. Prove that $\lim_{t\to+\infty}vP^t = \pi$. Then, derive that for all $i, j \in [n]$,
        \[\lim_{t\to+\infty}\Pr[X_t = j|X_0 = i] = \pi_j.\]


    \hint{Apply Part~\ref{part:1-norm} to $(v - \pi), (v - \pi)P, (v - \pi)P^2, \ldots$.}


    \item  \textbf{[Extra optional]} Extend the proof to the general case, where the Markov chain is irreducible and aperiodic but $P_{ij} > 0$ might not hold.
\end{enumerate}


\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/proof.tex}
\fi
\end{shaded}
\fi


\end{enumerate}
\end{document}
