Tetris-like falling sticky disks

Question

Suppose unit-radius disks fall vertically from $y=+\infty$, one by one, and create a random jumble of disks above the $x$-axis. When a falling disk hits another, it stops and sticks there. Otherwise, if the disk center reaches $y=0$, the disk stops with its center resting on the $x$-axis. Here is an example of 1000 disks falling at uniformly random $x$-locations within $[-50,50]$:
         
There are many questions one could ask about this (to me) beautiful and intriguing structure (e.g., about its contact graph), but to be specific, let me concentrate on one quantity: the maximum height $h_{\max}$ as a function of the number of disks $n$ and the $x$-range $R$. (In the above example, $R=100$ and $h_{\max}=94.9$.) It appears that $h_{\max}$ grows linearly, with $h_{\max} \approx n \frac{10}{R}$. Here is plot, where each point is an average of ten trials:
                   
Two questions:

Q1. Is there a simple explanation of the growth of $h_{\max}$?

Q2. Has this process, or something close to it, been studied before?

---

Ultimately I am interested in determining packing densities of randomly jostled shapes, as explored in the earlier MO question "Average degree of contact graph for balls in a box." Sticky disks are a very simple model along these lines.

---

Update (3Mar16). An article by Ivan Corwin on KPZ universality has just appeared (AMS Notices PDF), including this figure to illustrate the "random ballistic" model:

---

     

---

Users ansobol and Nechaev and Jeremy Voltz previously pointed to the relevance of KPZ universality.

Answer 1

A discrete space version of your picture (with squares instead of circles) has been studied quite a bit, known as Ballistic Deposition. Here is a video of the process in action:

Ballistic Deposition on YouTube

This process is believed to be in the KPZ Universality class, so that the scaling limit of the height function can be described by the Airy Process with $t^{1/3},t^{2/3}$ scaling parameters.

Here is a short introduction to the theory:

KPZ Universality Class

Answer 2

Diffusion-limited aggregation is different in that you consider ballistic rather than diffusive motion: randomness enters only through x-coordinates of the falling disks.

Have a look at the paper "Ballistic deposition patterns beneath a growing KPZ interface" (http://arxiv.org/abs/1006.4576; I happen to be one of the authors, and will ask my coauthors who are more versed in statistical physics to join the discussion). In particular, it contains some references to the existing literature on ballistic random growth.

People are usually interested in fluctuations of the upper envelope of the growing cluster, because for many such models it falls into the ``KPZ universality class'' (meaning that upon a proper rescaling its continuous limit converges to a kind of Airy process). In particular the behavior of $h_{\mathrm{max}}$ is a superposition of two phenomena: the obviously linear scaling of the mean height and the scatter of local heights around that mean, which is described by the Tracy-Widom law.

Answer 3

The density of a randomly growing heap is known, but it is model-dependent and non-universal. The linear dependence of the height on number of deposited blocks is evident, however the coefficient in front of this dependence is again model-dependent. The growth can be viewed as a special sequential matrix multiplication as described in http://arxiv.org/abs/1110.3524/ leading to dynamics of 1D Toda chain. One can play with different versions of this model, for example, supposing that there is only left-hand interaction. The corresponding profile will look different, however the fluctuations will be again of KPZ-type.

Answer 4

That the growth is asymptotically linear is clear. But if you keep the width $2R$ of the strip (over which the centers are chosen uniformly) fixed, then the growth speed $c_R$ is not strictly proportional to $R^{-1}$. This is clear when thinking to the small width case: if $R<1$, then there is only one branch in the tree because two consecutive disks always touch. If $d$ is the distance between their centers, then they will arrange with a height gap equal to $\sqrt{4-d^2}$. Because the distribution of $d$ has density $$\frac{2R-d}{2R^2},$$ we find that the growth average speed $$\frac1n\sum_1^nd_j$$ tends to the expectation of $\sqrt{4-d^2}$: $$c_R=\int_0^{2R}\sqrt{4-x^2}\frac{2R-x}{2R^2}dx.$$ Calculus gives $$c_R=\frac2R\sin^{-1}R+2\sqrt{1-R^2}+\frac4{3R^2}\left((1-R^2)^{3/2}-1\right).$$ As expected, $c_R\rightarrow2$ as $R\rightarrow0$. On the other hand, $c_1=\pi-\frac43$.

Presumably, the OP is interested with $\gamma=\lim_{R\rightarrow+\infty}Rc_R$.

Answer 5

Regarding the question

Has this process, or something close to it, been studied before?

I was recently made aware of an intriguing approach of Bob Macpherson and his post-doc Ben Schweinhart at IAS for investigating Brownian trees via computational topology in this pre-print. Since the investigation is topological, it will not yield answers to your question about maximum height, but it does capture other interesting global statistics.

The central idea is to let a diffusion-limited aggregation process run for a while and generate a configuration similar to that of your picture, but lacking any loops whatsoever. Essentially, each time a disc falling from infinity creates a cycle, it is discarded. However, this discarding step is not necessary for subsequent analysis and so would also apply to your (considerably loopier) situation.

In any case, once the process has run its course and generated a space consisting of the union of balls, you start growing the radii of these balls (allowing overlap of course). As you increase these radii, the homology of the space changes: some loops form, others get filled in and so forth. It is possible to unambiguously associate a (birth, death) interval to each such loop via the theory of persistent homology.