Mathematics – Probability
Scientific paper
2011-07-12
Mathematics
Probability
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
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.
Profile ID: LFWR-SCP-O-565452