\begin{document}

\begin{frontmatter}

\title{Differentiating the entropy of random walks on hyperbolic groups}
\runtitle{Differentiating the entropy of random walks}

\begin{aug}
\alphauthor[A]{\fnms{P.} \snm{Mathieu}\corref{}\ead[label=e1]{pierre.mathieu@cmi.univ-mrs.fr}}
\runauthor{P. Mathieu}
\alphaffiliation{Aix Marseille Universit\'e}
\alphaddress[A]{Aix Marseille Universit\'e\\
CNRS, Centrale Marseille\\
LATP, UMR 7353\\
13453 Marseille\\
France\\
\printead{e1}} 
\end{aug}

\received{\smonth{9} \syear{2012}}
\revised{\smonth{11} \syear{2013}}

\begin{abstract}
We show that the asymptotic entropy of a random walk on a nonelementary
hyperbolic group, with symmetric and bounded increments, is
differentiable and we identify its derivative as a correlation. We also
prove similar results for the rate of escape.
\end{abstract}

\begin{keyword}[class=AMS]
\kwd{60B15}
\kwd{37D40}
\end{keyword}

\begin{keyword}
\kwd{Random walks}
\kwd{rate of escape}
\kwd{entropy}
\kwd{Girsanov}
\kwd{hyperbolic groups}
\end{keyword}

\end{frontmatter}

\section{Introduction}

Let $\Gamma$ be an infinite, countable, discrete group with neutral element
$\mathrm{id}$, and let $\mu$ be a probability measure on $\Gammaamma$.
The entropy of $\mu$ is defined as

\[
H(\mu):=\sum_{x\in\Gammaamma} \bigl(-\lambdaog\mu(x)\bigr) \mu(x).
\]

Note that $H(\mu)$ is nonnegative and may be infinite.

Let $\mu^n$ denote the $n$th convolution power of $\mu$.

We assume that $H(\mu)<\infty$.
It is easy to check that the sequence\break $(H(\mu^n))_{n\in{\mathbb N}}$ is
subadditive so that the following limit does exist:

\begin{equation}
\lambdaabel{eq:0} h(\mu):=\lambdaim_{n\rightarrow\infty}\frac{1} n H\bigl(
\mu^n\bigr).
\end{equation}

The quantity $h(\mu)$ is called the \emph{asymptotic entropy} of
$\mu$.

The notion of asymptotic entropy was introduced by Avez in \cite
{kn:avez} in relation with random walk theory. In \cite{kn:avez2}, Avez
proved that, whenever $h(\mu)=0$, then $\mu$ satisfies the Liouville
property: bounded, $\mu$-harmonic functions are constant.
The converse was proved later; see \cite{kn:derrie} and \cite{kn:kaiver}.

Consider the random walk on $\Gammaamma$ whose increments are distributed
according to~$\mu$. The Liouville property is equivalent to the
triviality of the asymptotic $\sigma$-field of the random walk (its
so-called Poisson boundary); see \cite{kn:derrie} and \cite{kn:kaiver}
again. In more general terms, the entropy plays a central role in the
identification of the Poisson boundary of random walks in many
examples. We refer in particular to~\cite{kn:kaim} for groups with
hyperbolic features. In this latter case, the asymptotic entropy is
also related to the geometry of the harmonic measure through a
``dimension-rate of escape-entropy'' formula; see \cite{kn:bhm2} and the
references quoted therein.

The question of the regularity of $h$ as a function of $\mu$ was raised
by Erschler and Kaimanovich in \cite{kn:EK}, where it is proved
that, still for hyperbolic groups, the asymptotic entropy is
continuous. If we restrict ourselves to measures $\mu$ with fixed
finite support, Ledrappier recently proved in \cite{kn:led2} that
$h$ is Lipschitz continuous. We shall complement the result of
\cite{kn:led2} showing that, for a hyperbolic group $\Gammaamma$ and
restricting ourselves to symmetric measures
$\mu$ with a fixed finite support, the asymptotic entropy is
differentiable (Theorem~\ref{theo:entrop}).

There is an analogy between the definition of $h$ and the definition of
the \emph{rate of escape} of the random walk in some left-invariant
metric. More precisely, it can be proved that $h(\mu)$ coincides with
the rate of escape of the corresponding random walk in the so-called
Green metric; see the definition in Section \ref{sec:defre}. We also give
sufficient conditions on a metric ensuring that the rate of escape is
differentiable (Theorem~\ref{theo:rescp}).

Our approach completely differs from the one in \cite{kn:led2}. We
start with the simple observation that the derivative of the mean
position of a random walk is a correlation; see Section \ref{sec:heu}.
Thus, the natural candidate to be the derivative of the rate of escape
is some asymptotic covariance. These heuristics suggest a close
connection between the differentiability of the rate of escape and the
central limit theorem and explain the statement of Theorem~\ref{theo:rescp}.

As for the entropy, one deduces the differentiability of $h$ and the
value of its derivative from Theorem~\ref{theo:rescp} when choosing the
right metric (namely the Green metric) and observing that fluctuations
of the Green metric are of lower order---a fact that follows from the
``fundamental inequality'' between entropy and rate of escape and which
is true for random walks on nonamenable groups in general; see Section
\ref{sec:entrop}.

The version of the central limit theorem we need is a straightforward
extension of \cite{kn:bjork}. We also rely a lot on the ``Green metric
machinery'' developed in \cite{kn:bhm2}.

Let us emphasize that we do not claim that our results are optimal. It
is quite possible that the entropy and rate of escape are much more
regular that differentiable. It is actually known that the entropy and
rate of escape are analytic on the free group \cite{kn:led1} and that
the rate of escape is analytic for some Fuchsian groups~\cite{kn:HMM}.
One may hope analyticity holds for general hyperbolic groups (although
it does not hold for all groups, see \cite{kn:mm}). Anyway, we believe
the interpretation of the derivative as a correlation is rather
satisfactory, at least from an intuitive point of view. It clarifies
the connection between the regularity of the rate of escape and the
central limit theorem, an observation that seems to be new in our context.

Let us finally mention that the interpretation of the derivative of a
steady state (whatever it may mean) as some kind of correlation is a
well-known idea in theoretical physics or dynamical systems, where it
is sometimes called ``linear response theory'' or
``fluctuation-dissipation theory.'' See \cite{kn:ruelle} and other papers
of the same author.

\section{Definitions and results}
\lambdaabel{sec:defre}

\subsection{Definitions}

Let $\Gamma$ be an infinite, countable, discrete group with neutral
element $\mathrm{id}$.
Let $d$ be a left-invariant proper metric on $\Gamma$. We assume that $\Gamma$
is finitely generated and that $d$ is equivalent to a word metric.

When the context is clear, we may also use the notation $\vert x-y\vert
$ to denote the distance
between $x$ and $y$ and $\vert x\vert=\vert x-\mathrm{id}\vert$.

We define the Gromov product of points $x,y\in\Gamma$ with respect to the
base point $w\in\Gamma$ by

\[
(x,y)_w:=\tfrac{1}2 \bigl(\vert x-w\vert+\vert y-w\vert-\vert x-y
\vert\bigr).
\]

We recall that the distance $d$ is called \emph{hyperbolic} if there
exists a constant $\tau$ such that

\begin{equation}
\lambdaabel{eq:hyper} (x,y)_w\geq\min\bigl\{(x,z)_w,(z,y)_w
\bigr\} -\tau
\end{equation}

for all $x,y,z,w\in\Gammaamma$.

The group $\Gamma$ is called hyperbolic if any (equivalently some) word
metric is hyperbolic.
A hyperbolic group is called \emph{nonelementary} if it is nonamenable
(which turns out to be equivalent to requiring $\Gamma$ is not a finite
extension of~${\mathbb Z}$).

We refer to \cite{kn:gh} for background material on hyperbolic groups.

From now on, we will assume that $\Gamma$ is hyperbolic and nonelementary.

Following \cite{kn:bhm2}, we let ${\cal D}(\Gamma)$ be the set of left-invariant
proper metrics on $\Gamma$ which are both
equivalent to a word metric and hyperbolic.
Note that these last two conditions are not redundant. Indeed there
always exist nonhyperbolic (nongeodesic) metrics
equivalent to any word metric on $\Gammaamma$; see \cite{kn:bhm2},
Proposition~2.3. There may also exist hyperbolic metrics on $\Gamma$ that
are not equivalent to a word metric.

We shall consider the following two compactifications of $\Gamma$.
The \emph{visual \textup{(}Gromov\textup{)} compactification} is obtained by considering
all infinite sequences in $\Gamma$ and identifying two such sequences,
say $(x_n)$ and $(y_n)$, if the Gromov product $(x_n,y_n)_w$ tends to
infinity. The \emph{horo-function \textup{(}Busemann\textup{)} compactification} is constructed
by identifying a point $x\in\Gamma$ with the horo-function $k_x\dvtx \Gamma
\rightarrow{\mathbb R}$, $k_x(y)=\vert y-x\vert-\vert w-x\vert$ and taking
the closure
for the topology of pointwise convergence. By Ascoli's theorem, this is
indeed a compact. The group $\Gamma$ acts by homeomorphisms
on both compactifications. Up to equivariant homeomorphisms, the Gromov
compactification does not depend on the choice of
either the base point $w$ or the choice of $d\in{\cal D}(\Gamma)$. The Busemann
compactification is also independent of the choice
of the base point but not of the choice of the metric. We shall say
that $d$ satisfies \emph{Assumption \textup{(}BA\textup{)}} if, up to equivariant
homeomorphisms, the Gromov and Busemann compactifications coincide.

Assumption (\emph{BA}) is in particular satisfied by the class of metrics
called \emph{Green metrics}. These are constructed as follows.
We call a probability measure $\mu$ on $\Gamma$ ``symmetric'' if $\mu
(x^{-1})=\mu(x)$ for all $x\in\Gamma$.
The support of $\mu$ is the set of $x\in\Gamma$ such that $\mu(x)$ is
not zero.

Let $\mu$ be a probability measure on $\Gamma$. We assume that $\mu$ is
symmetric and
that the support of $\mu$ is finite and generates the whole group $\Gamma$.
The Green function associated to $\mu$ is defined by

\[
G^\mu(x)=\sum_{n=0}^\infty
\mu^n(x),
\]

where $\mu^n$ is the $n$th convolution power of $\mu$.

We assumed that $\Gamma$ is nonamenable. Therefore, the sequence $\mu^n(x)$
exponentially converges to zero so that the series defining $G^\mu$
does converge.
The Green distance between points $x$ and $y$ in $\Gamma$ is then

\begin{equation}
\lambdaabel{eq:green}d_G^\mu(x,y):=\lambdaog G^\mu(\mathrm{id})-\lambdaog
G^\mu\bigl(x^{-1}y\bigr).
\end{equation}

In \cite{kn:bhm2}, we proved that $d_G^\mu$ belongs to ${\cal D}(\Gamma)$.
Observe that $d_G^\mu$ need not be geodesic.
(As a matter of fact, it is not so difficult to deduce that $d_G^\mu$
is equivalent to a word metric from the nonamenability of $\Gamma$.
That $d_G^\mu$ is hyperbolic is equivalent to a certain
multiplicativity property of the Green function $G^\mu$ which is the content
of Ancona's classical---and difficult---theorem; see \cite{kn:anc}
and the proof in \cite{kn:woess}.)

We now give the definition of the \emph{random walk} associated to a
probability measure $\mu$ on $\Gamma$.
Because we will eventually use Radon--Nikodym transforms, it will be
more convenient to work with the canonical
construction on the set of trajectories on $\Gamma$, say $\Omegamega=\Gamma^{\mathbb N}$,
where ${\mathbb N}=\{0,1,\lambdadots\}$.
Given $\omega=(\omega_0,\omega_1,\lambdadots)\in\Omegamega$ and $n\in{\mathbb N}$,
we define the maps
$Z_n$ and $X_n$ from $\Omegamega$ to $\Gamma$ by $Z_n(\omega):=\omega_n$,
and $X_n(\omega):=(Z_{n-1}(\omega))^{-1}Z_n(\omega)$. Thus,
$Z_n(\omega)$ gives the
position of the trajectory $\omega$ at time $n$, while
$X_n(\omega)$ gives its increment also at time $n$.
Following the usual usage in probability theory, we often omit to
indicate that random functions, as $Z_n$ or $X_n$, depend on $\omega$.

We equip $\Omegamega$ with the product $\sigma$-field (i.e., the smallest
$\sigma$-field for which all functions $Z_n$ are measurable).
The law of the random walk with increments distributed like $\mu$ is,
by definition, the unique probability measure on $\Omegamega$
under which $Z_0=\mathrm{id}$ and the random variables $(X_n)_{n\in{\mathbb N}}$ are
independent and distributed like $\mu$. We denote it with ${\mathbb P}^\mu$.
We also use the notation ${\mathbb E}^\mu$ to denote the expectation with
respect to ${\mathbb P}^\mu$. Observe that the law of $Z_n$
under ${\mathbb P}^\mu$ is $\mu^n$.

We recall that, given a probability measure $\mu$ with finite support
and given a left-invariant metric $d\in{\cal D}(\Gamma)$, the \emph{rate of escape}
of $\mu$ in the metric $d$ is defined by

\[
\ell(\mu;d):=\lambdaim_{n\rightarrow\infty}\frac{1} n \sum
_{x\in\Gamma} d(\mathrm{id},x)\mu^n(x)
\]

and the \emph{asymptotic entropy} of $\mu$ is defined by

\[
h(\mu):=\lambdaim_{n\rightarrow\infty}\frac{1} n \sum
_{x\in\Gamma} \bigl(-\lambdaog\mu ^n(x)\bigr) \mu
^n(x).
\]

Kingman's subadditive theorem implies that

\[
\ell(\mu;d)=\lambdaim_{n\rightarrow\infty}\frac{1} n d(\mathrm{id},Z_n)\quad
\mbox{and}\quad h(\mu )=\lambdaim_{n\rightarrow\infty}-\frac{1} n \lambdaog
\mu^n(Z_n),
\]

where both limits hold ${\mathbb P}^\mu$ almost surely as well as in $L^1(\Omega
,{\mathbb P}
^\mu)$.

\subsection{Differentiability of \texorpdfstring{$\ell$}{$ell$} and $h$}

In the sequel, we shall study the derivatives of the rate of escape and
the entropy of probability measures with a fixed finite support.
A subset of $\Gamma$, say $S$, is ``symmetric'' if $x^{-1}\in S$ whenever
$x\in S$.
Let $S$ be a finite symmetric subset of $\Gamma$. We assume that $S$
generates the whole group $\Gamma$.
Let ${\mathcal P}_s(S)$ be the set of symmetric probability measures with support
equal to $S$. Then ${\mathcal P}_s(S)$ naturally identifies with an open
subset of ${\mathbb R}^d$ for some $d$. We use the differentiable structure it
inherits this way.

\emph{Regularity Assumption}: throughout the paper, we shall assume that
the function $\lambda\in[-1,1]\rightarrow\lambdaog\mu_\lambda(a)$ has a derivative
at $\lambda=0$ for all $a\in S$. Equivalently, we may write a first order
expansion of $\lambdaog\mu_\lambda(a)$ as $\lambda$ tends to $0$ in the form

\begin{equation}
\lambdaabel{eq:reg}\lambdaog\mu_\lambda(a)=\lambdaog\mu_0(a)+\lambda\nu (a)+\lambda
o_\lambda(a),
\end{equation}

where $\nu(a)$ is the derivative of the function $\lambda\rightarrow\lambdaog\mu_\lambda(a)$
at $\lambda=0$ and
$o_\lambda(a)$ converges to $0$.

Observe that since $S$ is finite, this is equivalent to requiring $o_\lambda
(a)$ to converge to $0$ uniformly with respect to $a\in S$.
We shall also repeatedly use the fact that $\nu$ is bounded.

We shall use the shorthand notation ${\mathbb P}^\lambda$ (resp., ${\mathbb E}^\lambda$) instead
of ${\mathbb P}^{\mu_\lambda}$ (resp., ${\mathbb E}^{\mu_\lambda}$).

From the condition that $\mu_\lambda$ is a probability measure, one deduces
that we must have

\[
\sum_{a\in S} \nu(a)\mu_0(a)=0.
\]

We define the sequence $M_0=0$ and, for $n\geq1$,

\[
M_n=\sum_{j=1}^n
\nu(X_j).
\]

Note that the random process $(M_n)_{n\in{\mathbb N}}$ is a centered
martingale under ${\mathbb P}^0$.

Let $d\in{\cal D}(\Gamma)$ and assume assumption (\emph{BA}) holds.
We shall see in Proposition~\ref{prop:clt} that the sequence $(\vert
Z_n\vert,M_n)$ satisfies a joint central limit theorem and that the asymptotic
covariance of $\vert Z_n\vert$ and $M_n$ is given by

\begin{equation}
\lambdaabel{eq:cov}\sigma(\nu,\mu_0;d):=\lambdaim_{n\rightarrow
\infty}
\frac{1} n {\mathbb E} ^0\bigl[\vert Z_n\vert M_n\bigr].
\end{equation}

\begin{theo}
\lambdaabel{theo:rescp}
Let $d\in{\cal D}(\Gamma)$ satisfy {(BA)}. Then the function $\lambda\rightarrow
\ell(\mu_\lambda
;d)$ is differentiable and its derivative satisfies

\begin{equation}
\lambdaabel{eq:rescp} \frac{d}{d\lambda}\bigg\vert _{\lambda=0} \ell(
\mu_\lambda;d) = \sigma(\nu,\mu_0;d).
\end{equation}

\end{theo}

\begin{theo}
\lambdaabel{theo:entrop}
The function $\lambda\rightarrow h(\mu_\lambda)$ has a derivative at $\lambda=0$ which satisfies

\begin{equation}
\lambdaabel{eq:entrop} \frac{d}{d\lambda}\bigg\vert _{\lambda=0} h(
\mu_\lambda) = \sigma\bigl(\nu,\mu_0;d_G^0
\bigr),
\end{equation}

where $d_G^\lambda:=d_G^{\mu_\lambda}$ is the Green metric associated to the
probability $\mu_\lambda$.
\end{theo}

In \cite{kn:bhm1}, we showed that the asymptotic entropy coincides with
the rate of escape in the Green metric:

\[
h(\mu)=\ell\bigl(\mu;d_G^\mu\bigr)
\]

for all $\mu\in{\mathcal P}_s(S)$.
Thus, using the result in Theorem~\ref{theo:rescp}, we may reformulate
(\ref{eq:entrop}) as follows:

\[
\lambdaim_{\lambda\rightarrow0}\frac{1}\lambda\bigl( h(\mu_\lambda)-h(
\mu_0)\bigr)=\lambdaim_{\lambda\rightarrow
0}\frac{1}\lambda\bigl( \ell
\bigl(\mu_\lambda;d_G^0\bigr)-\ell\bigl(
\mu_0;d_G^0\bigr)\bigr).
\]

In other words, as far as first-order terms are concerned, the
fluctuations of the Green metric do not contribute to the fluctuations
of the entropy. This turns out to be a quite general statement for
random walks on nonamenable groups; see Section~\ref{sec:entrop}.

\subsection{Heuristics} \lambdaabel{sec:heu}

We give a simple---but not completely rigorous---way to guess why
formula (\ref{eq:rescp})

should hold true. We provide these heuristics in order to clarify the
scheme of the proofs, with the hope that this scheme can be adapted to
other examples of random walks.

To compute the rate of escape, observe that

\begin{equation}
\lambdaabel{eq:gir} {\mathbb E}^\lambda\bigl[\vert Z_n\vert\bigr]={\mathbb E}^0
\Biggl[\vert Z_n\vert\prod_{j=1}^n
\frac
{\mu_\lambda
(X_j)}{\mu_0(X_j)}\Biggr].
\end{equation}

Taking the derivative in (\ref{eq:gir}), we get that

\begin{equation}
\lambdaabel{eq:gir2} \frac{d}{d\lambda}\bigg\vert _{\lambda=0}
{\mathbb E}^\lambda\bigl[\vert Z_n\vert\bigr]={\mathbb E} ^0\Biggl[\vert
Z_n\vert\sum_{j=1}^n
\nu(X_j)\Biggr] ={\mathbb E}^0\bigl[\vert Z_n\vert
M_n\bigr].
\end{equation}

Thus, we see that a reasonable candidate to be the derivative of $\ell
(\mu_\lambda;d)$ is the limit of
$\frac{1} n {\mathbb E}^0[\vert Z_n\vert M_n]$ as $n$ tends to $+\infty$.

Observe, however, that in order to turn this loose argument into a
proof, one needs justify how to exchange the order between the limit in
$n$ and the derivation in $\lambda$.

On the one hand, we shall rely on a quantitative version of the law of
large numbers for $\vert Z_n\vert$ to show that the derivative of
$\ell
(\mu_\lambda;d)$ is well approximated by the limit of the ratio $({\mathbb E}^\lambda
[\vert Z_n\vert]-{\mathbb E}^0[\vert Z_n\vert])/{\lambda n}$ as soon as $\lambda$ tend
to $0+$ and $n$ tend to $+\infty$ in such a way that the product $\lambda n$
tends to $+\infty$, see Lemma~\ref{lem:geoapp}. This follows from the
fact that the function $n\rightarrow{\mathbb E}^\lambda[\vert Z_n\vert]$ is almost
additive, uniformly in $\lambda$.

Thus, it is sufficient to describe the limit of ${\mathbb E}^\lambda[\vert
Z_n\vert
]/\lambda n$ when $\lambda n\rightarrow+\infty$. We will actually choose $\lambda$ and $n$
such that $\lambda\sqrt{n}$ tends to $1$. Then ${\mathbb E}^\lambda[\vert Z_n\vert
]/\lambda
n\sim{\mathbb E}^\lambda[\vert Z_n\vert]/\sqrt n$, which is the scaling of the
central limit theorem.

More precisely, we show a joint C.L.T. for the random vector $(\vert
Z_n\vert,M_n)$ under~${\mathbb P}^0$; see Proposition~\ref{prop:clt}. Let
$\sigma
(\nu,\mu_0;d)$ denote the asymptotic covariance of $\vert Z_n\vert$
and $M_n$.

Consider the Girsanov weight $\prod_{j=1}^n {\mu_\lambda(X_j)}/{\mu_0(X_j)}$
in formula (\ref{eq:gir}).
Up to error terms of smaller order, it coincides with the exponential
(in the sense of martingale theory) of the martingale $(\lambda M_n)_{n\in
{\mathbb N}
}$. With our choice of the scaling between $\lambda$ and $n$, the
asymptotic of
$\lambda M_n\sim M_n/\sqrt n$ is given by the central limit theorem.
Therefore, the limit of the Girsanov weight is of the form
 $e^{M-({1} /{2}){\mathbb E}[M^2]}$ for some Gaussian random variable $M$.
Moreover, provided we can check some integrability conditions, the
joint C.L.T. implies that the limit of
${\mathbb E}^\lambda[\vert Z_n\vert]-n\ell(\mu_0;d)]/\lambda n$
is then of the form ${\mathbb E}[Ze^{M-({1}/ {2}){\mathbb E}[M^2]}]$, where $(Z,M)$
is a Gaussian vector with covariance
${\mathbb E}[ZM]=\sigma(\nu,\mu_0;d)$. The integration by parts formula for
Gaussian laws implies that (for any Gaussian vector)

\[
{\mathbb E}\bigl[Ze^{M-({1}/ 2){\mathbb E}[M^2]}\bigr] ={\mathbb E}[ZM].
\]

The next theorem summarizes the part of this argument we just sketched
that does not explicitly use the hyperbolicity of $\Gamma$.

\begin{theo} \lambdaabel{theo:malliavin}
Let $\Gamma$ be a finitely generated group; $S$ a finite symmetric
generating set; $d$ a left-invariant proper metric on $\Gamma$ and $\lambda\in
[-1,1]\rightarrow\mu_\lambda\in{\mathcal P}_s(S)$ be a curve in ${\mathcal P}_s(S)$
satisfying the
Regularity Assumption. We further assume that:
\begin{longlist}[(ii)]
\item[(i)] the joint central limit theorem holds for the vector $(\vert
Z_n\vert, M_n)$ under ${\mathbb P}^0$ with asymptotic covariance $\sigma$,\vspace*{3pt}

\item[(ii)]

\[
\sup_n \frac{1} n{\mathbb E}^0\bigl[\bigl(\vert
Z_n\vert-n\ell(\mu_0;d)\bigr)^2\bigr]<+
\infty.
\]

Then we have

\[
\lambdaim_{n\rightarrow+\infty,\lambda\rightarrow0} \frac{1}{\lambda n} \bigl({\mathbb E}^\lambda \bigl[\vert
Z_n\vert\bigr]-{\mathbb E}^0\bigl[\vert Z_n\vert\bigr]\bigr)=
\sigma,
\]

along any sequence $\lambda$ such that $\lambdaimsup_{n\rightarrow+\infty} \lambda^2
n<+\infty$.
\end{longlist}
\end{theo}

Theorem~\ref{theo:malliavin} is proved in Section~\ref{sec:malliavin}.

\section{Proofs of Theorems \texorpdfstring{\protect\ref{theo:rescp}}{2.1} and \texorpdfstring{\protect\ref{theo:malliavin}}{2.3}}
\lambdaabel{sec:proof}

The proofs are organized in the following way: in Section \ref
{sec:geometricinput}, we recall some estimates on the mean distance
${\mathbb E}^\mu[\vert Z_n\vert]$ from~\cite{kn:bhm2} and use them to show
that Theorem~\ref{theo:rescp} can be deduced from Theorem~\ref
{theo:malliavin}. In Section~\ref{sec:centrallimittheorems}, we recall
results from \cite{kn:bjork} and show how they imply a slightly
stronger version of the assumptions of Theorem~\ref{theo:malliavin}.
Sections~\ref{sec:geometricinput} and \ref{sec:centrallimittheorems} use
the hyperbolicity of $\Gamma$ in an essential way.

In Section \ref{sec:malliavin}, we prove Theorem~\ref{theo:malliavin}.
Section \ref{sec:malliavin} can be read independently of the preceding ones.

Let $d\in{\cal D}(\Gamma)$ satisfy assumption \emph{(BA)}.
We will show that\break $\lambdaim_{\lambda\rightarrow0}\frac{1}\lambda(\ell(\mu_\lambda;d)-\ell
(\mu
_0;d))$ exists and equals $\sigma(\nu,\mu_0;d)$. In the proof, it will
be convenient to restrict ourselves to positive $\lambda$'s. This is no loss
of generality since $\sigma(\nu,\mu_0;d)$ is linear in $\nu$.

\subsection{Geometric input}
\lambdaabel{sec:geometricinput}

\begin{lm} \lambdaabel{lem:geoapp} Let $\lambda$ tend to $0+$ and $n$ tend to
$+\infty$ in such a way that the product $\lambda n$ tends to $+\infty$. Then

\[
\frac{\ell(\mu_\lambda;d)-\ell(\mu_0;d)}\lambda-\frac{{\mathbb E}^\lambda[\vert
Z_n\vert]-{\mathbb E}
^0[\vert Z_n\vert]}{\lambda n}
\]

tends to $0$.
\end{lm}

\begin{pf}
Let $\mu\in{\mathcal P}_s(S)$.

The triangle inequality implies that the sequence $a(n):={\mathbb E}^\mu
[\vert
Z_n\vert]$ is sub-additive. Therefore, we have $\ell(\mu;d)=\inf_n\frac
{a(n)}n$, and thus

\begin{equation}
\lambdaabel{eq:dev0} {\mathbb E}^\mu\bigl[\vert Z_n\vert\bigr]\geq n\ell (\mu;d)
\end{equation}

for all $n$.

We need a similar upper bound. It will follow from bounds on the
lateral deviation of a trajectory of a random walk. Let us recall some
results from \cite{kn:bhm2}.

In \cite{kn:bhm2}, Proposition~3.8, we showed that, for any $\mu\in
{\mathcal P}
_s(S)$, there exists a constant $\tau_0$ such that for all integers
$m$, $n$, $k$,

\begin{equation}
\lambdaabel{eq:dev2}{\mathbb E}^\mu \bigl[(Z_m,Z_{m+n+k})_{Z_{m+n}}
\bigr]\lambdaeq\tau_0.
\end{equation}

Applying this inequality with $m=0$ and using the fact that ${\mathbb E}^\mu
[\vert Z_{n+k}-Z_n\vert]={\mathbb E}^\mu[\vert Z_k\vert]$, we get that

\begin{equation}
\lambdaabel{eq:eq:dev3} {\mathbb E}^\mu\bigl[\vert Z_n\vert\bigr]+{\mathbb E}
^\mu\bigl[\vert Z_k\vert \bigr]\lambdaeq2\tau_0+
{\mathbb E}^\mu\bigl[\vert Z_{n+k}\vert\bigr].
\end{equation}

Thus, the sequence $b(n):=2\tau_0-{\mathbb E}^\mu[\vert Z_n\vert]$ is also
subadditive. Note that $b(n)/n$ converges to $-\ell(\mu;d)$. As above,
this implies that

\begin{equation}
\lambdaabel{eq:dev4} {\mathbb E}^\mu\bigl[\vert Z_n\vert\bigr]\lambdaeq n\ell (\mu
;d)+2\tau _0
\end{equation}

for all $n$.

Combining (\ref{eq:dev0}) and (\ref{eq:dev4}), we see that we have
proved that

\begin{equation}
\lambdaabel{eq:dev} \bigl\vert{\mathbb E}^\mu\bigl[\vert Z_n\vert\bigr]- n\ell(\mu
;d)\bigr\vert \lambdaeq2\tau_0
\end{equation}

for all $n$.

A close inspection of the proof of (\ref{eq:dev2}) reveals that the
constant $\tau_0$ is locally uniform in ${\mathcal P}_s(S)$ so that we may apply
(\ref{eq:dev}) with the same constant $\tau_0$ to all measures $\mu
_\lambda$
for $\lambda$ in a small enough neighborhood of $0$.
The statement of Lemma~\ref{lem:geoapp} immediately follows.
\end{pf}

Let us choose $\lambda$ tending to $0+$ and $n$ tending to $+\infty$ such
that $\lambda^2n$ tends to $1$.
Thus, Lemma~\ref{lem:geoapp} applies. In order to complete the proof of
Theorem~\ref{theo:rescp},
it only remains to show that

\begin{equation}
\lambdaabel{eq:fond} \lambdaim_{\lambda,n} \frac{{\mathbb E}^\lambda[\vert Z_n\vert]-{\mathbb E}^0[\vert Z_n\vert
]}{\lambda
n}=\sigma(\nu,
\mu_0;d).
\end{equation}

\subsection{Central limit theorems}
\lambdaabel{sec:centrallimittheorems}

In this part of the paper, we recall some results from \cite{kn:bjork}
on the central limit theorem for $\vert Z_n\vert$ and discuss their
extension to a joint C.L.T. for $(\vert Z_n\vert,M_n)$.

Let $d\in{\cal D}(\Gamma)$ satisfy assumption (\emph{BA}).
Let $\mu\in{\mathcal P}_s(S)$ be a finitely supported symmetric probability
measure on $\Gamma$.

Mimicking the situation of the discussion preceding Theorem~\ref
{theo:rescp}, we also let $\nu$ be a real valued function defined on
$S$ and satisfying the centering condition: $\sum_{a\in S} \nu(a)\mu
(a)=0$ and
consider the sequence of random variables $M_0=0$ and, for $n\geq1$,

\[
M_n=\sum_{j=1}^n
\nu(X_j).
\]

\begin{prop}\lambdaabel{prop:clt}
\textup{(i)} The law of the two-dimensional random vector
$( (\vert Z_n\vert-n\ell(\mu;d))/\sqrt{n},M_n/\sqrt{n})$ under ${\mathbb P}
^\mu$
weakly converges as $n$ tends to $+\infty$ to a centered Gaussian law
with some covariance matrix $\Sigma^\mu$.

\textup{(ii)} The covariance matrix of $( (\vert Z_n\vert-n\ell(\mu;d))/\sqrt {n},M_n/\sqrt{n})$ under ${\mathbb P}^\mu$ converges to $\Sigma^\mu$. \\
In particular, the sequence $\frac{1} n {\mathbb E}^\mu[\vert Z_n\vert M_n]$
converges as $n$ tends to $+\infty$ and its limit is the nondiagonal
term of $\Sigma^\mu$.
\end{prop}

\begin{pf}
We recall the following classical version of the martingale central
limit theorem (see \cite{kn:hel}).

\begin{lm} \lambdaabel{lem:clt}
Let $(\zeta_n)_{n\in{\mathbb N}}$ be a square integrable, centered martingale
with respect to a filtration
$({\mathcal F}_n)_{n\in{\mathbb N}}$, with stationary increments.
Assume that

\begin{equation}
\lambdaabel{eq:lind}\frac{1} n \sum_{j=1}^n
{\mathbb E}\bigl[(\zeta _j-\zeta _{j-1})^2\vert{\mathcal
F}_{j-1}\bigr]\rightarrow\sigma^2
\end{equation}

almost surely, where $\sigma^2$ is a deterministic real. Then the law
of $(\frac{1} {\sqrt{n}} \zeta_n)$ weakly converges to a centered
Gaussian law with variance $\sigma^2$.
\end{lm}

\textit{Step} 1:
Following \cite{kn:bjork}, we first prove a version of Proposition~\ref
{prop:clt} where $\vert Z_n\vert-n\ell(\mu;d)$ is replaced by an
appropriate martingale approximation that we denote with $(\chi_n)$.

Let $\partial\Gamma$ the Busemann boundary of $\Gamma$. We recall that the
Gromov product extends to the boundary.

Under ${\mathbb P}^\mu$, almost any trajectory $(Z_n)_{n\in N}$ converges to a
limiting point in $\partial\Gammaamma$, say $Z_\infty$.
This follows from assumption (\emph{BA}) since then $\partial\Gamma$
can be
identified with the Gromov boundary of $\Gamma$ and one knows that random
walk paths almost surely converge in the Gromov compactification of a
hyperbolic group; see \cite{kn:anc} or \cite{kn:kaim}.
The law of $Z_\infty$ is called the ``harmonic measure.'' We denote it
with $\xi^\mu$.

In \cite{kn:bjork}, part 4, it is proved that there exists a bounded
function $u$ on $\partial\Gamma$ such that
the sequence

\[
\chi_n:=k(Z_n)-n\ell(\mu;d)+u(k)-u\bigl(Z_n^{-1}k
\bigr)
\]

is a martingale under ${\mathbb P}^\mu$ for any $k\in\partial\Gamma$.

In the sequel, we shall assume that $k$ is chosen according to the
harmonic measure $\xi^\mu$ and independent of the walk $(Z_n)_{n\in
{\mathbb N}}$.
It then follows that $(\chi_n)_{n\in{\mathbb N}}$ has stationary increments.
It is also proved in Theorem~9 in \cite{kn:bjork} that the Lindeberg
condition (\ref{eq:lind}) is satisfied.

\begin{rmk}
The group $\Gamma$ has a natural action on its boundary. For each $k\in
\partial\Gamma$, the sequence $(Z_n^{-1}k)_{n\in{\mathbb N}}$ is a Markov chain
with values in $\partial\Gamma$ started at $k$. This Markov chain has a
unique invariant probability measure, namely the harmonic measure $\xi
^\mu$. Moreover, the Markov chain $(Z_n^{-1}k)_{n\in{\mathbb N}}$ has nice
mixing properties; see Lemma~4 in \cite{kn:bjork}. By choosing $k$
according to $\xi^\mu$, we are actually considering the chain in a
stationary regime.

We shall not explicitly use these remarks but they lie at the heart of
the proof of the central limit theorem in \cite{kn:bjork}.
\end{rmk}

On the other hand, the sequence $(M_n)_{n\in{\mathbb N}}$ being a sum of
independent bounded and centered random variables, is also a centered
martingale with stationary increments
under ${\mathbb P}^\mu$ satisfying condition (\ref{eq:lind}).

Thus, we deduce from Lemma~\ref{lem:clt} that the law of the vector
$(\chi_n/\sqrt{n},\break M_n/\sqrt{n})$ under ${\mathbb P}^\mu$ converges to a centered
Gaussian vector. Indeed, one may apply Lemma~\ref{lem:clt} to the
martingale $(a\chi_n+bM_n)_{n\in{\mathbb N}}$ for any $a,b\in{\mathbb R}$.

Let $\Sigma^\mu$ be the limit covariance matrix. For $(a,b)\in{\mathbb R}
^2$, we
use the notation $\Sigma^\mu(a,b)$ to denote the value of the quadratic
form associated to $\Sigma^\mu$ evaluated at $(a,b)$.
We observe that since both martingales $(\chi_n)$ and $(M_n)$ have
stationary increments, then $\Sigma^\mu$ is also the covariance (under
${\mathbb P}^\mu$) of the vector $(\chi_n/\sqrt{n},M_n/\sqrt{n})$ for any
$n\geq
1$, that is,

\begin{equation}
\lambdaabel{eq:bd1} \frac{1} n{\mathbb E}^\mu\bigl[(a\chi_n+bM_n)^2
\bigr]=\Sigma^\mu(a,b).
\end{equation}

\textit{Step} 2:
In the above claims, we wish to replace $\chi_n$ by $\vert Z_n\vert
-n\ell(\mu;d)$.
We shall use the following lemma.

\begin{lm}\lambdaabel{lem:shad}
There exists a constant $C$ such that, for all $D$ we have

\begin{equation}
\lambdaabel{eq:bd4} {\mathbb P}^\mu\bigl[(k,Z_n)_{\mathrm{id}}\geq D
\bigr]\lambdaeq C^{-1}e^{-CD}.
\end{equation}

Inequality (\ref{eq:bd4}) holds uniformly in $k\in\partial\Gamma$.
\end{lm}

\begin{pf}
The statement of the lemma actually directly follows from arguments in
\cite{kn:bhm2}.

One may for instance split the event $(k,Z_n)_{\mathrm{id}}\geq D$ into two, say
$A:=((k,Z_n)_{\mathrm{id}}\geq D)\cap((Z_\infty,Z_n)_{\mathrm{id}}\geq\frac{D} 2)$ and
$B:=((k,Z_n)_{\mathrm{id}}\geq D)\cap((Z_\infty,Z_n)_{\mathrm{id}}< \frac{D} 2)$.

Let us show that ${\mathbb P}^\mu[A]+{\mathbb P}^\mu[B]\lambdaeq C^{-1}e^{-CD}$.

In the argument below, $\tau_1$ is a constant that depends on $d$ and
$\mu$ only. We choose $D$ large enough and how large depends only on
the choice of the metric $d$ and the measure $\mu$. In particular, we
assume that $D\geq4\tau$, where $\tau$ is the hyperbolicity constant
from (\ref{eq:hyper}).

Hyperbolicity implies that, on $A$, we also have $(k,Z_\infty
)_{\mathrm{id}}\geq
\frac{D} 2-\tau_1\geq\frac{D} 2$.
We know from \cite{kn:bhm2}, Proposition~3.10, that $\xi^\mu$ satisfies
the doubling condition.
Therefore, the probability that $(k,Z_\infty)_{\mathrm{id}}\geq\frac{D} 2$ can
be compared to the harmonic measure of a ball
of $\partial\Gammaamma$ of radius of order $e^{-C_1 D}$ for some
$C_1$, and since $\xi^\mu$ is Ahlfors regular (see Theorem~1.1 in
\cite
{kn:bhm2}) we get that
${\mathbb P}^\mu[A]\lambdaeq C^{-1}e^{-CD}$.

On the event $B$, we have $(Z_\infty,Z_n)_{\mathrm{id}}< \frac{D} 2$ and $\vert
Z_n\vert\geq D-\tau\geq\frac{3}4 D$. Therefore, the distance between
$Z_n$ and any
quasiruler from $\mathrm{id}$ to $Z_\infty$ is larger than $\frac{D} 4-\tau_1$.
For large enough $D$, this last event has a probability bounded from above
by $C^{-1}e^{-CD}$ for some $C$ as follows from the deviation
inequality in Proposition~3.8 in \cite{kn:bhm2}. Therefore,
${\mathbb P}^\mu[B]\lambdaeq C^{-1}e^{-CD}$.
\end{pf}

Back to the proof of Proposition~\ref{prop:clt},
we observe that $k(x)=\vert x\vert-2(k,x)_{\mathrm{id}}$ for all $k\in\partial
\Gamma
$ and $x\in\Gamma$.
Therefore,

\[
\vert Z_n\vert-n\ell(\mu;d)-\chi _n=2(k,Z_n)_{\mathrm{id}}-
\bigl(u(k)-u\bigl(Z_n^{-1}k\bigr)\bigr).
\]

Using Lemma~\ref{lem:shad} and the fact that $u$ is bounded, we get that

\begin{equation}
\lambdaabel{eq:bd3}{\mathbb P}^\mu\bigl[\bigl\vert\vert Z_n\vert-n\ell (
\mu;d)-\chi_n \bigr\vert\geq D\bigr]\lambdaeq C^{-1}e^{-CD}
\end{equation}

for some constant $C$.

As a by-product of (\ref{eq:bd3}), we get that $\frac{1}{\sqrt{n}}
(\vert Z_n\vert-n\ell(\mu;d)-\chi_n)$ converges to $0$
in probability. Therefore, the two sequences of vectors $( (\vert
Z_n\vert-n\ell(\mu;d))/\sqrt{n},M_n/\sqrt{n})$ and
$( \chi_n/\sqrt{n},M_n/\sqrt{n})$ have the same limit in law. Thus, we
have proved that $( (\vert Z_n\vert-n\ell(\mu;d))/\sqrt {n},M_n/\sqrt {n})$ satisfies the central limit theorem with asymptotic variance
$\Sigma^\mu$.

We also deduce from (\ref{eq:bd3}) that

\begin{equation}
\lambdaabel{eq:bd2}\sup_n {\mathbb E}^\mu\bigl[\bigl(\vert
Z_n\vert -n\ell(\mu;d)-\chi _n\bigr)^2
\bigr]<\infty
\end{equation}

and

\[
\frac{1} n {\mathbb E}^\mu\bigl[\bigl(\vert Z_n\vert-n
\ell(\mu;d)-\chi_n\bigr)^2\bigr]\rightarrow0.
\]

Combining (\ref{eq:bd2}) with (\ref{eq:bd1}), we see that the
covariance matrix of $( (\vert Z_n\vert-n\ell(\mu;d))/\sqrt {n},M_n/\sqrt {n})$ under ${\mathbb P}^\mu$ converges to $\Sigma^\mu$.
Also

\[
\frac{1} n {\mathbb E}^\mu\bigl[\vert Z_n\vert
M_n\bigr]=\frac{1} n {\mathbb E}^\mu\bigl[\bigl(\vert
Z_n\vert-n\ell(\mu;d)\bigr) M_n\bigr]
\]

converges as $n$ tends to $+\infty$ and its limit is the nondiagonal
term of $\Sigma^\mu$.
This concludes the proof of the proposition.
\end{pf}

For further references, we observe that (\ref{eq:bd2}) with (\ref
{eq:bd1}) implies the following.

\begin{lm}\lambdaabel{lem:2ndmoment}
For all $\mu\in{\mathcal P}_s(S)$, we have

\[
\sup_n \frac{1} n{\mathbb E}^\mu\bigl[\bigl(\vert
Z_n\vert-n\ell (\mu;d)\bigr)^2\bigr]<\infty.
\]

\end{lm}

\subsection{Proof of Theorem \texorpdfstring{\protect\ref{theo:malliavin}}{2.3} and (\texorpdfstring{\protect\ref{eq:fond}}{3.6})}
\lambdaabel{sec:malliavin}

Here, $\Gamma$ is any finitely generated group.

We recall that we are assuming the joint central limit theorem for the
vector $(\vert Z_n\vert, M_n)$ under ${\mathbb P}^0$; namely the law of the
two-dimensional random vector
$( (\vert Z_n\vert-n\ell(\mu;d))/\sqrt{n},M_n/\sqrt{n})$ under ${\mathbb P}^0$
weakly converges as $n$ tends to $+\infty$ to a centered Gaussian law
with some covariance matrix $\Sigma$. Let $\sigma$ be the nondiagonal
element of $\Sigma$.

We also assume that

\begin{equation}
\lambdaabel{eq:varass}\sup_n \frac{1} n{\mathbb E}^0
\bigl[\bigl(\vert Z_n\vert-n\ell (\mu _0;d)
\bigr)^2\bigr]<+\infty.
\end{equation}

We wish to prove that

\begin{equation}
\lambdaabel{eq:fond'}\lambdaim_{n\rightarrow+\infty,\lambda
\rightarrow0} \frac{1}{\lambda n} \bigl(
{\mathbb E}^\lambda\bigl[\vert Z_n\vert\bigr]-{\mathbb E}^0\bigl[\vert
Z_n\vert\bigr]\bigr)=\sigma,
\end{equation}

along any sequence $\lambda$ such that $\lambdaimsup_{n\rightarrow+\infty} \lambda^2
n<+\infty$.
Without loss of generality, we may and will assume that $\lambda^2n$
converges to some limit $\alphalpha\ge0$. Then
$\lambda\sim\sqrt{\alphalpha/n}$.

We start dealing with the case $\alphalpha\neq0$.

First, note that

\[
\frac{{\mathbb E}^\lambda[\vert Z_n\vert]-{\mathbb E}^0[\vert
Z_n\vert]}{\lambda n} = \frac{{\mathbb E}^\lambda[\vert Z_n\vert-n\ell(\mu_0;d)]-{\mathbb E}^0[\vert
Z_n\vert
-n\ell(\mu_0;d)]}{\lambda n}.
\]

From the central limit theorem for $\vert Z_n\vert$ under ${\mathbb E}^0$ and
assumption (\ref{eq:varass}), we get that

\[
\frac{{\mathbb E}^0[\vert Z_n\vert-n\ell(\mu_0;d)]}{\lambda n} \sim\frac{{\mathbb E}^0[\vert Z_n\vert-n\ell(\mu_0;d)]}{\sqrt{\alphalpha
}\sqrt {n}}\rightarrow0.
\]

In order to compute the limit of ${\mathbb E}^\lambda[\vert Z_n\vert-n\ell(\mu
_0;d)]/\lambda n$, we write these terms in a form
that is more amenable to the application of the central limit theorem.

We have

\begin{equation}\qquad\qquad
\lambdaabel{eq:fond0} \frac{1}{\lambda n} {\mathbb E}^\lambda\bigl[\vert Z_n
\vert-n\ell(\mu_0;d)\bigr]=\frac{1}{\lambda n} {\mathbb E} ^0
\Biggl[\bigl(\vert Z_n\vert-n\ell(\mu_0;d)\bigr)
\prod_{j=1}^n \frac{\mu_\lambda
(X_j)}{\mu
_0(X_j)}\Biggr].
\end{equation}

Let $a\in S$. Recall that we have a first-order expansion of the
function $\lambda\rightarrow\mu_\lambda(a)$ in the form

\begin{equation}
\lambdaabel{eq:exp1} \lambdaog\frac{\mu_\lambda(a)}{\mu_0(a)}= \lambda\nu(a)+\lambda o_\lambda(a),
\end{equation}

where the function $o_\lambda$ uniformly converges to $0$ as $\lambda$ goes to $0$.

Because $\mu_\lambda$ is a probability for all $\lambda$, it follows from
(\ref
{eq:exp1}) that $\nu$ and $o_\lambda$ must
satisfy the following centering conditions:

\begin{eqnarray}
\lambdaabel{eq:center0} \sum_{a\in S} \nu(a)
\mu_0(a)&=&0\quad\mbox{and }
\\
\lambdaabel{eq:center}  \lambdaim_{\lambda\rightarrow0}\frac{1}\lambda
\sum_{a\in S} \biggl(o_\lambda(a)+\frac\lambda2
\nu^2(a)\biggr)\mu_0(a)&=&0.
\end{eqnarray}

To see why (\ref{eq:center0}) and (\ref{eq:center}) hold, note that
$\sum_{a\in S} \mu_\lambda(a)=1$ for all $\lambda$.
The expansion of $\sum_{a\in S} \mu_\lambda(a)$ in terms of $\lambda$ starts with
$\lambda\sum_{a\in S} \nu(a)\mu_0(a) +\lambda^2\frac{1}\lambda\sum_{a\in S}
(o_\lambda
(a)+\frac\lambda2 \nu^2(a))\mu_0(a)$, the rest being of order smaller than
$\lambda^2$.
Dividing by $\lambda$ and letting $\lambda$ tend to $0$, one gets (\ref
{eq:center0}). Then dividing by $\lambda^2$ and letting $\lambda$ tend to $0$,
one gets (\ref{eq:center}).

Let us rewrite (\ref{eq:fond0}) as

\begin{equation}\qquad\qquad
\lambdaabel{eq:fond1} \frac{1}{\lambda n} {\mathbb E}^\lambda\bigl[\vert Z_n
\vert-n\ell(\mu_0;d)\bigr]=\frac{1}{\lambda n} {\mathbb E} ^0\bigl[
\bigl(\vert Z_n\vert-n\ell(\mu_0;d)\bigr) e^{\lambda M_n-\lambda^2 A_n+ R^\lambda_n}
\bigr],
\end{equation}

where

\[
M_n:=\sum_{j=1}^n
\nu(X_j), \qquad\hspace*{-2pt} A_n:=\frac{1}2\sum
_{j=1}^n \nu^2(X_j) \hspace*{-1pt}\quad\mbox{and}\hspace*{-1pt} \quad R^\lambda_n=\lambda\sum_{j=1}^n
o_\lambda(X_j)+\frac\lambda2\nu^2(X_j).
\]

From the Law of Large Numbers for sums of i.i.d. random variables, it
follows that $\frac{1} n A_n$ almost surely converges
to $\frac{1}2 \sum_{a\in S} \nu^2(a)\mu_0(a)$ and, therefore, $\lambda^2A_n$
converges to $\frac{\alphalpha}2 \sum_{a\in S} \nu^2(a)\mu_0(a)$. We claim
that $R^\lambda_n$ converges to $0$ in probability under ${\mathbb P}^0$.

The argument for this last claim goes as follows. Let $Y^\lambda_j:=\frac{1}\lambda o_\lambda(X_j)+\frac{1} 2\nu^2(X_j)$, so that
$R^\lambda_n=\lambda^2\sum_{j=1}^nY^\lambda_j$.
For a fixed $n$, the random variables $(Y^\lambda_j)_{j=1}^n$ are
independent and equally distributed.
On the one hand, (\ref{eq:center}) implies that ${\mathbb E}^0[Y^\lambda_1]$ tends
to $0$ and, therefore, ${\mathbb E}^0[R^\lambda_n]$ also converges to $0$. On the
other hand, the variance of $Y^\lambda_j$ satisfies $\lambdaim_{\lambda\rightarrow0} \lambda
^2{\mathbb V}
^0[Y^\lambda_1]=0$. (Use the fact that $o_\lambda$ converges to $0$.)
Therefore, the variance of $R^\lambda_n$ is of lower order than
$\lambda^2n$ and tends to $0$. Thus, we get that both the mean and variance
of $R^\lambda_n$ converge to $0$.

We now use the central limit theorem for
$((\vert Z_n\vert-n\ell(\mu_0;d))/\sqrt{n}, M_n/\sqrt{n})$.

Ignoring for a moment that the function we integrate in (\ref
{eq:fond1}) is not bounded, we pass to the limit using the relation $\lambda
^2 n\rightarrow\alphalpha$ and get that

\begin{equation}
\lambdaabel{eq:fond2} \frac{1}{\lambda n} {\mathbb E}^\lambda\bigl[\vert Z_n
\vert-n\ell(\mu_0;d)\bigr] \rightarrow\frac{1}{\sqrt\alphalpha} {\mathbb E}
\bigl[Ze^{\sqrt{\alphalpha}M-(\alphalpha/ 2)\sum
_{a\in S} \nu^2(a)\mu_0(a)}\bigr],
\end{equation}

where $(Z,M)$ is a centered Gaussian vector with variance $\Sigma$.

Observe that the variance of $M_n$ equals $n\sum_{a\in S} \nu^2(a)\mu
_0(a)$ and, therefore,
$\sum_{a\in S} \nu^2(a)\mu_0(a)={\mathbb E}[M^2]$. Thus, the right-hand side
of (\ref{eq:fond2}) equals

\[
\frac{1}{\sqrt\alphalpha}{\mathbb E}\bigl[Ze^{\sqrt{\alphalpha}M-(\alphalpha/2){\mathbb E}
[M^2]}\bigr].
\]

The integration by parts formula for Gaussian laws implies that (for
any Gaussian vector and any $\alphalpha$)

\[
\frac{1}{\sqrt\alphalpha}{\mathbb E}\bigl[Ze^{\sqrt{\alphalpha}M-(\alphalpha/2){\mathbb E}[M^2]}\bigr] ={\mathbb E}[ZM]=\sigma.
\]

Thus, we are done with the proof of Theorem~\ref{theo:rescp} once we
justify that we may indeed pass to the limit in (\ref{eq:fond1}).
In order to do so, it is sufficient to have bounds on the moments of
the functions we integrate.

H\"older's inequality implies that

\begin{eqnarray*}
&&{\mathbb E}^0\biggl[\biggl(\frac{1}{\lambda n}\bigl(\vert Z_n
\vert-n\ell(\mu _0;d)\bigr) e^{\lambda
M_n-\lambda^2 A_n+ R^\lambda_n}\biggr)^{6/5}
\biggr]
\\
&&\qquad\lambdaeq {\mathbb E}^0\biggl[\frac{1}{(\lambda n)^2}\bigl(\vert Z_n
\vert-n\ell(\mu_0;d)\bigr)^2\biggr]^{6/10}
{\mathbb E}^0\bigl[e^{3\lambda M_n-3\lambda^2 A_n+3 R^\lambda_n}\bigr]^{4/10}.
\end{eqnarray*}

We already know from assumption (\ref{eq:varass}) that
$\frac{1}{(\lambda n)^2} {\mathbb E}^0[(\vert Z_n\vert-n\ell(\mu_0;d))^2]$ is
bounded in $n$.
Let us prove that ${\mathbb E}^0[e^{3\lambda M_n-3\lambda^2 A_n+3 R^\lambda_n}]$ is also
bounded in $n$.

Note that there exists a constant $C$ such that

\begin{eqnarray*}
{\mathbb E}^0\bigl[e^{3\lambda M_n-3\lambda^2 A_n+3 R^\lambda_n}\bigr]&\lambdae&{\mathbb E} ^0
\bigl[e^{3\lambda M_n+3
R^\lambda_n}\bigr]
\\
&=&e^{3{\mathbb E}^0[R^\lambda_n]}{\mathbb E}^0\bigl[e^{3\lambda M_n+3 (R^\lambda_n-{\mathbb E}^0[R^\lambda
_n])}\bigr]\\
&\lambdae&
e^C {\mathbb E}^0\bigl[e^{3\lambda M_n+3 (R^\lambda_n-{\mathbb E}^0[R^\lambda_n])}\bigr].
\end{eqnarray*}

(We used the fact that ${\mathbb E}^0[R^\lambda_n]$ is bounded for the last inequality.)

From the independence of the $X_j$'s follows that

\[
{\mathbb E}^0\bigl[e^{3\lambda M_n+3 (R^\lambda_n-{\mathbb E}^0[R^\lambda_n])}\bigr] ={\mathbb E}^0
\bigl[e^{3\lambda\nu(X_1)+3\lambda^2(Y^\lambda_1-{\mathbb E}^0[Y^\lambda_1])}\bigr]^n.
\]

But the random variables $\nu(X_1)+\lambda(Y^\lambda_1-{\mathbb E}^0[Y^\lambda_1])$ are
centered and\break bounded (uniformly in $\lambda$), that is, there exists a
number $M$ such that $\vert\nu(X_1)+\lambda(Y^\lambda_1-{\mathbb E}^0[Y^\lambda
_1])\vert\lambdae
M$ for all $\lambda$ and all trajectory $\omega$. Therefore,\break
${\mathbb E}^0[e^{3\lambda\nu(X_1)+3\lambda^2(Y^\lambda_1-{\mathbb E}^0[Y^\lambda_1])}]^n$ is bounded
whenever $\lambda^2n$ is also bounded. For this last step, we rely on the
following classical lemma; see part 7 of \cite{kn:dob}, for instance.

\begin{lm} \lambdaabel{lem:dobr}
For all $M$ and $K$, there exist constants $C_M$ and $n_0$ s.t. for all
random variable $X$
with $\vert X\vert\lambdae M$ and ${\mathbb E}[X]=0$ and for all $\lambda$ and $n\ge
n_0$ s.t. $\lambda^2n\lambdae K$ then

\[
{\mathbb E}\bigl[e^{\lambda X}\bigr]^n\lambdae e^{C_M}.
\]

\end{lm}

\begin{pf}
Since $X$ is bounded, the log-Laplace transform

\[
\Lambda(\lambda):=\lambdaog{\mathbb E}\bigl[e^{\lambda X}\bigr]
\]

is analytic in a neighborhood of $0$.
More precisely, we have:

Let $y\in\mathbb{C}$. Then

\[
\bigl\vert e^y-1-y\bigr\vert\lambdae\bigl\vert e^{\vert y\vert}-1-\vert y\vert\bigr\vert\lambdae
\vert y\vert^2e^{\vert y\vert}.
\]

Apply this to $\lambda X$, $\lambda\in\mathbb{C}$:

\[
\bigl\vert{\mathbb E}\bigl[e^{\lambda X}\bigr]-1\bigr\vert\lambdae\vert\lambda\vert^2M^2e^{\vert\lambda\vert
M}
\lambdae \tfrac{1}2,
\]

if $\vert\lambda\vert\lambdae\lambda_0$.
So $\vert{\mathbb E}[e^{\lambda X}]\vert\ge\frac{1}2$ for $\vert\lambda\vert\lambdae\lambda_0$.
So $\Lambda$ is analytic in $\{\lambda \mbox{ s.t. } \vert\lambda\vert\lambdae\lambda_0\}$ and
$\vert\Lambda(\lambda)\vert\lambdae c_0$ for some constant $c_0$, for all $\lambda$
s.t. $\vert\lambda\vert\lambdae\lambda_0$. Note that
$\lambda_0$ and $c_0$ depend only on $M$.

We have $\Lambda(0)=0$ and $\Lambda'(0)=0$ (because $X$ is centered).
So the function $\lambda^{-2} \Lambda(\lambda)$ is also analytic in $\{\lambda \mbox{ s.t. }
\vert\lambda\vert\lambdae\lambda_0\}$.
By the maximum principle, for any $\lambda$ such that $\vert\lambda\vert\lambdae
\lambda_0$,
we have

\[
\bigl\vert\Lambda(\lambda)\bigr\vert\lambdae C \vert\lambda\vert^2,
\]

where $C=\max_{z; \vert z\vert=\lambda_0}\frac{\Lambda(z)}{z^2}\lambdae
\frac
{c_0}{\lambda_0^2}$.

The statement of the lemma is thus proved with $n_0$ chosen such that
$K/n_0\lambdae\lambda_0^2$ and $C_M=c_0 K/\lambda_0^2$.

This completes the proof of (\ref{eq:fond'}) in the case $\alphalpha\neq0$.

The case $\alphalpha=0$ is easier. As we did in (\ref{eq:fond0}) and
(\ref
{eq:fond1}), we start writing that

\[
\frac{1}{\lambda n} \bigl({\mathbb E}^\lambda\bigl[\vert Z_n\vert\bigr]-
{\mathbb E}^0\bigl[\vert Z_n\vert\bigr]\bigr) =\frac{1}{\lambda n}
{\mathbb E}^0\bigl[\bigl(\vert Z_n\vert-n\ell(
\mu_0;d)\bigr) \bigl(e^{\lambda M_n-\lambda^2
A_n+ R^\lambda_n}-1\bigr)\bigr].
\]

Using similar arguments as for the case $\alphalpha\neq0$, it is not
difficult to show that

\begin{eqnarray*}
&&\lambdaim_{n\rightarrow+\infty,\lambda\rightarrow0,\lambda^2n\rightarrow0}\frac{1}{\lambda n} {\mathbb E}^0\bigl[\bigl(
\vert Z_n\vert-n\ell(\mu_0;d)\bigr) \bigl(e^{\lambda M_n-\lambda^2 A_n+ R^\lambda
_n}-1
\bigr)\bigr]
\\
&&\qquad= \lambdaim_{n\rightarrow+\infty,\lambda\rightarrow0,\lambda^2n\rightarrow0}\frac{1}{\lambda n} {\mathbb E}^0\bigl[\bigl(
\vert Z_n\vert-n\ell(\mu_0;d)\bigr) \lambda M_n
e^{-\lambda^2 A_n+ R^\lambda
_n}\bigr].
\end{eqnarray*}

Observe that

\begin{eqnarray*}
&&\frac{1}{\lambda n} {\mathbb E}^0\bigl[\bigl(\vert Z_n\vert-n
\ell(\mu_0;d)\bigr) \lambda M_n e^{-\lambda^2
A_n+ R^\lambda_n}\bigr] \\
&&\qquad=
\frac{1}{n} {\mathbb E}^0\bigl[\bigl(\vert Z_n\vert-n\ell(
\mu_0;d)\bigr) M_n e^{-\lambda^2 A_n+
R^\lambda_n}\bigr].
\end{eqnarray*}

The limit of this last expression is given by the central limit theorem
and, with the notation we already used, it coincides with ${\mathbb E}
[ZM]=\sigma$. Observe that,
with our scaling satisfying $\lambda^2n\rightarrow0$, we have $\lambda^2 A_n\rightarrow0$.
The details are similar to the case $\alphalpha\neq0$.
\end{pf}

\begin{pf*}{End of the proof of Theorem~\ref{theo:rescp}}
Proposition~\ref{prop:clt} and Lemma~\ref{lem:2ndmoment} from Section
\ref
{sec:centrallimittheorems} show that the assumptions of Theorem~\ref
{theo:malliavin} are satisfied. Thus, we get that

\[
\lambdaim_{n\rightarrow+\infty,\lambda\rightarrow0, \lambda^2n\rightarrow1} \frac{1}{\lambda n} \bigl({\mathbb E} ^\lambda \bigl[\vert
Z_n\vert\bigr]-{\mathbb E}^0\bigl[\vert Z_n\vert\bigr]\bigr) =
\sigma(\nu,\mu_0;d).
\]

But we observed in Section \ref{sec:geometricinput} that this convergence
implies Theorem~\ref{theo:rescp}.
\end{pf*}

\section{Proof of Theorem \texorpdfstring{\protect\ref{theo:entrop}}{2.2}}
\lambdaabel{sec:entrop}

We now explain how to deduce Theorem~\ref{theo:entrop} from Theorem~\ref
{theo:rescp}.

As in the proof of Theorem~\ref{theo:rescp}, we may and will restrict
ourselves to positive~$\lambda$'s.

We first recall that the entropy can be interpreted as a rate of escape
in the Green metric: $h(\mu)=\ell(\mu;d_G^\mu)$.
Thus, we have

\begin{equation}
\lambdaabel{eq:entrop1} h(\mu_\lambda)-h(\mu_0)= \bigl(h(
\mu_\lambda)-\ell\bigl(\mu_\lambda;d_G^0
\bigr) \bigr) + \bigl(\ell\bigl(\mu _\lambda;d_G^0
\bigr)-\ell\bigl(\mu_0;d_G^0\bigr) \bigr).
\end{equation}

By Theorem~\ref{theo:rescp} and since $d_G^0$ satisfies (\emph{BA}), once
divided by $\lambda$, the second term in~(\ref{eq:entrop1}) converges to
$\sigma(\nu,\mu_0;d_G^0)$. Thus, the proof of Theorem~\ref{theo:entrop}
will be complete once we prove that

\begin{equation}
\lambdaabel{eq:entroptrop} \lambdaim_{\lambda\rightarrow0+} \frac{1} \lambda \bigl(h(
\mu_\lambda)-\ell\bigl(\mu_\lambda;d_G^0
\bigr) \bigr)=0.
\end{equation}

It turns out the estimate (\ref{eq:entroptrop}) does not use the
hyperbolicity of $\Gamma$. We have the following more general property.

\begin{prop} \lambdaabel{prop:prop}
Let $\Gamma$ be a finitely generated group. Assume $\Gamma$ is nonamenable.
Let $\mu_0$ be a probability measure on $\Gamma$ such that
the support of $\mu_0$ generates $\Gamma$ (as a semigroup), and
$H(\mu_0)<\infty$.

Consider a curve of probability measures on $\Gamma$, say $\lambda\in
[-1,1]\rightarrow\mu
_\lambda$, satisfying the Regularity Assumption:

\[
\lambdaog\mu_\lambda(a)=\lambdaog\mu_0(a)+\lambda\nu(a)+\lambda
o_\lambda(a),
\]

where
$\nu$ is bounded and
$o_\lambda(a)$ converges to $0$ uniformly in $a\in\Gamma$.

Then

\[
\lambdaim_{\lambda\rightarrow0+} \frac{1} \lambda \bigl(h(\mu_\lambda)-\ell
\bigl(\mu_\lambda;d_G^0\bigr) \bigr)=0.
\]

\end{prop}

\begin{rmk}
We do not assume any more that $\mu_0$ or the $\mu_\lambda$'s are symmetric.
Then the Green metric may not be a real distance. Indeed, although it
still satisfies the triangle inequality, it may not be symmetric.

Thus, in this part of the paper, the word ``metric'' will refer to a
function on $\Gamma\times\Gammaamma$ that vanishes on the diagonal and
satisfies the triangle inequality.

The interpretation of the asymptotic entropy as the rate of escape in
the Green metric remains valid in this general framework; see \cite{kn:bhm1}.
\end{rmk}

\begin{rmk}
The assumption that $H(\mu_0)<\infty$ implies that $\mu_0$ has a finite
first moment with respect to $d_G^0$
(see Lemma~2.3 in \cite{kn:bhm1}).
The Regularity Assumption then implies that $H(\mu_\lambda)<\infty$ and that
$\mu_\lambda$ also has a finite first moment with respect to $d_G^0$.
\end{rmk}

\begin{pf*}{Proof of Proposition \ref{prop:prop}}
We give two separate arguments for lower and upper bounds for $h(\mu
_\lambda
)-\ell(\mu_\lambda;d_G^0)$. Both arguments are based on the so-called
``fundamental inequality'' that we first recall:
let $\mu$ be a probability measure on $\Gamma$ with finite entropy and let
$d$ a left-invariant proper metric on $\Gamma$. We denote with ${\mbox v}(d)$
the logarithmic volume growth of the metric $d$.
The ``fundamental inequality'' states that $h(\mu)\lambdaeq{\mbox v}(d) \ell
(\mu;d)$; see \cite{kn:guiv,kn:versh,kn:bhm1} and the
references quoted therein.

The ``fundamental inequality'' in particular applies to any Green
metrics $d_G^\alpha$. By a result in \cite{kn:bhm1}, we have ${\mbox
v}(d_G^\alpha)=1$. Therefore, we get that

\begin{equation}
\lambdaabel{eq:ineqfund} h(\mu_\lambda)=\ell\bigl(\mu_\lambda;d_G^\lambda
\bigr)\lambdaeq\ell\bigl(\mu_\lambda;d_G^\alpha\bigr)
\end{equation}

for all $\lambda$ and $\alpha$.

Applying (\ref{eq:ineqfund}) with $\alphalpha=0$, yields $h(\mu_\lambda)\lambdaeq
\ell(\mu_\lambda;d_G^0)$ and, therefore,

\begin{equation}
\lambdaabel{eq:entropup} \lambdaimsup_{\lambda\rightarrow0+} \frac{1} \lambda \bigl(h(
\mu_\lambda)-\ell\bigl(\mu_\lambda;d_G^0
\bigr) \bigr)\lambdaeq 0.
\end{equation}

It remains to prove the lower bound. We first need review properties of
the Green metric.
Consider a probability measure $\mu$ with finite entropy and whose
support generates the whole group $\Gammaamma$.
We recall that we defined the Green metric as

\[
d_G^\mu(x,y):=\lambdaog G^\mu(\mathrm{id})-\lambdaog
G^\mu\bigl(x^{-1}y\bigr),
\]

where $G^\mu(x)=\sum_{n=0}^\infty\mu^n(x) $ is the Green function of
the random walk.

We may equivalently express $d_G^\mu$ in terms of the hitting
probabilities of the random walk:
for a given trajectory $\omega\in\Omegamega$ and $z\in\Gamma$, let

\[
T_z(\omega)=\inf\bigl\{n\geq0; Z_n(\omega)=z\bigr\}
\]

be the hitting time of $z$ by $\omega$. Observe that $T_z(\omega)$
may be infinite.

Define $F^\mu(z):={\mathbb P}^\mu[T_z<\infty]$. Then

\[
d_G^\mu(\mathrm{id},z)=-\lambdaog F^\mu(z)
\]

as can be easily checked using the Markov property.

In the sequel, we use the notation $F^\lambda$ instead of $F^{\mu_\lambda}$.

\begin{lm}\lambdaabel{lm:ub}
The function $(\lambda,\alpha)\rightarrow\ell(\mu_\lambda;d_G^\alpha)$ is bounded on $[0,1]^2$:

\[
\sup_{0\lambdaeq\lambda\lambdaeq1; 0\lambdaeq\alpha\lambdaeq1}\ell\bigl(\mu_\lambda;d_G^\alpha
\bigr)<\infty.
\]

\end{lm}

 \begin{pf}
Let $\mu$ and $\mu'$ be probability measures on $\Gamma$ and let $d$ be a
proper left-invariant metric on $\Gamma$.
It is clear that

\[
\ell(\mu;d)\lambdaeq\sum_{a\in\Gamma} d(\mathrm{id},a) \mu(a).
\]

Also $F^{\mu'}(a)\geq\mu'(a)$ and, therefore, $d_G^{\mu'}(\mathrm{id},a)\lambdaeq
-\lambdaog\mu'(a)$.

Applying these two inequalities to $\mu=\mu_\lambda$ and $\mu'=\mu
_\alphalpha$,
we get that

\begin{eqnarray*}
\ell\bigl(\mu_\lambda;d_G^\alphalpha\bigr)&\lambdaeq&-\sum
_{a\in\Gamma}\bigl(\lambdaog\mu_\alphalpha (a)\bigr)
\mu_\lambda (a)
\\
&=&-\sum_{a\in\Gamma}\bigl(\lambdaog\mu_0(a)+\alphalpha
\nu(a)+\alphalpha o_\alphalpha (a)\bigr)\mu_\lambda (a).
\end{eqnarray*}

Since $\nu$ and $o_\lambda$ are bounded, we have $\mu_\lambda(a)\lambdaeq e^C\mu_0(a)$
for some constant $C$.
For the same reason, the term $\sum_{a\in\Gamma}(\alphalpha\nu(a)+\alphalpha
o_\alphalpha(a))\mu_\lambda(a)$ is also controlled by a constant.
Therefore,

\[
\ell\bigl(\mu_\lambda;d_G^\alphalpha\bigr)\lambdaeq
e^CH(\mu_0)+C
\]

for some constant $C$.
\end{pf}

We shall need the following estimate on $T_z$.

\begin{lm}\lambdaabel{lm:tau}
Let $\mu$ be a probability measure on $\Gammaamma$ whose support
generates~$\Gammaamma$.
Then there exists a positive constant
$\kappa$
such that

\[
\sup_{z\in\Gamma} {\mathbb E}^\mu\bigl[e^{\kappa T_z};
T_z<\infty\bigr]<\infty.
\]

\end{lm}

\begin{pf}
We use the nonamenability of $\Gamma$: there exists a constant $\rho<1$
such that, for all $n$ and all $z\in\Gamma$, we have
$\mu^n(z)\lambdaeq\rho^n$. Therefore,

\begin{eqnarray*}
{\mathbb E}^\mu\bigl[e^{\kappa T_z}; T_z<\infty\bigr] &=&
\sum_n e^{\kappa n} {\mathbb P}^\mu[T_z=n]
\\
&\lambdaeq& \sum_n e^{\kappa n}
{\mathbb P}^\mu[Z_n=z]=\sum_n
e^{\kappa n} \mu ^n(z)
\\
&\lambdaeq& \sum_n e^{\kappa n}
\rho^n<\infty
\end{eqnarray*}

as soon as $e^\kappa\rho<1$.
\end{pf}

\begin{pf*}{End of the proof of Proposition~\ref{prop:prop}: The lower bound}
We use the shorthand notation $F^\lambda(z):=F^{\mu_\lambda}(z)$.

As in (\ref{eq:fond0}), we have

\[
F^\lambda(z)={\mathbb E}^0\Biggl[\prod_{j=1}^{T_z}
\frac{\mu_\lambda(X_j)}{\mu_0(X_j)}; T_z<\infty\Biggr].
\]

Let us apply H\"older's inequality with positive parameters $(p,q,r)$
such that $1/p+1/q+1/r=1$ and with the notation
$\alpha=\lambda q$. We assume that $\alpha\lambdaeq1$. Thus,

\begin{eqnarray}
\lambdaabel{eq:f1} F^\lambda(z)&\lambdaeq& F^0(z)^{1/p}
F^\alpha(z)^{1/q}
\nonumber
\\[-8pt]
\\[-8pt]
\nonumber
&&{}\times {\mathbb E}^0\Biggl[ \Biggl(
\prod_{j=1}^{T_z} \frac{\mu_\lambda(X_j)}{\mu
_0(X_j)}\biggl(\frac{\mu
_0(X_j)}{\mu_\alpha(X_j)}
\biggr)^{1/q} \Biggr)^r; T_z<\infty
\Biggr]^{1/r}.
\end{eqnarray}

Let $a\in S$.
Using the Regularity Assumption and the relation $\alpha=\lambda q$, we get

\[
\frac{\mu_\lambda(a)}{\mu_0(a)}\biggl(\frac{\mu_0(a)}{\mu_\alpha(a)}\biggr)^{1/q}
=e^{\lambda(o_\lambda(a)-o_\alpha(a))}.
\]

Therefore, since $\lambda\lambdaeq\alpha\lambdaeq1$,
and remembering that $o_\lambda$ uniformly converges to $0$, we see that for
all ${\mathbb V}epsilon>0$, provided $\alpha$ is small enough then

\begin{equation}
\lambdaabel{eq:f2} \frac{\mu_\lambda(a)}{\mu_0(a)}\biggl(\frac
{\mu
_0(a)}{\mu_\alpha(a)}\biggr)^{1/q}
\lambdaeq\exp({\mathbb V}epsilon\lambda).
\end{equation}

Using (\ref{eq:f2}) in equation (\ref{eq:f1}), we see that

\[
F^\lambda(z)\lambdaeq F^0(z)^{1/p} F^\alpha(z)^{1/q}
{\mathbb E}^0\bigl[e^{{\mathbb V}epsilon\lambda rT_z}; T_z<\infty\bigr].
\]

If we further assume that ${\mathbb V}epsilon\lambda r\lambdaeq\kappa^0$, where $\kappa^0$ is
the constant given by Lemma~\ref{lm:tau} when choosing $\mu=\mu_0$,
then we have

\begin{equation}
\lambdaabel{eq:f3} F^\lambda(z)\lambdaeq C F^0(z)^{1/p}
F^\alpha(z)^{1/q}
\end{equation}

for a new constant $C$ that does not depend on $z$.

We evaluate inequality (\ref{eq:f3}) at $z=Z_n$; take the logarithm and
take the expectation with respect to ${\mathbb P}^\lambda$ to obtain

\[
{\mathbb E}^\lambda\bigl[d_G^\lambda(\mathrm{id},Z_n)
\bigr]\geq\frac{1} p {\mathbb E}^\lambda\bigl[d_G^0(\mathrm{id},Z_n)
\bigr]+\frac{1} q {\mathbb E}^\lambda\bigl[d_G^\alpha(\mathrm{id},Z_n)
\bigr]-\lambdaog C.
\]

Now divide by $n$ and let $n$ tend to $\infty$, to get that

\begin{equation}
\lambdaabel{eq:f4} h(\mu_\lambda)=\ell\bigl(\mu_\lambda;d_G^\lambda
\bigr)\geq\frac{1} p \ell\bigl(\mu_\lambda;d_G^0
\bigr)+\frac{1} q \ell\bigl(\mu_\lambda;d_G^\alpha
\bigr).
\end{equation}

We choose $r=\kappa^0/({\mathbb V}epsilon\lambda)$ and $\lambda$ small enough so that
$1/r+1/q<1$. Then (\ref{eq:f4}) becomes

\begin{equation}
\lambdaabel{eq:f5} h(\mu_\lambda)-\ell\bigl(\mu_\lambda;d_G^0
\bigr) \geq\frac\lambda\alpha \bigl(\ell\bigl(\mu_\lambda;d_G^\alpha
\bigr)-\ell\bigl(\mu_\lambda;d_G^0\bigr) \bigr)-
\frac
{{\mathbb V}epsilon\lambda}{\kappa^0} \ell\bigl(\mu_\lambda;d_G^0
\bigr).
\end{equation}

We let $\lambda$ tend to $0$ in (\ref{eq:f5}): by Lemma~\ref{lm:ub}, we
know that

\[
\lambda \bigl(\ell\bigl(\mu_\lambda;d_G^\alpha\bigr)-\ell
\bigl(\mu_\lambda;d_G^0\bigr) \bigr)\rightarrow0
\]

and $\lambda\ell(\mu_\lambda;d_G^0)\rightarrow0$. Therefore,

\begin{equation}
\lambdaabel{eq:f55} \lambdaiminf_{\lambda\rightarrow0+} \bigl(h(\mu_\lambda)-\ell
\bigl(\mu_\lambda;d_G^0\bigr) \bigr)\geq 0.
\end{equation}

Using the inequality $\ell(\mu_\lambda;d_G^\alpha)\geq h(\mu_\lambda)$ (which comes
from the ``fundamental inequality''), we deduce from (\ref{eq:f5}) that

\begin{equation}
\lambdaabel{eq:f56} \frac{1}\lambda{ \bigl(h(\mu_\lambda)-\ell\bigl(
\mu_\lambda;d_G^0\bigr) \bigr)} \geq
\frac{1}\alpha \bigl(h(\mu_\lambda)-\ell\bigl(\mu_\lambda;d_G^0
\bigr) \bigr)-\frac
{{\mathbb V}epsilon}{\kappa
^0} \ell\bigl(\mu_\lambda;d_G^0
\bigr).
\end{equation}

It follows from Lemma~\ref{lm:ub} that there exists a constant $\ell_0$
such that\break
$\frac{1}{\kappa^0} \ell(\mu_\lambda;d_G^0)\lambdaeq\ell_0$ for all $\lambda$.
By (\ref{eq:f55}), the term $h(\mu_\lambda)-\ell(\mu_\lambda;d_G^0)$ has a
nonnegative $\lambdaiminf$. Thus, we deduce from (\ref{eq:f56}) that

\begin{equation}
\lambdaabel{eq:f7} \lambdaiminf_{\lambda\rightarrow0+} \frac{1}\lambda \bigl(h(
\mu_\lambda)-\ell\bigl(\mu_\lambda;d_G^0
\bigr) \bigr)\geq -{\mathbb V}epsilon\ell_0.
\end{equation}

And since (\ref{eq:f7}) holds for any small enough ${\mathbb V}epsilon$, we have

\begin{equation}
\lambdaabel{eq:entropdown} \lambdaiminf_{\lambda\rightarrow0+} \frac{1}\lambda \bigl(h(
\mu_\lambda)-\ell\bigl(\mu_\lambda;d_G^0
\bigr) \bigr)\geq 0.
\end{equation}

\upqed\end{pf*}
\noqed\end{pf*}

\begin{rmk}
F. Ledrappier and L. Shu recently adapted our strategy in a continuous setting:
using martingales as here, they obtained differentiability results for
the entropy and rate of escape
of Brownian motions on the universal cover of negatively curved manifolds;
see \url{http://front.math.ucdavis.edu/1309.5182}.
\end{rmk}

\printaddresses

\end{document}