An official website of the United States government
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
Universal exploration dynamics of random walks
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
- Award ID(s):
- 1910736
- PAR ID:
- 10406469
- Date Published:
- Journal Name:
- Nature Communications
- Volume:
- 14
- Issue:
- 1
- ISSN:
- 2041-1723
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The frog model is a branching random walk on a graph in which particles branch only at unvisited sites. Consider an initial particle density of $$\unicode[STIX]{x1D707}$$ on the full $$d$$ -ary tree of height $$n$$ . If $$\unicode[STIX]{x1D707}=\unicode[STIX]{x1D6FA}(d^{2})$$ , all of the vertices are visited in time $$\unicode[STIX]{x1D6E9}(n\log n)$$ with high probability. Conversely, if $$\unicode[STIX]{x1D707}=O(d)$$ the cover time is $$\exp (\unicode[STIX]{x1D6E9}(\sqrt{n}))$$ with high probability.more » « less
-
null (Ed.)In the parking model on ℤd, each vertex is initially occupied by a car (with probability p) or by a vacant parking spot (with probability 1−p). Cars perform independent random walks and when they enter a vacant spot, they park there, thereby rendering the spot occupied. Cars visiting occupied spots simply keep driving (continuing their random walk). It is known that p=1/2 is a critical value in the sense that the origin is a.s. visited by finitely many distinct cars when p<1/2, and by infinitely many distinct cars when p≥1/2. Furthermore, any given car a.s. eventually parks for p≤1/2 and with positive probability does not park for p>1/2. We study the subcritical phase and prove that the tail of the parking time τ of the car initially at the origin obeys the bounds exp(−C1tdd+2)≤ℙp(τ>t)≤exp(−c2tdd+2) for p>0 sufficiently small. For d=1, we prove these inequalities for all p∈[0,1/2). This result presents an asymmetry with the supercritical phase (p>1/2), where methods of Bramson--Lebowitz imply that for d=1 the corresponding tail of the parking time of the parking spot of the origin decays like e−ct√. Our exponent d/(d+2) also differs from those previously obtained in the case of moving obstacles.more » « less
-
A reaction limited by standard diffusion is simulated stochastically to illustrate how the continuous time random walk (CTRW) formalism can be implemented with minimum statistical error. A step-by-step simulation of the diffusive random walk in one dimension reveals the fraction of surviving reactants P(t) as a function of time, and the time-dependent unimolecular reaction rate coefficient K(t). Accuracy is confirmed by comparing the time-dependent simulation to results from the analytical master equation, and the asymptotic solution to that of Fickian diffusion. An early transient feature is shown to arise from higher spatial harmonics in the Fourier distribution of walkers between reaction sites. Statistical ‘shot’ noise in the simulation is quantified along with the offset error due to the discrete time derivative, and an optimal simulation time interval t0 is derived to achieve minimal error in the finite time-difference estimation of the reaction rate. The number of walkers necessary to achieve a given error tolerance is derived, and W = 10^7 walkers is shown to achieve an accuracy of ±0.2% when the survival probability reaches P(t) ∼ 1/3 . The stochastic method presented here serves as an intuitive basis for understanding the CTRW formalism, and can be generalized to model anomalous diffusion-limited reactions to prespecified precision in regimes where the governing wait-time distributions have no analytical solution.more » « less
-
null (Ed.)Consider an algorithm performing a computation on a huge random object (for example a random graph or a "long" random walk). Is it necessary to generate the entire object prior to the computation, or is it possible to provide query access to the object and sample it incrementally "on-the-fly" (as requested by the algorithm)? Such an implementation should emulate the random object by answering queries in a manner consistent with an instance of the random object sampled from the true distribution (or close to it). This paradigm is useful when the algorithm is sub-linear and thus, sampling the entire object up front would ruin its efficiency. Our first set of results focus on undirected graphs with independent edge probabilities, i.e. each edge is chosen as an independent Bernoulli random variable. We provide a general implementation for this model under certain assumptions. Then, we use this to obtain the first efficient local implementations for the Erdös-Rényi G(n,p) model for all values of p, and the Stochastic Block model. As in previous local-access implementations for random graphs, we support Vertex-Pair and Next-Neighbor queries. In addition, we introduce a new Random-Neighbor query. Next, we give the first local-access implementation for All-Neighbors queries in the (sparse and directed) Kleinberg’s Small-World model. Our implementations require no pre-processing time, and answer each query using O(poly(log n)) time, random bits, and additional space. Next, we show how to implement random Catalan objects, specifically focusing on Dyck paths (balanced random walks on the integer line that are always non-negative). Here, we support Height queries to find the location of the walk, and First-Return queries to find the time when the walk returns to a specified location. This in turn can be used to implement Next-Neighbor queries on random rooted ordered trees, and Matching-Bracket queries on random well bracketed expressions (the Dyck language). Finally, we introduce two features to define a new model that: (1) allows multiple independent (and even simultaneous) instantiations of the same implementation, to be consistent with each other without the need for communication, (2) allows us to generate a richer class of random objects that do not have a succinct description. Specifically, we study uniformly random valid q-colorings of an input graph G with maximum degree Δ. This is in contrast to prior work in the area, where the relevant random objects are defined as a distribution with O(1) parameters (for example, n and p in the G(n,p) model). The distribution over valid colorings is instead specified via a "huge" input (the underlying graph G), that is far too large to be read by a sub-linear time algorithm. Instead, our implementation accesses G through local neighborhood probes, and is able to answer queries to the color of any given vertex in sub-linear time for q ≥ 9Δ, in a manner that is consistent with a specific random valid coloring of G. Furthermore, the implementation is memory-less, and can maintain consistency with non-communicating copies of itself.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1038/s41467-023-36233-5
