% -*- 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{5}
% Homework number

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

\due{22nd April 2013, 11:59PM}
        
\makeheader  

\noindent{\bf Q1. (Levin et. al. Ex 5.1, page 73)} Show that when
$(X_t, Y_t)$ is a coupling satisfying the condition that if $X_s =
Y_s$ then $X_t = Y_t, t \geq s$, for which $X_0$ follows the
distribution $\mu$ and $Y_0$ is distributed as $\nu$, then 
\[ \lVert \mu P^t - \nu P^t \rVert_{TV} \leq \pr(\tau_c > t),\]
where $\tau_c$ is the coupling time of the two chains. Further, use
this result to give an alternate proof of the convergence theorem.

% insert answer here.

\noindent{\bf Q2. (Source: Dana Randall's class on Markov Chain Monte
  Carlo Methods, CS8803, 2010)} Consider two positive integers $n,k$
with $k \leq n/2$. Let $\Omega$ be the set of all subsets of
$\{1,2,\ldots,n\}$ of size $k$. We define a lazy Markov chain on
$\Omega$ as follows: Given a state $S$, with probability 1/2 do
nothing. Otherwise, pick at random $a \in S$ and $b \in
\{1,2,\ldots,n\} \setminus S$ and move to state $S \setminus \{a\}
\cup \{b\}$.

\begin{enumerate}
\item What is the stationary distribution of this Markov chain?

\item Use a coupling argument to upper bound $t_{\mbox{mix}}$ or $t_{\mbox{mix}}(\epsilon)$.
\end{enumerate}


% insert answer here.


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