In class we have recently looked at the geometry of random objects such as a random walk or Brownian motion. As of 2022, we have a very good theoretical understanding of random walk/ Brownian motion. For example, we know that if a random walker takes 士1 steps with equal probability starting at the origin, we know that the distance from the origin after n steps grows approximately like n1/2 .

1    Diffusion Limited Aggregation

In this project we will investigate a different process, Diffusion Limited Aggregation.  Even though it has a very simple definition, very little is known about this process.

We will use consider the following version of the process.

First, an informal description:  Consider the half infinite strip [0 , 1] × [0, ~), extending infinitely to the right. Suppose a stream of particles starts far to the right, and each particle walks until it hits the bottom of the strip. One a particle has landed at the bottom, the next particle starts its walk. It stops when it either hits the left side, or if it hits another particle that has already landed.

Next, a more formal description.

1.  Choose a large integer W ≥ 1 and another large integer a. Instead of walking on the strip [0, 1] × [0, ~), we will walk on the rectangular lattice {0, 1, . . . , W 一 1} × {0, 1, 2, 3, . . . , AW 一 1}.

2.  Choose an integer t, the total number of particles.

3.  For each particle, choose a starting location at the top edge of the rectangular lattice uniformly at random. There are W possible places to start.

●  Suppose the particle is not adjacent to a landed particle and not at the bottom edge, say at (x, y). The particle takes a step in one of the four directions {(x 一 1, y), (x + 1, y), (x, y 一 1)} with equal probability, 1/3, 1/3, 1/3.  (If the particle is on the left or right edge, e.g. x = 0, you should assume that any step off the edge ‘wraps’ around to the other side.

4.  Once the particle reaches the bottom (y = 0), or is adjacent to another landed particle, stop the particle. Create a new particle and go to step 3. Keep doing this until you have landed t particles.

2    Programming Tasks

For bigger simulations, you may want to install jupyter notebook on your personal computer rather than running it in colab. There are instructions on the course website.

1.  Write a function dla(W,  A,  t) which generates the result of the DLA process described above.  It should return a W × AW matrix.

2.  Draw an image of the result of dla(W,A,  t) (using imshow), for W = {100, 200, 300} and t = 10000 and A = 2. In the image, the particles should be colored according to their ordering. You may need to implement the improvement below, first. Note: it may be desire-able to rotate the images in your written writeup. This is fine, just label accordingly.

3.  Performance can be greatly improved with the following observation: instead of starting the particles at the top, we can start the particles at height h + 1 where h is the height of the highest landed particle. Implement this change.

4.  Investigate the ‘growth rate’ of the process. That is, fix H = 100 and let T be the first time that a particle reaches height H . Can you come with a simple formula that describes the approximate relationship between T and W? You should be able to justify your answer using experimental data, and plots.

5.  Another related phenomenon is that the image is very ‘porous’ . If we define the density ρ = t/HW , we see that it is unlikely to be very close to 1 Can you give a heuristic reason for why this is the case? Can you give an approximate value of the density? How does this estimated density depend on W and t?