Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T16:53:26.005Z Has data issue: false hasContentIssue false
  • English
  • Français

Out-of-equilibrium random walks

Part of: Markov processes Limit theorems

Published online by Cambridge University Press:  24 September 2020

Leonardo A. Videla
Leonardo A. Videla*
Affiliation:
Universidad de Valparaíso
*
*Postal address: Instituto de Ingeniería Matemática - CIMFAV, General Cruz 222, 5th floor, Valparaíso, Chile. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the long-term behaviour of a random walker embedded in a growing sequence of graphs. We define a (generally non-Markovian) real-valued stochastic process, called the knowledge process, that represents the ratio between the number of vertices already visited by the walker and the current size of the graph. We mainly focus on the case where the underlying graph sequence is the growing sequence of complete graphs.

Keywords

Random walksgrowing graphsasymptotics

MSC classification

Primary: 60J28: Applications of continuous-time Markov processes on discrete state spaces
Secondary: 60F15: Strong theorems 60F25: $L^p$-limit theorems
Type
Original Article
Information
Advances in Applied Probability , Volume 52 , Issue 3 , September 2020 , pp. 772 - 797
Check for updates
Copyright
© Applied Probability Trust 2020

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

Aldous, K. and Fill, J. (1999). Reversible Markov Chains and Random Walks on Graphs. Unpublished manuscript. Available at http://www.stat.berkeley.edu/aldous/RWG/book.html.Google Scholar
Aleliunas, R. et al. (1979). Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science, IEEE Computer Science, Washington, DC, pp. 218–223.CrossRefGoogle Scholar
Amir, G., Benjamini, I., Gurel-Gurevich, O. and Kozma, G. (2017). Random walks in changing environment. Preprint. Available at https://arxiv.org/abs/1504.04870.Google Scholar
Avin, C., Koucký, M. and Lotker, Z. (2008). How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In Automata, Languages and Programming, Springer, Berlin, pp. 121–132.CrossRefGoogle Scholar
Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.CrossRefGoogle ScholarPubMed
Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18, 279–290.CrossRefGoogle Scholar
Cooper, C. and Frieze, A. (2003). Crawling on simple models of Web graphs. Internet Math. 1, 57–90.10.1080/15427951.2004.10129078CrossRefGoogle Scholar
Cooper, C. and Frieze, A. (2007). The cover time of the preferential attachment graph. J. Combinatorial Theory 97, 269–290.CrossRefGoogle Scholar
De Bacco, C., Majumdar, S. and Sollich, P. (2015). The average number of distinct sites visited by a random walker on random graphs. Preprint. Available at https://arxiv.org/abs/1501.01528v2.Google Scholar
Dembo, A., Huang, R. and Sidoravicius, V. (2014). Walking within growing domains: recurrence versus transience. Electron. J. Prob. 19, 1–20.CrossRefGoogle Scholar
Ding, J., Lee, J. R. and Peres, Y. (2012). Cover times, blanket times, and majorizing measures. Ann. Math. 175, 1409–1471.CrossRefGoogle Scholar
Dvoretzky, A. and Erdős, P. (1951). Some problems on random walk in space. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, pp. 353–367.Google Scholar
Levin, D., Peres, Y. and Wilmer, E. (2017). Markov Chains and Mixing Times, 2nd edn. American Mathematical Society, Providence, RI.CrossRefGoogle Scholar
Lovász, L. (1996). Random walks on graphs: a survey. In Combinatorics, Paul Erdős is Eighty, János Bolyai Mathematical Society, Budapest, pp. 353–398.Google Scholar
Matthews, P. (1988). Covering problems for Brownian motion on spheres. Ann. Prob. 16, 189–199.CrossRefGoogle Scholar
Spitzer, F. (1976). Principles of Random Walks. Springer, New York.CrossRefGoogle Scholar