Annals of Combinatorics 3 (1999) 475-481

Restricted Random Walks on a Graph

F.Y. Wu and H. Kunz

Department of Physics, Northeastern University, Boston, MA 02115, USA

Institut de Physique Théorique, Ecole Polytechnique Fédérale, Lausanne, Switzerland

Received November 1, 1998

AMS Subject Classification: 60J15, 82B41

Abstract. The problem of a restricted random walk on graphs, which keeps track of the number of immediate reversal steps, is considered by using a transfer matrix formulation. A closed-form expression is obtained for the generating function of the number of n-step walks with r reversal steps for walks on any graph. In the case of graphs of a uniform valence, we show that our result has a probabilistic meaning, and deduce explicit expressions for the generating function in terms of the eigenvalues of the adjacency matrix. Applications to periodic lattices and the complete graph are given.

Keywords: random walks, graphs, adjacency matrix


1.  J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, North Holland, New York, 1976.

2.  B.D. Hughes, Random Walks and Random Environments, Vol. 1, Oxford University Press, Oxford, 1995; Vol. 2, 1996.

3.  T. Kottos and U. Smilansky, Quantum chaos on graphs, Phys. Rev. Lett. 79 (1997) 4794–4797.

4.  E.W. Montroll, Markoff chains and excluded volume effect in polymer chains, J. Chem. Phys. 18 (1950) 734–743.

5.  F. Spitzer, Principles of Random Walk, Springer-Verlag, New York, 1976, p. 3.

6.  R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Monterey, California, 1986.

Get the DVI | PS | PDF file of this abstract.