\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}
\usepackage{mathtools}
\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}}
\newcommand{\Ex}[1]{\operatorname*{\mathbb{E}}\left[#1\right]}
\newcommand{\eps}{\epsilon}
\newcommand{\note}[1]{\noindent{[\textbf{NOTE:} \em #1 \em]}}
\newcommand{\pmin}{p_{\textrm{min}}}
\newcommand{\R}{\mathbb{R}}

\definecolor{shadecolor}{gray}{0.95}


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

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

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

\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 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

\item \pts{9} \textbf{Fundamental Theorem of Markov Chains: A Special Case}


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 \coloneqq \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 \pts{2} 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} \pts{3} 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 \pts{2} 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 \pts{0} \textbf{[Optional: this won't be graded.]} 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


\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 each neighboring states with equal probability $1/n$.  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



\end{enumerate}
\end{document}