Asymptotics of first-passage percolation on 1-dimensional graphs

Mathematics – Probability

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

In this paper we consider standard first-passage percolation on certain 1-dimensional periodic graphs. One such graph of particular interest is the $\Z\times\{0,1,...,K-1\}^{d-1}$ nearest neighbour graph for $d,K\geq1$. Let $T(u,v)$ denote the time it takes for an infection started at $u$ to reach $v$, and let $N(u,v)$ denote the length of the geodesic (path with minimal passage time) from $u$ to $v$. We derive asymptotic results that show how the behaviour of first-passage percolation on 1-dimensional graphs differ from what is known or expected in higher dimensions. Let $\mathbf{n}=(n,0,...,0)$. By subadditivity $T(0,\mathbf{n})/n\raw\mu$ for some $\mu>0$ as $n\raw\infty$, almost surely and in $L^1$. We show that for some $\sigma>0$, as $n\raw\infty$, $\big(T(0,\mathbf{n})-\mu n\big)/\sigma\sqrt{n}$ converges in distribution to a standard normal, and moreover, that $\limsup_{n\raw\infty}\big(T(0,\mathbf{n})-\mu n\big)/\sigma\sqrt{2n\log\log n}=1$, almost surely. We further prove that $\E\big[T(0,\mathbf{n})\big]$ and $\Var\big(T(0,\mathbf{n})\big)$ are monotonic in $n$, for large enough $n$. Results for $N(0,\mathbf{n})$ corresponding to the results mentioned for $T(0,\mathbf{n})$ are also derived. We also allow different sets of initially infected vertices, and construct an exact coupling of two infections with different starting configurations. Using this coupling we prove a 0--1 law.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Asymptotics of first-passage percolation on 1-dimensional graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotics of first-passage percolation on 1-dimensional graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotics of first-passage percolation on 1-dimensional graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-565452

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.