In the linked image, why does a pattern form, as opposed to random noise?

Question

Image in question

This image was generated line by line, with each pixel's value determined by a set of rules:

• If the pixel is on the edge, set to the same color as the previous pixel 1 away from the edge
• If the left and right pixels on the previous line are the same, set this pixel to white.
• Otherwise, set to black.
• The first line is randomly generated, with a much higher chance of creating black than white pixels (50:1).

Using these rules, I generated the linked image using a python script. Notice, the image does not devolve into pseudo-randomness (like I expected), but seems to have a sort of pattern -- seemingly resetting after a set amount of lines.

---

My question:

What causes this behavior? Does there exist theory that can help explain this?

Answer 1

More precisely you build a https://en.wikipedia.org/wiki/Sierpinski_triangle

Sierpinski Triangle !

(p.s. please can you validate my answer ! 8for the badge; as it really seems that I gave the most precise answer!)

Answer 2

Yes it's a pattern from Game of Life, look here :

https://cp4space.wordpress.com/2013/01/06/bombers-and-basilisks/

very similar to the "replicator" !!!

and here: http://www.tznik.com/portfolio_page/simulation-of-forest-fire/

Answer 3

Represent white with $0$ and black with $1$. Then your rule can be rephrased by saying that to generate the pixel at position $k$ of row $t$, you add modulo $2$ the pixels at positions $k-1$ and $k+1$ at row $t-1$. The pixels near the edge are generated by pretending that the pixels outside the array are $0$.

Without taking the remainder modulo $2$, the rule is exactly that of the Pascal triangle. With modulo $2$, it is the same as the Sierpinski triangle. The main difference between your model and the Pascal/Sierpinski triangle is that you start with several $1$s on the first row. But since the rule is linear, the result is the same as taking several Sierpinski triangles with different horizontal positions and adding them together modulo $2$. (The other difference is that you have a finite array with a fixed boundary condition, but that's a nuisance.) Indeed, if you look at your image, you recognize copies of the Sierpinski triangle (which is highly self-similar) all over the place.

Now you made a very interesting statement that

... the image does not devolve into pseudo-randomness (like I expected), but seems to have a sort of pattern -- seemingly resetting after a set amount of lines.

I am very curious to hear about your intuition on this. Why did you expect the pattern to devolve into pseudo-randomness?

The reason that the pattern "resets" every now and then has to do with the self-similar structure of the Sierpinski triangle, in particular, with the fact that for every $n=1,2,\ldots$, the $(2^n+1)$st row of the Sierpinski triangle has exactly two non-zero elements which are at distance $2^{n+1}$ from each other. So if you start with $\ell$ black pixels on the first row (and assuming the array is very large so we can ignore the effect of the boundary), then on any row $t$ of the form $t=2^n+1$ we have at most $2\ell$ black pixels. Likewise, if $t$ has the form $2^n+2^m+1$, then there are at most $4\ell$ black pixels on row $t$, and so on.

However, it is true that such occasional resets become more and more rare as $t$ grows. Indeed if you look at your image, aside from the "reset" rows, the rows on the bottom look much more evenly distributed than the rows on the top. There is in fact a theorem due to D. Lind that states that if we ignore a negligible set of rows, then the distribution of the pixels at row $t$ among the remaining rows approaches as $t\to\infty$ to the distribution of unbiased coin flips. This is under the assumption that the first row is initialized with possibly biased coin flips.