On the radial growth of ballistic aggregation and other aggregation models
Abstract.
For a class of aggregation models on the integer lattice , , in which clusters are formed by particles arriving one after the other and sticking irreversibly where they first hit the cluster, including the classical model of diffusion-limited aggregation (DLA), we study the growth of the clusters. We observe that a method of Kesten used to obtain an almost sure upper bound on the radial growth in the DLA model generalizes to a large class of such models. We use it in particular to prove such a bound for the so-called ballistic model, in which the arriving particles travel along straight lines. Our bound implies that the fractal dimension of ballistic aggregation clusters in is 2, which proves a long standing conjecture in the physics literature.
Key words and phrases:
diffusion-limited aggregation, incremental aggregation, growth rate, fractal dimension, ballistic aggregation2020 Mathematics Subject Classification:
Primary: 82B24, 60J10; Secondary: 60D05, 28A801. Introduction
Consider a process of cluster formation on the hypercubic lattice , , which starts at time one with a single particle placed at the origin. Then at each time step , a particle arrives and is added to the cluster by placing it at a site neighbouring the existing cluster. The position of the new particle is chosen at random independently of all previous choices and according to some distribution which only depends on the existing cluster at that time. We will call such aggregation models incremental aggregation in the sequel. Many such models are known and have been studied intensively in the physics literature. They differ only by the choice of the distributions governing the selection of the locations for the arriving particles.
The most popular among these models is certainly diffusion-limited aggregation (DLA), suggested by Witten and Sander [21] in 1981 as a model for metal-particle aggregation. Particles arrive from ‘far away’ and perform symmetric random walks until they hit the cluster for the first time. The distribution specifying the resulting cluster formation mechanism is known as the harmonic measure. The formed clusters have a dendrite-like structure and show a fractal behaviour, see Figure 1. Another even older model is the Eden growth model due to Murray Eden [7], in which the position of the next particle is chosen uniformly out of all sites neighboring the current cluster. The clusters formed in this model tend to be very dense and appear ball like with a rough boundary. Another variation is diffusion-limited annihilation due to Meakin and Deutch [15], nowadays better known as internal DLA. Here the particles start at the origin, i.e. within the cluster, perform symmetric random walks and are attached where they exit the cluster. As in the Eden model, the formed clusters tend to be ball-like with a rough boundary.
Another popular model in the physics literature is the Vold-Sutherland model or ballistic aggregation, in which arriving particles travel along straight lines (ballistic trajectories) and stick where they hit the cluster. It can be traced back to the work of the colloid chemists Marjorie J. Vold and David N. Sutherland, see e.g. [14, 20]. It has been suggested for situations in which molecules move in a low density vapour such that thermal interactions can be disregarded. The clusters formed by this model are denser than the ones formed by DLA, but have a similar dendritic structure, see Figure 1.


All these models and many variants have been studied intensively in physics and have found numerous applications, we refer to the surveys and books [20, 19, 8, 11, 3] for further details and references. Most results have been obtained either from simulations or from intriguing but non-rigorous theoretical considerations. Some of these models have also inspired mathematical research and a number of results have been obtained. However, the progress up to now is far behind what physicists have discovered.
One of the most basic questions (to which we will mainly restrict our attention in this paper) is the speed of growth of the radius (or diameter) of the cluster as the number of particles tends to . Regarding DLA, some rigorous almost sure bounds are due to Kesten [9, 10] (with some improvements for dimension 3 in [12] and recently in [4]), which we will recall in Section 3 below. They imply in particular that DLA clusters are not full-dimensional (in a discrete sense) and thus exhibit some fractal behaviour. For internal DLA (and the Eden model), the growth rate is in , as the number of particles tends to and thus the clusters are full-dimensional. For internal DLA even some shape theorems have been established showing that asymptotically the clusters are balls [13]. For the Eden model the existence of a limit shape is also known, due to some relation of this model to first passage percolation, cf. [1] and the references therein. The limit shape is conjectured to deviate from a Euclidean ball. Up to now this has only been established in very high dimensions. We refer to the survey article [17] for an overview of further results regarding DLA und internal DLA. In particular, in this article, attention is also given to results obtained on graphs other than the hypercubic lattices that we restrict ourselves to here. (It is obvious that the models may be transferred to any infinite connected graph.) In contrast to the situation for the other mentioned models, it seems that the ballistic model has not been investigated in the maths literature so far. To the best of our knowledge, the only paper, where it is mentioned (but not analyzed very far) is the article [16], in which also a number of new aggregation models are proposed and simulated.
In this article we make a first attempt to investigate rigorously the growth behaviour of the ballistic model. To this end, we start from a more general viewpoint and set up a natural class of models (incremental aggregation), which includes the models mentioned above (and many more). We revisit the argument of Kesten that he used in [9] to obtain an upper bound on the growth rates of DLA in and observe that the same argument may be applied to any incremental aggregation model. In a nutshell, the ‘method’ reduces the problem of finding a bound for the radial growth to the much easier task to establish an upper bound on the local mass of the distributions determining the model. We do not claim much originality here, as once the class of incremental aggregation models is set up it is fairly easy to see that Kesten’s argument works in general. Then we apply this new method to the ballistic model. First we give a rigorous definition of the ballistic model using some notions from geometric probability. Then we state some bound on the local mass for the ballistic measures (i.e., the distributions defining the ballistic model) and finally we apply Kesten’s method to obtain the desired growth rates. It turns out that the method has power in particular in dimension . For the ballistic model in we establish that the growth exponent is (i.e., the fractal dimension is 2), which is the value conjectured in the physics literature. For , our results imply that the fractal dimension is bounded from below by 2 (while the conjectured value is ).
In order to illustrate our results, we have also simulated aggregation clusters of the ballistic model (as we define it here) and DLA for comparison. The Python code is freely available, cf. [6], together more pictures of large simulated clusters.
The paper is organized as follows. In Section 2, we introduce incremental aggregation and show that this class of models includes DLA and the Eden model. In Section 3 we provide some definitions regarding radial growth and state some trivial facts about growth exponents and fractal dimensions of our models. We also recall the results of Kesten on the radial growth of DLA. In Section 4, we state Kesten’s method (Theorem 4.1) for general incremental aggregation and demonstrate how it can be applied to recover Kesten’s growth bounds for DLA and the known bounds for the Eden model. In Section 5, we define the ballistic model and apply Kesten’s method to obtain the mentioned results on the growth of these models. Finally, in Section 6 we provide a proof of our main tool, Kesten’s method.
2. Incremental aggregation
We set up a framework in which all the models can be treated in a unified way. Let denote the family of finite subsets of , i.e.
which we equip with the discrete -algebra. We consider the nearest neighbor graph on , i.e., the graph with vertex set and edge set . (Here and throughout denotes the Euclidean norm.) A set is called connected, if the subgraph of generated by is. For , the (outer) boundary of is the set
Throughout let be some suitable probability space. For , a random point in is a measurable mapping with . Denote by the family of all probability measures on , i.e., of all possible distributions of a random point in . Moreover, a random finite set is a measurable mapping .
Definition 2.1.
Let be a family of distributions s.t. for each . A sequence of random finite sets is called incremental aggregation (with distribution family ), if it satisfies the following conditions:
-
(i)
, where ;
-
(ii)
for any , , where is a random point in whose conditional distribution given is , i.e.,
is called cluster or aggregate at time , and the infinite cluster. Observe that
Moreover, for any , almost surely is connected and . It is easy to see that is a Markov chain, in particular, depends on , but not on the order, in which the points have been added to . Different aggregation models arise now by choosing different families of distributions. We start with the simple example of the Eden growth model.
Example 2.2 (Eden growth model).
For each , let be the uniform distribution on . Then incremental aggregation with distribution family is known as Eden growth model. Here, given , each point in the outer boundary of has exactly the same chance (namely ) of being the next point added to the cluster. From simulations one can observe that large clusters look ball-like with few holes and a rough boundary.
Our second example of incremental aggregation is diffusion limited aggregation. It has been introduced by Witten and Sander [21] as a model for metal-particle aggregation and became soon very popular in physics as a simple model for many different phenomena, where particles aggregate irreversibly and diffusion (thermal motion) is the means of particle transport.
Example 2.3 (Diffusion limited aggregation (DLA)).
Let be a symmetric random walk on started at , i.e., and for each and each
For , let be the hitting time of . It is well known that in , a random walk started at is recurrent, i.e. , and in , it is transient, i.e. . For and any point , define a distribution on by
It is a nontrivial but well established fact that by setting
a probability measure is defined on . It is called the harmonic measure of . DLA is now defined to be incremental aggregation with distribution family . So in the DLA model particles perform random walks started at infinity and stick where they first hit the existing cluster. This produces sparse dendrite-like structures as simulations show.
Below in Section 5 we will discuss another class of models called ballistic aggregation. In these models the particles travel along straight lines instead of random walk paths. In order to introduce them properly, we will need some concepts from geometric probability.
3. Growth of arms
Our aim is to study the speed of growth of aggregation clusters in incremental aggregation models. For any finite set with , let
(3.1) |
denote its radius, where denotes the Euclidean norm. Observe that
justifying the terminology. Denote by the diameter of and note that
(3.2) |
Instead of the radius one could similarly work with the diameter in the sequel, which might be more natural in any more general setting. Since we are only interested in incremental aggregation, which is started at , we stick to the radius for historic reasons. The following simple observation bounding the radius of a finite set in terms of its cardinality turns out to very useful.
Lemma 3.1.
Let be a finite, connected set with . Then
(3.3) |
Proof.
Note that the constant in (3.3) could be improved but we do not need it in the sequel. Note also that for the first inequality the assumption that is connected and contains is not needed.
Let be an increasing sequence of finite subsets of . We are looking for a suitable exponent (the ‘growth rate’ of the sequence) and a suitable constant such that
(Here means that the quotient converges to 1 as .) Since such exponent might not exist in general, we define the lower and upper growth rate of the sequence by
Alternatively, the lower and upper fractal dimension are defined by
It is immediately clear from the definitions that fractal dimension and growth rate are directly connected. In general one has and . This means in particular that an upper bound on the growth rate implies a lower bound on the fractal dimension and vice versa.
may be interpreted as the volume of the cluster . (We may identify with the union , where is the unit cube centered at . Then the volume of is exactly .) Moreover, may be interpreted as the diameter, cf. (3.2), which justifies calling the exponents and fractal dimensions.
The trivial bounds on the radius stated in Lemma 3.1 imply immediately some general bounds on the fractal dimensions and growth rates.
Proposition 3.2.
Let be an increasing sequence of finite, connected subsets of with . Then
Proof.
In incremental aggregation models, the sequence consists of random sets and therefore, for each , is a nonnegative random variable (while is constant almost surely). Hence the fractal dimensions and growth rates are random variables, too. Observe that they satisfy almost surely the bounds stated in Proposition 3.2.
Let now be DLA in , as defined in Example 2.3. The following celebrated result due to Kesten provides an almost sure upper bound on the radii of DLA clusters. For , a log-term appears which was improved slightly by Lawler [12] and later again by Benjamini and Yadin [4].
Theorem 3.3 (cf. [9, 10, 4]).
For DLA in there exists a constant (depending only on ) such that almost surely for sufficiently large
Theorem 3.3 implies the following lower bounds on the fractal dimension.
Corollary 3.4.
For DLA in , , one has almost surely
Proof.
This follows immediately by inserting the estimate in Theorem 3.3 into the definition of the lower fractal dimension (and the upper growth exponent). For , for instance, this yields almost surely
Simulations of the model suggest that the above bounds are not sharp. In they suggest that the fractal dimension exists and equals , which is strictly larger than the rigorous bound stated above. For general , it is conjectured, cf. e.g. [20], that for DLA in the dimension is given by
4. DLA and Kesten’s method
In his paper [9], Kesten used a certain strategy of proof for his bounds for the DLA model in , which is also described in Lawler’s book, see [12, § 2.6], and generalized to arbitrary graphs with bounded degree in [4]. It turns out that this method can be adapted to provide some bounds for any incremental aggregation model. The next theorem below describes this general method. Its proof will be discussed later in Section 6. Let be the family of outer boundaries of aggregation clusters in , that is, let
Recall that in any incremental aggregation model, at any time step the next point to be attached is chosen from the outer boundary of the current cluster . Therefore, it is in fact sufficient to specify the distributions for all in order to determine an incremental aggregation model completely. As a consequence, it is sufficient to impose conditions on the distribution family only for the distributions of outer boundary sets as in the statement below. Other sets are not relevant for the model.
Theorem 4.1 (Kesten’s method).
Let be some family of distributions such that for each . Suppose there exist some positive constants and such that for all , any with radius at least and any ,
(4.1) |
Then there is a constant , such that incremental aggregation with distribution family satisfies almost surely
for sufficiently large.
The method is rather crude. Roughly it says that if for all relevant distributions in the family the mass concentrated on single vertices is not too large compared to the radius of the corresponding cluster (implying that the probability mass must be spread out over a significant number of vertices), then some bound on the radial growth follows. This is plausible. The more spread out distributions are, the more options there are for the next particle to be placed. As only few of the possible locations are extremal in the sense that they lead to radial growth of the cluster, this limits the speed of growth.
In [4], the assumption (4.1) is called a -radius Beurling estimate in the context of the DLA model (for the function ). Our proof of Theorem 4.1 in Section 6 below follows essentially the proof of Lawler [12, § 2.6] but one might also want to compare it with [4, Lemma 2.4 and Theorem 2.6]. The important observation is that the relevant arguments in these proofs do not only apply to DLA but to any incremental aggregation.
To illustrate Kesten’s method, we briefly describe how it is applied to obtain the known bounds in for DLA and the Eden model. In the next section, we will use it to study ballistic aggregation. For the DLA model in , one can use the following well known estimate for harmonic measures.
Proposition 4.2.
(cf. e.g. [12, Proposition 2.5.2]) For any , any connected set with and radius at least , and any , one has
Observe that outer boundaries need not be connected such that the above estimates are not directly applicable. However, since any random walk started outside a set will first hit before hitting , we have
Hence the above estimates hold also for any boundary set . Applying Theorem 4.1 to DLA in , for which, by Proposition 4.2, the hypothesis is satisfied for , we conclude the existence of a constant such that almost surely for sufficiently large. This is the bound stated in Theorem 3.3 above.
Remark 4.3.
For DLA in , the bound for the harmonic measure stated in Proposition 4.2 implies that the hypothesis of Theorem 4.1 is satisfied for any . Thus, this theorem yields for any the existence of a constant such that a.s. the bound holds for sufficiently large. This is enough to conclude (by letting ) that a.s. , as stated in Corollary 3.4, but it is not enough to get the logarithmic correction for the bound on the radius stated in Theorem 3.3 for the case . For this a slight refinement of Kesten’s method is necessary, see e.g. [4].
For , Theorem 4.1 yields the existence of some such that a.s. the bound holds for sufficiently large. This is not as good as the bound stated in Theorem 3.3 and shows the rather poor performance of the method in higher dimensions. It is known that the exponent in Proposition 4.2 is optimal. There are sets (e.g. (discrete) line segments) for which the harmonic measure has atoms of this order, cf. e.g. [12, §2.4] for details. Hence Theorem 4.1 cannot provide a better bound for the growth rate in this case.
For the Eden growth model in (as defined in Example 2.2 above), we have the following estimate for the defining family of distributions :
Lemma 4.4.
For any , any boundary set with and any ,
Proof.
Denote by the coordinate directions. For there is a finite connected set with and , such that . Because of its radius must contain a point with . Hence there is a coordinate direction such that the -th coordinate of satisfies . Without loss of generality we can assume and . Since is an integer, we have (where denotes the integer part of ) such that .
Since is connected, also its projection onto the -axis must be connected. Hence, for each there is a vertex in whose first coordinate is . If one moves from in direction , to the first vertex outside , then this new vertex will be in . It is clear that all the vertices of reached in this way are distinct, which implies that
Hence as asserted. ∎
Applying now Kesten’s method to the Eden growth model in using the estimate provided in Lemma 4.4 (for the exponent ), we infer that there is a constant , such that almost surely
for sufficiently large. This implies for the lower fractal growth dimension of the Eden model in . For , by Proposition 3.2, we therefore recover
It is also well known that for the Eden model in , , but Kesten’s method as stated in Theorem 4.1 is not capable of providing such a result, as this would require an estimate of the form (4.1) with , which is simply not true. Indeed, for any there is a cluster such that for , and . (Take e.g. . Then and so .) This precludes an estimate of the form (4.1) to hold for any .
The hypothesis in Kesten’s method is rather restrictive. Requiring some deterministic estimate to be satisfied for all outer boundaries and at all locations leads to an exponent that is often too small in order to provide a good bound for the radial growth. Although the methods is able to provide lower bounds on radial growth in any dimension , it seems that the method is strong only in .
It seems plausible, that it should be enough to have a bound on available for outer boundaries of ’typical’ aggregation clusters (or for ’most of them’). However, this will require further investigation and is not covered by Theorem 4.1 above. Another approach (which leads in fact to the growth bounds for DLA stated above) are estimates in terms of the volume of the clusters rather than its radius, which will be a topic of further investigation.
5. Ballistic aggregation
We now introduce the ballistic model rigorously and discuss its growth properties. Ballistic aggregation in will be defined as incremental aggregation with a suitable distribution family . In order to determine the model all we have to do is to choose the family , i.e., to fix a distribution on each finite set . Roughly, for each , will be determined by the probability that a ‘directed random line through hits first’. In order to define this properly, we recall some ideas from stochastic geometry, in particular the concept of an isotropic random line. In what follows, we will view also as a subset of embedded in the natural way.
Let be the space of lines in (i.e., the affine Grassmannian of -flats). We equip it with the usual hit-or-miss topology and the associated Borel -algebra , see e.g. [18, Chapter 13] for details. For any compact set let
Then , where denotes the family of all convex bodies, that is, compact, convex sets in .
It is well known, cf. e.g. [18], that there is a unique Euclidean motion-invariant Radon measure on such that
Here is the unit ball in and denotes its volume.
Observe that, by the Crofton formula, cf. e.g. [18, Theorem 5.1.1], for any convex body ,
(5.1) | ||||
where the constant is given by and is the intrinsic volume of of degree . If has nonempty interior, then is half the surface area of . This means, the measure of lines hitting a given convex body is up to some universal constant given by the surface area of . Following [18, Definition 8.4.2], for any convex body with , an isotropic random line through is defined to be a random variable with distribution given by
This definition extends without any problem to arbitrary compact sets , provided that . However, the convenient interpretation (5.1) of in terms of (or the surface area) is no longer valid if is not convex. Observe that for any compact , one has , where denotes the convex hull of . Thus, for any compact set with , the distribution is well defined and so is an isotropic random line through . In one has the following additional property, which turns out to simplify the analysis significantly: for any connected, compact set ,
Therefore, (provided , i.e., not a singleton). Thus in dimension 2 one can work with convex hulls instead of the original sets. Unfortunately, this is not possible in any higher dimension.
For any finite set denote by the union of grid boxes centered in , that is, let
Then, for any and , the distribution of an isotropic random line through is well defined. The idea for the definition of the ballistic measure is now as follows: We identify with and generate an isotropic random line through . We choose randomly a direction on . Then for any , we let be the probability that, when traveling along in the chosen direction, the square is the first square in visited by . More formally, we fix for each a direction . (We choose such that the mapping is measurable.) For and , let
that is, is the set of those points in whose associated boxes are intersected by . Traversing in direction induces an order in . (For certain lines the order in which the boxes are visited is not well defined, namely if hits a box first at an intersection point of two or several boxes not visited before. In such a case the order can be made unique by fixing some order of the boxes in , such as the one induced by the lexicographic order in . However, for -almost all lines the order in is well defined without this.) Denote by and the first and last point in ‘visited’ by .
Definition 5.1.
(Ballistic measure) Let . For and define
Then a probability measure on is well defined by setting
We call the ballistic measure on .
Observe that for and . Hence, is indeed a probability measure which is concentrated on , that is, . Note also that, for any ,
(5.2) |
This gives a first upper bound of the probability mass of at single vertices. Ballistic aggregation (BA) on is now defined to be incremental aggregation with distribution family , where is the ballistic measure on .
For the ballistic model in , , we have the following main result concerning the radial growth of clusters, which parallels the one obtained by Kesten for DLA.
Theorem 5.2.
Let , and be ballistic aggregation in . There exists a constant such that almost surely for sufficiently large
Combining this bound with the trivial lower bound provided by Propositon 3.2, we conclude that in the fractal dimension of BA clusters exists and equals . This confirms a long standing conjecture in the physics literature, cf. [5, 14, 2, 20].
Corollary 5.3.
For the ballistic model in , one has almost surely.
Remark 5.4.
We can even get a slightly stronger conclusion from the above theorem regarding the asymptotic size of BA clusters. The ballistic model in satisfies almost surely
This may be interpreted as saying that asymptotically BA clusters cover a positive portion of the plane. (More precisely, the quotient of the area covered by the cluster (given by ) and the area of the smallest ball containing () is asymptotically bounded from below, as .)
For , the conclusion regarding the fractal dimension of the BA model is not quite as strong as for .
Corollary 5.5.
For the ballistic model in , , one has almost surely.
As in the case , this can be directly deduced from Theorem 5.2. Unfortunately, this lower bound for the fractal dimension is far from the conjectured value in this case.
The proof of Theorem 5.2 will be based on Kesten’s method (Theorem 4.1 above). In order to apply it, a suitable estimate for the local growth of the ballistic measures is required, which we state now.
Proposition 5.6.
For any , , there exists a constant such that, for any , any connected set with and , and any ,
For , is a suitable constant.
Before we provide a proof of Proposition 5.6, we first clarify that Theorem 5.2 easily follows from this statement.
Proof of Theorem 5.2.
Observe that any improvement on the exponent in Proposition 5.6 (i.e., any larger ) would allow to deduce from Kesten’s method a better bound for the radial growth. Unfortunately, the exponent in Proposition 5.6 turns out to be optimal in any dimension , as the following remark clarifies.
Remark 5.7.
The exponent in Proposition 5.6 is optimal (largest possible) in any space dimension . Consider for any , and any integer the set
Observe that is a union of unit size boxes placed side by side in a row. Hence is convex and . Moreover, noting that for any directed line hitting the cube at all, is always the first or the last cube of visited by , we obtain for the ballistic measure at (and similarly at )
For any , the denominator in the last expression is bounded from above by and therefore we obtain . Hence a bound as in Proposition 5.6 valid for the ballistic measures of all finite sets cannot be true for any .
Proof of Proposition 5.6.
We first discuss the case , for which our argument is much simpler than for the general case. Fix . Let be a connected set with and . Note that the connectedness implies . The set contains the square and another unit square with and . Hence contains and thus a rectangle with sidelengths and . (Choose one side of parallel to the vector .) Using (5.2) and the properties of the measure , we conclude that, for any ,
This shows the claimed estimate for and also that is a suitable constant in this case.
Now let us turn to the case . We start similary as for . Let and let be a connected set with and . As before, the set contains the square and another unit square with and , but now we can not simply replace by its convex hull, since the latter set may be hit by significantly many more lines than .
Since is connected, it must contain a path from to , that is, there are and points such that for . Let and let denote (the graph of) the shortest curve connecting these points in the given order. Notice that consists of axis-parallel segments of length 1. For and let
denote the -parallel set of . Observe that . (Indeed, any point in is contained in some ball with . If , then and if is on the segment connecting and , then obviously .) This yields
We claim now that there is a constant (independent of and ) such that
(5.3) |
Using (5.2), the properties of the measure and (5.1), we conclude from (5.3) that, for any ,
This shows the estimate stated in Proposition 5.6 (for the constant ).
It remains to provide a proof of (5.3). The rough idea here is to compare the measure of lines through the tube with the measure of lines through the tube , where is the segment connecting and , and to observe that the latter is of order . Observe that any hyperplane hitting does also hit the curve , since both curves have the same endpoints. (Indeed, if the hyperplane contains an endpoint of then it obviously intersects also . Otherwise the hyperplane contains an inner point of and separates the common endpoints of and . But then the curve must also intersect the hyperplane when passing from one side to the other.) This will be useful for decomposing .
Let denote the set of all -flats and the unique Euclidean motion invariant measure on such that , see [18, Ch. 13.2] for details. For denote by the set of lines in and let be the invariant line measure on (which is the image measure of on under some isometry from to . Recall that for the measure of any set of lines may be determined by computing its line measure in hyperplanes and then integrating over all hyperplanes. More precisely, for any ,
see e.g. [18, Thm. 7.1.2 and the subsequent Remark].
Let be the direction of the segment . For any , denote by some unit normal of and by the corresponding (signed) distance to (such that ). Note that is uniquely determined for a.a. if we require additionally . For a lower bound, we do not need to compute the line measure in all hyperplanes. We restrict our attention to the following set. Fix some and let
Observe that, for each , we have , i.e. there is some point , implying that contains the closed ball with radius and center . Hence, by (5.1),
where denotes a ball in with radius (centered at ). The most important thing to note here is that is some positive constant independent of and . Therefore, we infer
(5.4) | ||||
Employing [18, Theorem 13.2.12], we conclude that
where denotes the Grassmannian of hyperplanes in and the invariant measure on . Moreover, as before denotes the unit normal of such that and is the -dim. Lebesgue measure on . Now observe that the inner integral in the last term is bounded from below by . Indeed, we have if and only if . Moreover, if the first indicator is 1, then . Hence as claimed.
6. Proof of Kesten’s method
The first step towards a proof of Theorem 4.1 is an equivalent reformulation of the conclusion in a more convenient form. Let be some incremental aggregation. Recall the definition of the radius from (3.1). We define the two random functions
and
Clearly, is the first time step at which the growing cluster has radius at least . It is easy to see that almost surely the functions and are non-decreasing. Moreover, one has almost surely the relations for each , and for each . Note also that almost surely
The conclusion in Theorem 4.1 is an almost sure upper bound on the random function . Our aim is to reformulate this upper bound on equivalently as a lower bound on the waiting time . The following statement provides this link. Recall that a function is called multiplicative if and only if for all . Note that multiplicativity implies and . (The functions , are generic examples for such .)
Lemma 6.1.
Let and be a bijective, multiplicative and increasing function. For define the events
and
Then the following assertions are equivalent:
-
(i)
There exists a constant such that .
-
(ii)
There exists a constant such that .
Proof.
Fix some and let . Choose such that holds for all . (Here and in the sequel , and depend on , which we suppress in the notation.) Since is bijective and multiplicative, the last inequalities are equivalent to being satisfied for all , where . Since as , we can find large enough such that . Obviously this implies for all , since is increasing. Hence we infer that holds for each . Observe now that is increasing and multiplicative since is. Taking into account that , we conclude that for each
Hence . It is now important to note that does not depend on (but only on , and ). Therefore we have proved that .
With a completely analogous argument one can show that . Hence for any (and ). In particular, if for some , then . Similarly, if for some , then , and therefore . This completes the proof. ∎
Assume now that the hypothesis of Theorem 4.1 is satisfied for some . Consider for any the events
and
It is clear that the conclusion of Theorem 4.1 may be formulated as follows in terms of the events : There exists a constant such that .
Note that and are the same as the corresponding events defined in Lemma 6.1 for the choices and
Clearly, is bijective, multiplicative and increasing as required. Hence, by Lemma 6.1, the conclusion of Theorem 4.1 holds if and only if there exists a constant such that
(6.1) |
Therefore, in order to prove Theorem 4.1 it clearly suffices to prove that its hypothesis implies the existence of some constant such that (6.1) holds.
In order to achieve this we introduce some more notation. For we write , where denotes the (random) point added to the cluster at time . Fix some , which will be determined later on. For let and define
Let be the discrete sphere in of radius centered at the origin. (It is easy to see that any connected set with and will contain at least one point of , since there will be a path in connecting to some point at distance at least which can not avoid intersecting the set .) Further we define the set of all possible (self-avoiding) paths in of length (i.e., passing edges) with starting point in by
(6.2) |
For any we define the event
and the union of these events by
Note that this is a finite union, as for any there are only finitely many paths in . Note also that as well as depend (via ) on the choice of , which is suppressed in the notation but which will become important later. We claim that for each
(6.3) |
Indeed, if , then . For this implies , and hence . Thus contains a point with . Since is connected and contains the origin, there exists a path in connecting and (i.e., and ) with the additional property that , that is, the points of have been added to the cluster in the right order. (Not every path between and might satisfy this, but such a path must exist, since otherwise the cluster would be disconnected at some time.) contains a point of and thus a subpath connecting to . Since , has length at least . Hence, by taking the first steps of , we find some path of length exactly , that is, some in . This means which proves the set inclusion (6.3).
The following estimate will allow to complete the proof of (6.1).
Lemma 6.2.
There is some and constants , and (which depend on ) such that for all with
Before we prove Lemma 6.2 let us discuss how it is used to complete the proof of (6.1). Let us fix as required for applying the lemma. Then, clearly, since , we have
and thus, by (6.3),
Hence, by the Borel-Cantelli lemma, Since
we conclude that . This completes the proof of (6.1) and thus of Kesten’s method (up to a proof of Lemma 6.2).
In order to prepare the proof of Lemma 6.2, we introduce some more notation and provide a few auxiliary results. For any , any path (cf. (6)) and any , we define random variables
that is, is either the time point at which is added to the cluster or if this never happens. Further, for , we define waiting times
so is the waiting time between adding and to the cluster, if both are added and is added before . We also consider the event
that all the vertices of the path are added to the cluster in the right order (i.e., before ). Note that . We will now prove that the random variable conditioned on always dominates a geometrically distributed random variable with parameter
(6.4) |
where the constants and are the ones from the hypothesis in Theorem4.1. In particular, they are the same for all and independent of .
Lemma 6.3.
Proof.
Fix . Let , and let . It suffices to show that for any such that
(6.5) |
Indeed, since is a disjoint decomposition, we infer that
Now, by (6.5), the first probability in each summand can be bounded from below by and taking this factor out of the summation, the remaining summands sum to 1. Hence, we obtain as asserted in the lemma.
For a proof of (6.5), fix and define for any the event . Set . Then, by the multiplication formula of conditional probabilities, we have for any
Now observe that the condition in the -th factor implies, that at time the cluster has radius at least and contains but not . (And thus, due to the choice of , is in the outer boundary of .) Hence, by the hypothesis (4.1) in Kesten’s method (Theorem 4.1), we get
We conclude that holds for any , proving (6.5). ∎
Since we want to sum geometric random variables in a moment, we also provide the following standard bound, which can e.g. be found in [12, Lemma 2.6.2].
Lemma 6.4.
Let , and let be independent geometrically distributed random variables with parameter . Then for every ,
Based on this important observation we obtain the following bound for the waiting time until the path is completely added to the cluster conditioned on the event that it is added.
Lemma 6.5.
For any there is some such that for all with and all
where is the constant in the hypothesis of Theorem 4.1.
Proof.
Fix some and set . Choose large enough such that . Note that this implies for all .
Observe that and thus
Note that under the condition , may be represented as . Hence, for any , we obtain
Now recall from Lemma 6.3 that, conditioned on , each of the random variables dominates a geometric random variable with parameter . Moreover, given , the randomness in the variable will only depend on the subsequent steps of the construction. Hence their sum dominates a sum of independent geometric random variables with parameter . That is, for any
Specializing now to and recalling from the definition of and (6.4) that , we can apply Lemma 6.4 with , and . (Note that the hypothesis is satisfied for .) We obtain that for any with ,
which completes the proof. ∎
Now we have all the ingredients to provide a proof of Lemma 6.2.
Proof of Lemma 6.2.
Choose small enough that . By definition of and Lemma 6.5, there exists such that, for any ,
Recall that the paths of start in and observe that there is some constant such that . Hence there are at most starting points for paths in . Moreover, since each point in has neighbors and paths in have length , there are at most possible paths with a given starting point. Hence . We infer that for any
where , due to the choice of , and . Hence we have found some (and suitable constants , and ) such that the asserted bound in Lemma 6.2 holds for all with . ∎
References
- [1] A. Auffinger, M. Damron, and J. Hanson. 50 years of first-passage percolation, volume 68 of University Lecture Series. American Mathematical Society, Providence, RI, 2017. doi:10.1090/ulect/068.
- [2] R. C. Ball and T. A. Witten. Causality bound on the density of aggregates. Phys. Rev. A, 29:2966–2967, May 1984. URL: https://link.aps.org/doi/10.1103/PhysRevA.29.2966, doi:10.1103/PhysRevA.29.2966.
- [3] A.-L. Barabási and H. E. Stanley. Fractal Concepts in Surface Growth. Cambridge University Press, 1995. doi:10.1017/CBO9780511599798.
- [4] I. Benjamini and A. Yadin. Upper bounds on the growth rate of diffusion limited aggregation, 2017. arXiv:1705.06095.
- [5] D. Bensimon, E. Domany, and A. Aharony. Crossover of fractal dimension in diffusion-limited aggregates. Phys. Rev. Lett., 51:1394–1394, Oct 1983. URL: https://link.aps.org/doi/10.1103/PhysRevLett.51.1394, doi:10.1103/PhysRevLett.51.1394.
- [6] T. Bosch. Incremental-aggregations. https://github.com/tillmanntristanbosch/incremental-aggregations, 2021. Accessed: 2023-08-23.
- [7] M. Eden. A two-dimensional growth process. In Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Vol. IV, pages 223–239. Univ. California Press, Berkeley, Calif., 1961.
- [8] R. Jullien and R. Botet. Aggregation and fractal aggregates. World Scientific Publishing Co., Inc., Teaneck, NJ, 1987.
- [9] H. Kesten. How long are the arms in DLA? J. Phys. A, 20(1):L29–L33, 1987. doi:10.1088/0305-4470/20/1/007.
- [10] H. Kesten. Upper bounds for the growth rate of DLA. Phys. A, 168(1):529–535, 1990. doi:10.1016/0378-4371(90)90405-H.
- [11] M. Kolb. Structure Formation by Aggregation: Models and Applications, pages 381–389. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001. doi:10.1007/3-540-44946-9_31.
- [12] G. F. Lawler. Intersections of random walks. Probability and its Applications. Birkhäuser Boston, Inc., Boston, MA, 1991.
- [13] G. F. Lawler, M. Bramson, and D. Griffeath. Internal diffusion limited aggregation. Ann. Probab., 20(4):2117–2140, 1992. URL: http://links.jstor.org/sici?sici=0091-1798(199210)20:4<2117:IDLA>2.0.CO;2-K&origin=MSN.
- [14] P. Meakin. The Vold-Sutherland and Eden models of cluster formation. Journal of Colloid and Interface Science, 96(2):415–424, 1983. URL: https://www.sciencedirect.com/science/article/pii/0021979783900449, doi:10.1016/0021-9797(83)90044-9.
- [15] P. Meakin and J. M. Deutch. The formation of surfaces by diffusion limited annihilation. The Journal of Chemical Physics, 85(4):2320–2325, 08 1986. arXiv:https://pubs.aip.org/aip/jcp/article-pdf/85/4/2320/11207514/2320\_1\_online.pdf, doi:10.1063/1.451129.
- [16] I. S. Molchanov. Diffusion-limited aggregation with jumps and flights. J. Statist. Comput. Simulation, 64(4):357–381, 1999. doi:10.1080/00949659908811985.
- [17] E. Sava-Huss. From fractals in external DLA to internal DLA on fractals. In Fractal Geometry and Stochastics VI, volume 76 of Progr. Probab., pages 273–298. Birkhäuser/Springer, 2021. URL: https://doi.org/10.1007/978-3-030-59649-1_12, doi:10.1007/978-3-030-59649-1\_12.
- [18] R. Schneider and W. Weil. Stochastic and integral geometry. Probability and its Applications (New York). Springer-Verlag, Berlin, 2008. doi:10.1007/978-3-540-78859-1.
- [19] H. E. Stanley and N. Ostrowsky, editors. On growth and form, volume 100 of NATO Advanced Science Institutes Series E: Applied Sciences. Martinus Nijhoff Publishers, Dordrecht, 1986. Fractal and nonfractal patterns in physics, Papers from a course given as part of the NATO-ASI series at the Cargèse summer school, Cargèse, June 26–July 6, 1985.
- [20] T. Vicsek. Fractal growth phenomena. World Scientific Publishing Co., Inc., Teaneck, NJ, 1989. With a foreword by Benoit B. Mandelbrot. doi:10.1142/0511.
- [21] T. A. Witten and L. M. Sander. Diffusion-limited aggregation, a kinetic critical phenomenon. Phys. Rev. Lett., 47:1400–1403, Nov 1981. URL: https://link.aps.org/doi/10.1103/PhysRevLett.47.1400, doi:10.1103/PhysRevLett.47.1400.