Path Counting on Tree-like Graphs with a Single Entropic Trap: Critical Behavior and Finite Size Effects

• Published in: Entropy (Basel, Switzerland) Switzerland), 2023-09, Vol.25 (9), p.1318
• Main Authors: Gulyaev, Alexey V., Tamm, Mikhail V.
• Format: Article
• Language: English
• Subjects: Bias; Brownian motion; critical slowdown; Distribution (Probability theory); Distribution functions; Eigenvalues; Eigenvectors; Graphs; Localization; localization transition; maximal entropy random walk; Partitions (mathematics); path counting; Polymers; Probability; Probability distribution; Probability distribution functions; Random walk; Size effects; Step functions; Trees (mathematics)
• ISSN: 1099-4300; 1099-4300
• DOI: 10.3390/e25091318

It is known that maximal entropy random walks and partition functions that count long paths on graphs tend to become localized near nodes with a high degree. Here, we revisit the simplest toy model of such a localization: a regular tree of degree p with one special node (“root”) that has a degree different from all the others. We present an in-depth study of the path-counting problem precisely at the localization transition. We study paths that start from the root in both infinite trees and finite, locally tree-like regular random graphs (RRGs). For the infinite tree, we prove that the probability distribution function of the endpoints of the path is a step function. The position of the step moves away from the root at a constant velocity v=(p−2)/p. We find the width and asymptotic shape of the distribution in the vicinity of the shock. For a finite RRG, we show that a critical slowdown takes place, and the trajectory length needed to reach the equilibrium distribution is on the order of N instead of logp−1N away from the transition. We calculate the exact values of the equilibrium distribution and relaxation length, as well as the shapes of slowly relaxing modes.