The bi-dimensional Directed IDLA forest

Basic Information

• Paper ID: 2009.12090
• Title: The bi-dimensional Directed IDLA forest
• Authors: Nicolas Chenavier, David Coupier, Arnaud Rousselle
• Classification: math.PR (Probability Theory)
• Publication Date: September 2020 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2009.12090

Abstract

This paper investigates three variants of the Internal Diffusion Limited Aggregation (IDLA) model based on simple random walks on $\mathbb{Z}^2$ with infinitely many source points located on the vertical axis $I(\infty)=\{0\}\times\mathbb{Z}$. The paper provides various properties including stationarity, mixing, stabilization, and shape theorems. These results enable the authors to define a new directed (with respect to the horizontal direction) random forest spanning the entire $\mathbb{Z}^2$, based on the IDLA protocol and invariant in distribution under vertical translations.

Research Background and Motivation

Problem Background

1. Classical IDLA Problems: Internal Diffusion Limited Aggregation (IDLA) is a random growth model first introduced by Meakin and Deutch in 1986 and later developed within a mathematical framework by Diaconis and Fulton. In the classical IDLA model, the aggregate is defined by recursively adding points on the exterior of the aggregate visited for the first time by random walks.
2. Challenges in Infinite IDLA Trees: The infinite random tree $T_∞$ associated with classical IDLA exhibits radial characteristics (branches pointing toward the origin), which prevents its distribution from satisfying useful invariance properties, making the study difficult.

Research Motivation

1. Overcoming Radial Characteristics: To overcome the radial characteristic obstacle of $T_∞$, one must consider directed forests relative to some vector $u \in \mathbb{R}^2$ whose distribution possesses translation invariance orthogonal to $u$.
2. Approximation Strategy: In balls $B(-nu, R)$ sufficiently far from the origin, the radial characteristics of $T_∞$ should disappear, and branches should be oriented relative to vector $u$ rather than the origin.
3. Construction of New Forest Models: Construct directed forests based on IDLA processes with infinitely many source points, where the forest is invariant in distribution under vertical translations.

Core Contributions

1. Construction of Three Infinite IDLA Aggregates: $A_n[\infty]$, $A_n^*[\infty]$, and $A_n^†[\infty]$, based on infinitely many source points on the vertical axis $I(\infty)$.
2. Establishment of Stabilization Theorems: Proved that distant particles do not affect the central strip (Theorem 3.1), and central particles do not affect distant levels (Theorem 4.1).
3. Proof of Mixing Properties: Established mixing of the aggregate with respect to vertical translations (Proposition 5.1).
4. Derivation of Shape Theorems: Provided shape theorems with logarithmic fluctuations for $A_n[\infty]$ (Theorem 6.1) and polynomial fluctuations for $A_n^*[\infty]$ and $A_n^†[\infty]$ (Theorem 6.2).
5. Construction of Directed IDLA Forest: Defined a new random forest $F_\infty$ spanning the entire $\mathbb{Z}^2$, invariant in distribution under vertical translations and possessing mixing properties.

Detailed Methodology

Task Definition

The core task of this paper is to construct a directed random forest based on the IDLA protocol satisfying:

• Spanning the entire $\mathbb{Z}^2$
• Directed relative to the horizontal direction
• Invariant in distribution under vertical translations
• Possessing mixing properties

Three IDLA Models

1. Model $A_n[\infty]$

• Construction begins from finite aggregate $A_n[M]$, $M \geq 0$
• Particles are sent in "usual order": first $n$ particles from level 0, then $n$ particles from level 1, then $n$ particles from level -1, and so forth
• Define $A_n[\infty] = \bigcup_{M \geq 0} A_n[M]$

2. Model $A_n^*[\infty]$

• Similar to $A_n[\infty]$, but the number of particles $N_i$ sent from each source point $(0,i)$ is a Poisson random variable with parameter $n$
• Particles are still sent in usual order
• $E[\# A_n^*[M]] = (2M+1)n$

3. Model $A_n^†[\infty]$

• Based on independent Poisson point processes $(N_i)_{i \in \mathbb{Z}}$, each with intensity 1 on $\mathbb{R}_+$
• Particles are sent according to random clocks, no longer following usual order
• Satisfies abelian property: $A_n^†[M] \overset{law}{=} A_n^*[M]$

Key Technical Innovations

1. Stabilization Results

Theorem 3.1: There exists a random integer $M_0$ such that for any $M \geq M_0$, particle trajectories starting from level $|i| > M^α$ ($α > 1$) do not visit the horizontal strip $\mathbb{Z}_M$.

Theorem 4.1: The restriction of the aggregate at sufficiently high levels does not depend on particles sent from near the origin.

2. Mixing Properties

Proposition 5.1: The distributions of $A_n[\infty]$, $A_n^*[\infty]$, and $A_n^†[\infty]$ are mixing with respect to vertical translations.

3. Finite Connected Components

Corollary 5.2: $A_n^*[\infty]$ and $A_n^†[\infty]$ almost surely consist of infinitely many finite connected components.

Forest Construction Method

1. Finite Forest $F_n^†[M]$

For each aggregate $A_n^†[M]$, construct the forest inductively:

• If particle $j$ adds point $z$ which is a source point and visited for the first time, then $z$ becomes the root of a new tree
• Otherwise, add a directed edge from $z'$ (the last point in $A_{j-1}$ visited by particle $j$ before reaching $z$) to $z$

2. Existence of Infinite Forest $F_n$

Proposition 7.2: For any $K \geq 1$, almost surely there exists a random integer $M_0(K)$ such that for $M' > M \geq M_0(K)$ we have $F_n^†[M] \cap \mathbb{Z}_K = F_n^†[M'] \cap \mathbb{Z}_K$.

This ensures the well-definedness of $F_n = \bigcup_{K \geq 0} F_n^†[M_0(K)] \cap \mathbb{Z}_K$.

3. Directed IDLA Forest $F_\infty$

Due to consistency of the sequence $(F_n)_{n \geq 1}$ (Lemma 7.3), one can define: $F_\infty = \bigcup_{n \geq 1} F_n$

Experimental Setup

Numerical Simulations

The paper includes illustrations of multiple numerical experiments:

• Figure 1: Realization of $T_{1500}$
• Figure 2: Observation of $F_{40}^†[200]$ in $\mathbb{Z}_{30}$
• Figure 3: Realization of $A_{90}[200] \cap \mathbb{Z}_{20}$
• Figure 4: Realizations of forests with different parameters
• Figure 5: Demonstration of the change chain phenomenon

Verification Methods

Theoretical results are verified through numerical simulations, particularly:

1. Aggregate shapes approximate rectangles (verifying shape theorems)
2. Directedness and translation invariance of forests
3. Observation of stabilization phenomena

Experimental Results

Shape Theorem Verification

Theorem 6.1: For $A_n[\infty]$, there exists $A > 0$ such that almost surely there exists $N \geq 1$, for any $n \geq N$: $R_{n/2-A\log(n)} \cap \mathbb{Z}_{nα} \subset A_n[\infty] \cap \mathbb{Z}_{nα} \subset R_{n/2+A\log(n)} \cap \mathbb{Z}_{nα}$

Theorem 6.2: For $A_n^*[\infty]$ and $A_n^†[\infty]$, fluctuations are of order $n^{1/2+ε}$.

Forest Properties Verification

Theorem 7.4: The directed IDLA forest $F_\infty$ satisfies:

1. Almost surely spans the entire $\mathbb{Z}^2$
2. Consists of countably infinitely many directed trees rooted at $I(\infty)$
3. Distribution is invariant under vertical translations
4. Possesses mixing properties with respect to vertical translations
5. Exhibits symmetry with respect to the $y$-axis and horizontal symmetry axis

Related Work

Development of IDLA Models

1. Classical IDLA: First shape theorem established by Lawler, Bramson, and Griffeath
2. Fluctuation Studies: Improved fluctuation bounds by Asselah, Gaudillière, and others
3. Variant Studies: Variants on different graphs, multiple source points, drifted random walks, etc.

Directed Forest Research

1. Radial Spanning Trees: Research on radial spanning trees by Baccelli and Bordenave
2. Directed Spanning Forests: Connections with Brownian web
3. External DLA: Stationary external DLA models by Procaccia and others

Conclusions and Discussion

Main Conclusions

1. Successfully constructed a directed random forest $F_\infty$ based on the IDLA protocol
2. The forest is invariant in distribution under vertical translations and possesses mixing properties
3. Established a complete theoretical framework including stabilization, mixing, and shape theorems

Limitations

1. Shape theorems for $A_n^*[\infty]$ and $A_n^†[\infty]$ provide less precise fluctuation bounds than $A_n[\infty]$
2. Finiteness of trees in the forest remains an open problem
3. Straightness of branches has not been proven

Future Directions

The paper proposes four open problems:

1. Relationship with stationary models in external DLA
2. Whether the directed IDLA forest can approximate the infinite IDLA tree $T_\infty$
3. Whether all trees in the forest are almost surely finite
4. Fluctuation control and straightness of branches

In-Depth Evaluation

Strengths

1. Significant Theoretical Contribution: First construction of a translation-invariant directed forest based on IDLA, filling a gap in the field
2. Strong Technical Innovation: Clever use of abelian properties to connect different models, overcoming technical difficulties
3. Sophisticated Proof Techniques: Proofs of stabilization theorems employ refined probabilistic estimates and crossing lemmas
4. Complete Structure: Clear logical progression from finite to infinite models

Weaknesses

1. Computational Complexity: Some proof processes are highly technical with high barriers to understanding
2. Numerous Open Problems: Key questions such as tree finiteness remain unresolved
3. Limited Application Context: Discussion of practical application scenarios is relatively sparse

Impact

1. Academic Value: Opens new directions for IDLA theory and random forest research
2. Methodological Contribution: Provides a general framework for handling IDLA models with infinitely many source points
3. Foundation for Future Research: Establishes basis for research on related open problems

Applicable Scenarios

1. Study of random growth processes in probability theory
2. Modeling of aggregation phenomena in statistical physics
3. Analysis of directed graph structures in network theory
4. Study of phase transition phenomena in mathematical physics

References

The paper cites 41 related references, primarily including:

• Pioneering work on IDLA models 16, 27, 33
• Shape theorems and fluctuation studies 2, 3, 4, 22, 23, 24, 26
• Research on directed forests and random trees 6, 13, 14, 15, 18
• External DLA and stationary models 34, 35, 36, 37