Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-15T19:19:38.322Z Has data issue: false hasContentIssue false
  • English
  • Français

Gillis' Random Walks on Graphs

Published online by Cambridge University Press:  14 July 2016

Nadine Guillotin-Plantard
Nadine Guillotin-Plantard*
Affiliation:
Université Claude Bernard Lyon 1
*
∗Postal address: Université Claude Bernard Lyon 1, LaPCS, 50, avenue Tony Garnier, Domaine de Gerland, 69366 Lyon Cedex 07, France. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a random walker on a d-regular graph. Starting from a fixed vertex, the first step is a unit step in any one of the d directions, with common probability 1/d for each one. At any later step, the random walker moves in any one of the directions, with probability q for a reversal of direction and probability p for any other direction. This model was introduced and first studied by Gillis (1955), in the case when the graph is a d-dimensional square lattice. We prove that the Gillis random walk on a d-regular graph is recurrent if and only if the simple random walk on the graph is recurrent. The Green function of the Gillis random walk will be also given, in terms of that of the simple random walk.

Keywords

Random walkgenerating functionGreen functioncorrelated random walkrecurrence vs transience
Type
Short Communications
Information
Journal of Applied Probability , Volume 42 , Issue 1 , March 2005 , pp. 295 - 301
Copyright
© Applied Probability Trust 2005 

References

Bartholdi, L. (1999). Counting paths in graphs. Enseign. Math. (2) 45, 83–131.Google Scholar
Bender, C., Boettcher, S. and Mead, L. (1994). Random walks in noninteger dimension. J. Math. Phys. 35, 368–388.Google Scholar
Chen, A. Y. and Renshaw, E. (1992). The Gillis–Domb–Fisher correlated random walk. J. Appl. Prob. 29, 792–813.Google Scholar
Chen, A. Y. and Renshaw, E. (1994). The general correlated random walk. J. Appl. Prob. 31, 869–884.Google Scholar
Domb, C. and Fisher, M. E. (1958). On random walks with restricted reversals. Proc. Camb. Phil. Soc. 54, 48–59.Google Scholar
Gillis, J. (1955). Correlated random walk. Proc. Camb. Phil. Soc. 51, 639–651.Google Scholar
Grigorchuk, R. I. (1978). Banach invariant means on homogeneous spaces and random walks. , Moscow State University.Google Scholar
Grigorchuk, R. I. (1980). Symmetrical random walks on discrete groups. In Multicomponent Random Systems (Adv. Prob. Relat. Topics 6), Marcel Dekker, New York, pp. 285–325.Google Scholar
Iossif, G. (1986). Return probabilities for correlated random walks. J. Appl. Prob. 23, 201–207.Google Scholar
Kesten, H. (1959). Symmetric random walks on groups. Trans. Amer. Math. Soc. 92, 336–354.Google Scholar
Woess, W. (2000). Random Walks on Infinite Graphs and Groups (Camb. Tracts Math. 138). Cambridge University Press.Google Scholar