Lyapunov functions for random walks and strings in random environment. (English) Zbl 0938.60065

Summary: We study two typical examples of countable Markov chains in random environment using the Lyapunov functions method: random walk and random string in random environment. In each case we construct an explicit Lyapunov function. Investigating the behavior of this function, we get the classification for recurrence, transience, ergodicity. We obtain new results for random strings in random environment, though we simply review well-known results for random walks using our approach.


60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60G50 Sums of independent random variables; random walks
Full Text: DOI


[1] Aspandiiarov, S., Iasnogorodski, R. and Menshikov, M. V. (1996). Passage-time moments for non-negative stochastic processes and an application to reflected random walk in a quadrant. Ann. Probab. 24 932-960. · Zbl 0869.60036 · doi:10.1214/aop/1039639371
[2] Bougerol, P. (1986). Oscillation de produits de matrices aléatoires dont l’exposant de Lyapunov est nul. Lyapunov Exponents. Lecture Notes in Math. 1186 27-36. Springer, Berlin. · Zbl 0593.60044
[3] Bougerol, P. and Lacroix, J. (1985). Products of Random Matrices with Application to Schrödinger Operators. Birkhäuser, Boston. · Zbl 0572.60001
[4] Comets, F., Menshikov, M. and Popov, S. (1997). One-dimensional branching random walk in a random environment: a classification. Markov Processes Related Fields. · Zbl 0938.60081
[5] Csáki, E. (1978). On the lower limits of maxima and minima of Wiener process and partial sums.Wahrsch. Verw. Gebiete 43 205-221. · Zbl 0372.60113 · doi:10.1007/BF00536203
[6] Deheuvels, P. and Revész, P. (1986). Simple random walk on the line in random environment. Probab. Theory Related Fields 72 215-230. · Zbl 0572.60070 · doi:10.1007/BF00699104
[7] Fayolle, G., Malyshev, V. A. and Menshikov, M. V. (1995). Topics in the Constructive Theory of Countable Markov Chains. Cambridge Univ. Press. · Zbl 0823.60053
[8] Gajrat, A. S., Malyshev, V. A., Menshikov, M. V. and Pelih, K. D. (1995). Classification of Markov chains describing the evolution of a string of characters. Uspehi Mat. Nauk 50 5-24 (in Russian). · Zbl 0856.60069 · doi:10.1070/RM1995v050n02ABEH001701
[9] Gajrat, A. S., Malyshev, V. A. and Zamyatin, A. A. (1995). Two-sided evolution of a random chain. Markov Processes Related Fields 1 281-316. · Zbl 0901.60035
[10] Hu, Y. and Shi,(1998). The limits of Sinai’s simple random walk in random environment. Ann. Probab. 26 1477-1521. · Zbl 0936.60088 · doi:10.1214/aop/1022855871
[11] Kesten, H., Kozlov, M. V. and Spitzer, F. (1975). A limit law for random walk in a random environment. Comp. Math. 30 145-168. · Zbl 0388.60069
[12] Key, E. S. (1984). Recurrence and transience criteria for random walk in a random environment. Ann. Probab. 12 529-560. · Zbl 0545.60066 · doi:10.1214/aop/1176993304
[13] Kozlov, M. V. (1973). Random walk in one dimensional random medium. Theory Probab. Appl. 18 387-388. · Zbl 0299.60054 · doi:10.1137/1118048
[14] Ledrappier, F. (1984). Quelques propriétés des exposants caractéristiques. Lecture Notes in Math. 1097 305-396. Springer, Berlin. · Zbl 0578.60029
[15] Malyshev, V. A. (1997). Interacting strings. Uspehi Mat. Nauk 52 59-86 (in Russian). · Zbl 0931.60032 · doi:10.1070/RM1997v052n02ABEH001777
[16] Meyn, S. P. and Tweedie, R. (1993). Markov Chains and Stochastic Stability. Springer, London. · Zbl 0925.60001
[17] Oseledec, I. V. (1968). A multiplicative ergodic theorem. Lyapunov characteristic numbers for dynamical systems. Trans. Moscow Math. Soc. 19 197-231. · Zbl 0236.93034
[18] Révész, P. (1990). Random Walk in Random and Nonrandom Environments. World Scientific, Teaneck, NJ. · Zbl 0733.60091
[19] Sinaï, Ya. G. (1982). The limiting behavior of one-dimensional random walk in random medium. Theory Probab. Appl. 27 256-268. · Zbl 0505.60086 · doi:10.1137/1127028
[20] Solomon, F. (1975). Random walks in a random environment. Ann. Probab. 3 1-31. · Zbl 0305.60029 · doi:10.1214/aop/1176996444
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.