Research Study Group

I did my research study group project in stochastic growth models with John Sylvester and Qiaochu Chen supervised by Dr Nikos Zygouras and Dr Partha Dey.

In this project we considered 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.

Let

$\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,

$A_\mu\subseteq B_1$ .
If $p <\overrightarrow{p_{c}}$ then $A_\mu \subseteq B_1^\circ$ .
If $p >\overrightarrow{p_{c}}$ then $A_\mu\cap [0,\infty)^2 \cap \partial B_1 =I_p$ .
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$ .

The critical case is where $\alpha=1$ . Intuitively this is because the first-passage metric has no preference over the lengths of the edges hence there are many more paths to a specific vertex $\mathbf{x}$ of optimal length. This isn't the case when $\alpha \neq 1$ since for the supercritical case $(\alpha<1)$ we have that $k^\alpha$ is concave which means that longer edges are preferred therefore the only path to $\mathbf{x}$ which can be made in optimal time is the direct edge from the origin. Similarly, in the subcritical case $(\alpha>1)$ we have that $k^\alpha$ is convex and hence shorter edges are preferred. This means that the only paths to $\mathbf{x}$ which can be of optimal length consist of $||\mathbf{x}||$ edges of length $1$ .

Our main results are the following three theorems which show that in the critical case there are only finitely many lattice points which are not reached in optimal time, in the supercritical case the limiting shape of the scaled growth set is the unit $l^1$ ball and in the subcritical case a limiting shape exists and the exact form can be given in terms of the asymptotic speed.

Theorem 1:

If $\alpha=1, p \in (0,1]$ we have that for $\mu \in \mathcal{M}_p$ that the limiting shape:

$A_\mu^{(\alpha)} :=\lim\limits_{t\rightarrow \infty} t^{-1}\mathcal{B}^{(\alpha)}_t$

exists a.s. and

$A_\mu^{(\alpha)} = B_1.$

Theorem 2:

If $\alpha<1, p \in (0,1]$ we have that for $\mu \in \mathcal{M}_p$ and any $\varepsilon>0$ that:

$\mathbb{P}\left[B_{1-\varepsilon} \subseteq t^{-\frac{1}{\alpha}}\mathcal{B}^{(\alpha)}_t \subseteq B_{1+\varepsilon} \; for \; large \; t\right]=1$

Theorem 3:
If $\alpha \geq 1, \varepsilon>0$ we have that $\exists A_\mu^{(\alpha)}$ deterministic such that

$\mathbb{P}[(1-\varepsilon)A_\mu^{(\alpha)}\subseteq t^{-1}\mathcal{B}^{(\alpha)}_t \subseteq (1+\varepsilon)A_\mu^{(\alpha)} \quad for \; large \; t]=1$

Furthermore $A_\mu^{(\alpha)}=\{x \in \mathbb{R}^2: \varphi^{(\alpha)}\leq 1\}$ where

$\varphi^{(\alpha)}(x):=\lim_{n \rightarrow \infty}\frac{T^{(\alpha)}(0,nx)}{n}$

which exists almost surely and in $L^1$ , moreover the convergence is uniform on compact sets.

We have also proven that in the specific case that the distribution $\mu$ has bounded support then the flat piece of the long-range model coincides precisely with that of the nearest neighbour model. Based on this result, our simulation and heuristic arguments we conjecture that the flat piece for the long-range model coincides with that of the nearest neighbour model for any $\mu \in \mathcal{M}_p$ in the subcritical regime.

References

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. http://arxiv.org/abs/1309.5757.