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


\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{7}{March 11, 2009}{Ronitt Rubinfeld}{Dror Marcus, Yaron Ziner}

%%%% body goes in here %%%%
\section{Lecture Outline}
\subsection{List Of Subjects}
\begin{itemize}
\item Linear Algebra Review
\item Mixing Times
\item Mixing \& Saving Random Bits
\item Mixing \& Uniform Generation Of Matching
%
\end{itemize}
\subsection{General Plan}
In the last lecture, the notion of stationary distribution was defined. This lecture will focus on analyzing the time it takes to reach (or at least come fairly close to) such stationary distribution. We will refer to the time taking us to reach the stationary distribution as the \textit{Mixing Time}. To do so we will be using linear algebra, therefore, first we will refresh on some basic definitions and theorems of linear algebra.\\\\
We will also classify Markov Chains by the time it takes to reach their respective stationary distributions. Markov Chains with fast mixing times (such as CLIQUE) will be classified as \textit{good} while Markov Chains with slow mixing time (such as PATH or LOLLIPOP) we be classified as \textit{bad}.\\\\
Next, a new way for reducing random bits used in a randomized algorithm using random walks will be described.\\\\
Getting to the end of the lecture we will begin the subject of uniform generation of matching in a given graph using Markov Chains. We will do so by showing an algorithm for the construction of a \textit{good} Markov Chain Graph (i.e. with fast mixing times).
%
\section{Linear Algebra Review}
\subsection{Basic Definitions And Theorems}
\begin{definition}$v$ is an \emph{eigenvector} of a matrix $A$ with corresponding \emph{eigenvalue} $\lambda$ if $Av=\lambda v$.
\end{definition}
\begin{definition}The $L_2$ norm of vector $v$, marked as $\|v\|_2$, is $\|v\|_2 = \sqrt{\sum_{i=1}^n{v_i^2}}$
\end{definition}
\begin{definition} A set of vectors, $v^{(1)},v^{(2)},...,v^{(n)}$ are \emph{orthonormal} if $\forall i,j\in [1,n]$:
\end{definition}
\begin{equation*}
 v^{(i)} \cdot v^{(j)} =
\begin{cases}
1 & if\: i=j\: \text{(i.e. `normal')}\\
0 & if\: i\not =j \:\text{(i.e. `orthogonal')}
\end{cases}
\end{equation*}
\begin{theorem} (Unproven in this scribe) Given an $n\times n$ transition matrix P s.t. P is real and symmetrical, there exists eigenvectors $v^{(1)},v^{(2)},..,v^{(n)}$ for which the following holds:
\begin{enumerate}
\item $v^{(1)},v^{(2)},..,v^{(n)}$ form an orthonormal basis.
\item $v^{(1)},v^{(2)},..,v^{(n)}$ have corresponding eigenvalues s.t. $\lambda_1 = 1,\lambda_2,..,\lambda_n$, s.t.
$|\lambda_1| \leq |\lambda_2| \leq .. \leq |\lambda_n|$.
\item $v^{(1)} = \frac{1}{\sqrt{n}}(1,1,...,1)$.
\end{enumerate}
\end{theorem}
\begin{observation}
If $v^{(1)},v^{(2)},..,v^{(n)}$ form an orthonormal basis, then \textbf{any} vector w is expressible as \[w=\sum\alpha_i v^{(i)}\] also w's $L_2$ norm can be expressed as \[\|w\|_2=\sqrt{(\sum_i \alpha_i v^{(i)} )\cdot (\sum_j \alpha_j v^{(j)} )} =\sqrt{\sum_{i,j}\alpha_i \alpha_j v^{(i)}v^{(j)}}=\sum_i \alpha_i^2\]
\end{observation}
%
\subsection{Important Facts About Eigenvectors And Eigenvalues}
Given $n \times n$ matrix $P$ with eigenvectors $v^{(1)},v^{(2)},..,v^{(n)}$ and corresponding eigenvalues $\lambda_1,\lambda_2,..,\lambda_n$:
\begin{itemize}
\item For every scalar $\alpha$, matrix $\alpha P$ has eigenvectors $v^{(1)},v^{(2)},..,v^{(n)}$  with corresponding eigenvalues $\alpha\lambda_1,\alpha\lambda_2,..,\alpha\lambda_n$.
    \subitem \textbf{Proof}: Given $v^{(i)}$, $1\leq i \leq n$, the following holds - $(\alpha P)v^{(i)}=\alpha(Pv^{(i)})=\alpha\lambda_iv^{(i)}$.
\item Matrix P+I eigenvectors are $v^{(1)},v^{(2)},..,v^{(n)}$  with corresponding eigenvalues $\lambda_1 + 1,\lambda_2 + 1,..,\lambda_n + 1$.
    \subitem \textbf{Proof}: Given $v^{(i)}$, $1\leq i \leq n$, the following holds - $(I + P)v^{(i)}=(Iv^{(i)}+Pv^{(i)})=v^{(i)}+\lambda_iv^{(i)}=(1+\lambda_i)v^{(i)}$.
\item Matrix $P^k$ eigenvectors are $v^{(1)},v^{(2)},..,v^{(n)}$  with corresponding eigenvalues $\lambda_1^k,\lambda_2^k,..,\lambda_n^k$.
    \subitem \textbf{Proof}: Given $v^{(i)}$, $1\leq i \leq n$, the following holds - $(P^k)v^{(i)}=(P^{k-1})Pv^{(i)}=(P^{k-1})\lambda_iv^{(i)}=\lambda_i(P^{k-1})v^{(i)}=...=\lambda_i^{k-1}Pv^{(i)}=\lambda_i^kv^{(i)}$.
\item If P is a stochastic matrix then, $\forall i\in[1,n]$, $|\lambda_i|\leq 1$.
\end{itemize}
%
\subsection{Example}
Let P be the transition matrix for a d\_regular undirected graph (Notice that in this case the matrix is double stochastic, i.e., every row and every column sum to one, and has $d$ non zero entries), then:
\begin{enumerate}
\item The vector $(\frac{1}{n},....,\frac{1}{n})$ is the stochastic distribution and is an eigenvector of P with eigenvalue one i.e., $(\frac{1}{n},....,\frac{1}{n})P=1(\frac{1}{n},...,\frac{1}{n})$. Also notice that $|(\frac{1}{n},...,\frac{1}{n})|_1 = 1$.
\item The vector $(\frac{1}{\sqrt{n}},....,\frac{1}{\sqrt{n}})$ is also an eigenvector of P with eigenvalue one. Also notice that $|(\frac{1}{n},....,\frac{1}{n})|_2 = 1$.
\end{enumerate}
%
\section{Mixing Times}
\begin{definition}
Given $\varepsilon>0$ the \emph{mixing time} $T(\varepsilon)$ of a Markov Chain $A$ with a unique stationary distribution $\overline{\Pi}$ is the minimum $t$ s.t. $\forall \Pi^{(0)}$, $|\overline{\Pi}-\Pi^{(0)}A^t|_1<\varepsilon$
\end{definition}
\begin{definition}
Markov Chain $A$ is "\emph{rapidly mixing}" if $T(\varepsilon)=poly(log|V|,log\frac{1}{\varepsilon})$, where $V$ stands for the number of states in $A$.
\end{definition}
Next we will show the connection between properties of eigenvectors described in the previous section and mixing times.
\\
%
\begin{theorem}
Given transition matrix P of an undirected (= symmetric), non bipartite, d\_regular, connected graph, with $\Pi_0$ as the start distribution and $\overline{\Pi}$ its stationary distribution then:
\[\|\Pi_0P^t-\overline{\Pi}\|_2 \leq |\lambda_2|^t\]
\end{theorem}
\begin{proof}
P is real and symmetric hence, its eigenvectors $v^{(1)},v^{(2)},..,v^{(n)}$ form an orthonormal basis with eigenvalues $\lambda_1=1$, $|\lambda_1| \leq |\lambda_2| \leq .. \leq |\lambda_n|$, so for any vector, in particular the vectors $\Pi_0$:
\[\Pi_0=\sum_{i=1}^n\alpha_i v_{(i)},\]
\[|\Pi_0P^t=\sum_{i=1}^n\alpha_i v^{(i)}P^t=\sum_{i=1}^n\alpha_i \lambda_i^t v^{(i)}\]
We know that $\lambda_1 = 1$ so
\[\Pi_0=\alpha_1v^{(1)}+\sum_{i=2}^n\alpha_i \lambda_i^t v^{(i)}\]
Therefore
\[\|\Pi_0P^t-\alpha_1v^{(1)}\|_2=\|\sum_{i=2}^n\alpha_i \lambda_i^t v^{(i)}\|_2=\sqrt{\sum_{i=2}^n\alpha_i^2 \lambda_i^{2t}}\]
Where the last transition was possible due to the orthonormality of the eigenvectors $v^{(i)}$. Also notice that $\forall i>2$, $|\lambda_2|^2 \geq |\lambda_i|^2$. Using this in the previous eq. we get
\[\|\Pi_0P^t-\alpha_1v^{(1)}\|_2\leq |\lambda_i^{t}|\sqrt{\sum_{i=2}^n\alpha_i^2} \leq |\lambda_i^{t}|\]
The last transition is due to the fact that
\[1=|\Pi_0|_1\geq \|\Pi_0\|_2=\sqrt{\sum_{i=1}^n\alpha_i^2} \Rightarrow \sqrt{\sum_{i=2}^n\alpha_i^2}\leq 1\]
Now notice that as $t$ increases (indicating more steps taken at the random walk) $|\lambda_2|^t$ is getting smaller, so $|\Pi_0P^t-\overline{\Pi}\|_2$ is getting closer to zero. Therefore the stationary distribution must be $\overline{\Pi}=\alpha_1v^{(1)}$ and we get from the last equation
\[\|\Pi_0P^t-\overline{\Pi}\|_2 \leq |\lambda_2|^t\]
\end{proof}

\section{Reducing Random Bits Using Random Walks}
In this part of the lecture we will use our previous result on the eigenvalues of the matrix P and
apply it to a new way of reducing the number of random bits needed with amplification of randomized
algorithms.
\\
\\
Let's consider a decision problem L, for which we have a randomized algorithm A with one sided-error as follows:
\begin{itemize}
\item A's behavior is:
\begin{itemize}
\item If $x\in L$ then ${Pr}[A(x)\:outputs\:"x\in L"]<\frac{1}{100}$
\item If $x\notin L$ then $A(x)\:alway\:outputs\:"x\notin L"$
\end{itemize}
\item A uses at most $r(n)$ random bits on problems of size $n$.
\end{itemize}
An example of such a decision problem is the STCON for which we saw a randomized algorithm who uses random
walks that is never mistaken when vertices $s,t$ are not connected, and errs with small probability when
$s,t$ are connected.
\\
\\
We saw in previous lectures a few ways to amplify a randomized algorithm's performance. In summation, using these previously discussed methods, in order to achieve an error probability of $2^{-k}$ we could:
\begin{itemize}
\item By running algorithm A for $k$ times. we were able to get an error probability of $2^{-k}$ by using $O(k\cdot r)$ random bits.
\item Using pair-wise independent hash functions we were able to improve the previous result and get an error probability of $2^{-k}$ using only $O(k+r)$ random bits.
\item In this lecture we will use random walks on graph to achieve an amplification scheme which only uses $r+O(k)$ random bits and achieving the optimal constant in front of the r.
\end{itemize}
The main idea behind the amplification scheme is the use a d-regular graph G (for some const d) with $2^{r}$ nodes, each one corresponds the a random assignment $w$ of random bits in algorithm A. There are a few important notes we should mention about the graph G: \begin{itemize}
\item Graph G is a huge graph that could not be constructed in polynomial time. The algorithm will use the graph by computing the adjacency matrix locally only when needed. We thus have a requirement that for a given node G's adjacent edges can be computed efficiently.
\item Graph G has no connection to algorithm A nor to its input. The graph is a generic graph suited to amplify any algorithm that confirms to the terms stated above.
\item G should have \emph{extractor} property:
\begin{itemize}
\item For G's transition matrix P the following holds: $\abs{\lambda_{2}}\leq \frac{1}{10}$
\end{itemize}
\end{itemize}
In this lecture we will not show how to construct these graphs.
\\
\\
\textbf{The Scheme}:
\begin{enumerate}
\item Pick uniformly at random $w\in_{R} \{0,1\}^{r}$, a start node in G
\item Repeat the following $k$ times:
\begin{enumerate}
\item $w\leftarrow$ random neighbor of $w$
\item Run $A(x)$ with $w$ as the random bits.
\end{enumerate}
\item If ever see $"\in L"$ output $"x\in L"$ otherwise output $"x\notin L"$
\end{enumerate}
Since step (1) takes $r$ random bits and step (2.a) takes $k \cdot \log{d} $ bits, the scheme uses $r + O(k)$ random bits as claimed.
\begin{claim}
The scheme presented above will err with probability at most $(\frac{1}{5})^{k}$
\end{claim}
\begin{proof}
We divide the analysis into two classes:\\\\
If $x \notin L$, than obviously the scheme will never err since $A(x)$ never errors in this case.\\\\
If $x \in L$, Let's denote $B = \{ w|A(x)\:with\:random\:bits\: w\:is\:incorrect\}$. From the definition of A, it is clear that $|B|\leq \frac{2^{r}}{100}$\\\\
Let's define a diagonal matrix N with
\begin{equation*}
N_{ww}=
\begin{cases}
0 & \text{if w$\in$ B}\\
1 & \text{otherwise}
\end{cases}
\end{equation*}\\
Notice that if $q$ is a distribution on the nodes of G then:
\begin{equation*}
|qN|_{1}=Pr_{w\in q}[w\:is\:bad\:random\:string\:for\:A(x)]
\end{equation*}\\
or in general:
\begin{equation*}
|q(NP)^{k}N|=Pr_{w\in q}[w\:and\:the\:next\:k\:steps\:are\:bad\:strings\:for\:A(x)]
\end{equation*}\\
we can see that in order to prove a bound on this probability we should bound $|q(NP)^{k}N|$. To do this, we prove the following lemma:
\begin{lemma}
For all distributions $\Pi$ we have $\|\pi PN\|_{2} \leq \frac{1}{5} \|\pi \|$
\end{lemma}
\begin{observation}
For every vector $s$ we have $\|sN\|_{2} = \sqrt{\sum_{i=1}^{2^{r}}(s_{i}N_{ii})^{2}} \leq \sqrt{\sum_{i=1}^{2^{r}}s_{i}^{2}} = \|s\|_{2}$
\end{observation}
\begin{proof}
Express $\pi$ as $\pi = \sum_{i=1}^{2^{r}} \alpha_{i} v_{i}$ (where $v_{i}$ are eigenvectors of P). Note that $v_{1}=(\frac{1}{\sqrt{2^{r}}},...,\frac{1}{\sqrt{2^{r}}})$.\\\\ Let's analyze:
\begin{equation*}
\|\pi PN\|=\| \sum_{i=1}^{2^r} \alpha_{i} v_{i} PN\|_{2} = \| \sum_{i=1}^{2^r} \alpha_{i} \lambda_{i} v_{i} N \|_{2} \leq \| \alpha_{1} \lambda_{1} v_{1} N \|_{2} + \| \sum_{i=2}^{2^{r}} \alpha_{i} \lambda{i} v_{i} N \|_{2}
\end{equation*}
The first step is because $v_{i}$ are eigenvectors of P, and the second step is due to Cauchy-Schwartz.\\\\
If we analyze each term separately we get:
\begin{enumerate}
\item $\| \alpha_{1} \lambda_{1} v_{1} N \|_{2} = \| \alpha_{1} v_{1} N \|_{2} = \abs{\alpha_{1}} \|v_{1} N\|_{2} = \abs{\alpha_{1}} \cdot \sqrt{\sum_{i \in B}({\frac{1}{ \sqrt{2^{r}} }})^{2}} = \abs{\alpha_{1}} \sqrt{\frac{|B|}{2^{r}}} \leq \frac{\abs{\alpha_{1}}}{10} \leq \frac{\| \pi \|_{2}}{10}$\\\\ the first step is due to $\lambda_{1}=1$ and the last step is due to $\abs{\alpha_{1}} \leq \sqrt{\sum \alpha_{i}^{2} } = \| \pi \|_{2}$\\
\item $\| \sum_{i=2}^{2^{r}} \alpha_{i} \lambda_{i} v_{i} N \|_{2} \leq \| \sum_{i=2}^{2^{r}} \alpha_{i} \lambda_{i} v_{i} = \sqrt{\sum_{i=2}^{2^{r}} \alpha_{i}^{2} \lambda_{i}^{2}} \leq \frac{1}{10} \sqrt{\sum_{i=2}^{2^{r}} \alpha_{i}^{2}} \leq \frac{\|\pi \|_{2}}{10}$\\\\ Here we used the fact that $\forall i>2.\abs{\lambda_{2}} \geq \abs{\lambda_{i}}$.
\end{enumerate}
Overall, we got $\| \pi PN \|_{2} \leq \frac{\|\pi \|_{2}}{10} + \frac{\|\pi \|_{2}}{10} = \frac{\|\pi \|_{2}}{5}$
\end{proof}
\\\\
How do we use this lemma?\\\\
$Pr[A(x)\:is\:incorrect\:for\:all\:w] \leq \abs{U_{2^{r}}(NP)^{k}}_{1} \leq \sqrt{2^{r}} \cdot \|U_{2^{r}} (PN)^{k} \| _{2} \leq \sqrt{2^{r}} \| U_{2^{r}} \| \cdot \frac{1}{5^{k}} = \frac{1}{5^{k}}$\\\\
At the second step we used the inequality $|v|_{1} \leq \sqrt{d}\|v\|_{2}$ (where $d$ stands for $v$'s dimensionality.)
\end{proof}
\section{Mixing \& Uniform Generation Of Matching}
We will now show a general construction of a rapidly mixing Markov Chain, and implement this construction on an algorithm for the uniform generation of matching un a given graph. Note that the proof of correctness will follow on the next lecture.

\subsection{General Plan}
Given graph $G=(V,E)$, Construct (a "huge") markov chain s.t.
\begin{enumerate}
\item The states of the Markov Chain, V', corresponds to objects we are trying to uniformly generate (exponential number of states i.e. $|V'|=O(2^{|V|})$)
\subitem E.g. For matching the states will be \{M$|$M is a matching in G\}.
\item The Transition correspond to local changes s.t. the degree is polynomial in original G, and we will only need polytime to choose a transition.
\subitem E.g. For matching remove, add edges, or unchanged (self loop).
\item Start at an arbitrary node (we cannot pick a random node).
\item Analyze the stationary distribution (ideally uniform).
\item Find the mixing time. Remember that by definition, in order for the Markov Chain to be rapidly mixing, we need it to be $poly(log|V'|)$ or $poly(V)$), so we are want to show that rapid mixing times $\Rightarrow$ polytime algorithm.
\end{enumerate}
\subsection{Algorithm For Matching}
\begin{enumerate}
\item Pick Edge $e\in_RE$
\item if $e\in M$
\subitem set $M\leftarrow M-\{e\}$
\item else if $M\cup \{e\}$ is matching
\subitem set $M\leftarrow M\cup \{e\}$
\item else
\subitem stay in current state
\end{enumerate}
Notice that the graph constructed is:
\begin{itemize}
\item Undirected (the graph is reversible - every edge deleted can be added later).
\item Connected.
\item Not bipartite (can stay at the same state, i.e. containing self loops).
\item With degree $|E|$, therefore, the stationary distribution is uniform.
\end{itemize}
\end{document}
