Random Walks on Groups and Monoids with a Markovian Harmonic Measure

Mairesse Jean (CNRS - Universite Paris 7)

Abstract


We consider a transient nearest neighbor random walk on a group $G$ with finite set of generators $S$. The pair $(G,S)$ is assumed to admit a natural notion of normal form words where only the last letter is modified by multiplication by a generator. The basic examples are the free products of a finitely generated free group and a finite family of finite groups, with natural generators. We prove that the harmonic measure is Markovian of a particular type. The transition matrix is entirely determined by the initial distribution which is itself the unique solution of a finite set of polynomial equations of degree two. This enables to efficiently compute the drift, the entropy, the probability of ever hitting an element, and the minimal positive harmonic functions of the walk. The results extend to monoids.

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

Pages: 1417-1441

Publication Date: December 16, 2005

DOI: 10.1214/EJP.v10-293

References

  1. C. Aliprantis and K. Border. Infinite Dimensional Analysis: a Hitchhiker's Guide, 2nd ed. (1999) Springer-Verlag. Math. Review 2000k:46001
  2. A. Avez. Entropie des groupes de type fini. C. R. Acad. Sci. Paris Sér. A-B 275 (1972), 1363--1366. Math. Review 0324741
  3. D. Cartwright and B. Krön. Classification of 0-automatic pairs. Preprint (2004).
  4. Y. Derriennic. Quelques applications du théorème ergodique sous-additif. Astérisque 74 (1980), 183-201. Math. Review 82e:60013
  5. Y. Derriennic. Entropie, théorèmes limite et marches aléatoires. Probability measures on groups, VIII (Oberwolfach, 1985) Lecture Notes in Math. 1210 (1986), 241-284, Springer. Math. Review 89f:60076b
  6. E. Dynkin and M. Malyutov. Random walk on groups with a finite number of generators. Sov. Math. Dokl. 2 (1961), 399--402. Math. Review 0131904
  7. D. Epstein, J. Cannon, D. Holt, S. Levy, M. Paterson, and W. Thurston. Word processing in groups. (1992) Jones and Bartlett. Math. Review 93i:20036
  8. H. Furstenberg. Noncommuting random products. Trans. Amer. Math. Soc. 108 (1963), 377-428. Math. Review 0163345
  9. H. Furstenberg. Random walks and discrete subgroups of Lie groups. Advances Probab. Related Topics, Vol. 1 (1971), 1-63, Dekker. Math. Review 0284569
  10. M. Gromov. Hyperbolic groups. Essays in group theory. Math. Sci. Res. Inst. Publ. 8 (1987), 75-263, Springer. Math. Review 89e:20070
  11. Y. Guivarc'h. Sur la loi des grands nombres et le rayon spectral d'une marche aléatoire. Astérisque 74 (1980), 47-98. Math. Review 82g:60016
  12. R. Haring-Smith. Groups and simple languages. Trans. Amer. Math. Soc. 279 (1983), no. 1, 337-356. Math. Review 85b:20045
  13. G. Högnäs and A. Mukherjea. Probability measures on semigroups : convolution products, random walks, and random matrices. The University Series in Mathematics (1995), Plenum Press. Math. Review 97c:60018
  14. V. Kaimanovich. The Poisson formula for groups with hyperbolic properties. Ann. of Math. (2) 152 (2000), no. 3, 659-692. Math. Review 2002d:60064
  15. V. Kaimanovich and A. Vershik. Random walks on discrete groups: boundary and entropy. Ann. Probab. 11 (1983), no. 3, 457-490. Math. Review 85d:60024
  16. J.F.C. Kingman. Subadditive ergodic theory. Ann. Probab. 1 (1973), 883-909. Math. Review 0356192
  17. S. Lalley. Finite range random walk on free groups and homogeneous trees. Ann. Probab. 21 (1993), no. 4, 2087-2130. Math. Review 94m:60051
  18. S. Lalley. Random walks on regular languages and algebraic systems of generating functions. Algebraic methods in statistics and probability. Contemp. Math. 287 (2001), 201-230, Amer. Math. Soc. Math. Review 2002m:60038
  19. F. Ledrappier. Some asymptotic properties of random walks on free groups. Topics in probability and Lie groups: boundary theory. CRM Proc. Lect. Notes 28 (2001), 117-152, Amer. Math. Soc. Math. Review 2002g:60116
  20. R. Lyons. Random walks and the growth of groups. C. R. Acad. Sci., Paris, Sér. I 320 (1995), no. 11, 1361-1366. Math. Review 96e:60015
  21. J. Mairesse. Zero-automaticity for groups and monoids. Preprint available at http://www.liafa.jussieu.fr/~mairesse/Article (2004).
  22. J. Mairesse and F. Mathéus. Random walks on free products of cyclic groups. arXiv:math.PR/0509211 (2005).
  23. J. Mairesse and F. Mathéus. Random walks on groups with a tree-like Cayley graph. Mathematics and computer science. III. Algorithms, trees, combinatorics and probabilities. Trends Math. (2004), 445-460, Birkhäuser. Math. Review 2006a:60076
  24. T. Nagnibeda and W. Woess. Random walks on trees with finitely many cone types. J. Theoret. Probab. 15 (2002), no. 2, 383-422. Math. Review 2003k:60098
  25. S. Sawyer and T. Steger. The rate of escape for anisotropic random walks in a tree. Probab. Theory Related Fields 76 (1987), no. 2, 207-230. Math. Review 89a:60165
  26. P. Soardi. Limit theorems for random walks on discrete semigroups related to nonhomogeneous trees and Chebyshev polynomials. Math. Z. 200 (1989), no. 3, 313-325. Math. Review 90b:60011
  27. J. Stallings. A remark about the description of free products of groups. Proc. Cambridge Philos. Soc. 62 (1966), 129-134. Math. Review 0188332
  28. C. Takacs. Random walk on periodic trees. Electron. J. Probab. 2 (1997), no. 1, 1-16. Math. Review 97m:60101
  29. A. Vershik. Dynamic theory of growth in groups: Entropy, boundaries, examples. Russ. Math. Surv. 55 (2000), no. 4, 667-733. Math. Review 2001m:37019
  30. W. Woess. A description of the Martin boundary for nearest neighbour random walks on free products. Probability measures on groups, VIII (Oberwolfach, 1985) Lecture Notes in Math. 1210 (1986), 203-215, Springer. Math. Review 88i:60121
  31. W. Woess. Random walks on infinite graphs and groups. Cambridge Tracts in Mathematics 138 (2000), Cambridge University Press. Math. Review 2001k:60006
Bookmark and Share


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