An official website of the United States government
We examine a class of random walks in random environments on Z with bounded jumps, a generalization of the classic one-dimensional model. The environments we study have i.i.d. transition probability vectors drawn from Dirichlet distributions. For the transient case of this model, we characterize ballisticity: nonzero limiting velocity. We do this in terms of two parameters, κ0 and κ1. The parameter κ0 governs finite trapping effects. The parameter κ1, which already is known to characterize directional transience, also governs repeated traversals of arbitrarily large regions of the graph. We show that the walk is ballistic if and only if min(κ0, κ1) > 1. We prove some stronger results regarding moments of the quenched Green function and other functions that the quenched Green function dominates. These results help us to better understand the phenomena and parameters affecting ballisticity.
more »
« less
This content will become publicly available on September 29, 2026
Existence of generalized Busemann functions and Gibbs measures for random walks in random potentials
We establish the existence of generalized Busemann functions and Gibbs-Dobrushin-Landford-Ruelle measures for a general class of lattice random walks in random potentials with finitely many admissible steps. This class encompasses directed polymers in random environments, first- and last-passage percolation, and elliptic random walks in both static and dynamic random environments in all dimensions and with minimal assumptions on the random potential.
more »
« less
- PAR ID:
- 10583025
- Publisher / Repository:
- Transactions of the American Mathematical Society
- Date Published:
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
We compute the eigenvalue fluctuations of uniformly distributed random biregular bipartite graphs with fixed and growing degrees for a large class of analytic functions. As a key step in the proof, we obtain a total variation distance bound for the Poisson approximation of the number of cycles and cyclically non-backtracking walks in random biregular bipartite graphs, which might be of independent interest. We also prove a semicircle law for random [Formula: see text]-biregular bipartite graphs when [Formula: see text]. As an application, we translate the results to adjacency matrices of uniformly distributed random regular hypergraphs.more » « less
-
The random order graph streaming model has received significant attention recently, with problems such as matching size estimation, component counting, and the evaluation of bounded degree constant query testable properties shown to admit surprisingly space efficient algorithms. The main result of this paper is a space efficient single pass random order streaming algorithm for simulating nearly independent random walks that start at uniformly random vertices. We show that the distribution of k-step walks from b vertices chosen uniformly at random can be approximated up to error ∊ per walk using  words of space with a single pass over a randomly ordered stream of edges, solving an open problem of Peng and Sohler [SODA '18]. Applications of our result include the estimation of the average return probability of the k-step walk (the trace of the kth power of the random walk matrix) as well as the estimation of PageRank. We complement our algorithm with a strong impossibility result for directed graphs.more » « less
-
Abstract We investigate the statistical learning of nodal attribute functionals in homophily networks using random walks. Attributes can be discrete or continuous. A generalization of various existing canonical models, based on preferential attachment is studied (model class $$\mathscr {P}$$ P ), where new nodes form connections dependent on both their attribute values and popularity as measured by degree. An associated model class $$\mathscr {U}$$ U is described, which is amenable to theoretical analysis and gives access to asymptotics of a host of functionals of interest. Settings where asymptotics for model class $$\mathscr {U}$$ U transfer over to model class $$\mathscr {P}$$ P through the phenomenon of resolvability are analyzed. For the statistical learning, we consider several canonical attribute agnostic sampling schemes such as Metropolis-Hasting random walk, versions of node2vec (Grover and Leskovec, 2016) that incorporate both classical random walk and non-backtracking propensities and propose new variants which use attribute information in addition to topological information to explore the network. Estimators for learning the attribute distribution, degree distribution for an attribute type and homophily measures are proposed. The performance of such statistical learning framework is studied on both synthetic networks (model class $$\mathscr {P}$$ P ) and real world systems, and its dependence on the network topology, degree of homophily or absence thereof, (un)balanced attributes, is assessed.more » « less
