\documentclass[10pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{14}{April 3, 2006}{Ronitt Rubinfeld}{Kyle Burke}

%%%% body goes in here %%%%

\section{Analysis of the Markov Chain}

\subsection{Using Congestion and Canonical Paths}
How do we see that the transitions of the Markov Chain from lecture 13 has low congestion?  We use a canonical path argument.  Consider one edge, from matching $M_a$ to $M_b$.  Consider some canonical path, as specified in lecture 13, from matching $M_1$ to $M_2$ that uses this edge.  Given the edge (And the direction we cross it), we only need a small amount of additional information to uniquely identify $M_1$ and $M_2$.  The amount of information we need limits the number of canonical paths that cross the edge and thus provides a bound on congestion.

\subsection{Identifying a Path}
We will need some notation:  

Let $M_1 \oplus M_2$ be the set of edges in exactly one of $M_1, M_2$.  

Let $\overline{M} = \left(M_1 \oplus M_2\right)\setminus M_a$, though this is not necessarily a matching.

\begin{claim}
We can reconstruct $\left( M_1, M_2 \right)$ from $\left( \overline{M}, M_a, M_b\right)$.
\begin{itemize}
\item Uncorrected edges in $M_a$ match edges in $M_1$.  (We know what has been corrected, since we know the lexicographical ordering.)
\item Corrected edges in $M_a \oplus \overline{M}$ reveal the other edges of $M_1$.
\item We can determine $M_2$ similarly from $M_B$.
\end{itemize}
\end{claim}

\subsection{$\overline{M}$ is Almost a Matching}
We will sidestep the issue of the number of bits needed to specify $\overline{M}$ by bounding the congestion in terms of $n$; the size of the Markov Chain.  We notice that although $\overline{M}$ is not a matching, it can be transformed into a matching by removing at most 2 edges, due to the structure of the fixing procedure definted earlier.

With the 2 edges $e_1$ and $e_2$ such that $\overline{M}\setminus\{e_1, e_2\}$ is a matching, we can specify $\left(\overline{M}, M_a, M_b\right)$ with $\left(\overline{M}\setminus\{e_1, e_2\}, e_1, e_2, M_a, M_b\right)$.

\subsection{Putting All the Pieces Together}
Now, the matching $\overline{M}\setminus\{e_1, e_2\}$ can correspond to any state of the Markov Chain, while the edges could be any edges.  Thus, any transition from $M_a$ to $M_b$ has congestion at most $(\# \mbox{ states in Markov Chain})\cdot m^2$.  We saw, from our previous analysis of the Canonical Path Technique, that if we have congestion of  $(\# \mbox{ states in Markov Chain})\cdot \alpha$ in a $d$-regular graph, then the conductance, $\Phi_G$ is $\geq \frac{1}{d \cdot \alpha}$.  Thus, the conductance here is at least $\frac{1}{m^3}$.

\subsection{Determining the Mixing Time}
Again from the previous lecture, in order to mix we will need a number of steps equal to 

$t = \frac{4}{\left(\frac{1}{m^3}\right)^2} \ln \left(\frac{2}{\epsilon^2}\cdot (\# \mbox{ matchings})\right)$

$ = 4 m^6 \ln \left(\frac{2}{\epsilon^2}\cdot (\# \mbox{ matchings})\right)$

$ \leq 4m^6 \ln \left(\frac{2}{\epsilon^2} \cdot 2^m \right)$

$ \leq O\left(m^7 \ln \left(\frac{1}{\epsilon^2}\right)\right)$

\subsection{Conclusions for the Markov Chain}
Thus we need only a number of steps polynomial in the size of the graph and the reciprocal of the error (although this is a large polynomial).  The Markov Chain we defined in the last class will mix rapidly enough to provide near-uniform generation.

\section{Relating Linear Algebra to Mixing}

\subsection{Graphs and Linear Algebra}
Given an undirected, $d$-regular graph $G$, let $P$ be the transition matrix of $G$.   $P$ is both real and symmetric.  Recalling our Linear Algebra, we say that $v$ is an \emph{eigenvector} of $P$ with \emph{eigenvalue} $\lambda$ if $vP = \lambda v$.

\begin{theorem}
If $P$ is real and symmetric, then $\exists$ an orthonormal basis $v^{(1)}, \ldots, v^{(n)}$ of eigenvectors of $P$ with associated eigenvalues $\lambda_1, \ldots, \lambda_n$.  We will label these so that $\abs{\lambda_{i}} \geq \abs{\lambda_{i+1}}$.
\end{theorem}

Example: The transition matrix, $P$, of a random walk on a $d$-regular graph has eigenvector $\left(\frac{1}{n}, \frac{1}{n}, \cdots, \frac{1}{n}\right)$ with eigenvalue 1.

Next time:  We will review more Linear Algebra and look at relating eigenvalues of $P$ with the mixing time of $G$.


\end{document}