We study the rate of convergence in the Shape Theorem of first-passage percolation, obtaining the precise asymptotic rate of decay for the probability of linear order deviations under a moment condition. Our results are stated for a given time and co
mplements recent work by the same author, in which the rate of convergence was studied from the standard spatial perspective.
Consider a monotone Boolean function $f:{0,1}^nto{0,1}$ and the canonical monotone coupling ${eta_p:pin[0,1]}$ of an element in ${0,1}^n$ chosen according to product measure with intensity $pin[0,1]$. The random point $pin[0,1]$ where $f(eta_p)$ flip
s from $0$ to $1$ is often concentrated near a particular point, thus exhibiting a threshold phenomenon. For a sequence of such Boolean functions, we peer closely into this threshold window and consider, for large $n$, the limiting distribution (properly normalized to be nondegenerate) of this random point where the Boolean function switches from being 0 to 1. We determine this distribution for a number of the Boolean functions which are typically studied and pay particular attention to the functions corresponding to iterated majority and percolation crossings. It turns out that these limiting distributions have quite varying behavior. In fact, we show that any nondegenerate probability measure on $mathbb{R}$ arises in this way for some sequence of Boolean functions.
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.
Let $mathcal{H}$ denote a collection of subsets of ${1,2,ldots,n}$, and assign independent random variables uniformly distributed over $[0,1]$ to the $n$ elements. Declare an element $p$-present if its corresponding value is at most $p$. In this pape
r, we quantify how much the observation of the $r$-present ($r>p$) set of elements affects the probability that the set of $p$-present elements is contained in $mathcal{H}$. In the context of percolation, we find that this question is closely linked to the near-critical regime. As a consequence, we show that for every $r>1/2$, bond percolation on the subgraph of the square lattice given by the set of $r$-present edges is almost surely noise sensitive at criticality, thus generalizing a result due to Benjamini, Kalai and Schramm.
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 exi
stence 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.
In this note we study some properties of infinite percolation clusters on non-amenable graphs. In particular, we study the percolative properties of the complement of infinite percolation clusters. An approach based on mass-transport is adapted to sh
ow that for a large class of non-amenable graphs, the graph obtained by removing each site contained in an infinite percolation cluster has critical percolation threshold which can be arbitrarily close to the critical threshold for the original graph, almost surely, as p approaches p_c. Closely related is the self-destructive percolation process, introduced by J. van den Berg and R. Brouwer, for which we prove that an infinite cluster emerges for any small reinforcement.
