Random Walks On Finite Groups With Few Random Generators

Igor Pak (Yale University)

Abstract


Let $G$ be a finite group. Choose a set $S$ of size $k$ uniformly from $G$ and consider a lazy random walk on the corresponding Cayley graph. We show that for almost all choices of $S$ given $k = 2a\, \log_2 |G|$, $a>1$, this walk mixes in under $m = 2a \,\log\frac{a}{a-1} \log |G|$ steps. A similar result was obtained earlier by Alon and Roichman and also by Dou and Hildebrand using a different techniques. We also prove that when sets are of size $k = \log_2 |G| + O(\log \log |G|)$, $m = O(\log^3 |G|)$ steps suffice for mixing of the corresponding symmetric lazy random walk. Finally, when $G$ is abelian we obtain better bounds in both cases.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-11

Publication Date: November 11, 1998

DOI: 10.1214/EJP.v4-38

References

  1. D. Aldous and P. Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93, (1986), 333--348 Math Review link
  2. D. Aldous and P. Diaconis, Strong uniform times and finite random walks, Adv. in Appl. Math. 8, (1987), no. 1, 69--97 Math Review link
  3. D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs, monograph in preparation
  4. N. Alon and Y. Roichman, Random Cayley graphs and expanders. Random Structures Algorithms 5, (1994), no. 2, 271--284 Math Review link
  5. A. Astashkevich and I. Pak, Random walks on nilpotent and supersolvable groups, preprint, (1997)
  6. L. Babai, Local expansion of vertex-transitive graphs and random geneartion in finite groups, Proc 23rd ACM STOC, (1991), 164--174
  7. L. Babai, Automorphism groups, isomorphism, reconstruction. Handbook of combinatorics, Vol. 2, 1447--1540, Elsevier, Amsterdam, 1995. Math Review link
  8. L. Babai and G. Hetyei, On the diameter of random Cayley graphs of the symmetric group. Combin. Probab. Comput. 1, (1992), no. 3, 201--208. Math Review link
  9. P. Diaconis, Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes---Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. Math Review link
  10. P. Diaconis, The cutoff phenomenon in finite Markov chains. Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 4, 1659--1664. Math Review link
  11. P. Diaconis, R. Graham and J. Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures Algorithms 1 (1990), no. 1, 51--72. Math Review link
  12. P. Diaconis, L. Saloff--Coste, Comparison techniques for random walk on finite groups. Ann. Probab. 21 (1993), no. 4, 2131--2156. Math Review link
  13. C. Dou and M. Hildebrand, Enumeration and random random walks on finite groups. Ann. Probab. 24, (1996), no. 2, 987--1000. Math Review link
  14. P. Erdos and R.R. Hall, Probabilistic methods in group theory. II. Houston J. Math. 2, (1976), no. 2, 173--180.
  15. P. ErdH os and A. R' enyi , Probabilistic methods in group theory. J. Analyse Math. 14, (1965), 127--138.
  16. W. Feller, An introduction to probability theory and its applications. Vol. I. Third edition John Wiley & Sons, Inc., New York, 1968.
  17. A. Greenhalgh, A model for random random-walks on finite groups. Combin. Probab. Comput. 6 (1997), no. 1, 49--56. Math Review link
  18. M. Hildebrand, Random walks supported on random points of $bold Z/nbold Z$. Probab. Theory Related Fields 100 (1994), no. 2, 191--203. Math Review link
  19. W. M. Kantor and A. Lubotzky, The probability of generating a finite classical group. Geom. Dedicata 36 (1990), no. 1, 67--87. Math Review link
  20. M. W. Liebeck and A. Shalev, The probability of generating a finite simple group. Geom. Dedicata 56 (1995), no. 1, 103--113. Math Review link
  21. I. Pak, Random walks on groups: strong uniform time approach, Ph.D. Thesis, Harvard U., (1997)
  22. I. Pak, On finite geometric random walks, preprint, (1998)
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.