Skip to main content Skip to navigation

Stochastic Growth Models

Authors: Adam Bowditch, John Sylvester and Qiaochu Chen
Supervisors: Nikolaos Zygouras and Partha Dey.

We consider a long-range first-passage percolation model on the lattice$\; $ $\mathbb{Z}^2 $ from 'Multiple phase transitions in long-range first passage percolation' under a specific class of distributions supported away from $0$ as in 'Strict inequalities for the time constant in first passage percolation'. We have shown that in the critical and supercritical cases that the limiting shape of an appropriately scaled growth set is the unit $l^1$ ball and in the subcritical case a limiting shape exists and that under some assumptions this deterministic shape has a flat piece which coincides with that of the nearest neighbour model.

This is a simulation of the growth set evolving over time in the supercritical regime.



\[\mathcal{E}' := \{ \langle\mathbf{x},\mathbf{z}\rangle : \mathbf{x},\mathbf{z} \in \mathbb{Z}^2, \mathbf{x} \neq \mathbf{z} \}\]

be the edge set for the infinite complete graph on $\mathbb{Z}^2$. To each $ e \in \mathcal{E}'$ we assign an independent random weight $\omega_e$, where $\{\omega_e\}_{e \in \mathcal{E}'}$ are i.i.d. with common distribution

\[\mu \in \mathcal{M}_p:=\{\mu \in \mathcal{M}: supp(\mu)\subseteq [1,\infty), \; \mu(\{1\})=p>0\}\].

We fix $\alpha>0$ then the random variable

\[W_e := \omega_e||e||^\alpha \]

represents the passage-time through the edge $e$. For $\pi$, a finite $\mathcal{E}'$-path, we define the corresponding passage-time to be

\[ W_\pi := \sum\limits_{e \in \pi} W_e = \sum\limits_{e \in \pi } \omega_e||e||^\alpha \]

Based on these $W_\pi$, the first-passage time to reach $\mathbf{x} \in\mathbb{Z}^2$ from $\mathbf{z} \in\mathbb{Z}^2$ is defined to be the minimum passage-time over all finite $\mathcal{E}'$-paths from $\mathbf{x}$ to $\mathbf{z}$:

\[ T^{(\alpha)}(\mathbf{x},\mathbf{z}) := \inf\{W_\pi |\pi \in \mathcal{P}'_{\mathbf{x},\mathbf{z}}\}\]

where $\mathcal{P}'_{\mathbf{x},\mathbf{z}}$ is the set of all finite $\mathcal{E}'$-paths from $\mathbf{x}$ to $\mathbf{z}$. This defines a random metric on $\mathbb{Z}^2$ which we refer to as the LRFPP metric. Using this first-passage time define the growth set

\[\mathcal{B}^{(\alpha)}_t = \{\mathbf{x} \in \mathbb{Z}^2 : T^{(\alpha)}(\mathbf{0},\mathbf{x}) \leq t\}\]

which is the ball of radius $t>0$ in this metric.

Cox & Durrett have shown, in their paper 'Some limit theorems for percolation with necessary and sufficient conditions', that in the nearest neighbour case where we use the edge set

\[\mathcal{E} := \{ \langle\mathbf{x},\mathbf{z}\rangle : \mathbf{x},\mathbf{z} \in \mathbb{Z}^d, ||\mathbf{x}- \mathbf{z}||=1 \}\]

that there exists a deterministic limiting shape $A_\mu$ such that for any $\varepsilon>0$ we have that

\[ \mathbb{P}\left[ (1-\varepsilon) A_\mu \subseteq t^{-1}\mathcal{B}_t \subseteq (1+\varepsilon) A_\mu \; \forall \text{ large } t\right] =1\]

Marchand, in her paper 'Strict inequalities for the time constant in first passage percolation', (among others) have extended this result to characterise the existence of a flat piece on the boundary of $A_\mu$. In particular letting $\overrightarrow{p_c}$ denote the critical threshold for oriented bond percolation in $\mathbb{Z}^2$ and $\varphi_p$ the asymptotic growth speed of the oriented percolation, we can write $I_p$ to be the line segment connecting $M_p:=(1/2-\varphi_p/\sqrt{2}, 1/2+\varphi_p/\sqrt{2}),N_p:=(1/2+\varphi_p/\sqrt{2}, 1/2-\varphi_p/\sqrt{2})$ we have that

If $\mu \in \mathcal{M}_p$ then,

  1. $A_\mu\subseteq B_1$.
  2. If $p <\overrightarrow{p_{c}}$ then $A_\mu \subseteq B_1^\circ$.
  3. If $p >\overrightarrow{p_{c}}$ then $A_\mu\cap [0,\infty)^2 \cap \partial B_1 =I_p$.
  4. If $p =\overrightarrow{p_{c}}$ then $A_\mu\cap [0,\infty)^2 \cap \partial B_1 = (\frac{1}{2}, \frac{1}{2})$.

We extend these results to the long-range model for three distinct cases depending on the value of $\alpha$.


  • J.M. Hammersley, D.J.A. Welsh. First-passage percolation, subadditive processes, stochastic networks and generalized renewal theory. Proc. Internat. Res. Semin., Statist. Lab. Univ. California, Berkeley, Calif., pages 61 –110, 1965.
  • J.T. Cox, R. Durrett. Some limit theorems for percolation with necessary and sufficient conditions. Ann. Appl. Probab., 9:583–603, 1981.
  • Marchand, R. Strict inequalities for the time constant in first passage percolation. Ann. Appl. Probab., 12:1001–1038, 2002.
  • S. Chatterjee, P. Dey. Multiple phase transitions in long-range first-passage percolation on square lattices. preprint.


We acknowledge and thank the help of our supervisors Dr Nikolaos Zygouras and Dr Partha Dey.
We also acknowledge the funding body EPSRC and the support from MASDOC CDT.