Disease spread through checkerboard

Question

Suppose we have an infinite checkerboard (square grid) with a single “infected” square at time $t=0$. After each discrete time step, each square that is adjacent (sharing an edge) to one or more infected squares becomes infected with probability $p$. Infected squares stay infected forever.

Let $X_t$ be the number of squares infected at time $t$. It is probably far too complicated and difficult to explicitly calculate $\mathbb E[X_t]$. However, we can anticipate that $X_t\sim c\cdot t^2$ for some constant $c$ that depends on $p$. Does anyone know how to make this asymptotic estimate sharper by calculating the explicit value of $c$ in terms of $p$? In other words, can we find $$\lim_{t\to\infty}\frac{\mathbb E[X_t]}{t^2}=c=\space ?$$ I do know that $c=2$ when $p=1$ and $c=0$ when $p=0$, so I would expect something like $c=2p$ or $c=2p^2$. However, I have no idea how to go about finding $c$. Can somebody please help?

Answer 1

Some extremely rough estimates / possible approach / too long for a comment

It seems $c$ goes as $p^2$.

• Following OP, let $X_t$ be the no. of infected cells at time $t$. This is a sort of "area". $X_1 = 1$.

• Let $B_t$ be the no of non-infected cells which are next to some infected cells. This is a sort of "boundary" or "circumference" of the "area" $X_t$. $B_1 = 4$.

• By the infection model, $X_{t+1} - X_t = p B_t$.

We need another relation between $X$ and $B$ before attempting to solve. It seems plausible that $B^2 \propto X$. Lets say $B^2 = k X$. What is $k$?

• If $X$ were a perfect $45^\circ$ tilted-square (such as when $p=1$), we would have $k=8$.

• If $X$ were a perfect square with sides parallel to the axes, we would have $k=16$.

• If $X$ were a circle, we would have (I'm not sure...) maybe $k = {(2\pi r)^2 \over \pi r^2} = 4\pi$.

We now have enough to plug in $X_t = c t^2$ and solve for $c$:

• $X_{t+1} - X_t = c ( (t+1)^2 - t^2) = c(2t+1) \approx 2ct$

• $pB_t = p \sqrt{kX} = p \sqrt{kc} \;t$

• Equating them: $2ct = p\sqrt{kc}\; t \implies \sqrt{c} = p\sqrt{k/4} \implies c = p^2 k/4$.

So if the tilted-square $(k=8)$ case is typical, we have $c = 2 p^2$.

Further thoughts: this is of course extremely rough. Moreover, I believe there is one systemic bias: I believe $k=8$ is actually the minimal value for $k$, i.e. for any shape (any set of infected cells) $B^2 / X \ge 8$, with equality iff the shape is a perfect tilted square (which is guaranteed when $p=1$). If so, maybe we can argue that $c=2p^2$ is in fact a rough lower bound?

Answer 2

New Answer. This model is called Richardson growth model.

Richardson proved in $[2]$ that, for each $p \in (0, 1)$, there exists a norm $\varphi_p$ on $\mathbb{R}^2$ such that the infected cluster at time $t$, normalized by time $t$, is asymptotically the unit ball with respect to $\varphi_p$. In particular, this shows that

$$ \lim_{t\to\infty} \frac{\mathbb{E}[X_t]}{t^2} = \operatorname{Area}(\{x \in \mathbb{R}^2 : \varphi_p(x) \leq 1\}) $$

is the area of the unit ball with respect to $\varphi_p$. In $[1]$, Durrett and Liggett provided further discussions by relating this model to the first-passage percolation with passage times distributed as $\operatorname{Geom}(p)$.

References.

• $[1]$ Durrett, R. and Liggett, T. (1981). The shape of the limit set in Richardson’s growth model. Annals of Probab., 9, 186–193.

• $[2]$ Richardson, D. (1973). Random growth in a tessellation. Proc. Cambridge Philos. Soc., 74, 515–528.

---

Old Answer. Here are some simulations of the values $c = c(p)$ using the grid of size $1000\times1000$ and $500$ steps together with some fitting curves.

$\hspace{8em}$

The data clearly deviates from the polynomial $2p^2$, and although the above plot may seem to suggest that $c(p)$ assumes a nice closed form, I believe that it is some artifact of numerical fitting and I am prone to believe that $c(p)$ is not given in a nice closed form in $p$. Also, using the same grid and number of steps, for $p = 1/2$, the cluster looks like

$\hspace{12em}$

The boundary is surprisingly smooth when compared to other well-known cluster growth models. And what is more surprising to me is that I was unable to find literature on this specific model. Perhaps I am simply missing the right keyword, but if it is the case that this model has yet been studied, even proving that $X_t$ typically grows at the speed of $\asymp t^2$ almost surely will make a very interesting result, letting alone scaling limit statement on the shape of the cluster.

Answer 3

When $p$ is small, the leading-order probability that a cell $(\pm x,\pm y)$ is infected is $${x+y\choose x}{t\choose x+y}p^{x+y}\\ \approx {(tp)^{x+y}\over x!y!}$$ If I count the points where this approximation is greater than $1$, that implies that, for small $p$, the region is bounded by the curve $$tp=\sqrt[|x|+|y|]{|x|!|y|!}$$ Unfortunately, the contour plot of that function has an indent at $y=0$, which is not seen in Sanchul Lee's image. $\sqrt[x+y]{x!y!}$">