\documentstyle[12pt]{article}
\parindent 0in
\parskip 1.5ex
\def\a{\alpha}
\def\b{\beta}
\def\d{\delta}
\def\D{\Delta}
\def\e{\epsilon}
\def\f{\phi}
\def\F{\Phi}
\def\g{\gamma}
\def\G{\Gamma}
\def\k{\kappa}
\def\K{\Kappa}
\def\ups{\varsigma}
\def\z{\zeta}
\def\th{\theta}
\def\TH{\Theta}
\def\l{\lambda}
\def\L{\Lambda}
\def\m{\mu}
\def\n{\nu}
\def\p{\pi}
\def\P{\Pi}
\def\r{\rho}
\def\R{\Rho}
\def\s{\sigma}
\def\S{\Sigma}
\def\t{\tau}
\def\om{\omega}
\def\OM{\Omega}
\def\SS{\sqrt{ { \p(S)\over \p(\bar{S} ) } } }

\def\Min{\hbox{ Min }}
\def\Max{\hbox{ Max }}
\def\for{\hbox{ for }}
\def\where{\hbox{ where  } }

\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newcommand{\limninf}{\mbox{$\lim_{n \rightarrow \infty}$}}
\newcommand{\proofstart}{{\bf Proof\hspace{2em}}}
\newcommand{\proofend}{\hspace*{\fill}\mbox{$\Box$}}
\newcommand{\bfm}[1]{\mbox{\boldmath $#1$}}
\newcommand{\reals}{\mbox{\bfm{R}}}
\newcommand{\Prob}{\mbox{\bf Pr}}
\newcommand{\expect}{\mbox{\bf E}}
\newcommand{\card}[1]{\mbox{$|#1|$}}
\newcommand{\half}{\mbox{$\frac{1}{2}$}}
\newcommand{\scaps}[1]{\mbox{\sc #1}}
\newcommand{\rdup}[1]{{\mbox{$ \lceil #1 \rceil $}}}
\newcommand{\rdown}[1]{{\mbox{$ \lfloor #1 \rfloor $}}}
\newcommand{\inner}[2]{\mbox{$<#1 , #2 >$}}
\begin{document}

\baselineskip 20pt \lineskip 3pt

\title{SAMPLING FROM LOG-CONCAVE DISTRIBUTIONS}
\author{Alan Frieze\thanks{
Department of Mathematics,  Carnegie Mellon University,
Pittsburgh PA15213, U.S.A., Supported by NSF grant CCR-9024935  }
\and 
Ravi Kannan\thanks{
BellCore, Morristown NJ 07962, and 
Carnegie Mellon University, Pittsburgh, PA 15213.}
\and 
Nick Polson\thanks{
Graduate School of Business, 
University of Chicago, 
Chicago IL60637, U.S.A.}
 }
\maketitle
\begin{abstract}
We consider the problem of sampling according to a distribution with log-concave density $F$ over a convex body $K\subseteq \reals^n$. The sampling is done using a biassed random walk and we prove polynomial upper bounds on the time to get a sample point with distribution close to $F$.
\end{abstract}
\section{Introduction}

This paper is concerned with the efficient sampling of random points  
from $\reals^n$ where the underlying density $F$ is log-concave (i.e. $\log F$ is concave). This  
is a natural restriction which is satisfied by many common  
distributions e.g. the multi-variate normal. The algorithm we use generates a sample path from a Markov
chain whose stationary distribution is (close to) $F$. 
The algorithm falls into the class of Metropolis algorithms. It
has applications to the problem of computing the volume of
convex bodies and in statistics. Recent statistics literature
has focused on the many applications of Markov chain Monte Carlo
algorithms (see Tierney \cite{Ti}). However theoretical bounds on the 
convergence rate of such algorithms have been limited. Using recent developments in the theory of rapidly mixing Markov chains, in particular the notion of conductance \cite{SJ,LS1} Applegate and Kannan \cite{AK} proved a bound on the convergence rate of the chain considered in this paper. These theoretical bounds are too large to be useful in practice. In this paper we prove tighter bounds using an approach related to the classical Poincar\'e inequalities instead of conductance. These bounds are small enough to be useful in proactice and have already found application in the generation of random contingency tables \cite{DKM}.

Instead of sampling from the continuum of points in ${\bf R}^n$, we discretize
the problem by assuming that ${\bf R}^n$ is divided into a set of hypercubes ${\cal C}_{\reals}$ of side
$\delta $ ($\delta $ is a given small positive real number) and the problem
is to choose one of these cubes each with probability proportional to the
integral of $F$ over the cube. [If necessary, a sample from the continuum
can then be picked by standard rejection sampling techniques from the cube 
chosen; we omit details of this.] Secondly, we assume 
that we have a compact convex set $K$ and 
we wish to choose points only from $K$ (not all of ${\bf R}^n$). This is 
justified because clearly for any positive real number $\epsilon $, we can 
find a compact convex set (for example a ball) such that the integral of $F$
over the set is at least $(1-\epsilon )$ times the integral over ${\bf R}^n$.
While it would suffice to consider the case when $K$ is a ball, the generality
of convex sets is useful in many contexts. 

In what follows ${\cal C}$ denotes a subset of the cubes ${\cal C}_{\reals}$ whose union contains $K$. For example ${\cal C}$ could be the  
set of cubes ${\cal C}_I(K)$ which have nonempty intersection with 
 $K$. Let $C$ denote the set of centres of  
these cubes. For $x\in \reals^n$ we denote the cube of side $\d$ and  
centre $x$ by $C(x)$. (Thus $C(x)\in {\cal C}$ if and only if $x\in C$.) We choose our sample point $X$ by  
performing a random walk over ${C}$. The walk is biassed so that its  
steady state is (close to) what we want and we run the walk until it  
is close enough to the steady state. The main results of this paper  
concern the rate of convergence of the walk to its steady state.

We may not be able to compute $F$ exactly and so we assume we have  
good approximations $\bar{F}(x) ,x\in C$. Further we assume that $\bar F(x)$ is
strictly positive for all $x\in C$. 

We can only take advantage of the log-concavity of $F$ if our grid is  
sufficiently fine and our approximations $\bar{F}(x)$ are  
sufficiently good. In this context we will assume that for some small  
$\a>0$
\begin{equation}
\label{eq1}
(1+\a)^{-1}\bar{F}(x)\leq \bar{F}(y)\leq (1+\a)\bar{F}(x)
\end{equation}
and
\begin{equation}
\label{eq2}
(1+\a)^{-1}\d^{n-1}\bar{F}(x)\leq \int_{C(x)\cap C(y)}F(\xi)d\xi\leq  
(1+\a)\d^{n-1}\bar{F}(x) 
\end{equation}
whenever $C(x),C(y)$ are cubes of ${\cal C}$ sharing a face $C(x)\cap  
C(y)$ of dimension $n-1$. Furthermore, we assume 
\begin{equation}
\label{eq3}
(1+\a)^{-1}\d^n\bar{F}(x)\leq \int_{C(x)}F(\xi)d\xi\leq  
(1+\a)\d^n\bar{F}(x) \hspace{1in} \forall x\in C.
\end{equation}

When we have $\bar F=F$, 
it is easy to check that all three conditions are satisfied if we choose 
$\alpha $ to be $e^{M\delta }-1$ where $M$ is the Lipschitz constant of 
$\ln F$ with respect to the infinity norm. (i.e., $M$ satisfies 
$|\ln F(x) - \ln F(y) | \leq M |x-y|_\infty \quad, \forall x,y\in K$). However,
an $\alpha $ smaller than $e^{M\delta }-1$ may satisfy
(\ref{eq1})-(\ref{eq3}); this is in fact
the case for important functions like $F(x) = e ^{-c |x|}$ and
$F(x)=e^{-c |x|^2}$ as tedious, but simple calculations show. This is
the reason for stating the cumbersome conditions (\ref{eq1})-(\ref{eq3}). As we
will see (Theorems \ref{th1} and \ref{th2}),
the rate of convergence to the steady state depnds upon $(1+\alpha )$. In 
typical applications, one would make $1+\alpha $ a constant. (For example this 
can be ensured by choosing $\delta = O(1/ M)$.)




The walk we consider fits into the scheme of Metropolis algorithms  
introduced in Metropolis, Rosenberg, Rosenbluth, Teller and Teller  
\cite{metro}. It was used by Applegate and Kannan \cite{AK} in their  
paper on volume computation.

In the following, for any natural number $m$, we 
let  $[m]=\{1,2,\ldots ,m\}$ and $e_1,e_2,\ldots ,e_m$  
are the standard basis vectors of $\reals^m$.

{\bf The Random Walk}

This generates a random sequence $X_0,X_1,X_2,\ldots ,X_t,\ldots  
\in C$ where $X_0$ is picked according to some initial distribution 
$p_0(x)$ and $X_{t+1}$ is
obtained from $X_t$ as follows:
\begin{description}
\item[Step 1] Choose $j$ randomly from $[n].\qquad $ Choose $\s$ randomly from 
$\{\pm1 \}$.
\item[Step 2] Let $y=X_t+\s e_j$.
\item[Step 3] If $y\not\in C$ then $X_{t+1}=X_t$,
otherwise,  put $X_{t+1}=y$ with probability $\theta=\Min \left\{ 1,
\bar F(y)/\bar F(X_t)\right\} $ and $X_{t+1}=X_t$ with probability
$1-\th$.
\end{description}

Formally, the transition probabilities $P(x,y)=\Prob (X_{t+1} = y \mid
X_t = x)$ are given by 
$$P(x,y) = {1\over 2n} \Min \left\{ 1,\bar F(y)/ \bar F(x)\right\} \hbox
      { for } x\not= y;\;  x, y \hbox{ adjacent } \quad $$
and
$$P(x,x) = 1-\sum _{y\not= x } P(x, y).$$

We refer to this as ``the random walk'' in the paper. It will be useful also to
consider a modified random walk. ``The modified random walk'' has 
$$P(x,y) = {\nu \over 2n} \Min \left\{ 1,\bar F(y)/ \bar F(x)\right\} \hbox
      { for } x\not= y;\;  x, y \hbox{ adjacent } \quad $$
and
$$P(x,x) = 1-\sum _{y\not= x } P(x, y)$$
where $\nu = \left(1 + {2\delta^2 \over (1+\alpha )^3 nd (d+2\sqrt n\delta )}\right)^{-1}$. In 
most applications, $\nu $ will be very close to 1. So the modification can be
thought of as : with a small probability, the walk stays put, otherwise
does what ``the (unmodified) random walk'' did. 


When ${\cal C}={\cal C}_I(K)$ we will refer to the walk as the ``body intersecting'' walk. In this case testing whether $y\in C$ can be a significant computational problem,  
but nevertheless polynomially solvable, in general. In specific cases  
e.g. when $K=B(0,R)$, the ball of radius $R$ centred at the origin  
the problem is rather trivial.

We will also consider the computationally simpler random walk over those cubes ${\cal C}_C(K)$ in ${\cal C}_{\reals}$ whose centres are in $K$. We call this the ``centre point'' random walk.

It is easy to see that the chain is ergodic and thus, there are steady state 
probabilities $\pi (x)$ with $\lim_{t\rightarrow \infty }\Prob (X_t=x) = \pi 
(x)$ for all $x$ independent of the distribution of $X_0$. It is easy to verify
that 
$$\p(x)=\bar{F}(x)/\D,$$
where $\D=\sum_{x\in C}\bar{F}(x)$. We assume that the $\bar{F}(x)$  
are sufficiently good approximations so that sampling according to  
$\p$ can be considered to be our objective.

Note that this chain is {\em time reversible} i.e.
$$\p(x)P(x,y)=\p(y)P(y,x) \hspace{1in} \mbox{for all }x,y\in C.$$

The main theorem describing the rate of convergence is stated below as
Theorem 1. We use the so-called ``chi-squared'' 
distance of the distribution after $t$ steps to the steady state as a measure
of closeness (see Mihail \cite{M} and Fill \cite{F}).
Let $p_t(x) = \Prob (X_t=x)$ be the distribution after $t$ steps.
Then this distance is given by 
$$\sum_{x\in {C}}\left( {p_t(x)\over \pi (x)}-1\right) ^2\pi (x).$$
There are other measures one could use, including the more traditional 
``variational distance'' given by
$$\sum_{x\in {\cal C}} | p_t(x)-\pi (x) |.$$

The chi-squared measure turns out to yield stronger
theorems and in fact (as Fill points out), 
one can derive a bound on the variational distance 
using the bound on the chi-squared distance. (See Corollary \ref{cor1}). 

In Theorems \ref{th1} and \ref{th2}, which will be proved later, we have a random walk over a set of cubes ${\cal C}$.
$$T=\bigcup_{D\in {\cal C}}D$$
and 
$$d=diam(T),$$
(maximum distance between two points).
\begin{theorem} \label{th1}

Let $K$ be a convex set in ${\bf R}^n$. Let ${\cal C}$ be a subset of ${\cal C}_{\reals}$ (with $\d\leq d/10$) such that $K\subseteq T$. 
Let $C$ be the set of centres of 
these cubes. Let $S$ be the set of centres of those 
cubes in ${\cal C}$ which are not wholly contained in $K$ and 
let $\bar S=C\setminus S$. 
Let $F$ be a log-concave positive real valued function on $K$
with $\alpha $ satisfying (1), (2) and (3). Consider the random walk 
$X_0,X_1,\ldots X_t,\ldots $ described above. Then with $p_t(x) = 
\Prob (X_t = x )$, (and $\pi (x)$, the steady state probability of being
at $x$), we have 
%<
\begin{eqnarray*}
\left(\sum _{x\in C} \left( {p_t(x)\over \pi (x)} - 1\right)^2\pi
(x)\right)^{1/2} & \leq & 
(1-\lambda _1)^t  \left(\sum_{x\in C}\left( {p_0(x)\over \pi (x)} -
1\right)^2\pi (x)\right)^{1/2} \\
& + & \left( {3\over 1-\lambda_1}\max_{x\in C} \left| {p_0(x)\over\pi
(x)}-1\right|\right)\left( {\pi (S)\over \pi (\bar S)}\right)^{1/2},
\end{eqnarray*}
where 
$$\k_0 =  {d\over 4\d}(d+2\sqrt{n}\d)$$
and
\begin{eqnarray}
\lambda_1 ^{-1} & = & \max \left\{ {(1+\a)^3\k_0n\over \delta}
              , {d^2\over 6\d^2}\right\} \label{NOO}\\
& \approx & {nd^2\over 4\d^2}, \label{5}
\end{eqnarray}
and the final approximate equation holds under the assumptions : $\alpha\approx
0$ and $2\sqrt n\d /d \approx 0$.

Further, the modified random walk satisfies the inequality with $\l_1$ replaced by $\hat{\l}_1$ where
$$\hat{\lambda}_1^{-1} = \nu^{-1} {(1+\a)^3\k_0n\over \delta}$$
and where $\nu = \left(1 + {\delta \over 2(1+\alpha )^3 \k_0n}\right)^{-1}$.
[$\nu\approx 1$ under the same assumptions as above.]

\end{theorem}
{\bf Remark 1:} When $n$ is large the term $\tau_2=d^2/(6\d^2)$ in
(\ref{NOO}) is dominated by the other term. But when $n$ is small,
this may not be the case and the modified random walk will be preferable.

{\bf Remark 2} $1-\l_1$ estimates the second largest eigenvalue of the transition matrix of the walk. The constant 4 in (\ref{5}) is reasonably close to optimal. For example when $n=1$ the second largest eigenvalue is $1-2\sin(\p\d/d)^2\approx 1-\p^2\d^2/(2d^2)$ - see Anderson and Morley \cite{AM}.

\begin{corollary}\label{cor1}

Under the same conditions as in Theorem \ref{th1}, we have the following
bound on the
variational distance:
\begin{eqnarray*}
\sum _{x\in C} \left| p_t(x)-\pi (x)\right| & \leq & (1-\lambda _1)^t  
\left( \sum_{x\in C}\left( {p_0(x)\over \pi (x)} - 1\right)^2\pi (x) \right)^
{1/2}\\
& + & \left({3\over 1-\lambda_1 }\max_{x\in C} \left| {p_0(x)\over\pi
(x)}-1\right|\right)  \left( {\pi (S)\over \pi (\bar S)}\right)^{1/2}  . 
\end{eqnarray*}
\end{corollary}
\proofstart Using the Cauchy-Schwarz inequality we have:
$$\sum _{x\in C} \left| p_t(x)-\pi (x)\right| \leq \left(\sum_{x\in C}
{(p_t(x)  -\pi (x) )^2\over \pi (x)}\right)^{1/2}
   \left(\sum_{x\in C}\p (x)\right)^{1/2}.$$

The latter quantity equals the left hand side of the inequality in the 
Theorem and so we have the corollary.

\proofend

We first consider the body intersecting walk. Here we can apply the Theorem and its Corollary directly. The first term of the bound falls off exponentially to zero
with $t$. 
The Theorem is only of use if $\pi (S)$ is small. For any log-concave function
$F$, we can chose a suffciently large compact set such that the integral
of $F$ over the set is close to the integral of $F$ over ${\bf R}^n$. If now
we choose $K$ to be somewhat larger than this set, then clearly, $\pi (S)$ will
be small. We do not quantify these observations here, because that would 
depend upon the properties of the specific $F$ 's. 

Let us now consider the centre point walk. We define the convex set $K'=\{x\in K:C(x)\subseteq K\},$ run the walk with ${\cal C}={\cal C}_C(K)$ and apply the Theorem to ${\cal C}$ and $K'$. This is valid as $K'\subseteq \bigcup_{D\in {\cal C}}D$ and when $\d$ is small $K$ and $K'$ will be ``close'' to each other. The comments in the previous paragraph are valid in this case too.

It would be preferable to remove the term involving $\pi(S)$ in Theorem \ref{th1}, since it does not tend to zero as $t\rightarrow\infty$. With extra assumptions we can manage this.

Assume without loss that $o\in K$. For $u\in {\bf R}^n$,  with $|u|=1$, let $L_u=\{ru:r\in{\bf R}^+\}$ be the ray in direction $u$ emanating from the origin. Let $h(r)=h_u(r)=r^{n-1}F(ru)$. Theorem \ref{th2} below is proved under the assumption that the following hold for 
all unit vectors $u$:
\begin{equation}
\label{A1}
L_u\cap T\mbox{ is an interval}.
\end{equation}
Let $R=R(u)=\card{L_u\cap K}$ and $R_1=R_1(u)=\card{L_u\cap T}$.
\begin{equation}
\label{A2}
R_1<2R
\end{equation}
Let $\ups=R_1-R$.
\begin{equation}
\label{A3}
h(r')\leq \k_1h(r)\hspace{.25in}\mbox{for }R-\ups\leq r\leq r'\leq r+\ups,
\end{equation}
where $\k_1\geq 1$ is defined to be the smallest value satisfying (\ref{A3}). Let
$$\k_2=2\k_1\left({\ups\over \d}+\sqrt{n}\right).$$
\begin{theorem}   
\label{th2} 
Let $F$ be a log-concave positive real valued function on $\reals^n$ with $\alpha $ satisfying (\ref{eq1})-(\ref{eq3}). Assume (\ref{A1}) - (\ref{A3}) hold.
Consider the random walk 
$X_0,X_1,\ldots X_t,\ldots $ described above, with ${\cal C}={\cal C}_I(B)$ and $5\d\leq R$. Then we have 
$$\left(\sum _{x\in C} \left( {p_t(x)\over \pi (x)} - 1\right)^2\pi
(x)\right)^{1/2}\leq (1-\lambda _2)^t  \left(\sum_{x\in C}\left(
{p_0(x)\over \pi (x)} - 1\right)^2\pi (x)\right)^{1/2} $$ 
where 
\begin{eqnarray*}
\lambda_2 ^{-1} & = & \max \left\{ (1+\a)^3(\k_0\k_1+\k_0+\k_2+2\sqrt{\k_0\k_1\k_2}){n\over\d}
              , {d^2\over 6\d^2}\right\} \\
& \approx & {n\over 2}\left({d\over \d}\right)^2,
\end{eqnarray*}
and the final approximate equation holds under the assumptions :
$\alpha\approx 0$, $\k_1\approx 1$, $\k_2\ll \k_0$ and $ 18\d \sqrt n/d\approx 0$. 
\end{theorem}
\begin{corollary}
\label{cor2}
Under the same conditions as in Theorem \ref{th2}, we have the following
bound on the
variational distance:
$$\sum _{x\in C} \left| p_t(x)-\pi (x)\right| \leq (1-\lambda _2)^t  
\left( \sum_{x\in C}\left( {p_0(x)\over \pi (x)} - 1\right)^2\pi (x)\right)^
{1/2} .$$
\end{corollary}

In the next section we prove a general result about the rate  
of convergence to the steady state for arbitrary time reversible  
chains. It is then a matter of estimating quantities associated with
this result.


\section{Convergence rates of time reversible chains: dealing with small sets}

In the analysis of geometric random walks, it turns out that certain  
sets of
states with relatively small steady state probabilities are not easy  
to
analyse. In the case of random walks on convex sets, where the  
problem is
usually discretized by using a set of cubes as the states, this  
problem arises
for the set of $S$ of {\em boundary cubes} which are those cubes in  
${\cal C}$ which are not wholly contained in the convex set. This  
irksome problem has cost volume computation algorithms significant  
added complexity \cite{DFK},\cite{LS1} and has also led to new ideas  
like the use of log-concave damping functions as in \cite{AK}. In this section,
we propose a general way of tackling the problem of small sets. In  
some sense, this serves a purpose analogous to that of $\mu-$conductance  
proposed by Lov\'asz and Simonovits \cite{LS1}. 

Suppose $P$ 
is the $N\times N$
transition probability matrix of an ergodic Markov Chain with $N$ states
and 
steady state probabilities $\pi (\cdot )$. We assume throughout that the chain
is time-reversible, i.e., that $\pi (x) P(x,y) = \pi (y) P(y, x)$ for
all $x,y$.
Suppose we start the chain with initial distribution $p_0(\cdot )$ [ i.e.,
$\Prob (X_0 = x)= p_0(x)$ for all $x$.] Let $p_t(\cdot )$ be the probability 
distribution of $X_t$. We define the following
quantity 
$$\phi_t (x) = { p_t(x)\over \pi (x) } - 1.$$
This leads to what Fill \cite{F} calls the chi-squared
distance between distributions.  

To define this distance, we first define an inner product on $\reals^N$ by 
$$\inner{\f}{\psi} =  \sum_{x\in [N]}\f(x)\psi(x)\p(x)$$
and denote its associated norm by 
$$\mid \f\mid_{\p}  =  \inner{\f}{\f}^{1/2}. $$
%
We also retain the more familiar notation that $\card{\ }$ denotes Euclidean 
length and that $\card{\f}_{\infty}=\max\{|\f(x)|:x\in[N]\}$. 

Suppose 
$$\sigma _0 = \sup 
        \left\{ { \left| < \phi ,P\phi >\right| \over <\phi ,\phi >
}:\phi\not=  0 , \pi ^T\phi = 0\right\}.$$
[From Linear Algebra and time-reversibility, it can be seen that $P$'s
largest eigenvalue is 1 and that
$\sigma_0$ is the largest absolute value of an eigenvalue of $P$ other than 1.
We will only use the first of these facts.]

Using arguments similar to the ones used by Fill \cite{F} to get his inequality
(2.11), we can get the following inequality :
$$|\phi_t|_\pi \leq \sigma_0 ^t |\phi _0|_\pi .$$

So it would suffice then to prove an upper bound on $\sigma_0$. This, we
are not
always able to do for the random walk described in Section 1. 
We are able to prove a bound on a quantity similar to $\sigma_0$ which ignores a small set $S$. Our aim in this section is to prove
an inequality for general time-reversible chains, similar to the one above, 
but with the new quantity $\sigma $ replacing $\sigma_0$. 

Let $S$ be an arbitrary set of states which will remain fixed for the
rest of this section.
Let 
$$\OM=\{\f\in\reals^N:\p^T\f=0\mbox{ and }\f(x)=0,x\in S\}$$
and
$$\sigma = \sup\left\{ { \left| < \phi ,P\phi >\right| \over <\phi ,\phi >
}:\phi\in \OM \setminus \{ 0\} , \pi ^T\phi
  = 0\right\}.$$

The main Theorem of this section is the following :

\begin{theorem}
\label{th3}
\begin{equation}
\label{l0}
\card{\phi_t}_\pi \leq \sigma^t\card{\phi_0}_\pi
         + {3\card{\f_0}_{\infty}\over (1-\s )}\SS.
\end{equation}
\end{theorem}

We need some preliminary Linear Algebra.
Let $D$ denote the $N\times N$ diagonal matrix whose $(x,x)$'th entry is  
$\sqrt{\p(x)}$. Then time reversibility is equivalent to
\begin{equation}
\label{a1}
D^2P=P^TD^2.
\end{equation}
Let
$$Q=DPD^{-1}.$$
$Q$ has the same eigenvalues as $P$ and equation (\ref{a1}) implies  
that it is symmetric.

$D$ ``converts'' $\card{\ }_\p$ to $\card{\ }$ in a natural way. This  
follows from
$$\inner{\f}{\psi}=(D\f)^T(D\psi)$$
for $\f,\psi\in\reals^N$.
Thus
$$\card{\f}_\p=\card{D\f}\quad\hbox{and }\quad \inner{\f}{P\f}=(D\f)^TQ(D\f).$$
So using $\psi=D\f$ we obtain
\begin{equation}
\label{8}
\s=\sup_{{\psi\in\tilde{\OM}\atop \psi\neq 0}}\left\{\left|{\psi^T  
Q\psi\over \psi^T\psi}\right|\right\}
\end{equation}
where
$$\tilde{\OM}=\{\psi:\z^T\psi=0\mbox{ and }\psi(x)=0,x\in S\}$$
and $\z(x)=\sqrt{\p(x)}$ for $x\in[N]$.
Let $A$ denote the orthogonal projection of $\reals^N$ to  
$\tilde{\OM}$. It is easy to see that $A$ is defined by 
$$A\psi(x)=\left\{
\begin{array}{ll}
\psi (x)- { \sqrt {\pi (x)}\over {\pi (\bar S)}}\left( \sum_{{y\in\bar S}}
               \psi(y) \sqrt {\pi (y)}\right)& x\in \bar S,\\
0 & x\in S.
\end{array}
\right.
$$

\begin{lemma}
\label{lem1}
Let $Q,\tilde\OM , A, \sigma $ be as above. Then 
$$\card{AQA\f}\leq \s\card{\f},\ \ \ \ \hbox{ for all }\f\in \reals^N.$$
\end{lemma}

\proofstart
For $\phi \in \tilde\OM $, we have $\phi ^T Q\phi = \phi^TAQA\phi$. So, 
$$
\s  =  \sup_{{\f\in \tilde\OM\atop \f\neq 0}}\left\{\left|{\f^TAQA\f\over  
\f^T\f}\right|\right\} \quad
 \leq  \sup_{{\f\in R^N \atop \f\neq  
0}}\left\{\left|{\f^TAQA\f\over \f^T\f}\right|\right\} \quad
 =  \s_1$$
where $\s_1$ is the largest eigenvalue of the symmetric matrix  
$B=AQA$. (From standard Linear Algebra, if $\tilde\OM = \{ x : x = Cy\}$, where
$C$ is a matrix with independent columns, then $A=C(C^TC)^{-1}C^T$ and is 
therefore symmetric.)
But if $\f$ is a corresponding eigenvector of $B$ then  
$B\f =\s_1\f$ implies that $\f\in \tilde\OM$. Hence $\s=\s_1$ and the lemma  
follows.
\proofend

\begin{lemma}
\label{lem2}
$\z^T\psi=0$ implies
$$\card{\psi-A\psi}\leq\card{D^{-1}\psi}_{\infty}\SS.$$
\end{lemma}

\proofstart
Assume $\z^T\psi=0$. Let  
${\psi}^\prime =\psi-A\psi\; ; \; $ $\phi = D^{-1}\psi \; ; \; $ and  
$M=\card{\phi }_{\infty}$. Then
\begin{eqnarray*}
\sum_{x\in[N]}{\psi}^\prime (x)^2 & = & \sum_{x\in S}\psi(x)^2+{1\over  
\p(\bar{S})^2}\sum_{x\in \bar{S}}\left(\sum_{y\in  
\bar{S}}\psi(y)\sqrt{\p(y)}\right)^2\p(x) \\
& = & \sum_{x\in S}\phi (x)^2\pi (x) + {1\over \pi (\bar S)^2}\sum_{x\in 
            \bar S}\pi (x) \left( \sum_{y\in \bar S}\phi (y)\pi
(y)\right)^2 \\ 
& = & \sum_{x\in S}\phi (x)^2\pi (x) + {1\over \pi (\bar S)^2}\sum_{x\in 
            \bar S}\pi (x) \left( \sum_{y\in S}\phi (y)\pi
(y)\right)^2 \\ 
& \leq & M^2\p(S)+M^2\p(S)^2/\p(\bar{S}) \\
& = & M^2\p(S)/\p(\bar{S}).
\end{eqnarray*}
\proofend

We now go back to the proof of the main theorem of the section, Theorem
\ref{th3}. 

{\bf Proof}(of Theorem \ref{th3}) \hspace{.1in} Let $\psi_t=D\f_t$. Observe that $|\phi |_\pi = |\psi |$. We will prove that 
\begin{equation}
\label{j1}
\card{\psi_{t+1}}\leq \s\card{\psi_t}+3\card{\f_0}_{\infty}\SS,
\end{equation}
from which we get by induction on $t$, 
\begin{eqnarray*}
\card{\psi_t} & \leq & \s^t\card{\psi_0}+3\card{\f_0}_{\infty}\left({1 
-\s^{t+1}\over 1-\s}\right)\SS  \\ 
& \leq & \s^t\card{\psi_0}+3{\card{\f_0}_{\infty}
\over 1-\s }\SS 
\end{eqnarray*}
as desired. Now
$$\z^T\psi_t=\sum_{x\in[N]}(p_t(x)-\p(x))=0$$
Also, using time-reversibility, we get, 
$$
(P\f_t)(x)  =  \sum_{y\in[N]}{P(x,y)p_t(y)\over \p(y)}\ -1 \ 
 =  \sum_{y\in[N]}{P(y,x)p_t(y)\over \p(x)}\ -1  
 =  \f_{t+1}(x) .$$
%
Thus $P\f_t=\f_{t+1}$ and  pre-multiplying by  
$D$, we get 
$$\psi_{t+1} = Q\psi_t\for t\geq 0  .$$

To prove (\ref{j1}), we proceed as follows : 
$$|\psi_{t+1}|=|Q\psi_t|\leq |QA\psi_t|+|Q(\psi_t -A\psi_t)|.$$
Using the fact that $Q$'s eigenvalues have absolute value at most 1, 
and Lemma \ref{lem2}, along with the fact that $|\phi_{t+1}|_\infty\leq
|\phi_t|_\infty$ (since $P$ has row sums equal to 1), we have, 
$$|Q(\psi_t - A\psi_t )|\leq |\psi_t -A\psi_t|\leq |\phi_0|_\infty \SS.$$
Now we need to bound $|QA\psi_t|$. But, 
$$|QA\psi_t| = |AQA\psi_t| + | QA\psi_t - AQA\psi_t|.$$
We have by Lemma \ref{lem1} that
$|AQA\psi_t|\leq \sigma |\psi_t|$. So it now suffices to prove that 
$$| QA\psi_t - AQA\psi_t|\leq 2 |\phi_0|_\infty \SS .$$
Now, 
\begin{eqnarray*}
| QA\psi_t - A(QA\psi_t)| & = & |(I-A) QA\psi_t| \\
& \leq & |(I-A)Q\psi_t|+ |(I-A)Q(A\psi_t -\psi_t)| \\
& \leq & |(I-A)\psi_{t+1} | + |A\psi_t -\psi_t|
\end{eqnarray*}
since $Q$ has all eigenvalues of absolute value at most 1 and also for all
vectors $v$, $|(I-A)v|\leq |v|$, because $A$ is a projection.
Each of the last two quantities is at most $|\phi_0|_\infty\SS $, 
by Lemma \ref{lem2} . This finishes the proof of the Theorem.

\proofend


Our aim is to prove an upper bound on 
$$\sigma = \sup_{ { \phi\in \OM \setminus \{ 0\} \atop \pi ^T\phi
  = 0} }\left\{ { \left| < \phi ,P\phi >\right| \over <\phi ,\phi > }\right\}$$
for the case of the walk of Section 1.
We will split the task into two parts. In the next section, 
we prove that for any $\phi $ in $\OM \setminus \{ 0\} $ with $\pi
^T\phi = 0$, 
we have 
\begin{equation}
\label{eq33}
{< \phi ,P\phi > \over <\phi ,\phi > }\geq - 
\left( 1-{\delta^2\over 6d^2}\right) .
\end{equation}
Clearly for this it suffices to consider the $\phi $ satisfying $< \phi , 
     P\phi >   < 0$. Then in the ensuing section, we prove the more difficult
bounds : 
$$ {  < \phi ,P\phi > \over <\phi ,\phi > }\leq 1-\l,$$
where $\l=\l_1$ (Theorem \ref{th1}) or $\l=\l_2$ (Theorem \ref{th2}).
\section{Proof of (\protect\ref{eq33}) - $<\f,P\f><0$}

We now return to the specific chain corresponding to our random walk.  
The following lemma considers the case where $\inner{\f}{P\f}$ is  
negative.
\begin{lemma}
$\f\in \OM$ implies
$$\inner{\f}{P\f}\geq -(1-\t )\inner{\f}{\f}$$
where $\t = \d^2/6d^2$.
\end{lemma}
\proofstart
Consider
\begin{eqnarray}
\inner{\f}{P\f}+(1-\t)\inner{\f}{\f} & = & \nonumber \\
\sum_{x\in C}\left(\sum_{y\in  
C}P(x,y)\f(y)\right)\f(x)\p(x)+\sum_{x\in C}(1-\t)\f(x)^2\p(x) & = &  
\nonumber \\
\sum_{x\in C}\sum_{y\neq x}P(x,y)\f(y)\f(x)\p(x)+\sum_{x\in  
C}(1-P(x,x))\f(x)^2\p(x)+\sum_{x\in C}(2P(x,x)-\t)\f(x)^2\p(x) & = &  
\nonumber \\
\sum_{x\in C}\sum_{y\neq  
x}(P(x,y)\f(y)\f(x)\p(x)+P(x,y)\f(x)^2\p(x))+\sum_{x\in  
C}(2P(x,x)-\t)\f(x)^2\p(x) & = &  \nonumber \\
\sum_{\{x,y\}\in E}\p(x)P(x,y)(\f(x)+\f(y))^2+\sum_{x\in  
C}(2P(x,x)-\t)\f(x)^2\p(x) , & & \label{b1}
\end{eqnarray}
where $E=\{\{x,y\}:x\neq y\mbox{ and }P(x,y)>0\}$ and the last equation follows by  
time-reversibility.

Suppose next that the walk is at $x\in C$. Let $P_i(x,x)$ denote the  
probability that the $i$'th direction is chosen and that no movement  
is made at the current iteration. Thus
$$P_i(x,x)={1\over 2n}\left(1-\min\left\{1,{\p(x+e_i)\over  
\p(x)}\right\}+1-\min\left\{1,{\p(x-e_i)\over \p(x)}\right\}\right)$$
and of course
$$P(x,x)=\sum_{i=1}^nP_i(x,x).$$
We will show for each $i, i=1,2\ldots n$, 
that with $E_i=\{(x,y)\in E:x-y=\pm \d e_i\}$, 

\begin{equation}
\label{y1}
\sum_{\{x,y\}\in  
E_i}\p(x)P(x,y)(\f(x)+\f(y))^2+\sum_{x\in  
C}\left(2P_i(x,x)-{\t\over n}\right)\f(x)^2\p(x)   \geq 0.
\end{equation}

Fix $i$ and consider the lines in $\reals^n$ parallel to $e_i$ which  
go through  the centres $C$ of the cubes ${\cal C}$. These lines  
induce a natural partition of $C$ into ${\cal L}_i$ where each  
$L\in{\cal L}_i$ is the set of cube centres lying on some line. Now  
fix $L\in{\cal L}_i$ and suppose that
\begin{eqnarray*}
L & = & \{x,x+e_i,x+2e_i,\ldots ,x+se_i\} \\
& = & \{x^{(0)},x^{(1)},\ldots ,x^{(s)}\}.
\end{eqnarray*}
We break $L$ into {\em maximal} contiguous segments $L_1,L_2,\ldots$  
of the form
$$\{x^{(k)},x^{(k+1)},\ldots ,x^{(\ell)}\}$$
such that
$$\p(x^{(r+1)})\geq \p(x^{(r)})\left(1-{\d\over d}\right)$$
for $r=k,k+1,\ldots ,\ell-1$.

(A segment ends when $\p(x^{(\ell+1)})<  
\p(x^{(\ell)})\left(1-{\d\over d}\right)$, which includes $\ell=s$ as  
then the ``next'' cube centre has $\p(\cdot)=0$.)

Thus
\begin{equation}
\label{y2}
P(x^{(r)},x^{(r+1)})\geq {1\over 2n}\left(1-{\d\over  
d}\right),\hspace{.5in}r=k,k+1,\ldots ,\ell-1,
\end{equation}
and, 
\begin{equation}
\p(x^{(r)}) \geq  \th\p(x^{(r')}),\hspace{.5in} k\leq r'\leq r\leq \ell  
, \label{y3}
\end{equation}
where $\th=\left(1-{\d\over  d}\right)^{(d/\d)-1}$.

Finally,
\begin{equation}
\label{y4}
P_i(x^{(\ell)},x^{(\ell)})\geq {1\over 2n}{\d\over d}.
\end{equation}
We prove (\ref{y1}) by showing that
\begin{equation}
\label{y5}
\sum_{r=k}^{\ell-1}\p(x^{(r)})P(x^{(r)},x^{(r+1)})(\f(x^{(r)})+\f(x^{ 
(r+1)}))^2+\sum_{r=k}^{\ell}\left(2P_i(x^{(r)},x^{(r)})-{\t\over 
 n}\right)\f(x^{(r)})^2\p(x^{(r)})\geq 0. 
\end{equation}
Now for $k\leq r<\ell$,
$$\f(x^{(r)})=(\f(x^{(r)})+\f(x^{(r+1)}))-(\f(x^{(r+1)})+\f(x^{(r+2)} 
))+\cdots \pm(\f(x^{(\ell-1)})+\f(x^{(\ell)}))\pm\f(x^{(\ell)}).$$

Applying the Cauchy-Schwarz inequality twice, we get 
\begin{eqnarray*}
\f(x^{(r)})^2\p(x^{(r)}) & \leq & 
2 \p(x^{(r)})\left( \sum_{r'=r}^{\ell-1}|\f(x^{(r')})+\f(x^{(r'+1)})
|\right)^2+
2 \f(x^{(\ell)})^2\p(x^{(r)}) \\
&\leq & 2 (\ell -r)
\p(x^{(r)})\sum_{r'=r}^{\ell-1}(\f(x^{(r')})+\f(x^{(r'+1)}))^2+ 2 
\f(x^{(\ell)})^2\p(x^{(r)}) \\
& \leq & 4\th^{-1}\left(1-{\d\over d}\right)^{-1}n(\ell -
r)\sum_{r'=r}^{\ell-1}\p(x^{(r')})P(x^{(r')},x^{(r'+1)})(\f(x^ {(r')})
+\f(x^{(r'+1)}))^2\\  
& &  +2\th^{-1}\f(x^{(\ell)})^2\p(x^{(\ell)}).
\end{eqnarray*}
%
Summing over $r=k,k+1,\ldots ,\ell-1$ and adding  
$\f(x^{(\ell)})^2\p(x^{(\ell)})$, we obtain
\begin{eqnarray*}
\sum_{r=k}^{\ell}\f(x^{(r)})^2\p(x^{(r)}) & \leq & 2\th^{-1}\left(1-{\d\over d}\right)^{-1}n\left({d\over  
\d}\right)^2 \sum_{r=k}^{\ell-1}\p(x^{(r)})P(x^{(r)},x^{(r+1)})(\f(x^{(r) 
}) +\f(x^{(r+1)}))^2\\
& & +\left(1+2\th^{-1}{d\over  \d}\right)\f(x^{(\ell)})^2\p(x^{(\ell)}).
\end{eqnarray*}
Comparing this with what we want i.e.(\ref{y5}) 
we see that the following suffices: 
$$2\th^{-1}\left(1-{\d\over d}\right)^{-1}{\t\over n}\left({d\over \d}\right)^2 n\leq 1$$
and
$${\t\over n}\left(1+2\th^{-1}{d\over  \d}\right)\leq  
2P_i(x^{(\ell)},x^{(\ell )}).$$
Under the assumption that $10\delta \leq d$, we get that 
$\t = \d^2/6d^2$ satisfies the inequalities since we have
(\ref{y4}).

\proofend

{\bf Remark 3:} The modified walk has $P(x,x)\geq 1-\nu$ and the argument can be stopped at (\ref{b1}) provided $\t\leq 2(1-\nu)$. We thus need $\nu\geq 1-\hat{\l}_1/2$ in the modified walk. Note that we have $\hat{\l}_1$ rather than $\l_1$ as the modification introduces a factor of $\n$ into our eigenvalue estimate - see Remark 4.

\section{Reduction to a continuous problem}

We first introduce the quantity
$$E(\f,\f)=\inner{\f}{\f}-\inner{\f}{P\f}$$
for all $\f\in \reals^C$.
The time reversibility of $P$ allows us to conclude

\begin{equation}
\label{E}
2E(\f,\f)=\sum_{x\in C}\sum_{y\in \G(x)}(\f(x)-\f(y))^2\p(x)P(x,y)
\end{equation}
where $\G(x)=\{y\in C:P(x,y)>0\}$.

To prove (\ref{E}) write
\begin{eqnarray*}
\sum_{x\in C}\sum_{y\in C}\p(x)P(x,y)(\f(x)-\f(y))^2 & = & \\
\sum_{x\in C}\p(x)\f(x)^2\sum_{y\in C}P(x,y)+\sum_{y\in  
C}\p(y)\f(y)^2\sum_{x\in C}P(y,x)-2\sum_{x\in C}\p(x)\f(x)\sum_{y\in  
C}P(x,y)\f(y).&&
\end{eqnarray*}
%
In this notation we must now prove that
$$\inf_{\f\in\OM}{E(\f,\f)\over \inner{\f}{\f}}\geq \l.$$
Let $1_C$ denote the $C$-vector of 1's, $\bar{\f}=\sum \p (x)\f (x)$ and let  
$\bar{\OM}=\{\f:\f(x)=\bar{\f}\mbox{ for }x\in S\}$. If  
$\f\in\bar{\OM}$ then $\f-\bar{\f}1_C\in\OM$. Also for all $\f\in\reals^N$  
and for all $z\in \reals$, we have 
$$E(\f-z1_N,\f-z1_N)=E(\f,\f).$$
%
$$\inner{\f-\bar{\f}1_C}{\f-\bar{\f}1_C}=\inner{\f}{\f}-\bar{\f}^2$$
and so we can re-define our objective as proving
\begin{equation}
\label{eq4}
\inf_{{\f\in\bar{\OM}\atop \f\mbox{ non-constant}}}{E(\f,\f)\over  
\inner{\f}{\f}-\bar{\f}^2}\geq \l.
\end{equation}
For the rest of this section, we fix a particular non-constant $\f$ 
in $\tilde\OM$. 
Let $T=\bigcup_{x\in C}C(x)$ which is ``slightly'' bigger than $K$.  
Define $\tilde{F}:T\rightarrow \reals$ as follows: suppose $\xi\in  
C(x)$ for some $x\in C$. $\tilde{F}(\xi)=\bar{F}(x)$ if  
$\xi\not\in\partial C(x)$ and $\tilde{F}(\xi)=0$ otherwise.

Given $\f\in\reals^N$ and a small $\e>0$ we define  
$\F_\e:T\rightarrow \reals$ as follows: suppose $z\in C(x)$ for some  
$x\in C$. Let $C(x,\e)$ denote the cube centred at $x$ with side  
$\d-2\e$. If $z\in C(x,\e)$ we let $\F_\e(z)=\f(x)$. If $z\not\in  
C(x,\e)$ let $D$ be a face of $C(x)$ which is closest to $z$. 
(If there is a tie for $D$, the value of $\Phi_\epsilon $ does not matter, as
we will see.) Suppose  
first that $D=C(x)\cap C(y)$ for some $y\in C$ and that  
$dist(z,D)=\eta\e$ where $0\leq\eta<1$. In this case we let  
$\F_\e(z)=((1+\eta)\f(x)+(1-\eta)\f(y))/2$. In this way, if we start  
at a point on a face of $C(x,\e)$ parallel to $D$ and move towards  
$D$ then $\F_\e$ changes linearly from $\f(x)$ to $\f(y)$ over a  
distance $2\e$. Finally, if the hypercube on the other side of $D$ to  
$C(x)$ is not in ${\cal C}$ then we keep $\F_\e(z)=\f(x)$.

Let
$$I_\e=\int_T\card{\nabla\F_\e(z)}^2\tilde{F}(z)dz.$$
$\F_\e$ is not differentiable on a set $Z$ of measure zero
(consisting of points for which there is a tie for $D$). We can  
however easily ``smooth out'' $\F_\e$ close to $Z$ so that (\ref{E})  
and (\ref{eq1}) imply
\begin{eqnarray*}
\e I_\e & = & \d^{n-1}\sum_{x\in  
C}\sum_{y\in\G(x)}\left({\f(x)-\f(y)\over  
2}\right)^2\bar{F}(x) +O(\e) \\
& \leq & \left({1+\a\over 4}\right)\d^{n-1}\sum_{x\in  
C}\sum_{y\in\G(x)}({\f(x)-\f(y)})^2\min\{\bar{F}(x),\bar{F}(y)\}+O(\e 
) \\
& = & (1+\a)\D n\d^{n-1}E(\f,\f)+O(\e),
\end{eqnarray*}
where the hidden constant in $O(\e)$ may depend on $n,F,\f$.

{\bf Remark 4:} for the modified walk we need a factor of $\n^{-1}$ in order to get the final equation.

On the other hand, the concavity of $\ln F$ implies that it is continuous; so 
for small enough $\e$, we have $\int_S F(\z )d\z \leq (1+f(\e ))\int_{C(x)\cap
     C(y)}F(\z )d\z$ where $S$ is obtained by translating $C(x)\cap C(y)$
towards $x$ by some $\e^\prime\in [0,\e ]$ and $f$ is some function with
lim sup$_{\e\rightarrow 0}f(\e ) =0$. This along with (2) implies that
$$\e I_\e\geq  
(1+ f(\e ))^{-1}(1+\a)^{-1}\e\int_T\card{\nabla\F_\e(z)}^2{F}(z)dz-O(\e).$$
So
\begin{equation}
\label{eq5}
E(\f,\f)\geq {\e\int_T\card{\nabla\F_\e(z)}^2{F}(z)dz\over  
(1+\a)^2(1+f(\e ) )n\d^{n-1}\D}-O(\e).
\end{equation}
This deals with the numerator in (\ref{eq4}). For the denominator
%
\begin{eqnarray}
\inner{\f}{\f}-\bar{\f}^2 & = & \D^{-1}\sum_{x\in  
C}\f(x)^2\bar{F}(x)-\bar{\f}^2 \nonumber  
\\
& = & \D^{-1}\sum_{x\in  
C}(\f(x)-\z)^2\bar{F}(x)-(\bar{\f}-\z)^2\hspace{.5in}\mbox{for any  
}\z\in\reals. \nonumber \\
& & \label{eq55}
\end{eqnarray}
We will use the above with $\z=\m$ where
$$\m={\int_K\F_\e(z)F(z)dz\over \int_K F(z)dz} \mbox{ and then let  
}\psi(z)=\F_\e(z)-\m.$$
We will show in Section \ref{sec5} that
\begin{equation}
\label{eq6}
\int_K\psi(z)^2F(z)dz\leq \e\k_0\int_K\card{\nabla\psi}^2{F}(z)dz
\end{equation}
and in Section  
\ref{sec6} (for use in Theorem \ref{th2})
\begin{equation}
\label{eq7}
\int_{T\setminus K}\psi(z)^2F(z)dz\leq  
a\k_1\int_K\psi(z)^2F(z)dz+b\e\k_2\int_T\card{\nabla\psi}^2{F}(z)dz,
\end{equation}
for any $a,b\geq 1$ satisfying $(a-1)(b-1)\geq 1$.

Consider first Theorem \ref{th1}. It follows from (\ref{eq55}) that
\begin{eqnarray}
\inner{\f}{\f}-\bar{\f}^2 & = & \D^{-1}\sum_{x\in C\setminus  
S}(\f(x)-\m)^2\bar{F}(x)+\D^{-1}\sum_{x\in
 S}(\f(x)-\m)^2\bar{F}(x)-(\bar{\f}-\m)^2 \nonumber \\
& \leq & {1+\a\over \d^n\D}\int_K\psi(z)^2F(z)dz +O(\e) \label{28a}
\end{eqnarray}
since $\f=\bar{\f}$ for $x\in S$.

Thus, by (\ref{eq6}),
\begin{eqnarray}
\inner{\f}{\f}-\bar{\f}^2 & \leq &  
{1+\a\over \d^n\D}\e\k_0\int_K\card{\nabla\psi(z)}^2{F}(z)dz+O(\e)  
\nonumber \\
& \leq &  
{1+\a\over \d^n\D}\k_0(1+\a)^2 (1+f(\e))n\d^{n-1}\D E(\f,\f)+O(\e) \nonumber \\
& &  
\label{28b}
\end{eqnarray}
The second inequality comes from (\ref{eq5}) and $K\subseteq T$.
Now, (\ref{28b}) is true for all $\e>0$ and so (\ref{eq4}) follows in the  
case of Theorem \ref{th1}.

Now consider Theorem \ref{th2}. It follows from (\ref{eq55}) that
\begin{eqnarray*}
\inner{\f}{\f}-\bar{\f}^2 & \leq &  
{1+\a\over \d^n\D}\int_T(\F_\e(z)-\m)^2{F}(z)dz+O(\e) \\
& = & {1+\a\over \d^n\D}\left(\int_K\psi^2{F}(x)dx+\int_{T\setminus  
K}\psi^2{F}(z)dz\right)+O(\e) \\
& \leq &  
{1+\a\over \d^n\D}\left((a\k_1+1)\int_K\psi^2{F}(z)dz+b\e\k_2\int_T
\card{\nabla\F_\e(x)}^2{F}(z)dz\right)+O(\e) \\
& \leq &  
{1+\a\over \d^n\D}(\k_0(a\k_1+1)+b\k_2)\e\int_T\card{\nabla\F_\e(z)}^2{ 
F}(z)dz+O(\e) \\
& \leq &  
{1+\a\over \d^n\D}(\k_0(a\k_1+1)+b\k_2)(1+\a)^2(1+f(\e))n\d^{n-1}\D E
(\f,\f)+O(\e).
\end{eqnarray*}
Substituting $a=1+\sqrt{\k_2/(\k_0\k_1)}$ and $b=1+(a-1)^{-1}$ we obtain
$$\inner{\f}{\f}-\bar{\f}^2 \leq {1+\a\over \d^n\D}(\k_0\k_1+\k_0+\k_2+2\sqrt{\k_0\k_1\k_2})(1+\a)^2(1+f(\e))n\d^{n-1}\D E
(\f,\f)+O(\e).$$
This is true for all $\e>0$ and so (\ref{eq4}) follows for the case of  
Theorem \ref{th2}.

\section{Proof of (\protect\ref{eq6})}

\label{sec5}
We will reduce the geometry to one dimension by applying the following  
{\em localisation lemma} of Lov\'asz and Simonovits \cite{LS2}:
\begin{lemma}
\label{lemloc}
Let $f_1,f_2$ be upper semi-continuous functions defined on  
$\reals^n$ such that
$$\int_{\reals^n}f_i(z)dz>0\ \ i=1,2.$$
Then there exist $a,b\in \reals^n$ and a linear function  
$\ell:[0,1]\rightarrow \reals_+$ such that
$$\int_{t=0}^1f(ta+(1-t)b)\ell(t)^{n-1}dt>0,\ \ i=1,2.$$
\end{lemma}
To apply this we replace (\ref{eq6}) by the equivalent
\begin{equation}
\label{eq16}
\int_K\F_{\e}^2(z)F(z)dz-{\left(\int_K\F_{\e}(z)F(z)dz\right)^2\over  
\int_KF(z)dz}\leq \e\k_0\int_K\card{\nabla\F_\e(z)}^2F(z)dz.
\end{equation}
Adding a constant to $\F_{\e}$ does not change either side of this  
inequality and so we can assume that $\F_{\e}(z)$ is positive on $K$.  
We then use the fact that under this assumption (\ref{eq16}) {\em  
fails} to hold if and only if there exists $\a>0$ such that
$$\int_K\F_{\e}^2(z)F(z)dz-\a\int_K\F_{\e}(z)F(z)dz>\e\k_0\int_K\card{\nabla\F_
\e(z)}^2F(z)dz$$
and
$$-\int_K\F_{\e}(z)F(z)dz+\a\int_KF(z)dz>0.$$
We apply Lemma \ref{lemloc} with
$$f_1=(\F_\e^2F-\a\F_\e F-\e\k_0\card{\nabla\F_\e(x)}^2F)\chi_K$$
and
$$f_2=(-\F_\e F+\a F)\chi_K.$$
($\chi_K$ is the indicator function of the body $K$.)

Let $a,b,\ell$ be as in the lemma. We observe that we can take  
$a,b\in K$ because of the factor $\chi_K$. Let  
$g(t)=\F_\e((1-t)a+tb)$, $h(t)=F((1-t)a+tb)\ell(t)^{n-1}$,  
$\p(t)=h(t)/\int_{\xi=0}^1h(\xi)d\xi$ and  
$\tilde{g}(t)=\card{\nabla\F_\e((1-t)a+tb)}$. Note that $\p(t)$ is  
log-concave.

We then see that if (\ref{eq16}) fails to hold then
\begin{equation}
\label{eq17}
\int_{t=0}^1g(t)^2\p(t)dt-\left(\int_{t=0}^1g(t)\p(t)dt\right)^2\leq  
\e\k_0\int_{t=0}^1\tilde{g}(t)^2\p(t)dt
\end{equation}
fails to hold.

We can thus prove (\ref{eq6}) by proving (\ref{eq17}). We replace the  
LHS of (\ref{eq17}) using the identity
\begin{equation}
\label{eq18}
\int_{t=0}^1g(t)^2\p(t)dt-\left(\int_{t=0}^1g(t)\p(t)dt\right)^2={1\over
2}\int_{ 
s=0}^1\int_{t=0}^1(g(t)-g(s))^2\p(s)\p(t)dsdt.
\end{equation}
Let $\hat{d}=\card{b-a}$ and $u=(b-a)/\hat{d}$. Then for $0\leq s\leq  
t\leq 1$,
\begin{eqnarray*}
(g(t)-g(s))^2 & = & \left( \int_{\xi =s}^t g^\prime (\xi ) d\xi \right)^2 \\
& = & \hat d^2\left( \int_{\xi=s}^t \sum_{j=1}^n u_j\chi _j(\xi ) {\partial\F _\e\over \partial x_j}( (1-\xi )a + \xi b)\; d\xi \right)^2,
\end{eqnarray*}
where $\chi_j(\cdot )$ is defined by
$$\chi_j(\xi ) = \left\{
\begin{array}{ll}
1 & \hbox{if } {\partial\F _\e\over
       \partial x_j}( (1-\xi )a + \xi b)\not= 0 \\
0 & \hbox{otherwise }.
\end{array}
\right.$$
By the Cauchy-Schwarz inequality, we have 
$$\sum_{j=1}^n |u_j\chi_j(\xi ){\partial\F _\e\over
       \partial x_j}( (1-\xi )a + \xi b)| \leq \left( \sum_{j=1}^n u_j^2\chi_j(\xi )
   \right)^{1/2}\tilde{g}(\xi ).$$
So we get with another application of Cauchy-Schwarz, 
\begin{eqnarray*}
(g(t)-g(s) )^2 & \leq & \hat d^2 \left(\int_{\xi = s}^t \left( \sum_{j=1}^n
u_j^2\chi_j(\xi )\right)^{1/2} \tilde{g}(\xi )d\xi\right)^2 \\
& \leq & \hat d^2 \left( \int_{\xi = s}^t \sum_{j=1}^n u_j^2\chi_j(\xi )d\xi\right)
     \left( \int_{\xi = s}^t \tilde g (\xi )^2 d\xi \right).
\end{eqnarray*}
%
Now each time the line from $s$ to $t$ crosses a hyperplane of the form
$x_j = m\delta $, $m$ an integer, we get a contribution of $2\epsilon /
     \hat du_j $ to $\int \chi_j(\xi )d \xi$. Furthermore, the number of such
crossings is at most 
\begin{equation}
\label{bug}
{\hat d u_j (t-s)\over \delta }+1.
\end{equation}
So we get (using the facts that $\sum_{j=1}^n u_j^2 = 1$ and $\sum |u_j|\leq
\sqrt n$)
$$( g(t) -g(s) )^2\leq  2 \hat d^2\epsilon \left( {|t-s|\over\delta} +
{\sqrt n\over \hat{d}}\right)\int_{\xi =s}^t \tilde g (\xi )^2 d\xi.$$
Thus if RHS(\ref{eq18}) denotes the RHS of (\ref{eq18}) then
\begin{eqnarray}
\mbox{RHS}(\ref{eq18}) & \leq &  
\hat{d}^2\e\int_{s=0}^1\int_{t=0}^1\left({|t-s|\over  
\d}+{\sqrt{n}\over\hat{d}}\right)\int_{\xi=s}^t\tilde{g}(\xi)^2d\xi\p(t)\
\p(s) dtds \nonumber \\
& = &  
2 \hat{d}^2\e\int_{\xi=0}^1\tilde{g}(\xi)^2\p(\xi)\left(\int_{s=0}^
{\xi }\int_{t=\xi}^1\left({t-s\over
\d}+{\sqrt{n}\over\hat{d}}\right){\p(s)\p(t)\over  
\p(\xi)}dtds\right)d\xi
\nonumber \\
& & \label{eq19}
\end{eqnarray}
where the last equation is obtained by interchanging the order of integration, 
the factor of 2 coming from the fact that $s,t$ are interchangable in the 
previous expression. Now let
$$\P=\{\p\in[0,1]\rightarrow\reals_+:\p\mbox{ is log-concave and  
}\int_{t=0}^1\p(t)dt=1\}.$$
Let
$$M_1=\sup_{{\p\in\P\atop  
\xi\in[0,1]}}\int_{s=0}^{\xi}\int_{t=\xi}^1(t-s){\p(s)\p(t)\over  
\p(\xi)}dtds$$
and
$$M_2=\sup_{{\p\in\P\atop  
\xi\in[0,1]}}\int_{s=0}^{\xi}\int_{t=\xi}^1{\p(s)\p(t)\over  
\p(\xi)}dtds.$$
Then (\ref{eq19}) implies
\begin{equation}
\label{eq20}
\mbox{RHS}(\ref{eq18})\leq 2 \hat{d}^2\e\left({M_1\over  
\d}+{M_2\sqrt{n}\over\hat{d}}\right)\int_{\xi=0}^1\tilde{g}(\xi)^2\p(\xi)d\xi.
\end{equation}
We will prove below that
$$M_1={1\over 8}\mbox{ and }M_2={1\over 4}$$
and (\ref{eq6}) follows immediately from (\ref{eq20}).
%
\section{Computation of $M_1$ and $M_2$}
We begin with $M_1$. Rather than restrict $\pi\in\Pi$ we prove that  
if $h:[0,1]\rightarrow \reals_+$ is log-concave then
\begin{equation}
\label{v1}
\int_{s=0}^{\xi}\int_{t=\xi}^1(t-s)h(s)h(t)dtds\leq{h(\xi)\over  
8}\int_{s=0}^1h(s)ds.
\end{equation}
This will prove $M_1\leq 1/8$ which is what we want. We then note  
that $h=1$ satisfies (\ref{v1}) with equality.

Since $\log h$ is concave there exists $\a\in\reals$ such that
\begin{equation}
\label{v2}
 h(s)\leq h(\xi)e^{\a(s-\xi)},\hspace{1in}s\in[0,1].
\end{equation}
Our aim first is to show that the extremal $h$ satisfies (\ref{v2})  
with equality for all $s\in[0,1]$, for some $\a$.
Let
$$I_0=\int_{s=0}^{\xi}h(s)ds\mbox{ and }I_1=\int_{s=\xi}^{1}h(s)ds,$$
$$J_0=\int_{s=0}^{\xi}(\xi-s)h(s)ds\mbox{ and  
}J_1=\int_{t=\xi}^{1}(t-\xi)h(t)dt.$$
Then (\ref{v1}) is equivalent to
$${I_0J_1+I_1J_0\over I_0+I_1}\leq {h(\xi)\over 8}$$
or
$$\left({J_1\over I_1}+{J_0\over I_0}\right){1\over  
I_0^{-1}+I_1^{-1}}\leq {h(\xi)\over 8}.$$
Suppose now that we fix $\a$ and also $h(\xi)=\b>0$. Let  
$I_0(\a,\b)=\int_{s=0}^{\xi}\b e^{\a(s-\xi)}$ and let  
$I_1(\a,\b),J_0(\a,\b),J_1(\a,\b)$ be defined analogously. Clearly,  
under these circumstances $I_k\leq I_k(\a,\b)$ for $k=0,1$ and so
\begin{equation}
\label{v3}
{1\over I_0^{-1}+I_1^{-1}}\leq {1\over  
I_0(\a,\b)^{-1}+I_1(\a,\b)^{-1}}.
\end{equation}
We now prove that
\begin{equation}
\label{v4}
{J_k\over I_k}\leq {J_k(\a,\b)\over I_k(\a,\b)}\hspace{1in}k=0,1.
\end{equation}
We prove (\ref{v4}) for $k=1$, the proof for $k=0$ being essentially  
the same. Let $M$ be a positive integer and $\th=(1-\xi)/M$. Let  
$g=\log h$ and let $g_\ell =g(\xi+\ell \th),\ell =0,1,\ldots,M$. The concavity of  
$g$ implies that
\begin{equation}
\label{v5}
g_{\ell +2}-g_{\ell +1}\leq g_{\ell+1} -g_{\ell }\hspace{1in}0\leq \ell <M-2,
\end{equation}
and (\ref{v2}) implies
\begin{equation}
\label{v6}
g_\ell \leq g_0+\a \ell \th\hspace{1.5in}0\leq \ell \leq M.
\end{equation}
Now choose $\eta>0$ small. By choosing $M$ sufficiently large we can  
ensure that
\begin{equation}
\label{v7}
{J_1\over I_1}\leq {\sum_{\ell =0}^M\ell e^{g_\ell }\over  
\sum_{\ell =0}^Me^{g_\ell }}+\eta.
\end{equation}
Denote the RHS of (\ref{v7}) by $\r(g_0,g_1,\ldots,g_M)$.  Since  
$\eta$ is arbitrary, we need only show that subject to  
(\ref{v5}),(\ref{v6}), $\r$ is maximised when $g_\ell =g_0+\a \ell \th$ i.e.
\begin{equation}
\label{v8}
\r(g)\leq {\sum_{\ell =0}^M\ell e^{g_0+\a \ell \th}\over \sum_{\ell =0}^Me^{g_0+\a  
\ell \th}}.
\end{equation}
This is easy to do by backwards induction on
$$k=k(g)=\max\{m:g_\ell =g_0+\a \ell \th,0\leq \ell \leq m\}.$$
The base case $k=M$ is trivial and so assume that (\ref{v8}) holds  
for $k=\k+1$ and assume that $k=\k$. Let
$$\n=g_0+\a\k\th-g_\k>0.$$
Define $\bar{g}$ by
$$\bar{g}_\ell =\left\{
\begin{array}{ll}
g_\ell  & 0\leq \ell <\k \\
g_\ell +\n & \k\leq \ell \leq M
\end{array}
\right.
$$
Note that $\bar{g}$ satisfies (\ref{v5}) and (\ref{v6}) and that  
$k(\bar{g})=\k+1$. Hence our inductive assumption implies that  
$\bar{g}$ satisfies (\ref{v8}). On the other hand if $e^{\n\th}=1+\e$  
and $h_\ell =e^{g_\ell }$ then
\begin{eqnarray*}
\r({\bar{g}})-\r(g) & = & {\sum_{\ell =0}^M\ell h_\ell +\e\sum_{\ell =\k}^M\ell h_\ell \over  
\sum_{\ell =0}^Mh_\ell +\e\sum_{\ell =\k}^Mh_\ell }-{\sum_{\ell =0}^M\ell h_\ell \over  
\sum_{\ell =0}^Mh_\ell } \\
& = &  
{\e\left(\sum_{\ell =0}^{\k-1}h_\ell \sum_{\ell =\k}^M\ell h_\ell -\sum_{\ell =0}^{\k-1}\ell h_\ell 
\sum_{\ell =\k}^Mh_\ell \right)\over  
\left(\sum_{\ell =0}^Mh_\ell +\e\sum_{\ell =\k}^Mh_\ell \right)\sum_{\ell =0}^Mh_\ell } \\
& \geq & 0,
\end{eqnarray*}
since clearly
$${\sum_{\ell =\k}^M\ell h_\ell \over \sum_{\ell =\k}^Mh_\ell }\geq  
\k>{\sum_{\ell =0}^{\k-1}\ell h_\ell \over \sum_{\ell =0}^{\k-1}h_\ell }.$$
We can therefore assume from now on that $h(s)=\b e^{\a(s-\xi)}$ for  
some $\a,\b$. We can in fact assume that $\b=1$ as $\b$ contributes a  
factor of $\b^2$ to both sides of (\ref{v1}).
So now let
\begin{eqnarray*}
\g(\a,\xi) & = &  
{\int_{s=0}^{\xi}\int_{t=\xi}^1(t-s)e^{\a(s+t)}dtds\over  
e^{\a\xi}\int_{s=0}^{1}e^{\a s}ds} \\
& = & {e^{\a}+\xi-\xi e^{\a}-e^{\a(1-\xi)}\over \a(e^{\a}-1)}.
\end{eqnarray*}
We must show that $\g(\a,\xi)\leq 1/8$ for $\a\in\reals$ and  
$\xi\in[0,1]$. Now,
$${\partial\g\over \partial\xi}={1\over \a(e^{\a}-1)}(1-e^{\a}+\a  
e^{\a(1-\xi)})$$
and
$${\partial^2\g\over \partial\xi^2}={1\over \a(e^{\a}-1)}(-\a^2  
e^{\a(1-\xi)})<0.$$
It follows that for fixed $\a$, $\g$ is maximised when
$$\xi=\xi^*={1\over \a}\log \left({\a\over 1-e^{-\a}}\right).$$
Now let
\begin{eqnarray*}
f(\a) & = & \g(\a,\xi^*(\a)) \\
& = & {1\over \a^2}\log \left({e^{\a}-1\over \a}\right)-{1\over  
\a^2}+{1\over \a(e^{\a}-1)}.
\end{eqnarray*}
A simple computation yields
$$\lim_{\a\rightarrow 0}f(\a)={1\over 8}$$
and that $f$ is even i.e. $f(-\a)=f(\a)$ for all $\a\in\reals$.

Next let
$$g(\a)=\a^2f(\a)-{\a^2\over 8}.$$
Then
$$g'(\a)  =  -{e^{2\a}(\a-2)^2+e^{\a}(2\a^2-8)+(\a+2)^2\over  
4\a(e^{\a}-1)^2}$$
By checking that the series expansion of the numerator above  
contains only non-negative coefficients we see that $g'(\a)\leq 0$ for  
$\a\geq 0$. Thus $g(\a)\leq g(0)=0$ for $\a\geq 0$ and since $f$ is  
even this completes the proof that $M_1=1/8$.

For the computation of $M_2$ we need to show
$$\int_{s=0}^{\xi}\int_{t=\xi}^1h(s)h(t)dtds\leq{h(\xi)\over  
4}\int_{s=0}^1h(s)ds.$$
Fixing $h(\xi)=\b$ and assuming (\ref{v2}), this amounts to
$${I_0I_1\over I_0+I_1}\leq {\b\over 4}.$$
Thus we can once again assume that the extremal $h$ satisfies  
(\ref{v2}) and that $\b=1$.

So now let
\begin{eqnarray*}
\z(\a,\xi) & = & {\int_{s=0}^{\xi}\int_{t=\xi}^1e^{\a(s+t)}dtds\over  
e^{\a\xi}\int_{s=0}^{1}e^{\a s}ds} \\
& = & {\int_{s=0}^{\xi}e^{\a s}ds\int_{t=\xi}^1e^{\a t}dt\over  
e^{\a\xi}\int_{s=0}^{1}e^{\a s}ds} \\
& = & {(e^{\a\xi}-1)(e^{\a}-e^{\a\xi})\over \a e^{\a\xi}(e^{\a}-1)}  
\\
& = & {e^{\a}-e^{\a\xi}-e^{\a(1-\xi)}+1\over \a(e^{\a}-1)}.
\end{eqnarray*}
We need to show that $\z(\a,\xi)\leq 1/4$ for $\xi\in[0,1]$.
Now
$${\partial\z\over \partial\xi}={1\over  
(e^{\a}-1)}(e^{\a(1-\xi)}-e^{\a\xi})$$
and
$${\partial^2\z\over \partial\xi^2}=-{\a\over  
(e^{\a}-1)}((e^{\a(1-\xi)}+e^{\a\xi})<0.$$
Thus $\z(\a,\xi)$ is maximised at $\xi=1/2$, independent of $\a$. Now  
let
$$f(\a)=\z(\a,1/2)  =  {(e^{\a/2}-1)^2\over \a(e^{\a}-1)}. $$
Then
$$\lim_{\a\rightarrow 0}f(\a)=1/4$$
and if $g(\a)=\a f(\a)-\a/4$ then
$$g'(\a)=-{(e^{\a/2}-1)^2\over 4(e^{\a/2}+1)^2}\leq 0.$$
This shows that $g(\a)\leq g(0)=0$ for $\a\geq 0$ and $g(\a)\geq  
g(0)$ for $\a\leq 0$ and completes our proof that $M_2=1/4$.
\section{Proof of (\protect\ref{eq7})}
\label{sec6}
Recall assumptions (\ref{A1}) - (\ref{A3}).

We introduce polar coordinates  
$(r,\th=(\th_1,\th_2,\ldots,\th_{n-1}))$ so that
$$z_j=r\sin(\th_j)\prod_{i=1}^{j-1}\cos(\th_i),\hspace{1in}j\in[n].$$
Then
\begin{equation}
\label{n1}
\int_{T\setminus K}\psi(z)^2F(z)dz 
=\int_{\th}\left(\int_{r=R}^{R_1}r^{n-1}\psi(r,\th)^2F(r,\th)dr
\right)J(\th)d\th
\end{equation}
where $r^{n-1}J(\th)$ is the  
Jacobian of the transformation. Similarly,
\begin{equation}
\label{n2}
\int_{B}\psi(z)^2F(z)dz=\int_{\th}\left(\int_{r=0}^{R}r^{n-1}\psi(r,\th) 
^2F(r,\th)dr\right)J(\th)d\th
\end{equation}
and
\begin{equation}
\label{n3}
\int_{T}\card{\nabla\psi}^2F(z)dz=\int_{\th}\left(\int_{r=R}^{R_1(\th 
)}r^{n-1}\card{\nabla\psi}^2F(r,\th)dr\right)J(\th)d\th
\end{equation}
Now consider a fixed $\th$. Let $h(r)=r^{n-1}F(r,\th)$ and  
$g(r)=\psi(r,\th)$. Note that $h$ is log-concave. Let $u$ denote the vector of Euclidean length one  
in the direction $\th$. Then we can write
$$g'(r)=\sum_{j=1}^nu_j\chi_j{\partial\psi\over \partial z_j}$$
where $\chi_j=\chi_j(r)$ is the indicator for ${\partial\psi\over  
\partial z_j}\neq 0$.

We prove, where $R'=R-\ups$,
\begin{lemma}
\label{lemx}
For any real $a,b\geq 1$ such that $(a-1)(b-1)\geq 1$,
\begin{equation}
\label{bag}  
\int_{r=R}^{R_1}g(r)^2h(r)dr\leq a\k_1\int_{r=R'}^Rg(r)^2h(r)dr+\e b\k_2\int_{r=R'}^{R_1}\card{\nabla\psi}^2h(r)dr,
\end{equation}
\end{lemma}
Inequality (\ref{eq7}) follows from (\ref{n1}) - (\ref{bag}). 

{\bf Proof of Lemma \ref{lemx}:}

Let $r\geq R$. 
We have, using the inequalities $g(r)^2\leq a (g(r-\ups ))^2 + b(g(r)-g(r-\ups 
))^2$, and $h(r)\leq \k_1h(r-\ups )$
\begin{equation}
\label{eq100}
\int_{r=R}^{R_1} g(r)^2 h(r) dr \leq a \k_1\int_{R^\prime }^R g(r)^2 h(r)dr
+b\int_{R^\prime }^R (g(r+\ups )-g(r))^2 h(r+\ups )dr. 
\end{equation}
We will bound the second term. To do so, note that for any $\z$ and $\a$, 
\begin{eqnarray}
|g(\z)-g(\a)| & = & |\int_{\lambda =\a}^{\z}g'(\lambda )d\lambda | \nonumber \\
& = & |\int_{\lambda =\a}^{\z}\sum_{j=1}^nu_j\chi_j{\partial\psi\over  
\partial z_j}\sqrt{h(\lambda )/h(\lambda )}d\lambda |. \label{eq8}
\end{eqnarray}
Now using Cauchy Schwarz twice we get
\begin{eqnarray}
|g(\z)-g(\a)| & \leq &  
\int_{\lambda =\a}^{\z}\left(\sum_{j=1}^nu_j^2\chi_j^2h(\lambda )^{-1}\right)^{1/2}  
\left(\sum_{j=1}^n\left({\partial\psi\over \partial  
z_j}\right)^2h(\lambda )\right)^{1/2}d\lambda  \nonumber \\
& \leq & \left(\int_{\lambda =\a}^{\z}
\sum_{j=1}^nu_j^2\chi_j^2h(\lambda )^{-1}d\lambda \right)^{1/2}  
\left(\int_{\lambda =\a}^{\z}\card{\nabla\psi}^2h(\lambda )d\lambda \right)^{1/2}. \label{eq9}
\end{eqnarray}
We wish to apply this to (\ref{eq100}) 
with $\z =r+\ups$ and $\a =r$ where $r\in [R^\prime,R]$.
Then as $\lambda$ runs from $r $ to $r+\ups$, we have $\k_1h(\lambda )
\geq h(r+\ups )$, so we have
$$(g(r+\ups )-g(r))^2h(r+\ups ) \leq \k_1\left(\int_{\lambda =r}^{r+\ups }
\sum_{j=1}^nu_j^2\chi_j^2 d\lambda \right)
\left(\int_{\lambda =r}^{r+\ups }\card{\nabla\psi}^2h(\lambda )d\lambda \right)
.$$


We bound the first term above as in (\ref{bug}) to obtain
$$\int_{\lambda =r}^{r+\ups }
\sum_{j=1}^nu_j^2\chi_j^2 d\lambda  \leq 2\epsilon \left({\ups\over\delta}+\sqrt n\right).$$

So we get 
$$\int_{R^\prime}^R (g(r+\ups )-g(r))^2h(r+\ups )dr \leq 2\epsilon \k_1
\left( {l_0\over \delta }+\sqrt n\right) \int_{R^\prime }^{R_1}\card{\nabla\psi}
     ^2h(\lambda )d\lambda .$$
Plugging this into (\ref{eq100}) we get the lemma.  
\section{Conclusion}
We have given good estimates of the second eigenvalue of the transition matrices of our chains. It would be of great interest if we could replace the $\ell_2$ diameter $d$ by the smaller $\ell_\infty$ diameter.
\begin{thebibliography}{99}

\bibitem{AK}D.Applegate and R.Kannan, {\em Sampling and integration of
log-concave functions}, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (1991) 156-163.
%
\bibitem{AM}W.N.Anderson and T.D.Morley, {\em Eigenvalues of the Laplacian of a
graph}, Linear and Multilinear Algebra 18 (1985) 141-145.
%
\bibitem{DFK}M.E.Dyer, A.M.Frieze and R.Kannan, {\em A random polynomial
time algorithm for approximating the volume of convexbodies}, Journal
of the Association for Computing Machinery 38 , (1991) 1-17. 
%
\bibitem{DKM}M.E.Dyer, R.Kannan and J.Mount, {\em ????}
%
\bibitem{F}J.A.Fill, {\em Eigenvalue bounds on convergence to 
stationarity for nonreversible Markov Chains, with an application
to the exclusion process}, The Annals of Applied Probability, Vol. 1, No. 1
(1991) , pp 62-87.
%
\bibitem{LS1}L.Lov\'asz and M.Simonovits, {\em Mixing rate of Markov
chains, an isoperimetric inequality and computing the volume},
Proceedings of the 31'st Annual IEEE Symposium on Foundations of
Computer Science, (1990) 346-355.
%
\bibitem{LS2}L.Lov\'asz and M.Simonovits, {\em Random walks in a convex
body and an improved volume algorithm}, to appear in Random Structures
and Algorithms.
%
\bibitem{metro}N.Metropolis, Rosenberg, Rosenbluth, Teller and Teller,
{\em Equation of state calculation by fast computing machines}, Journal
of Chemical Physics 21 (1953) pp 1087-1092.
%
\bibitem{M} M. Mihail, {\em Combinatorial aspects of expanders}, Ph.D.
Dissertation, Dept. of Computer Science, Harvard University, (1989).
%
\bibitem{SJ}A. J. Sinclair and M. R. Jerrum, {\em Approximate counting,
uniform generation and rapidly mixing Markov chains}, Information and
Computation {82} (1989), 93-133.
%
\bibitem{Ti}L. Tierney, {\em Exploring posterior distributions using Markov
chains}, To appear in Annals of Statistics.

\end{thebibliography}
\end{document}


let
$$
\begin{array}{lll}
\k_0 & = & {d\over 4\d}(d+2\sqrt{n}\d) \\
\\
\k_1 & = & {18\d\sqrt{n}\over d} \\
\\
\k_2 & = & 9\sqrt{n}(d/2+\d(\sqrt{n}+1))
\end{array}
$$







