MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking for a reference for an inequality related to the "fundamental inequality" about entropy and rate of escape of random walks (on the Cayley graph of a group). Namely,

$\textbf{Question}$: Under which conditions (on the measure $P$), do the following inequalities hold: $$ l_P^2 \leq h_P \leq v l_P. $$

The second inequality (called "fundamental", due to Vershik and/or Guivarc'h, I have unfortunately no access to any of these paper) is valid for a large class of measures, but my concern is about the first one.

The above quantities are defined by: $$ H_{n,P} = -\sum_{g \in G} P^{(n)}(g) \ln P^{(n)}(g), \qquad \text{and } \qquad L_{n,P} = \sum_{g \in G} |g| P^{(n)}(g) $$ where $P^{(n)}$ is the convolution of $P$ with itself $n$ times [EDIT:and $|g|$ is the word length of $g$ for the generating set of the Cayley graph]. Then define the [asympotic] entropy, the rate of escape (or drift, or Green speed) and the exponential volume growth to be $$ h_P = \lim_{n \to \infty} \tfrac{1}{n} H_{n,P}, \qquad l_P = \lim_{n \to \infty} \tfrac{1}{n} L_{n,P}, \qquad \text{and } v = \lim_{n \to \infty} \tfrac{1}{n} \log |B_n| $$ where $|B_n|$ is the cardinality of the ball of radius $n$ around the identity.

PS: If I understood correctly, a paper of Blachère, Haïssinsky and Mathieu shows that (if $\sum_{g \in G} P^{(1)}(g) \ln P^{(1)}(g)$ is finite) $l_P=0$ is equivalent to $h_P=0$. This would be a consequence of the above inequalities, so I assume they are not too trivial in this generality.

share|cite|improve this question
In the formula for $L_{n,P}$, what is $|g|$? – Vaughn Climenhaga Apr 29 '13 at 16:54
$|g|$=word length, right. So that $L_{n,P}$ is the expected distance from the origin in terms of the generators after $n$ steps. Since it grows sublinearly, $l_P$ exists. – Anthony Quas Apr 29 '13 at 17:38
up vote 1 down vote accepted

You got all the references and some of the notions you mention wrong. First about the "fundamental inequality". It was first obtained by Guivarc'h in late 70s (although in a somewhat different form), however, by mid-80s it was obvious to all specialists in the area (in particular, for technically more involved Brownian motion on covering manifolds it appears in the work of Ledrappier and Kaimanovich), so that when Vershik called it "fundamental" in 2000 he was really reinventing the wheel. The point is that this inequality immediately follows from the Shannon equidistribution property for the entropy of convolution powers (for instance, by the Kingman subadditive theorem). By the way, it is completely wrong to call the rate of escape the "Green speed". If you want to use this terminology, then the "Green speed" is the rate of escape for a very particular distance on the group determined by the Green kernel (it was introduced by Brofferio), and it coincides with the asymptotic entropy as it is proved in the paper by Blachère, Haïssinsky and Mathieu you are apparently quoting.

Now, in what concerns the first inequality, first of all its scope is more restricted than that of the second one. Indeed, the second one makes sense for any measure with a finite first moment (which implies finiteness of entropy - not the other way round as you claim), whereas any random walk with a non-trivial drift on $\mathbb Z$ provides an obvious counterexample to the first one. As it was proved by Karlsson and Ledrappier in 2006 or 2007, this is actually the only obstacle to equivalence of $h=0$ and $l=0$. In particular, for symmetric measures with a finite first moment $h=0 \iff l=0$ (it is completely wrong to attribute this result to Blachère, Haïssinsky and Mathieu).

In the form you formulate the first inequality ($h\ge l^2$), as far as I know it was established only for Brownian motion on cocompact manifolds (by Kaimanovich and Ledrappier). For symmetric random walks on groups with an additional multiplicative constant it was recently proved by Erschler and Karlsson.

share|cite|improve this answer
Thanks for the clarifications. – Antoine Apr 30 '13 at 0:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.