% -*- 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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%