×

zbMATH — the first resource for mathematics

Boundaries of random walks on graphs and groups with infinitely many ends. (English) Zbl 0723.60009
Given an irreducible random walk \((Z_ n)\) on a locally finite graph G with infinitely many ends, whose transition function is invariant with respect to a closed subgroup \(\Gamma\) of automorphisms of G acting transitively on the vertex set of G, the author studies the asymptotic behavior of \((Z_ n)\) on the space \(\Omega\) of ends of G. Apart of a special case (i.e. if \(\Gamma\) is amenable) \(\Omega\) can be shown to be a Furstenberg boundary, \((Z_ n)\) converges almost surely (towards \(\Omega\)), and the corresponding Dirichlet problem can be solved. If \((Z_ n)\) has finite range, then \(\Omega\) can be identified with the Poisson boundary. Some of the results are applied to discrete groups with finitely many ends.

MSC:
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
60G50 Sums of independent random variables; random walks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Ancona,Positive harmonic functions and hyperbolicity, inPotential Theory, Surveys and Problems (J. Král, J. Lukeš, I. Netuka and J. Veselý, eds.), Lecture Notes in Math.1344, Springer-Verlag, Berlin-Heidelberg-New York, 1988, pp. 1–23.
[2] W. Betori, J. Faraut and M. Pagliacci,An inversion formula for the Radon transform on trees, Math. Z.201 (1989), 327–337. · Zbl 0651.43003 · doi:10.1007/BF01214899
[3] P. Cartier,Fonctions harmoniques sur un arbre, Symposia Math.9 (1972), 203–270. · Zbl 0283.31005
[4] D. I. Cartwright and P. M. Soardi,Convergence to ends for random walks on the automorphism group of a tree, Proc. Am. Math. Soc., in press. · Zbl 0682.60059
[5] Y. Derriennic,Marche aléatoire sur le groupe libre et frontière de Martin, Z. Wahrscheinlichkeitstneor. Verw. Geb.32 (1975), 261–276. · Zbl 0364.60117 · doi:10.1007/BF00535840
[6] M. J. Dunwoody,Cutting up graphs, Combinatorica2 (1982), 15–23. · Zbl 0504.05035 · doi:10.1007/BF02579278
[7] E. B. Dynkin and M. B. Malyutov,Random walks on groups with a finite number of generators, Soviet Math. Doklady2 (1961), 399–402. · Zbl 0214.44101
[8] H. Freudenthal,Über die Enden diskreter Räume und Gruppen, Comment. Math. Helv.17 (1944), 1–38. · Zbl 0060.40007 · doi:10.1007/BF02566233
[9] H. Furstenberg,Non commuting random products, Trans. Am. Math. Soc.108 (1963), 377–428. · Zbl 0203.19102 · doi:10.1090/S0002-9947-1963-0163345-0
[10] H. Furstenberg,Random walks and discrete subgroups of Lie groups, inAdvances in Probability and Related Topics, Vol. 1 (P. Ney, ed.), M. Dekker, New York, 1971, pp. 1–63.
[11] P. Gerl and W. Woess,Simple random walks on trees, Eur. J. Comb.7 (1986), 321–331. · Zbl 0606.05021
[12] M. Gromov,Hyperbolic groups, inEssays in Group Theory (S. M. Gersten, ed.), Math. Sci. Res. Inst. Publ.8, Springer-Verlag, New York-Berlin-Heidelberg, 1987, pp. 75–263. · Zbl 0634.20015
[13] Y. Guivarc’h, M. Keane and B. Roynette,Marches Aléatoires sur les groupes de Lie, Lecture Notes in Math.624, Springer-Verlag, Berlin-Heidelberg-New York, 1977.
[14] R. Halin,Über unendliche Wege in Graphen, Math. Ann.157 (1964), 125–137. · Zbl 0125.11701 · doi:10.1007/BF01362670
[15] R. Halin,Automorphisms and endomorphisms of infinite locally finite graphs, Abh. Math. Sem. Univ. Hamburg39 (1973), 251–283. · Zbl 0265.05118 · doi:10.1007/BF02992834
[16] E. Hewitt and K. A. Ross,Abstract Harmonic Analysis, Vol. I, Springer-Verlag, Berlin-Heidelberg-New York, 1963. · Zbl 0115.10603
[17] H. A. Jung,Connectivity in infinite graphs, inStudies in Pure Math. (L. Mirksy, ed.), Academic Press, New York-London, 1971, pp. 137–143.
[18] V. A. Kaimanovich,An entropy criterion for maximality of the boundary of random walks on discrete groups, Soviet Math. Doklady31 (1985), 193–197.
[19] V. A. Kaimanovich and A. M. Vershik,Random walks on discrete groups: boundary and entropy, Ann. Prob.11 (1983), 457–490. · Zbl 0641.60009 · doi:10.1214/aop/1176993497
[20] J. G. Kemeny, J. L. Snell and A. W. Knapp,Denumerable Markov Chains, 2nd ed., Springer-Verlag, New York-Heidelberg-Berlin, 1976. · Zbl 0348.60090
[21] R. C. Lyndon and P. E. Schupp,Combinatorial Group Theory, Springer-Verlag, Berlin-Heidelberg-New York, 1977. · Zbl 0368.20023
[22] M. A. Picardello and W. Woess,Martin boundaries of random walks: ends of trees and groups, Trans. Am. Math. Soc.302 (1987), 185–205. · Zbl 0615.60068 · doi:10.1090/S0002-9947-1987-0887505-2
[23] M. A. Picardello and W. Woess,Harmonic functions and ends of graphs, Proc. Edinburgh Math. Soc.31 (1988), 457–461. · Zbl 0664.60075
[24] E. Seneta,Non-negative Matrices and Markov Chains, 2nd ed., Springer Series in Statistics, Springer-Verlag, Berlin-Heidelberg-New York, 1981. · Zbl 0471.60001
[25] P. M. Soardi and W. Woess,Amenability, unimodularity, and the spectral radius of random walks on infinite graphs, Univ. Milan, preprint (1988). · Zbl 0693.43001
[26] J. Stallings,Group Theory and Three-dimensional Manifolds, Yale Univ. Press, New Haven-London, 1971. · Zbl 0241.57001
[27] W. Woess,A description of the Martin boundary for nearest neighbour random walks on free products, inProbability Measures on Groups (H. Heyer, ed.), Lecture Notes in Math.1210, Springer-Verlag, Berlin-Heidelberg-New York, 1986, pp. 203–215. · Zbl 0611.60006
[28] W. Woess,Amenable group actions on infinite graphs, Math. Ann.284 (1989), 251–265. · Zbl 0648.43002 · doi:10.1007/BF01442875
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.