Restricted random walks on a graph |
| |
Authors: | F. Y. Wu H. Kunz |
| |
Affiliation: | (1) Department of Physics, Northeastern University, 02115 Boston, MA, USA;(2) Institut de Physique Théorique, Ecole Polytechnique Fédérale, Lausanne, Switzerland |
| |
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 ofn-step walks withr 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.Supported in part by National Science Foundation Grant DMR-9614170. |
| |
Keywords: | 60J15 82B41 |
本文献已被 SpringerLink 等数据库收录! |
|