\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}
\usepackage{fullpage,graphicx}
\usepackage{mathtools,amsfonts,amsthm,amssymb,multirow}
\usepackage{algorithmic,comment,url,enumerate}
\usepackage{tikz}
\usepackage{framed}
\usetikzlibrary{decorations.pathreplacing, shapes}
\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}
\usepackage[normalem]{ulem}
\newcommand{\mkw}[1]{\textcolor{red}{[ #1 --mary ]}}

\newtheorem{claim}{Claim}

\newcommand{\eps}{\epsilon}
\newcommand{\Ex}[1]{\operatorname*{\mathbb{E}}\left[#1\right]}
\newcommand{\note}[1]{\noindent{[\textbf{NOTE:} \em #1 \em]}}
\newcommand{\pmin}{p_{\textrm{min}}}
\newcommand{\R}{\mathbb{R}}

\begin{document}
\noindent
\textbf{Problem Set 7 \ifdefined\sol Solution \fi} \hfill CS265, Autumn 2023
\ifdefined\sol\else
\newline
Due: Friday December 1 at 11:59PM
\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}

\begin{enumerate}

\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{11} Let $n > 2$, and consider the Markov chain $\{X_t\}$ defined on the states $\{0,1,\ldots,n\}$ consisting of a random walk with reflecting barriers at $0$ and $n$:
\begin{center}
\begin{tikzpicture}[scale=1.6]
\foreach \x in {0,1,2,3,4}
{
	\node[draw, circle](a\x) at (\x,0) {\x};
}
\node[draw, circle](anm2) at (6,0) {\small $n-2$};
\node[draw, circle](anm1) at (7,0) {\small $n-1$};
\node[draw, circle](an) at (8,0) {$n$};
\foreach[evaluate={\y=int(\x+1)}]\x in {1,2,3}{
\draw[->] (a\x) to[out=30,in=150,edge node={node [above]{\footnotesize$1/2$}}] (a\y);
\draw[->] (a\y) to[out=-150,in=-30,edge node={node [below]{\footnotesize$1/2$}}] (a\x);
}
\draw[->] (anm2) to[out=30,in=150,edge node={node [above]{\footnotesize$1/2$}}] (anm1);
\draw[->] (anm1) to[out=30,in=150,edge node={node [above]{\footnotesize$1/2$}}] (an);
\draw[->] (anm1) to[out=-150,in=-30,edge node={node [below]{\footnotesize$1/2$}}] (anm2);
\draw[->] (an) to[out=-150,in=-30,edge node={node [below]{\footnotesize$1$}}] (anm1);
\draw[->] (a0) to[out=30,in=150,edge node={node [above]{\footnotesize$1$}}] (a1);
\draw[->] (a1) to[out=-150,in=-30,edge node={node [below]{\footnotesize$1/2$}}] (a0);
\node at (5,0) {\Huge $\cdots$};
\end{tikzpicture}
\end{center}

  That is, $\{X_t\}$ is defined by the following transition probabilities: 
\begin{itemize}
\item For $i \in \{1,\ldots,n-1\}$, we have \[ \Pr[X_t = i+1|X_{t-1}=i]=\Pr[X_t = i-1|X_{t-1}=i] = \frac{1}{2}.\]
\item At $0$ and $n$, we have reflecting barriers:
\[ \Pr[X_t = 1|X_{t-1}=0]=\Pr[X_t = n-1|X_{t-1}=n] = 1. \]
\end{itemize}
\begin{enumerate}

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

\item \pts{5} 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\}$.  Define a coupling for $\tilde{X}_t$ that ensures that the two chains in your coupling ``never cross without meeting.''  That is, if you are coupling $\{\tilde{X}_t\}$ and $\{\tilde{Y}_t\}$, you should ensure that if $\tilde{X}_0 \le \tilde{Y}_0,$ then it will hold that $\tilde{X}_t \le \tilde{Y}_t$ for all $t$.

\item \pts{4} Show that $\{\tilde{X}_t\}$ has a unique stationary distribution, and that the mixing time of $\{\tilde{X}_t\}$ is bounded by $O(n^2)$.  

\hint{To bound the mixing time, use the coupling you defined in part (b).}

\hint{Recall Lemma 6 from Class 13, which says that if $Z_t$ is a walk on $\{0,1,2,\ldots\}$ with a reflecting barrier at $0$ (so $\Pr[Z_t = 1 | Z_{t-1} = 0] = 1$, and otherwise $Z_t = Z_{t-1} \pm 1$ with probability $1/2$ each), then the expected amount of time before $Z_t = n$, given that $Z_0 \leq n$,  is at most $n^2$.}

\end{enumerate}

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



\end{enumerate}

\end{document}
