Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-26T04:03:23.815Z Has data issue: false hasContentIssue false
  • English
  • Français

A matrix equation approach to solving recurrence relations in two-dimensional random walks

Part of: Basic linear algebra

Published online by Cambridge University Press:  14 July 2016

James W. Miller
James W. Miller*
Affiliation:
Southern Methodist University
*
∗ Postal address: Department of Statistical Science, Southern Methodist University, Dallas, TX 75275–0322, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

The purpose of this paper is to provide explicit formulas for a variety of probabilistic quantities associated with an asymmetric random walk on a finite rectangular lattice with absorbing barriers. Quantities of interest include probabilities that a walker will exit the lattice onto some particular set of boundary states, the expected duration of the walk, and the expected number of visits to one state given a start in another. These quantities are shown to satisfy two-dimensional recurrence relations that are very similar in structure. In each case, the recurrence relations may be represented by matrix equations of the form X = AX + XB + C, where A and B are tridiagonal Toeplitz matrices. The spectral properties of A and B are investigated and used to provide solutions to this matrix equation. The solutions to the matrix equations then lead to solutions for the recurrence relations in very general cases.

Keywords

MARKOV CHAINSLINEAR MATRIX EQUATIONS

MSC classification

Secondary: 15A06: Linear equations
Type
Research Papers
Information
Journal of Applied Probability , Volume 31 , Issue 3 , September 1994 , pp. 646 - 659
Copyright
Copyright © Applied Probability Trust 1994 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Doyle, P. and Snell, J. L. (1984) Random Walks and Electrical Networks. Mathematical Association of America.Google Scholar
Feller, W. (1968) An Introduction to Probability Theory and its Applications, Vol. I, 3d ed. Wiley, New York.Google Scholar
Jameson, A. (1968) Solution of the equation AX + XB = C by inversion of an M × M or N × N matrix. SIAM J. Appl. Math. 16, 1020–1023.CrossRefGoogle Scholar
Kemeny, J. G. and Snell, J. L. (1960) Finite Markov Chains. Van Nostrand, Princeton.Google Scholar
Kucera, V. (1974) The matrix equation AX + XB = C. SIAM J. Appl. Math. 26, 15–25.Google Scholar
Lancaster, P. (1970) Explicit solutions of linear matrix equations. SIAM Rev. 12, 544–566.Google Scholar
Lancaster, P. and Tismenetsky, M. (1985) The Theory of Matrices, 2d edn. Academic Press, San Diego.Google Scholar
Ma, E. (1966) A finite series solution of the matrix equation AX - XB = C. SIAM J. Appl. Math. 14, 490–495.CrossRefGoogle Scholar
McCrea, W. H. and Whipple, F. J. W. (1940) Random paths in two and three dimensions. Proc. R . Soc. Edinburgh 60, 281–298.Google Scholar
Rubin, R. J. (1965) Span of a polymer chain. J. Chem. Phys. 43, 2392–2407.Google Scholar