0
$\begingroup$

Can someone please provide a reference (starting point) for analysing recurrence/transience of random walks on graphs with general edge weights? Looking into random walks that are known to be NOT reversible.

Improve this question
$\endgroup$
1
  • $\begingroup$ How are the transition probabilities related to the edge weights? $\endgroup$
    – R W
    Commented Jan 20, 2022 at 0:08

1 Answer 1

Reset to default
0
$\begingroup$

The most powerful and flexible method to prove recurrence or transience for nonreversible walks is the method of Lyapunov functions. One of the origins of the method is Foster's criteria for recurrence and positive recurrence. [1], [2]. See Theorem 1 page 2 in [3] (or page 40 of [9]) for a concise statement of the recurrence criterion. The method is expounded with many examples and references in the books [4], [5], [6]. Some specific applications to delicate problems are in [3], [4].

[1] F. G. Foster: On the stochastic matrices associated with certain queuing processes. Ann. Math. Statistics 24 (1953) 355–360.

[2] https://en.wikipedia.org/wiki/Foster%27s_theorem

[3] https://mathweb.ucsd.edu/~pfitz/downloads/courses/spring05/math280c/foster.pdf

[4] Fayolle, Guy, Vadim Aleksandrovich Malyshev, and Mikhail Vasilʹevich Menʹshikov. Topics in the constructive theory of countable Markov chains. Cambridge university press, 1995.

[5] Menshikov, Mikhail, Serguei Popov, and Andrew Wade. Non-homogeneous random walks: Lyapunov function methods for near-critical stochastic systems. Vol. 209. Cambridge University Press, 2016.

[6] S.P. Meyn and R.L. Tweedie: Markov Chains and Stochastic Stability. SpringerVerlag, London, 1993.

[7] Asymont, Inna M., Guy Fayolle, and Μ. V. Menshikov. "Random walks in a quarter plane with zero drifts: transience and recurrence." Journal of applied probability 32, no. 4 (1995): 941-955.

[8] Peres, Yuval, Serguei Popov, and Perla Sousi. "On recurrence and transience of self-interacting random walks." Bulletin of the Brazilian Mathematical Society, New Series 44, no. 4 (2013): 841-867.

[9] https://www.math.stonybrook.edu/~rdhough/mat639-spring17/lectures/lecture12.pdf

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .