% -*- LaTeX -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Template for homeworks
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%**start of header

\documentclass[12pt,theorems]{mts-hw}

%**end of header
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsmath}
\usepackage{amsfonts}
\newtheorem{fact}[theorem]{Fact}
\def\ZZ{\mathbb{Z}}
\def\RR{\mathbb{R}}
\def\CF{{\cal F}}
\def\CA{{\cal A}}
\def\CB{{\cal B}}
\def\pr{\mbox{P}}
\def\ex{\mbox{E}}


\begin{document}

\class {CSL857}{Randomized algorithms}      % Note: two arguments.

\author{Your name here}            

\prof {Amitabha Bagchi}                                                       
%
% Lecturer's name
%

\hwnumber{4}
% Homework number

\sem{II Sem, 2012-13}
% semester name

\due{12th April 2013, 11:59PM}
        
\makeheader  

\noindent{\bf Q1. (Levin et. al.  Ex 2.8, page 34)} Show that if a
random walk on a group is reversible then the increment distribution
is symmetric.

% insert answer here.

\noindent{\bf Q2. (Levin et. al.  Ex 2.10, page 34)} Read Section 2.7
of Levin's book which was skipped in class and then solve the
following problem. Let $\{S_n\}_{n \geq 0}$ be the simple random walk
on $\ZZ$. Use the reflection principle discussed in Section 2.7 to
show that
\[\pr\left(\max_{i \leq j \leq n} |S_j| \geq c \right) \leq 2
\pr(|S_n|\geq c).\]

% insert answer here.

\noindent{\bf Q3. (Levin et. al. Ex 4.3 and Ex 4.4, page 59)} Let $P$
be the transition matrix of a Markov chain with state space $\Omega$
and let $\mu$ and $\nu$ be any two distributions on $\Omega$. Prove
that 
\[ \lVert \mu P - \nu P\rVert_{TV} \leq \lVert\mu - \nu\rVert_{TV}.\]
Use this fact, or prove otherwise that for a Markov chain with
stationary distribution $\pi$, for any $t \geq 0$
\[ d(t+1) \leq d(t).\]

% insert answer here.

\noindent{\bf Q4. } Given a simple random walk on a graph the {\em
  hitting time} of vertex $j$ starting from vertex $i$, denoted
$H_{i,j}$, is the expected number of steps taken to reach $j$ starting
from $i$. And the cover time of the random walk starting from node
$i$, denoted $C_i$, is the expected number of steps taken to visit
every node of the graph at least once when the walk is started from
node $i$. The cover times of the random walk, $C$, is $\max_{i \in V}
C_i$. 

\noindent{\bf Q4.1.} What is the hitting time of any pair $H_{i,j}$ in
the random walk on a complete graph on $n$ nodes? 

\noindent{\bf Q4.2.} Compute the cover time of the random walk on the
complete graph on $n$ nodes.

\noindent{\bf Q4.3.} Prove that if $H = \max_{i,j\in V}H_{i,j}$ for a
random walk on some graph $G$ of size $n$, then $C \leq 2 \log n \cdot
H$. ({\bf Hint.} Prove that if $b$ is the time taken to vist at least half
the nodes of the graph then $b \leq 2H$.)




% insert answer here.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%