More Like this

1. Local Access to Random Walks , January 2022

   Biswas, A.S.; Pyne, E.; Rubinfeld, R. (January 2022, Innovations in Theoretical Computer Science (ITCS 2022))

   For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting positionG(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/ poly(n) close to those of a uniformly random walk in ℓ1 distance. We first give an algorithm for local access to random walks on a given undirected d-regular graph with eO( 1 1−λ √ n) runtime per query, where λ is the second-largest eigenvalue of the random walk matrix of the graph in absolute value. Since random d-regular graphs G(n, d) are expanders with high probability, this gives an eO(√ n) algorithm for a graph drawn from G(n, d) whp, which improves on the naive method for small numbers of queries. We then prove that no algorithm with subconstant error given probe access to an input d-regular graph can have runtime better than Ω(√ n/ log(n)) per query in expectation when the input graph is drawn from G(n, d), obtaining a nearly matching lower bound. We further show an Ω(n1/4) runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance). We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime polylog(n) per query. This also allows for efficient local access to walks on polylog degree expanders. We show that our techniques apply to graphs with high degree by extending or results to graphs constructed using the tensor product (giving fast local access to walks on degree nϵ graphs for any ϵ ∈ (0, 1]) and Cartesian product. 

   more » « less
2. Limit Theorems for Some Long Range Random Walks on Torsion Free Nilpotent Groups

   Chen, Zhen-Qing; Kumagai, Takashi; Saloff-Coste, Laurent; Wang, Jian; Zheng, Tianyi (July 2023, Springer)

   This book develops limit theorems for a natural class of long range random walks on finitely generated torsion free nilpotent groups. The limits in these limit theorems are Lévy processes on some simply connected nilpotent Lie groups. Both the limit Lévy process and the limit Lie group carrying this process are determined by and depend on the law of the original random walk. The book offers the first systematic study of such limit theorems involving stable-like random walks and stable limit Lévy processes in the context of (non-commutative) nilpotent groups. 

   more » « less
3. Joint localization of directed polymers

   https://doi.org/10.1214/23-EJP1000  

   Bakhtin, Yuri; Dow, Douglas (January 2023, Electronic Journal of Probability)

   We consider (1 + 1)-dimensional directed polymers in a random potential and provide sufficient conditions guaranteeing joint localization. Joint localization means that for typical realizations of the environment, and for polymers started at different starting points, all the associated endpoint distributions localize in a common random region that does not grow with the length of the polymer. In particular, we prove that joint localization holds when the reference random walk of the polymer model is either a simple symmetric lattice walk or a Gaussian random walk. We also prove that the very strong disorder property holds for a large class of space-continuous polymer models, implying the usual single polymer localization. 

   more » « less
4. On the trace of random walks on random graphs

   Frieze, A; Krivelevich, M; Michaeli, P; Peled, R (January 2017, Journal of the London Mathematical Society)

   We study graph-theoretic properties of the trace of a random walk on a random graph. We show that for any $$\varepsilon>0$$ there exists $C>1$ such that the trace of the simple random walk of length $$(1+\varepsilon)n\ln{n}$$ on the random graph $$G\sim\gnp$$ for $$p>C\ln{n}/n$$ is, with high probability, Hamiltonian and $$\Theta(\ln{n})$$-connected. In the special case $p=1$$ (i.e.\ when $$G=K_n$), we show a hitting time result according to which, with high probability, exactly one step after the last vertex has been visited, the trace becomes Hamiltonian, and one step after the last vertex has been visited for the $$k$$'th time, the trace becomes $2k$-connected. 

   more » « less
5. Universal exploration dynamics of random walks

   https://doi.org/10.1038/s41467-023-36233-5  

   Régnier, Léo; Dolgushev, Maxim; Redner, S.; Bénichou, Olivier (December 2023, Nature Communications)

   Abstract The territory explored by a random walk is a key property that may be quantified by the number of distinct sites that the random walk visits up to a given time. We introduce a more fundamental quantity, the time τ n required by a random walk to find a site that it never visited previously when the walk has already visited n distinct sites, which encompasses the full dynamics about the visitation statistics. To study it, we develop a theoretical approach that relies on a mapping with a trapping problem, in which the spatial distribution of traps is continuously updated by the random walk itself. Despite the geometrical complexity of the territory explored by a random walk, the distribution of the τ n can be accounted for by simple analytical expressions. Processes as varied as regular diffusion, anomalous diffusion, and diffusion in disordered media and fractals, fall into the same universality classes. 

   more » « less