A stochastic method to generate the Sierpinski triangle

Taking midpoint between a point and tringle vertex is a transformation that scales everything by 1/2 with this vertex as pivot.

By choosing one of such three transformations randomly you are scaling the whole triangle into three smaller copies of itself that it cosists of.

If you start with a point belonging to Sierpinski trinagle, you are adding more and more points belonging to that triangle.

Fun thing is that you can use the same algorithm with different number and kind of transformations to get other fractals with such random walk. For exaple a fractal tree or fern leaf or Sierpinski carpet.

Another interesting thing is you can start with a point not belonging to a fractal and it pretty quickly coverges. It's because fractals are attractors.

> The most common algorithm to compute IFS fractals is called the "chaos game". It consists of picking a random point in the plane, then iteratively applying one of the functions chosen at random from the function system to transform the point to get a next point. An alternative algorithm is to generate each possible sequence of functions up to a given maximum length, and then to plot the results of applying each of these sequences of functions to an initial point or shape.

Suppose you start by drawing a point uniformly at random from the triangle. We'll call this step 0. With probability 1 this point is not in the sierpinski triangle, but if we consider finite approximations of the sierpinsky triangle it is in the level 0 sierpinski triangle (see this random illustration I found on Google [1]). In particular, since the Level 0 sierpinski triangle is just the whole triangle, the initial point is uniformly distributed in the level 0 sierpinski triangle.

This is a base case. Then we can do an induction step: If we have a point which is uniformly distributed in the level k sierpinski triangle, applying the transformation (pick one vertex of the triangle at random and move halfway towards it) results in a point which is uniformly distributed in the level k+1 sierpinski triangle. This is because each corner of the level k+1 sierpinski triangle is a scaled copy of the level k sierpinski triangle.

Putting the base case and induction step together, we deduce that when we repeatedly apply the transformation of picking a vertex and moving halfway towards it, at each step k we have a point which is uniformly distributed in the level k sierpinski triangle.

This is enough to show that if we start with a sample of N points drawn uniformly from the triangle, after k steps we'll have N points drawn uniformly from the level k sierpinski triangle (i.e. an arbitrarily good approximation of the sierpinski triangle, if we make k large enough). It's not quite enough to show that if we start with a single point and record the location after each step we'll end up with something that looks like the sierpinski triangle. For that we need to establish ergodicity of the Markov chain. The details are technical but not difficult to show; basically the Markov chain needs to not get caught in fixed-length loops (aperiodicity) and never get stuck unable to reach part of the triangle (irreducibility). Both these conditions are satisfied, so the Markov chain is ergodic and starting from a single point will approximate a sierpinski triangle.

I've glossed over a bunch of details but hopefully that shows the basic idea.

[1] https://www.researchgate.net/profile/Ali-Bashir-4/publicatio...

A sketch of the argument in the IFS goes like this: consider the set of maps {f1, f2, f3} as acting on compact subsets of R^2 by the action F -> f1(F) U f2(F) U f3(F). Since the maps fi are continuous, the image is a compact set. But one can also prove that this action is a contraction mapping on the space of compact subsets of R^2 equipped with Hausdorff metric [1], and appealing to the Banach fixed point theorem [2],

(1) there is a unique compact set K fixed by this action, and

(2) the images of F converge "geometrically fast" to the set K

In other words, there is some constant 0 < r < 1 such that after k steps of this algorithm (not the random process), the distance from the k^th approximation to the Sierpinsky triangle is at most r^k

Actual convergence rates of the corresponding random process are more complicated. One of my colleagues recently wrote a paper on convergence rates of the "chaos game" (essentially what this is doing), and one can get really sharp information on how fast the random process converges [3]. However, this uses some non-trivial covering time theory for Markov processes. It's not too complex to follow, but definitely way more detail than I can write up in this note here.

[1] https://en.wikipedia.org/wiki/Hausdorff_distance

[2] https://en.wikipedia.org/wiki/Banach_fixed-point_theorem

[3] https://arxiv.org/abs/2007.11517

Edit: To see that the points converge to the Sierpinsky triangle (with no quantitative information) is a "bit less challenging" (i.e. within the realm of "standard" material - not necessarily easier!) - you can essentially reduce this problem to an application of the Birkhoff ergodic theorem [4]. Firstly, we can consider this process as a random map

pi: {1,2,3}^{\mathbb{N}} -> R^2

which is defined by taking finite subsequences (i1, i2, ..., ik) and mapping them to the images fi1(fi2( ... (fik(x_0))), and taking the limit in k, for some fixed starting point x0.

Then the "apply map fi" can be interpreted as looking at pi(sigma(i1,i2,...)) where sigma is the left-shift map sigma(i1, i2, ...) = (i2, i3, ...). But the shift map plays very nicely with the measure on the sequence space (the Bernoulli measure), in the sense that the Birkhoff ergodic theorem can be applied. This gives that for "typical" sequences of random function applications, this process will converge to the Sierpinsky triangle.

Here's another way to see it: let's say I apply maps fi1, fi2, ..., fik to my starting point x0. Then if we code the "level k" approximations to the Sierpinsky triangle in the same way [triangle (i1, ..., ik) = fi1(...(fik(initial triangle)))], the image of the point x0 will lie in triangle (i1, ..., ik). But these triangles, for large k, approximate the Sierpinsky triangle. Some more argumentation is required to deal with the case when the starting point does not sit in the Sierpinsky triangle, but this isn't a problem because of the fast convergence result explained above (if you wait a long time, all the points will be "very close"). The above ergodic theory argument is just showing that every possible finite subsequence will show up for "typical" random function applications.

[4] https://en.wikipedia.org/wiki/Ergodic_theory