Let $\Gamma$ be an infinite, finitely generated group, and $X_n$ a random walk over $\Gamma$ with step distribution $\mu$. recall the definitions of :
- Entropy of $X_n$ : $\frac{-\log \mu^{*n}(X_n)}{n} \to h$, a.s.
- Speed of $X_n$ : $\frac{\vert X_n \vert}{n} \to \ell$, a.s.
- Exponential growth rate of $\Gamma$ : $\beta = \lim_{n\to\infty}\frac{\log \vert B_n\vert}{n}$, where $B_n$ is the ball of radius $n$ for $\Gamma$
I would like to prove that
$h \leq \beta\ell$
Using that $h = \lim\frac{H(X_n)}{n}$ with $H(X_n)$ Shannon entropy of $X_n$, and that $H(X_n) \leq \log\vert B_n\vert$, we have the immediate result that $h\leq \beta$. I need to introduce the random walk's speed. I've seen this paper, page 8, but the "proof" includes at least one big mistake (switching a $\geq$ into a $\leq$), and it goes way to fast through Egorov's theorem.
Any input on how to prove the inequality?
Edit
I'm trying to fix the proof in the aforementioned paper. With $H(X_n)\leq \log\vert B_n\vert$, we know that for any $\gamma>0$, for $n$ large enough, $$ H(X_n) \leq (\beta +\gamma) n$$
For any $\varepsilon>0$, we can still split the calculation of $H(X_n)$ as $$H(X_n) = \sum_{x\in B_{n(\ell+\varepsilon)}}p_n(x)(-\log p_n(x))+\sum_{x\not\in B_{n(\ell+\varepsilon)}}p_n(x)(-\log p_n(x))$$
And we can now upper bound the first term using the max entropy $$\sum_{x\in B_{n(\ell+\varepsilon)}}p_n(x)(-\log p_n(x)) \leq (\beta+\gamma)(\ell+\varepsilon)n$$ In order to conclude I only need to understand the section about Egorov's Theorem, and the fact that
$$\vert X_n(\omega)\vert\leq n(\ell+\varepsilon)$$ uniformly for $\omega\in E$, where $E$ is an event with $\mathbb{P}(E)\geq 1-\varepsilon$, leading to $$ \mathbb{P}\left(X_n \not\in B_{n(\ell+\varepsilon)}\right) \leq \varepsilon$$
I don't even understand the notation $X_n(\omega)$, any idea?
Edit 2 I think we could use the argument :
Because $\vert X_n\vert / n$ tends to $\ell$ almost surely, then it also converge in probability, and for any $\varepsilon>0$, for $n$ large enough $$ \mathbb{P}\left[ \vert X_n\vert\leq n(\ell+\varepsilon)\right] = 1$$ And then $$\mathbb{P}[X_n\in B_{n(\ell+\varepsilon)}]=1 $$
Then we should be able to conclude : $$ h \leq (\beta+\gamma)(\ell+\varepsilon)$$ True for any $\gamma>0$ and any $\varepsilon>0$ hence $$ h \leq \beta+\ell$$
I will write the full argument in a neat answer, and I will post it tomorrow if noone contradicts me before.
The first important note is to understand the concept of speed of random walk : for any random walk $X_n$, it is obvious that $\vert X_n\vert \in B_n$. But if $X_n$ has speed $\ell$, then for any $\varepsilon>0$, for $n$ large enough, \begin{align} \mathbb{P}\left[ X_n \in B_{n(\ell+\varepsilon)}\right] &= 1 \qquad (1)\\ \mathbb{P}\left[ X_n \not\in B_{n(\ell-\varepsilon)}\right] &= 1 \qquad (2) \end{align} This is because a.s. convergence implies convergence in probability.
Now, we have $H(X_n) = -\sum p(x)\log p(x)$ with $p(x)=\mu^{*n}(x)$. We'll split the sum between $x\in B_{n(\ell+\varepsilon)}$ and $x\not\in B_{n(\ell+\varepsilon)}$ : $$H(X_n) = \underbrace{-\sum_{x\in B_{n(\ell+\varepsilon)}} p(x)\log p(x)}_{(A)} \quad \underbrace{-\sum_{x\not\in B_{n(\ell+\varepsilon)}} p(x)\log p(x)}_{(B)}$$
For the first part $(A)$, we use that for any variable X \in F, $H(X)\leq \log\vert F\vert$, therefore $$A \leq \log \vert B_{n(\ell+\varepsilon)}\vert$$ And because $\beta$ is the exponential growth rate of the group, then for any $\gamma>0$, for $n$ large enough, $\log \vert B_n\vert \leq n(\beta+\gamma)$, $$A \leq \log \vert B_{n(\ell+\varepsilon)}\vert \leq n(\ell+\varepsilon)(\beta+\gamma)$$
For the second part $(B)$ we need the additional hypothesis that $\mu$ has finite support and $X_n$ is irreducible. That's fine if the random walk is a nearest-neighbour one for example as the group is finitely generated. We can define $$\delta = min\{ \mu(x), x\in supp(\mu)\} > 0$$ So that for any $x$, $p(x)\geq \delta^n$ and $$ B = -\sum_{x\not\in B_{n(\ell+\varepsilon)}} p(x)\log p(x) \leq -n\log\delta\cdot \mathbb{P}\left[ X_n \not\in B_{n(\ell+\varepsilon)}\right]=0$$
And finally $$h = \lim_{n\to\infty} \frac{H(X_n)}{n} \leq (\ell+\varepsilon)(\beta+\gamma)$$ This is true for any $\varepsilon>0$ and any $\gamma>0$, therefore $$h\leq \beta\ell$$