Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Hsu-Robbins-ErdH{o}s strong law in first-passage percolation
149
0
0.0
(
0
)
Authors
Daniel Ahlberg
Ask ChatGPT about the research
No Arabic abstract
Large deviations in the context of first-passage percolation was first studied in the early 1980s by Grimmett and Kesten, and has since been revisited in a variety of studies. However, none of these studies provides a precise relation between the existence of moments of polynomial order and the decay of probability tails. Such a relation is derived in this paper, and is used to strengthen the conclusion of the shape theorem. In contrast to its one-dimensional counterpart - the Hsu-Robbins-ErdH{o}s strong law - this strengthening is obtained without imposing a higher-order moment condition.
rate research
Read More
We study first-passage percolation where edges in the left and right half-planes are assigned values according to different distributions. We show that the asymptotic growth of the resulting inhomogeneous first-passage process obeys a shape theorem, and we express the limiting shape in terms of the limiting shapes for the homogeneous processes for the two weight distributions. We further show that there exist pairs of distributions for which the rate of growth in the vertical direction is strictly larger than the rate of growth of the homogeneous process with either of the two distributions, and that this corresponds to the creation of a defect along the vertical axis in the form of a `pyramid.
We consider first-passage percolation with i.i.d. non-negative weights coming from some continuous distribution under a moment condition. We review recent results in the study of geodesics in first-passage percolation and study their implications for the multi-type Richardson model. In two dimensions this establishes a dual relation between the existence of infinite geodesics and coexistence among competing types. The argument amounts to making precise the heuristic that infinite geodesics can be thought of as `highways to infinity. We explain the limitations of the current techniques by presenting a partial result in dimensions higher than two.
In this paper we consider the first passage percolation with identical and independent exponentially distributions, called the Eden growth model, and we study the upper tail large deviations for the first passage time ${rm T}$. Our main results prove that for any $xi>0$ and $x eq 0$, $mathbb{P}({rm T}(0,nx)>n(mu+xi))$ decays as $exp{(-(2dxi +o(1))n)}$ with a time constant $mu$ and a dimension $d$. Moreover, we extend the result to stretched exponential distributions. On the contrary, we construct a continuous distribution with a finite exponential moment where the rate function does not exist.
Consider first passage percolation with identical and independent weight distributions and first passage time ${rm T}$. In this paper, we study the upper tail large deviations $mathbb{P}({rm T}(0,nx)>n(mu+xi))$, for $xi>0$ and $x eq 0$ with a time constant $mu$ and a dimension $d$, for weights that satisfy a tail assumption $ beta_1exp{(-alpha t^r)}leq mathbb P(tau_e>t)leq beta_2exp{(-alpha t^r)}.$ When $rleq 1$ (this includes the well-known Eden growth model), we show that the upper tail large deviation decays as $exp{(-(2dxi +o(1))n)}$. When $1< rleq d$, we find that the rate function can be naturally described by a variational formula, called the discrete p-Capacity, and we study its asymptotics. For $r<d$, we show that the large deviation event ${rm T}(0,nx)>n(mu+xi)$ is described by a localization of high weights around the origin. The picture changes for $rgeq d$ where the configuration is not anymore localized.
One model of real-life spreading processes is First Passage Percolation (also called SI model) on random graphs. Social interactions often follow bursty patterns, which are usually modelled with i.i.d.~heavy-tailed passage times on edges. On the other hand, random graphs are often locally tree-like, and spreading on trees with leaves might be very slow, because of bottleneck edges with huge passage times. Here we consider the SI model with passage times following a power law distribution $mathbb{P}(xi>t)sim t^{-alpha}$, with infinite mean. For any finite connected graph $G$ with a root $s$, we find the largest number of vertices $kappa(G,s)$ that are infected in finite expected time, and prove that for every $k leq kappa(G,s)$, the expected time to infect $k$ vertices is at most $O(k^{1/alpha})$. Then, we show that adding a single edge from $s$ to a random vertex in a random tree $mathcal{T}$ typically increases $kappa(mathcal{T},s)$ from a bounded variable to a fraction of the size of $mathcal{T}$, thus severely accelerating the process. We examine this acceleration effect on some natural models of random graphs: critical Galton-Watson trees conditioned to be large, uniform spanning trees of the complete graph, and on the largest cluster of near-critical ErdH{o}s-Renyi graphs. In particular, at the upper end of the critical window, the process is already much faster than exactly at criticality.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
