Percolation, first-passage percolation, and covering times for Richardson's model on the n-cube
| dc.creator | Fill, James Allen | |
| dc.creator | Pemantle, Robin | |
| dc.date | 2004-04-01 | |
| dc.date.accessioned | 2026-07-07T05:06:58Z | |
| dc.date.available | 2026-07-07T05:06:58Z | |
| dc.description | Percolation with edge-passage probability p and first-passage percolation are studied for the n-cube 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->infty. This resolves a conjecture of David 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->infty. | |
| dc.description | 51 pages | |
| dc.identifier | https://arxiv.org/abs/math/0404015 | |
| dc.identifier | http://arxiv.org/abs/math/0404015 | |
| dc.identifier | Ann. Appl. Prob., 3, 593 - 629 (1993) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70679 | |
| dc.subject | Probability | |
| dc.subject | Primary 60K35 (Primary), 60C05 (secondary) | |
| dc.title | Percolation, first-passage percolation, and covering times for Richardson's model on the n-cube | |
| dc.type | text |