For a (symmetric) random walks on countable groups generated by $\mu$, there is a "brute-force computation" argument of Avez (1974) that shows that if the entropy $h_\mu$ is trivial then there are no non-constant $\mu$-harmonic functions on the group. [Definitions are below.]

Given it is fairly easy to show that zero speed implies zero entropy (the converse is also true but requires the Gaussian estimates from Varopoulos/Carne)...

$\textbf{Question:}$ is there a simpler "brute-force" way of seeing that zero speed implies the absence of non-constant $\mu$-harmonic functions?


$\cdot$ A random walk on group $G$ is generated by $\mu$ symmetric (i.e. $\mu(g)= \mu(g^{-1})$) and finitely supported if the kernel of the Markov chain is $K(g,h) = \mu(g^{-1}h)$. In other words, the law of the $n^{\text{th}}$-step distribution is $\mu^{*n} = \mu*\mu*\cdots*\mu$ (convolution with $n$ appearances of $\mu$).

$\cdot$ $f$ is said $\mu$-harmonic if $f*\mu = f$.

$\cdot$ The entropy $h_\mu$ is defined as $\lim_{n \to \infty} \frac{1}{n} H_{n,\mu}$ and $H_{n,\mu} = - \sum_{g \in G} \mu^{*n}(g) \ln \mu^{*n}(g)$. Subadditivity of $n \mapsto H_{n,\mu}$ ensures the existence of the limit.

$\cdot$ The speed $l_\mu$ is defined as $\lim_{n \to \infty} \frac{1}{n} L_{n,\mu}$ and $L_{n,\mu} = \sum_{g \in G} \mu^{*n}(g) |g|$ (where $|g|$ is the word length for some fixed generating set). Subadditivity ensures the existence of the limit again.


2 Answers 2


Here is an alternative simple proof (without any entropy) of non-Liouville $\Rightarrow$ positive speed using some of the theory of the Martin boundary/positive harmonic functions. It's quite high-level so not really what you're looking for, but is too long for a comment.

Let $G$ be a transient graph with associated simple random walk transition probabilities $p(x,y)$ and let $\rho$ be a fixed root vertex. The Martin kernel of a vertex $v$ is defined to be \begin{equation} M_v(u) = \frac{\mathbb{E}_u[\text{visits to }v]}{\mathbb{E}_\rho[\text{visits to }v]}.\end{equation} Some standard results from the Martin boundary theory (see e.g. Woess): If there are non-constant bounded harmonic functions on $G$, the Martin kernels $M_{X_n}$along the random walk converge pointiwse to some non-constant positive harmonic function $h$, and the law of the random walk conditioned on $h$ is the Markov chain with transition probabilities \begin{equation} p^h(x,y) = \frac{h(y)}{h(x)}p(x,y). \end{equation} This is the $h$-transform of the simple random walk on $G$.

Now, using the fact that we are on a Cayley graph, the sequence $h(X_{n+1})/h(X_n)$ is stationary and ergodic and, using the above expression for the law of $X$ conditional on $h$, we see that $\mathbb{E}[\log h(X_1)]>0$, and so the Ergodic Theorem implies that \begin{equation} \lim \frac{1}{n}\log h(X_n) = \lim \frac{1}{n}\sum \log \frac{h(X_n)}{h(X_{n-1})} = \mathbb{E}[\log h(X_1)]>0 \end{equation} so that $h$ grows exponentially along the random walk path almost surely. Now, again because we are in a Cayley graph and in particular have bounded degree, and $h$ is positive harmonic, $h(v)/h(u) \leq \deg(u)$ (we implicitly used this to get integrability in our application of the Ergodic Theorem also) and so $\log h$ is Lipschitz in the graph distance, so that the walk must have positive speed amost surely.

  • 1
    $\begingroup$ Well, it's kind of cheating to say that this argument is "without any entropy" as the limit in the displayed formula is precisely the entropy. $\endgroup$
    – R W
    Commented Nov 12, 2014 at 21:22
  • $\begingroup$ Nice to see an argument although it is indeed not what I was looking for (a more direct probabilistic interpretation). The question I asked turns out to be a 3* question in G.Pete's note Probability and Geometry on groups, and given other 3* questions are unsolved conjectures, it's certainly harder than I thought. In any case, both answers are helpful and in order to close the "open"-status I'm picking the one with more votes... $\endgroup$
    – ARG
    Commented Nov 24, 2014 at 8:42

First about the background, which you present in a somewhat misleading form. The "brute force" argument of Avez you are referring to works just for finitely supported measures. On the other hand (and contrary to what you say) it does not use symmetry. Concerning the implication "zero entropy $\implies$ zero speed", for finitely supported symmetric measures this, indeed, follows from Varopoulos-Carne inequalities. However, there is a much more comprehensive approach due to Karlsson and Ledrappier MR2402595 (which works in the natural generality of measures with a finite first moment). According to them, if the entropy vanishes, then the only way for the rate of escape to be positive is when there is a group homomorphism onto $\mathbb Z$ with non-zero mean. In particular, for all symmetric measures with a finite first moment zero entropy implies zero speed.

Now, concerning your question. I am not aware of any arguments which would really avoid entropy (see my comment to Tom Hutchcroft's answer). Entropy is much closer related to the Liouville property than the rate of escape. One of the reasons for that is that the asymptotic entropy is just the weighted sum of Kullback-Leibler distance between the harmonic measures and its translates (or, before passing to limit, between $n$-fold convolutions of $\mu$ and their translates). The "brute force approach" of Avez then essentially consists in obtaining an upper bound for the total variation distance in terms of the KL distance (also see similar estimates in Erschler-Karlsson MR2791651). The latter paper also contains some pretty explicit inequalities involving the entropy and the first moment of $n$-fold convolution, which can probably be qualified as "brute force" as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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