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

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

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

\noindent{\bf Q1. (Kazdan, Linear Algebra, Spring 2012,
  Univ. Pennsylvania)} Suppose that $\lambda$ is an eigenvalue of an
$n \times n$ matrix and let $E_\lambda$ be the set of all eigenvectors
with the same eigenvalue. Show that $E_\lambda$ is a linear subspace
of $\RR^n$. 

% insert answer here.

\noindent{\bf Q2. (Levin et. al.  Ex 1.7, page 18)} A transition matrix
$P$ is symmetric if $P(x,y) = P(y,x)$ for all $x,y \in \Omega$. Show
that if $P$ is symmetric then the uniform distribution on $\Omega$ is
stationary for $P$.

% insert answer here.

\noindent{\bf Q3. (Levin et. al.  Ex 1.8, page 19)} Let $P$ be a
transition matrix that is reversible with respect to the probability
distribution $\pi$ on $\Omega$. Show that the transition matrix $P^2$
corresponding to two steps of the chain is also reversible with
respect to $\pi$.

% insert answer here.

\noindent{\bf Q4. (Levin et. al.  Ex 1.13, page 19)} A direct proof of
the uniqueness of the stationary distribution of an irreducible chain
can be given starting from the following argument: Given two
stationary distributions $\pi_1$ and $\pi_2$, consider the state $x
\in \Omega$ that minimizes $\pi_1(x)/\pi_2(x)$ and show that all $y$
with $P(x,y) > 0$ have $\pi_1(x)/\pi_2(x) = \pi_1(y)/\pi_2(y)$. Argue
this and complete the proof.

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