\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}

\begin{document}
\lecture{21}{November 2, 2001}{Igor Pak}{B. Virag}

\newcommand{\ee}{\mathcal E}
\newcommand{\ev}{\mbox{\bf E}}
\newcommand{\pr}{\mbox{\bf P}}

\section{Dirichlet forms and mixing time}

Let $G$ be a finite group, and let $V$ be the vector space of
real-valued functions from $G$. There is a natural inner
product on this space
$$
\langle \phi, \varphi \rangle = \sum_{x\in G} \varphi(x)
\psi(x) = |G| \ev \varphi(X) \psi(X)
$$
where $X$ is chosen from $g$ according to uniform measure. Let
$\pi$ be a probability distribution on $G$, and let $P_\pi$
denote the transition kernel of the random walk $\{X_n\}$ that
moves from $x$ to $xy$ in every step, where $y$ is distributed
according to $\pi$. Just like any other transition kernel,
$P_\pi$ acts on the space of functions on $G$ as follows
$$
\left[P_\pi \varphi\right](x) =\sum_{y \in G} \varphi(xy)
\pi(y) =\ev[\varphi(X_1)\ | \ X_0=x].
$$
Define the support of $\varphi\in V$ in the usual way,
$$
\mbox{supp} (\varphi) = \{x\in G \ |\ \varphi(x) \not=0\}.
$$
We now define the Dirichlet form
$$
\ee_\pi(\varphi, \varphi)=\langle(I-P_\pi)\varphi,
\varphi\rangle = |G| \ev \left[
\left(\varphi(X_0)-\varphi(X_1)\right) \varphi (X_0)\right]
$$
where now $X_0$ is chosen according to uniform distribution on
$G$. Note that if $Z_0,\ Z_1$ are real-valued random variables
with the same distribution, then
$$
\ev [(Z_0-Z_1)Z_0] = {1\over 2} \ev (Z_0-Z_1)^2.
$$
Since the uniform distribution is stationary with respect to
convolution, $X_0$ and $X_1$ have the same distribution, and we
may apply this to $\varphi(X_0),\ \varphi(X_1)$ to get the
alternative formula for the Dirichlet form
$$
\ee_\pi(\varphi,\varphi) = {|G|\over 2} \ev
(\varphi(X_0)-\varphi(X_1))^2 = {1 \over 2}\sum_{x,y\in G}
(\varphi(x)-\varphi(xy))^2 \pi(y).
$$
Now let $\Gamma=\Gamma(G,S)$ be a Cayley graph of $G$ with
respect to a symmetric generator set $S$. Let $\gamma$ be a
function that assigns to each $y\in G$  a path from the
identity to $y$ in $\Gamma$. We will assume that  $\gamma$ is
geodesic, that is its values are shortest paths. Let $
\mu_s(y)=\mu_s(y,\gamma) $ denote the number of times a
generator $s$ appears in the decomposition
\begin{equation}\label{deco}
y= s_1 s_2 \ldots s_\ell
\end{equation}
along the path $\gamma(y)$. For $C\subseteq G$  Let
$$
N_\gamma(s,C)= \max_{x,y\in C} \mu_s(x^{-1}y).
$$
We have a following version of a theorem by Diaconis and
Saloff-Coste.

\begin{theorem}[Comparison of Dirichlet forms]
Let $C\subseteq G$, let $\overline C = C \cup
\partial C$, and let $d={\rm diam}(\overline C)$.
Consider $\pi,\ \tilde \pi$ symmetric probability distributions
on $G$, and let $S\subseteq{\rm supp}(\pi)$. Then
$$
\ee_\pi (\varphi, \varphi) \ge {1 \over A}\ee_{\tilde \pi}
(\varphi, \varphi)
$$
where
$$
A = d \max_{s\in S} {N_\gamma (s, \overline C) \over \pi(s)}.
$$
\end{theorem}

\begin{proof}
Let $y\in G$, and write $y$ in the form (\ref{deco}). We can
write
$$
\varphi(x) - \varphi (xy) = [\varphi(xs)-\varphi(xs_1)] +
\ldots + [\varphi(xs_1 \ldots s_{\ell-1} - \varphi (xy)].
$$
It follows, for example, by the Cauchy-Schwarz inequality that
$$
(\varphi(x) - \varphi (xy))^2 \le \ell^* \sum_{i=1}^{\ell}
(\varphi(xs_1\ldots s_{i-1})- \varphi(xs_1 \ldots s_i))^2
$$
where $\ell^*$ is the number of nonzero terms in the sum, and
is bounded above by $d=$diam$(\overline C)$, since $\gamma$ is
geodesic. Summing this inequality over $x\in G$ we get
$$
\sum_{x\in G} (\varphi(x) - \varphi (xy)) ^2 \le d  \sum_{z\in
G, s\in S } N_\gamma(s, \overline C)(\varphi(z)-
\varphi(zs))^2.
$$
Since this holds for all $y\in G$, we may average the left hand
side with respect to $y$ with weights $\tilde \pi(y)$ to get
$$
\sum_{x,y\in G} (\varphi(x)-\varphi(xy))^2 \tilde \pi(y) \le d
\sum_{z\in G,s\in S} N_\gamma(s,\overline
C)(\varphi(z)-\varphi(zs))^2
$$
Finally, the right hand side is clearly bounded by
$$
A \sum_{z\in G, s\in S} (\varphi(z)-\varphi(zs))^2 \pi(s)
$$
and the statement of the theorem follows.
\end{proof}

By the way, the symmetry assumption for $S$ was not used.

\end{document}