Computer Science/Discrete Mathematics Seminar II

In a paper from 1981 Sanders and Witten introduced the (2-Dim) DLA process --- a stochastic growth model, in which a "Discrete fractal" subset of $Z^2$ is grown from the origin in an inductive process, where in each step a particle, starting at "infinity" makes a simple random walk on $Z^2$ until it becomes a neighbor of the aggregate, then glues to it. The process turned out to be extremely difficult to analyze, and in spite of attracting a lot of attention, very little is known on the structure of the n-th step set or the limit set. In this lecture we will define a family of 1-dimensional analogs of the standard DLA process - the 1-DLA process, which are more prone to analysis. The process is parameterized by an integer random variable $X$, which we will call the step distribution. The aggregates are subsets of $Z$ built inductively by starting with the set $A_0 = \{0\}$ and then at each step releasing a particle "near infinity" , letting it make a random walk with jump distribution $X$ until it hits $A_n$. If the particle first hits the set $A_n$ by making a jump from $x\not\in A_n$ to $a\in A_n$ then we set $A_{n+1} = A_n \cup \{x\}$. (precise definitions will be given). We will analyze this process for various choices of the step distribution, getting bounds for the growth of the diameter, and show a transient walk for whom the limit aggregate is the whole of $Z$ despite the diameter growing super exponentially. Joint work with O. Angel, I. Benjamini and G. Kozma.