\documentclass{article}
\usepackage{amsmath,amssymb}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
\newcounter{lecnum}
%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
  \pagestyle{myheadings}
  \thispagestyle{plain}
  \newpage
  \setcounter{lecnum}{#1}
  \setcounter{page}{1}
  \noindent
  \begin{center}
    \framebox{
      \vbox{\vspace{2mm}
        \hbox to 6.28in { {{\bf 18.317~Combinatorics, Probability, and
  Computations on Groups} \hfill #2} }
        \vspace{4mm}
        \hbox to 6.28in { {\Large \hfill Lecture #1  \hfill} }
        \vspace{2mm}
        \hbox to 6.28in { {\it Lecturer: #3 \hfill Scribe: #4} }
        \vspace{2mm}}}
  \end{center}
  \markboth{Lecture #1: #2}{Lecture #1: #2}
  \vspace*{4mm}
}

\input{epsf}
%usage: \fig{LABEL}{FIGURE-HEIGHT}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
        \begin{figure}
        \setlength{\epsfysize}{#2}
        \centerline{\epsfbox{#4}}
        \caption{#3} \label{#1}
        \end{figure}
        }

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
\newenvironment{mproof}[1]{{\bf #1}}{\hfill\rule{2mm}{2mm}}

\def\E#1{{\rm E}[#1]}
\def\i{\hspace*{5mm}}
\newcounter{lineno}
\setcounter{lineno}{0}
\def\n{\addtocounter{lineno}{1} \hbox to 7mm{\hfill \arabic{lineno}:}\hspace{2mm}}
\def\resetn{\setcounter{lineno}{0}}
\def\tqbfk{\tqbf_k^\exists}
\def\ep{\epsilon}
\def\erd{Erd\H{o}s}
\def\<{\langle}
\def\>{\rangle}

\begin{document}
\lecture{22}{5 November 2001}{Igor Pak}{Nate Ackerman}
%
\begin{theorem}
{\rm (This is a special case of the theorem from last class.) }
\newline
Suppose $\Gamma = \Gamma(G,S)$, $\upsilon = $ set of paths in
$\Gamma$, and $\gamma = \{\gamma_x$: path from id to x$\}$. Also
suppose that $\pi, \widetilde{\pi}$ are symmetric, $s\subseteq $
support$(\pi)$, diam $\upsilon = \max_x |\gamma_x| = d$ and
$\mu_s(x) = $ number of generators $s$ in $\gamma_x=s_{i_1}s_{i_2}
\cdots$. \newline\newline%
Then $\mathcal{E}_\pi (\varphi, \varphi) \geq (1/|A|) \cdot
\mathcal{E}_{\widetilde{\pi}} (\varphi, \varphi)$ where $A = d
\cdot \max_{s\in S} (\max_{x\in G} \mu_s(x))/\pi(s)$. \newline%
%(This is a long and complicated theorem).
\end{theorem}
%

We shall prove the following important corollary from the Theorem.

\begin{lemma} Suppose \, $\mathcal{E}_{\widetilde{\pi}} (\varphi,
\varphi) \leq A \cdot \mathcal{E}_{\pi} (\varphi, \varphi)  \ \forall
\varphi$. \,  %\newline
Then
$$1-\widetilde{\lambda_i} \leq A(1-\lambda_i),$$
where
$\lambda_i$ are the eigenvalues of $M_\pi$.
\end{lemma}
%
For every probability distribution $\pi$, consider the matrix %
$$M_\pi =(a_{xy})_{|G|\times |G|}, a_{xy} = \pi(x^{-1}y)$$ %
Here it is important $\pi$ is symmetric so all eigenvectors are
real: $1= \lambda_0 \geq \lambda_1
\geq \dots \geq -1$. \newline\newline%
%
Recall that $\mathcal{E}_{\pi} (\varphi, \varphi) = \< (I-P_{\pi})
\varphi, \varphi\>$, where $P_\pi$ is exactly convolution with
$\pi$. Then \, $M_\pi$ \, is then exactly the matrix of that operation. \newline%
Consider the scalar product of a function
and an operator on that function. \newline\newline%
Lets call this operation $Q = I- P_\pi$.\newline
%
\begin{lemma} For every symmetric operator $Q$,
$$\min_\varphi \frac{\<Q\varphi, \varphi\>}
{\<\varphi, \varphi\>}$$
is equal to the smallest eigenvalue of $Q$.
\end{lemma}

\begin{proof}
To see this let us look at it the other way. We see easily from
linear algebra that $\max_\varphi \<Q\varphi, \varphi\>/
\<\varphi, \varphi\>$ is just the maximal eigenvalue of $Q$.
Similarly
$$\min_\varphi \, \frac{\<Q\varphi, \varphi\>}{ \<\varphi,
\varphi\>}  \, = \, \min_{\varphi: \ \Sigma \varphi = 0}
\, \frac{\<Q\varphi,\varphi\>}{ \<\varphi, \varphi\>} \, = \, \lambda_1$$
\end{proof}\newline\newline%
We just need one more well known result from linear algebra to complete the
proof of Lemma~2.
%
\begin{theorem}
{\rm \bf (min-max principle)}
\newline
Let $Q$ be a symmetric linear
operator on $V$ with eigenvalues $q_0 \leq q_1 \leq \cdots \leq
q_n$. Let $m(W) = \min \{ \<Qf,f\>/\<f,f\> : f \in W\subseteq V\}$. Then %
$$q_i = \max\{m(W): dim (W) = i\}$$%
\end{theorem}
This follows when you consider vector spaces generated by first $i$
eigenvectors.
\newline\newline%
%
This is all we need to complete the proof of Lemma~2. Indeed,
Theorem~4 implies: \,
$1-\widetilde{\lambda_i} \leq A(1-\lambda_i).$ \newline %
%
Therefore \, $\lambda_1 \leq 1-(1-\widetilde{\lambda_1})/A$
\newline\newline%

Let $\widetilde{\pi} = U(G)$ = uniform distribution on the
group, and let $\pi = U(S)$ be a uniform distribution on
the generating set. Assume our generating set is the whole
group ($S= G$). Then the transition matrix $M_{\widetilde{\pi}}$ %
is given by
$$\frac1{|G|} \left(\begin{array}{cccc}
                    1 & 1 & 1 & \cdots\\%
                    1 & 1 & 1 & \cdots\\%
                    \vdots &\vdots &\vdots &\ddots \end{array}
                     \right).$$%
This matrix has an eigenvalue of 1. But, because it also has rank
1, we know that all remaining eigenvalues are 0.
Thus, $\lambda_0 =1$, $\lambda_i = 0$, and therefore
$\widetilde{\lambda_1} = 0$. Finally, we conclude
{$\lambda_1 \leq 1-1/A$} \newline %
%
Recall that
$$A = d \cdot \max_{s\in S} \max_{g\in G} \frac{\mu_s(x)}{\pi(s)},$$
where $d = $ diameter$(\gamma)$, and $\pi(s)=
1/|S|$ since $\pi$ is the uniform distribution. Therefore,
$$A= d \cdot |S| \cdot \max_{s\in S} N_\gamma(S,G),$$
and  we obtain: %

\begin{theorem} Let $G$ be a finite group, let $S=S^{-1}$ be a
symmetric generating set, and let \, $\Gamma = \Gamma(G,S)$ be a
Cayley graph with diameter~$d$. Then
$$\lambda_1 \leq 1-\frac{1}{A} \leq 1- \frac1{d\cdot |S|\cdot N_\gamma}
\leq 1- \frac1{d^2\,|S|},$$%
where  \, $N_\gamma = \max_{s\in S} \, N_\gamma(S,G)$. %
\end{theorem}
%
\begin{corollary}
\ \

a) \ The relaxation time \, $\tau_1 = 1/(1-\lambda_1) \leq d\cdot
|S|\cdot N_\gamma$.

\noindent
b) \ The mixing time of the lazy random walk ${\cal W}$ on
$\Gamma(G,S)$ satisfies:
$$\tau_3 \leq d \cdot |S| \cdot N_\gamma \log|G| \leq d^2|S|
\log|G|$$
\end{corollary}

Part \, b) \,  in the corollary follows from part \, a) \, and
\, $\tau_3^* \leq \tau_1 \log|G|$, where * refers to the lazy
random walk.
%
Now, let us consider several special cases

\bigskip

\underline{Example 1} \ Let $G = \mathbb{Z}_n$, $S= \{\pm 1 \}$.
\newline%
The corollary gives \, mix = $O(n^2 \log(n))$, which is slightly
weaker from the tight bound \, mix = $O(n^2)$.

\bigskip
%
\underline{Example 2} \ Let $G = \mathbb{Z}_2^n$, $S= \{(a_{1},
\cdots, a_{n}) \, : a_i = 1 $ and the rest are 0, for $1\leq i \leq
n$\}. \newline%
To calculate the mixing time we need the diameter (d) and
$|S|$. Since \, d=$n$, and \, $|S| = n$, we obtain
$$\tau_3^* \leq d^2|S| \log |G| = O(n^4).$$
On the other hand, a stronger inequality \,
$\tau_3^* \leq d  |S|  N_\gamma \log |G|$ \,
gives us a better (but still not great) upper bound. Indeed, \,
since $N_\gamma =1$, we get \, $\tau_3^* \leq O(n^3)$.
This should be compared with $\tau_3^* = O(n \log n)$ we obtained
by a stopping times argument.

\bigskip

\underline{Example 3} \ Let $G = S_n$, $R= \{(12)(13)\cdots (1n)\}$
Consider \, $d=$ diam $\Gamma(S_n, R)$).
The largest distance to identity has a permutation \,
$g=(23)(45)\cdots(2m, 2m+1), n= 2m+1$. \newline%
This implies that \,
$$\text{\rm diam} \, \Gamma(S_n, R) = \sim 3/2 n + O(1).$$
We also have \, $|S| = n-1 = O(n)$, and \, $\log|G| = O(n\log(n))$,
so, mix $\leq d^2|R|\log|G| \leq O(n^4\log (n))$.

On the other hand, we know that $N_\gamma$ is small.
In fact, an easy check shows that $N_\gamma$ is at most 2, and so %
$$\text{mix} \, \leq \, d\, |R|\, N_\gamma \, \log|G| \,  = \, O(n^3\log(n))$$

Recall that by a stopping time argument we obtained a tight upper
bound of $O(n \log n)$ in this case.

\bigskip

%
\underline{Example 4} \
Let $G = S_n$, $R= \{(ij): 1\leq i < j \leq n\}$ \newline%
We can do a similar stopping argument to show that in fact mix$= C
n \log(n)$. \newline%
However, the upper bound given by corollary is not nearly that good.
We have: \, $|R| = O(n^2)$, \, $d = O(n)$, and \, $N_\gamma = 1$.
Therefore, have \, mix$\leq d \, N_\gamma \, |R| \log|G| =
O(n^4\log(n))$.

\smallskip

This is another example of weakness of the bound given by
Corollary~6. The larger the generating set, the bigger the bound
on the mixing time. This is unfortunate, as the larger the
generating set, the smaller the mixing time tends to be.
\newline \newline%
%
{\bf Multicomodity flows}\newline %
Imagine we have an industrial structure that looks like a Cayley
graph, and each place has to trade commodities with the other
places. In particular between any two plans 1 commodity must flow.
However, the 1 unit flow along different paths. All that matters
is that the sum total of the flow is 1 unit (so the flows look
like a probability distribution on the paths between any two
sites.)\newline \newline%
%
Let $\gamma = \{\gamma_x$ = flow from id to x in $G \}$. So
$\gamma_x$ can consist of several different paths so long as the
flows add to 1. \newline\newline%
%
$N_\gamma = \max_{s\in S} \max_{x\in S} \mu_s(\gamma_x)$ (=
expected number of times $s$ occurs in a path from id to
$x$)\newline\newline%
%
\underline{Claim} \ Theorem~1 and Corollary~6 remain correct
under this generalization. \newline%
\begin{corollary}
If $\Gamma = \Gamma(G,S)$ is vertex transitive. (e.g. if
$H\subseteq $Aut$(G)$ then $H$ acts transitively on $S$) \newline
Then the relaxation time \, $\tau_1 = O(d^2)$, and the mixing time \,
$\tau_3 = O(d^2\log|G|)$ \newline%
\end{corollary}
Indeed, consider a uniform distribution on all paths giving a shortest
decomposition of an element. Then \,  $N_\gamma = d/ |S|$, and we have \,
$d|S|N_\gamma = d^2$. In a special case of the Example~4 the
corollary gives \, $O(n^3 \log n)$ \, bound now.
%
\end{document}
















\begin{eqnarray*}
\left[ xy, z \right] & = & x y z y^{-1} x^{-1} z^{-1} \\ & = & x
(y z y^{-1} z^{-1} ) z x^{-1} z^{-1} \\ & = & x (y z y^{-1} z^{-1}
) x^{-1} x z x^{-1} z^{-1} \\ & = & (x \left[ y, z \right] x^{-1})
(\left[ x, z \right])
\end{eqnarray*}