Percolation with edge-passage probability $p$ and first-passage percolation are studied for the $n$-cube $\mathscr{B}_n = \{0, 1\}^n$ with nearest neighbor edges. For oriented and unoriented percolation, $p = e/n$ and $p = 1/n$ are the respective critical probabilities. For oriented first-passage percolation with i.i.d. edge-passage times having a density of 1 near the origin, the percolation time (time to reach the opposite corner of the cube) converges in probability to 1 as $n \rightarrow \infty$. This resolves a conjecture of Aldous. When the edge-passage distribution is standard exponential, the (smaller) percolation time for unoriented edges is at least 0.88. These results are applied to Richardson's model on the (unoriented) $n$-cube. Richardson's model, otherwise known as the contact process with no recoveries, models the spread of infection as a Poisson process on each edge connecting an infected node to an uninfected one. It is shown that the time to cover the entire $n$-cube is bounded between 1.41 and 14.05 in probability as $n \rightarrow \infty$.
Publié le : 1993-05-14
Classification:
Richardson's model,
$n$-cube,
percolation,
oriented percolation,
first-passage percolation,
large deviations,
broadcasting,
60K35,
60C05
@article{1177005440,
author = {Fill, James Allen and Pemantle, Robin},
title = {Percolation, First-Passage Percolation and Covering Times for Richardson's Model on the $n$-Cube},
journal = {Ann. Appl. Probab.},
volume = {3},
number = {4},
year = {1993},
pages = { 593-629},
language = {en},
url = {http://dml.mathdoc.fr/item/1177005440}
}
Fill, James Allen; Pemantle, Robin. Percolation, First-Passage Percolation and Covering Times for Richardson's Model on the $n$-Cube. Ann. Appl. Probab., Tome 3 (1993) no. 4, pp. 593-629. http://gdmltest.u-ga.fr/item/1177005440/