 Self-switching random walks on Erdös–Rényi random graphs feel the phase transitionG. Iacobelli, G. Ost and D.Y. Takahashi Stochastic Processes and their Applications, 2025, vol. 183, issue C Abstract: We study random walks on Erdös–Rényi random graphs in which, every time the random walk returns to the starting point, first an edge probability is independently sampled according to a priori measure μ, and then an Erdös–Rényi random graph is sampled according to that edge probability. When the edge probability p does not depend on the size of the graph n (dense case), we show that the proportion of time the random walk spends on different values of p – occupation measure – converges to the a priori measure μ as n goes to infinity. More interestingly, when p=λ/n (sparse case), we show that the occupation measure converges to a limiting measure with a density that is a function of the survival probability of a Poisson branching process. This limiting measure is supported on the supercritical values for the Erdös–Rényi random graphs, showing that self-witching random walks can detect the phase transition. Keywords: Random graphs; Phase transition; Random walks; Self-switching Markov chains (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:183:y:2025:i:c:s0304414925000304 Ordering information: This journal article can be ordered from DOI: 10.1016/j.spa.2025.104589 Access Statistics for this article Stochastic Processes and their Applications is currently edited by T. Mikosch More articles in Stochastic Processes and their Applications from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.