Asymptotic Entropy of Random Walks on Free Products

Lorenz A. Gilch (Graz University of Technology)


Suppose we are given the free product $V$ of a finite family of finite or countable sets. We consider a transient random walk on the free product arising naturally from a convex combination of random walks on the free factors. We prove the existence of the asymptotic entropy and present three different, equivalent formulas, which are derived by three different techniques. In particular, we will show that the entropy is the rate of escape with respect to the Greenian metric. Moreover, we link asymptotic entropy with the rate of escape and volume growth resulting in two inequalities.

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

Pages: 76-105

Publication Date: January 2, 2011

DOI: 10.1214/EJP.v16-841


  1. A. Avez. Entropie des groupes de type fini. C.R. Acad. Sci. Paris Sér. A-B 275 (1972), A1363--A1366. Math. Review MR0324741 (48 #3090)
  2. I.Benjamini and Y.Peres. Tree-indexed random walks on groups and first passage percolation. Probab. Theory Related Fields, 98(1) (1994), 91--112. Math. Review MR1254826 (94m:60141)
  3. S.Blachère and P.Haïssinsky and P.Mathieu. Asymptotic entropy and Green speed for random walks on countable groups. Ann. of Probab., 36(3) (2008), 1134--1152 Math. Review MR2408585 (2009g:60009)
  4. E.Candellero and L.Gilch. Phase Transitions for Random Walk Asymptotics on Free Products of Groups. Submitted, current version available at arXiv:0909.1893v3, 2009. Math. Review number not available.
  5. D.I.Cartwright and P.M.Soardi. Random walks on free products, quotients and amalgams. Nagoya Math. J., 102 (1986), 163--180. Math. Review MR0846137 (88i:60120a)
  6. T.Cover and J.Thomas. Elements of Information Theory. Wiley & Sons, 2nd edition, 2006. Math. Review MR2239987 (2007h:00002)
  7. Y.Derriennic. Quelques applications du théorème ergodique sous-additif. Astérisque, 74 (1980), 183--201. Math. Review MR0588163 (82e:60013)
  8. A.Erschler. On the asymptotics of drift. J. of Math. Sciences, 121(3) (2004), 2437--2440. Math. Review MR1879073 (2003a:60065)
  9. A.Erschler and V.Kaimanovich. Continuity of entropy for random walks on hyperbolic groups. In preparation, 2010. Math. Review number not available.
  10. P.Gerl and W.Woess. Local Limits and Harmonic Functions for Nonisotropic Random Walks on Free Groups. Probab. Theory Rel. Fields, 71 (1986), 341--355. Math. Review MR0824708 (87m:60055)
  11. L.A. Gilch. Rate Of Escape of Random Walks on Free Products. J. Aust. Math. Soc., 83(I) (2007), 31--54. Math. Review MR2378433 (2009e:60102)
  12. L.A.Gilch and S.Müller. Random Walks on Directed Covers of Graphs. J. of Theoret. Probab., DOI 10.1007/s10959-009-0256-0, 2009. Math. Review number not available.
  13. 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 MR0588157 (82g:60016)
  14. V.A.Kaimanovich and A.M.Vershik. Random walks on discrete groups: boundary and entropy. Ann. of Prob., 11 (1983), 457--490. Math. Review MR0704539 (85d:60024)
  15. V.Kaimanovich and W.Woess. Boundary and entropy of space homogeneous Markov chains. Ann. of Prob., 30 (2002), 323--363. Math. Review MR1894110 (2003d:60152)
  16. A.Karlsson and F.Ledrappier. Linear drift and Poisson boundary for random walks. Pure Appl. Math. Q., 3 (2007), 1027--1036. Math. Review MR2402595 (2009d:60133)
  17. J.F.C.Kingman. The ergodic theory of subadditive processes. J. Royal Stat. Soc., Ser. B, 30 (1968), 499--510. Math. Review MR0254907 (40 #8114)
  18. S.Lalley. Finite range random walk on free groups and homogeneous trees. Ann. of Prob., 21(4) (1993), 2087--2130. Math. Review MR1245302 (94m:60051)
  19. F.Ledrappier. Analyticity of the entropy for some random walks. Preprint, available at arXiv:1009.5354v1, 2010. Math. Review number not available.
  20. R.Lyons, with Y. Peres. Probability on Trees and Networks. In preparation. Current version available at, 2010. Math. Review number not available.
  21. J.Mairesse and F.Mathéus. Random walks on free products of cyclic groups. J. London Math. Soc., 75(1) (2007), 47--66. Math. Review MR2302729 (2007m:60125)
  22. J.C.McLaughlin. Random Walks and Convolution Operators on Free Products. PhD thesis, New York Univ., 1986. Math. Review MR2635581
  23. T.Nagnibeda and W.Woess. Random walks on trees with finitely many cone types. J. Theoret. Probab., 15 (2002), 399--438. Math. Review MR1898814 (2003k:60098)
  24. S.Sawyer. Isotropic random walks in a tree. Zeitschrift f. Wahrscheinlichkeitstheorie, 42 (1978), 279--292. Math. Review MR0491493 (80a:60092)
  25. S.Sawyer and T.Steger. The rate of escape for anisotropic random walks in a tree. Probab. Theory Rel. Fields, 76 (1987), 207--230. Math. Review MR0906775 (89a:60165)
  26. N.T.Varopoulos. Long range estimates for Markov chains. Bull. Sc. math., 109 (1985), 225--252. Math. Review MR0822826 (87j:60100)
  27. D.Voiculescu. Addition of certain non-commuting random variables. J. Funct. Anal., 66 (1986), 323--346. Math. Review MR0839105 (87j:46122)
  28. W.Woess. Nearest neighbour random walks on free products of discrete groups. Boll. Un. Mat. Ital., 5-B (1986), 961--982. Math. Review MR0846137 (88i:60120a)
  29. W.~Woess. Random Walks on Infinite Graphs and Groups. Cambridge University Press, 2000. Math. Review MR1743100 (2001k:60006)

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