Amir’s conjecture for random walks on groups is true

Algebra, Probability and Statistics 2 Minutes

You need to know: Group, set of generators, finitely generated group, basic probability theory, independent identically distributed (i.i.d.) random variables.

 Background: Let G be an infinite group with finite generating set S. Let S^{-1}=\{g \in G\,|\,g^{-1}\in S\}, and let |g| be the smallest integer k\geq 0 such that g\in G has representation g=\prod_{i=1}^k s_i with each s_i \in S \cup S^{-1}. A symmetric finitely supported probability measure on G is a function \mu:G\to[0,1] such that set \{g \in G\,|\,\mu(g)>0\} is finite, \sum_{g\in G} \mu(g)=1, and \mu(g^{-1})=\mu(g) for all g \in G. Let X_1, X_2, \dots be a sequence of i.i.d. random variables with distribution \mu, that is, such that {\mathbb P}[X_i=g]=\mu(g) for all g\in G and all i. A random walk on G with step distribution \mu is the sequence W_1,W_2,\dots given by W_n=\prod_{i=1}^n X_i. A speed function of random walk W_n is L_\mu(n) = {\mathbb E}[|W_n|] = \sum_{g\in G}|g|{\mathbb P}[W_n=g]. Its entropy is H_\mu(n) = - \sum_{g\in G}{\mathbb P}[W_n=g]\log{\mathbb P}[W_n=g]. The exponent of a function f is \lim_{n\to\infty} \frac{\log f(n)}{\log n}, provided that the limit exists.

The Theorem: On 27th October 2015, Jérémie Brieussel and Tianyi Zheng submitted to arxiv a paper in which they proved that for any \gamma\in[1/2,1] and \theta\in[1/2,1] satisfying \theta \leq \gamma \leq \frac{1}{2}(\theta+1), there exist a finitely generated group G and a symmetric probability measure \mu of finite support on G, such that the random walk on G with step distribution \mu has speed exponent \gamma and entropy exponent \theta.

Short context: The main research directions in studying random walks on groups are (i) given a group, establish properties of random walk on it, and, conversely (ii) given properties of a random walk, find if there exists a group with such random walk. The Theorem contributes to direction (ii). It confirms a conjecture of Amir who proved the same result for \gamma,\theta\in[3/4,1].

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment