\documentclass[11pt]{article}
\usepackage{fullpage,amssymb,graphicx}
\newcommand{\Q}[1]{\item {[{\em #1 pts\/}]}\ }
\newcommand{\fighere}[2]{\begin{figure}[h]\begin{center}%
\includegraphics[scale=#2]{#1.pdf}\end{center}%
\end{figure}\vspace{-\bigskipamount}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\eps}{\varepsilon}
\newcommand{\OO}{\widetilde{O}}
\newcommand{\down}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\up}[1]{\left\lceil #1\right\rceil}
\newcommand{\IGNORE}[1]{}
\begin{document}
%\thispagestyle{empty}
\hfill CS 574, Spring 2021\par\hfill Timothy Chan
\bigskip
\begin{center}\large\bf Homework 5 (due April 30 Friday 5pm (CT))
\end{center}
\medskip\noindent
{\bf Note}: This homework is shorter and will be weighted less
(counted as half of a regular homework).
\medskip\noindent
{\bf Instructions}:
You may work in groups of at most 3; submit one set of solutions per group.
Always acknowledge any discussions you have with other people and
any sources you have used (although most homework problems should be doable without using outside sources). In any case,
\emph{solutions must be written entirely in your own words}.
\begin{enumerate}
\Q{18}
Consider the Markov chain associated with the following undirected graph:
\fighere{hw5fig1}{0.9}
\begin{enumerate}
\Q{6}
Let $\pi$ be its stationary distribution. Write down a linear system of equations for $\pi=(\pi_1,\ldots,\pi_5)$ and solve for $\pi_1,\ldots,\pi_5$.
(The calculations here should be doable by hand.)
\Q{6}
Recall that $h_{j1}$ denotes the expected number of steps to reach state 1 starting at
state~$j$. Note that for $j=1$, we take $h_{11}$ to be the expected
number of steps to return to state 1 starting at state 1.
Write down a linear system of equations
for $h_{11},h_{21},\ldots,h_{51}$ (in a manner similar to the one-dimensional random walk example
from class) and solve for $h_{11},h_{21},\ldots,h_{51}$.
\Q{6}
In general, for any Markov chain where a stationary distribution $\pi$
exists with $\pi_i>0$, give a direct proof that $h_{11}=1/\pi_1$.
Do not invoke the Fundamental Theorem, but rather use the linear systems
of equations for the $\pi_i$'s and the $h_{j1}$'s.
\end{enumerate}
\bigskip
\Q{32}
Consider an undirected connected graph $G=(V,E)$.
As in class, let $h_{uv}$ be the expected number of steps to reach $v$
in a random walk starting at $u$ (the hitting time),
and let $C_s$ be the expected number of steps to visit all vertices
in a random walk starting at $s$ (the cover time).
Let $h^* = \max_{u,v\in V} h_{uv}$ and
$C^* = \max_{s\in V} C_s$.
A straightforward argument (by summing $h_{uv}$ over the edges of
a spanning tree) implies that $C^*\le O(n)\cdot h^*$
(actually, it shows $C^*\le O(n) \cdot\max_{u,v\in V:\, uv\in E} h_{uv}$).
You will consider two approaches to prove the stronger bound
$C^* \le O(\log n)\cdot h^*$.
First approach:
\begin{enumerate}
\Q{4} For any fixed vertices $u$ and $v$, first prove that the
probability that a random walk of length $\lceil 2h^*\rceil$
starting at $u$ does not visit $v$ is at most $1/2$.
\Q{6} For any fixed vertices $s$ and $v$, prove that the
probability that a random walk of length $\lceil 2h^*\rceil \cdot
\lceil c\log_2 n\rceil$
starting at $s$ does not visit $v$ is at most $1/n^c$ (by using (a)).
\Q{6} Conclude that $C^*\le O(h^*\log n)$ (by using (b)).
\end{enumerate}
Second approach:
\begin{enumerate}
\setcounter{enumii}{3}
\Q{4}
Consider a fixed (not random) walk starting at $u$.
Consider a random permutation $v_1,\ldots,v_n$ of $V$.
Let $T_i$ be the first time when $v_i$ is visited in the walk.
Let $M_i=\max(T_1,\ldots,T_i)$.
Show that $\Pr[M_i\neq M_{i-1}]=1/i$.
\Q{6}
Now consider a fixed permutation $v_1,\ldots,v_n$ of $V$.
Consider a random walk starting at $u$.
Let $T_i$ be the first time when $v_i$ is visited in the walk.
Let $M_i=\max(T_1,\ldots,T_i)$.
Show that $E[M_i-M_{i-1}\mid M_i\neq M_{i-1}] \le h^*$.
{\em Hint}: argue that the event $M_i\neq M_{i-1}$ is dependent only on
the part of the walk before time $M_{i-1}$.
\Q{6} Conclude that $C^*\le O(h^*\log n)$ (by using (d) and (e)).
Is the hidden constant factor here better or worse than in (c)?
\end{enumerate}
\end{enumerate}
\end{document}