Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 12 (2007) > Paper 20 open journal systems 


On the range of the simple random walk bridge on groups

Itai Benjamini, Weizmann Institute of Science
Roey Izkovsky, Weizmann Institute of Science
Harry Kesten, Cornell University


Abstract
Abstract. Let G be a vertex transitive graph. A study of the range of simple random walk on G and of its bridge is proposed. While it is expected that on a graph of polynomial growth the sizes of the range of the unrestricted random walk and of its bridge are the same in first order, this is not the case on some larger graphs such as regular trees. Of particular interest is the case when G is the Cayley graph of a group. In this case we even study the range of a general symmetric (not necessarily simple) random walk on G. We hope that the few examples for which we calculate the first order behavior of the range here will help to discover some relation between the group structure and the behavior of the range. Further problems regarding bridges are presented.


Full text: PDF

Pages: 591-612

Published on: May 1, 2007
Bibliography
  1. Avez, André. Limite de quotients pour des marches aléatoires sur des groupes. (French) C. R. Acad. Sci. Paris Sér. A-B 276 (1973), A317--A320. MR0315750 (47 #4299)
  2. Bougerol, Philippe; Jeulin, Thierry. Brownian bridge on hyperbolic spaces and on homogeneous trees. Probab. Theory Related Fields 115 (1999), no. 1, 95--120. MR1715541 (2000k:60161)
  3. Cartwright, Donald I. Some examples of random walks on free products of discrete groups. Ann. Mat. Pura Appl. (4) 151 (1988), 1--15. MR0964500 (90f:60018)
  4. Chow, Yuan Shih; Teicher, Henry. Probability theory. Independence, interchangeability, martingales. Third edition. Springer Texts in Statistics. Springer-Verlag, New York, 1997. xxii+488 pp. ISBN: 0-387-98228-0 MR1476912 (98e:60003)
  5. Dekking, F. M. On transience and recurrence of generalized random walks. Z. Wahrsch. Verw. Gebiete 61 (1982), no. 4, 459--465. MR0682573 (84c:60099)
  6. Donsker, M. D.; Varadhan, S. R. S. On the number of distinct sites visited by a random walk. Comm. Pure Appl. Math. 32 (1979), no. 6, 721--747. MR0539157 (81j:60080)
  7. Dvoretzky, A.; Erdös, P. Some problems on random walk in space. Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1950. pp. 353--367. University of California Press, Berkeley and Los Angeles, 1951. MR0047272 (13,852b)
  8. Erschler, Anna. Isoperimetry for wreath products of Markov chains and multiplicity of selfintersections of random walks. Probab. Theory Related Fields 136 (2006), no. 4, 560--586. MR2257136
  9. Feller, William. An introduction to probability theory and its applications. Vol. I. Third edition John Wiley & Sons, Inc., New York-London-Sydney 1968 xviii+509 pp. MR0228020 (37 #3604)
  10. Gerl, Peter. Über die Anzahl der Darstellungen von Worten. (German) Monatsh. Math. 75 (1971), 205--214. MR0295923 (45 #4985)
  11. Gerl, Peter. Diskrete, mittelbare Gruppen. (German) Monatsh. Math. 77 (1973), 307--318. MR0341550 (49 #6298)
  12. Grigorchuk, R. I. Degrees of growth of finitely generated groups and the theory of invariant means. (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 5, 939--985. MR0764305 (86h:20041)
  13. Hamana, Yuji. An almost sure invariance principle for the range of random walks. Stochastic Process. Appl. 78 (1998), no. 2, 131--143. MR1657371 (2000a:60090)
  14. Hebisch, W.; Saloff-Coste, L. Gaussian estimates for Markov chains and random walks on groups. Ann. Probab. 21 (1993), no. 2, 673--709. MR1217561 (94m:60144)
  15. Jain, Naresh C.; Pruitt, William E. The range of random walk. Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. III: Probability theory, pp. 31--50. Univ. California Press, Berkeley, Calif., 1972. MR0410936 (53 #14677)
  16. Khaimanovich, V. A.; Vershik, A. M. Random walks on discrete groups: boundary and entropy. Ann. Probab. 11 (1983), no. 3, 457--490. MR0704539 (85d:60024)
  17. Kesten, Harry. Full Banach mean values on countable groups. Math. Scand. 7 1959 146--156. MR0112053 (22 #2911)
  18. Kesten, Harry. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 4, 425--487. MR0871905 (88b:60232)
  19. Lalley, Steven P. Finite range random walk on free groups and homogeneous trees. Ann. Probab. 21 (1993), no. 4, 2087--2130. MR1245302 (94m:60051)
  20. Levit, B. Ja.; Molchanov, S. A. Invariant chains on a free group with a finite number of generators. (Russian) Vestnik Moskov. Univ. Ser. I Mat. Meh. 26 (1971), no. 4, 80--88. MR0298721 (45 #7770)
  21. R. Lyons and Y. Peres, Probability on Trees and Networks. To appear (2006). here (45 #7770)
  22. Nechaev, S. K.; Grosberg, A. Yu.; Vershik, A. M. Random walks on braid groups: Brownian bridges, complexity and statistics. J. Phys. A 29 (1996), no. 10, 2411--2433. MR1396938 (97j:60015)
  23. Paterson, Alan L. T. Amenability. Mathematical Surveys and Monographs, 29. American Mathematical Society, Providence, RI, 1988. xx+452 pp. ISBN: 0-8218-1529-6 MR0961261 (90e:43001)
  24. Pittet, C.; Saloff-Coste, L. On random walks on wreath products. Ann. Probab. 30 (2002), no. 2, 948--977. MR1905862 (2003d:60013)
  25. Rudin, Walter. Functional analysis. Second edition. International Series in Pure and Applied Mathematics. McGraw-Hill, Inc., New York, 1991. xviii+424 pp. ISBN: 0-07-054236-8 MR1157815 (92k:46001)
  26. Sawyer, Stanley. Isotropic random walks in a tree. Z. Wahrsch. Verw. Gebiete 42 (1978), no. 4, 279--292. MR0491493 (80a:60092)
  27. Sinclair, Alistair. Algorithms for random generation and counting. A Markov chain approach. Progress in Theoretical Computer Science. Birkhäuser Boston, Inc., Boston, MA, 1993. vi+146 pp. ISBN: 0-8176-3658-7 MR1201590 (93j:65011)
  28. Spitzer, Frank. Principles of random walks. Second edition. Graduate Texts in Mathematics, Vol. 34. Springer-Verlag, New York-Heidelberg, 1976. xiii+408 pp. MR0388547 (52 #9383)
  29. F. Spitzer in discussionof Subadditive ergodic theory. Ann. Probability 1 (1973), 904--905. MR0356192 (50 #8663)
  30. Vere-Jones, D. Ergodic properties of nonnegative matrices. I. Pacific J. Math. 22 1967 361--386. MR0214145 (35 #4996)
  31. Woess, Wolfgang. Random walks on infinite graphs and groups. Cambridge Tracts in Mathematics, 138. Cambridge University Press, Cambridge, 2000. xii+334 pp. ISBN: 0-521-55292-3 MR1743100 (2001k:60006)
  32. R. Young. Averaged Dehn functions for nilpotent groups, arXiv math. GR/0510665













Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489