# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Moderate growth and random walk on finite groups. (English) Zbl 0795.60005

Let $G$ be a finite group with a symmetric generating set $E\subset G$ containing the identity. Let $q$ be the probability measure on $G$ which is uniformly distributed on $E$. The authors study the rate of convergence of the distributions ${q}^{\left(n\right)}$ $\left(n\ge 1\right)$ of the associated symmetric random walk to the uniform distribution $u$ of $G$ with respect to the total variation norm. This problem is interesting in particular for families of finite groups with a similar structure where the sizes $|G|$ tend to $\infty$, and where $E$ or at least the size of $E$ does not change.

The authors define the volume growth $V\left(n\right):=|{E}^{n}|$ and the diameter $\gamma :=min\left\{n:V\left(n\right)=|G|\right\}$ of $G$ with respect to $E$. Then $G$ is called $\left(A,d\right)$-moderate growing with respect to $E$, if

$V\left(n\right)/V\left(\gamma \right)\ge {A}^{-1}·{\left(n/\gamma \right)}^{d}\phantom{\rule{1.em}{0ex}}\phantom{\rule{4.pt}{0ex}}\text{for}\phantom{\rule{4.pt}{0ex}}1\le n\le \gamma ·$

The main result of this paper states that $\left(A,d\right)$- moderate growth implies that for all $c>0$

$\parallel {q}^{\left(n\right)}-u\parallel \le B·{e}^{-c}\phantom{\rule{1.em}{0ex}}\text{for}\phantom{\rule{4.pt}{0ex}}n=\left(1+c\right)|E|{\gamma }^{2},\phantom{\rule{4pt}{0ex}}B={A}^{1/2}{2}^{d\left(d+3\right)/4}$

and

$\parallel {q}^{\left(n\right)}-u\parallel \ge {e}^{-c}/2\phantom{\rule{1.em}{0ex}}\phantom{\rule{4.pt}{0ex}}\text{for}\phantom{\rule{4.pt}{0ex}}n=c{\gamma }^{2}/\left({2}^{4d+2}{A}^{2}\right)·$

Therefore, for finite groups with moderate growth one needs roughly ${\gamma }^{2}$ steps to get close to the uniform distribution. Examples of families of groups with moderate growth are given by nilpotent groups (with fixed degree of nilpotency), and, in particular, by finite Heisenberg groups and $p$- groups. At the end of this paper, a version of Gromov’s theorem is used to show that $\left(A,d\right)$-polynomial growth of $G$ (i.e. $V\left(n\right)\le A{n}^{d}$ for $n\in ℕ\right)$ yields that $G$ has $\left(\stackrel{˜}{A},\stackrel{˜}{d}\right)$-moderate growth where $\stackrel{˜}{A},\stackrel{˜}{d}$ depend on $A,d$ only.

##### MSC:
 60B15 Probability measures on groups or semigroups, Fourier transforms, factorization 60B10 Convergence of probability measures 60G50 Sums of independent random variables; random walks
##### References:
 [1] [AD]D. Aldous, P. Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 (1986), 333–348. · Zbl 0603.60006 · doi:10.2307/2323590 [2] [B]H. Bass, The degree of polynomial growth of finitely generated nilpotent groups, Proc. London Math Soc. 25 (1982), 603–614. · Zbl 0259.20045 · doi:10.1112/plms/s3-25.4.603 [3] [C]T. Carne, A transmutation formula for Markov chains, Bull. Sc. Math. 2nd série 109 (1985), 399–405. [4] [ChDG]F. Chung, P. Diaconis, R. L. Graham, A random walk problem arising in random number generation, Ann. Prob. 15 (1987), 1148–1165. · Zbl 0622.60016 · doi:10.1214/aop/1176992088 [5] [CoS-C]T. Coulhon, L. Saloff-Coste, Puissance d’un operateur regularisant, Ann. Inst. H. Poincare Proba. Stat. 26 (1990), 419–436. [6] [D]P. Diaconis, Group Representations in Probability and Statistics, Institute of Mathematical Statistics, Hayward, CA (1988). [7] [DG]P. Diaconis, R. L. Graham, An affine walk on the hypercube, Jour. Comp. Appl. Math 41 (1992), 215–235. · Zbl 0754.60074 · doi:10.1016/0377-0427(92)90251-R [8] [DS-C1]P. Diaconis, L. Saloff-Coste, Nash’s inequality and convergence of finite Markov chains to equilibrium, Technical report (1992). [9] [DS-C2]P. Diaconis, L. Saloff-Coste, Comparison theorems for random walk on groups, To appear in Ann. Prob. 21 (1993). [10] [DS-C3]P. Diaconis, L. Saloff-Coste, An application of Harnack inequalities to random walk on nilpotent quotients, Technical report, Dept. of Mathematics, Harvard University (1993). [11] [DStr]P. Diaconis, D. Stroock, Geometric bounds for reversible Markov chains, Ann. Appl. Prob. 1 (1991), 36–61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980 [12] [E]J. Ellenberg, A sharp diameter bound for upper triangular matrices, Senior honors thesis, Dept. Math., Harvard University (1993). [13] [Gr]M. Gromov, Groups of polynomial growth and expanding maps, Publ. Math. I.H.E.S. 53 (1981), 53–73. [14] [Gu]Y. Guivarc’h, Croissance polynomiale et periodes des fonctions harmoniques, Bull. Soc. Math. France, 101 (1973), 333–379. [15] [H]M. Hall, The Theory of Groups, 2nd ed, Chelsea, New York (1976). [16] [Ha]P. Hall, Nilpotent Groups. In Collected Works of Philip Hall, Oxford University Press, Oxford (1957), 417–462. [17] [He]W. Hebisch, On heat kernels on Lie groups.Math Zeit. 210 (1992), 593–605. · Zbl 0792.22007 · doi:10.1007/BF02571816 [18] [HeS-C]W. Hebisch, L. Saloff-Coste, Gaussian estimates for Markov chains, Ann. Proba. 21 (1993), 673–709. · Zbl 0776.60086 · doi:10.1214/aop/1176989263 [19] [Hi]M. Hildebrand, Random processes of the formX n+1=a n X n +b n (modp), Ann. Proba. 21 (1993), 710–720. · Zbl 0776.60012 · doi:10.1214/aop/1176989264 [20] [IR]K. Ireland, M. Rosen, Elements of Number Theory, Bogdon and Quigley, Tarrytown, New York (1972). [21] [J]D.L. Johnson, The groups of formal power series under substitutions, Jour. Austral. Math Soc. (A) 45 (1988), 296–302. · doi:10.1017/S1446788700031001 [22] [MKSo]W. Magnus, A. Karrass, D. Solitar, Combinatorial Group Theory, 2nd ed., Dover, New York (1972). [23] [Ro]J. Rotman, The Theory of Groups: An Introduction, 3rd ed., Allyn and Bacon, Boston (1984). [24] [St]R. Stong, A random walk on the Heisenberg group, Technical report, Department of Mathematics, U.C.L.A. (1992). [25] [Su1]M. Suzuki, Group Theory I, Springer Verlag, New York (1982). [26] [Su2]M. Suzuki, Group Theory II, Springer Verlag, New York (1986). [27] [T]J. Tits, Appendix to Gromov’s paper, Publ. Math. I.H.E.S. 58 (1981), 74–78. [28] [V]N. Varopoulos, Long range estimates for Markov chains, Bull. Sc. Math. 109 (1985), 225–252. [29] [VS-CCo]N. Varopoulos, L. Saloff-Coste, Th. Coulhon, Analysis and geometry on groups, Cambridge University Press, Cambridge (1993). [30] [Z]M. Zack, A random walk on the Heisenberg group. Ph.D Thesis, Dept. Math., University of California, La Jolla (1989).