# If the Chaos Game result is a Sierpinski attractor when the random seed is a sequence (Möbius function), does it imply that the sequence is random?

The Chaos Game is the famous method to create fractals elaborated by professor Michael Barnsley. As Wikipedia explains: "The fractal is created by iteratively creating a sequence of points, starting with the initial random point, in which each point in the sequence is a given fraction of the distance between the previous point and one of the vertices of the polygon; the vertex is chosen at random in each iteration."

I have been learning how to make the basic example, to produce the Sierpinski triangle attractor. For instance this is a very basic Python test result: I have generated the attractor by doing $$100000$$ iterations following the basic rules: (1) generate a random value from $$1$$ to $$6$$ (the equivalent of throwing a dice and getting a value), then (2) if the random value is $$1$$ or $$2$$, the next point will be at half distance of the vertex $$(0,0)$$, if it is $$3,4$$ the next point will be at half distance of the vertex $$(0.5,1)$$ and if it is $$5,6$$ the next point will be at half distance of the vertex $$(1,0)$$.

The point and my first doubt is that the Sierpinski attractor, if I am not wrong, will only appear if the sequence of random values generated at step (1) is totally random. If it is not a random sequence, the Sierpinski attractor will not appear. Is this correct?

For instance I tried for step (1) as follows: iterating $$n$$ from $$1$$ to $$100000$$, the (false) random value is $$((n\ mod\ 6)+1)$$ and then applying step (2). In that case the attractor / fractal do not appear (as expected), only some scattered points. There is not randomness in sequence used to generate the random values of the "dice". Here is the result: And here is my second doubt: if the Sierpinski attractor implies that the "dice" generation sequence is totally random, then for instance do the results when using the Möbius function imply that the Möbius function is totally random?

I did the exercise, using for step (1) the Möbius function to simulate the dice, by doing $$1000000$$ iterations following the basic rules for step (2): if $$\mu(n)=-1$$, the next point will be at half distance of the vertex $$(0,0)$$ (like getting a random $$1$$ or $$2$$ from a dice), if $$\mu(n)=0$$ the next point will be at half distance of the vertex $$(0.5,1)$$ (like getting a random $$3$$ or $$4$$ from a dice), and if $$\mu(n)=1$$ the next point will be at half distance of the vertex $$(1,0)$$ (like getting a random $$5$$ or $$6$$ from a dice). And this is the result, the Sierpinski attractor appears as well (more noisy, but the structure of the fractal is quite visible): I would like to share the following questions:

1. If the Sierpinski attractor appears, does it mean that the sequence used to simulate the dice is random, or a non-random sequence can also generate the Sierpinski attractor?

2. In the case of the Möbius function, would it mean that its behavior is the behavior of a totally random sequence?

Thank you!

(I have included the elementary number theory tag because the question is also related with the properties of the Möbius function)

• Your procedure is equivalent to rolling a three-sided die and moving closer to the 1st, 2nd, or 3rd vertex accordingly. The Sierpinski attractor will appear if every finite sequence of 1s, 2s, and 3s eventually appears in the sequence. This does not necessarily mean that the sequence is random; for example, it could be the sequence 123111213212223313233111112113..., i.e. (1)(2)(3)(11)(12)(13)(21)(22)(23)(31)(32)(33)(111)(112)(113)...
– user856
Jul 21, 2015 at 2:51
• You also have to ask yourself what it means for a particular sequence to be "random". The matter is quite subtle, and the analogous question for numbers is meaningless: Is 9 random? Is 4?
– user856
Jul 21, 2015 at 2:54
• @Rahul thanks for the comments and example.In the question I am using (n mod 6)+1 as a sequence to simulate the dice that do not show the attractor,that sequence would contain finite sequences of 1s, 2s and 3s, but the attractor do not appear.For instance:if n is not square or prime,go to vertex (0,0) (dice 1,2),in other case if n is perfect square go to vertex (0.5,1) (dice 3,4) and finally if it is prime go to vertex (1,0) (dice 5,6).That sequence does not show the Sierpinski attractor as well, and it should contain every finite sequence of 1s,2s and 3s (if I understood correctly). Jul 21, 2015 at 3:08
• @Rahul, it's not clear to me that it's sufficient for every finite sequence from $\{1, 2, 3\}$ to appear everywhere in order to get Sierpinski; am I missing something? Jul 21, 2015 at 3:11
• Why don't you use the ternary digits of $\pi$ or some other interesting number to determine your sequence. Or you might try a sequence generated by an interesting cellular automaton or a gray code or the iteration of a chaotic function. These are all deterministic but likely to generate the full Sierpinski triangle. Jul 31, 2015 at 10:15

Let's look at Sierpinski. Let me reformulate things:

• Given an infinite sequence $A=a_0, a_2, a_2, . . .$ of numbers in $\{1, 2, 3\}$ (no need for 4, 5, and 6),

• we build a sequence of points $p_0, p_1, p_2, . . .$ in the plane according to the usual rules;

• we finally let $P_A$ be the set of limit points of $\{p_0, p_1, p_2, . . .\}$. ($x$ is a limit point of $S$ if, for any $\epsilon>0$, there is a $y\in S$ - other than $x$ itself - which is within $\epsilon$ of $S$.)

We know that any sufficiently random sequence $A$ will have $P_A=$ the Sierpinski triangle $\mathfrak{T}$. One way to phrase this is: $\{A: P_A=\mathfrak{T}\}$ has measure 1 as a subset of $3^\omega$ (=the set of infinite sequences from $\{1, 2, 3\}$). In particular, $\{A: P_A=\mathfrak{T}\}$ is dense: given any finite sequence $\sigma\in3^{<\omega}$ there is an infinite sequence $A\in 3^\omega$ such that $\sigma\prec A$ and $P_A=\mathfrak{T}$.

Your question, then, is: what can we conclude about $A$, if we know that $P_A=\mathfrak{T}$? In particular, can we conclude that $A$ is random?

Well, this will certainly hinge on what we mean by "random," but one property that every reasonable definition of randomness will have is the following: if $A\in 3^\omega$ is random, then $$\lim_{n\rightarrow\infty} {\vert\{i: i<n, a_i=1\}\vert\over n}={1\over 3},$$ that is, one-third of the terms of $A$ are "$1$."

Claim: there is a sequence $A\in 3^\omega$ such that $P_A=\mathfrak{T}$, but $$\limsup_{n\rightarrow\infty} {\vert\{i: i<n, a_i=1\}\vert\over n}=1$$ and $$\liminf_{n\rightarrow\infty} {\vert\{i: i<n, a_i=1\}\vert\over n}=0.$$

Proving this completely is a good exercise. Basically, we build $A$ in stages, by performing one of three actions:

• Add a long string of $1$s to $A$-so-far (make the limsup big).

• Add a long string of not-$1$s to $A$-so-far (make the liminf small).

• Pick some point $x\in\mathfrak{T}$ and some $\epsilon>0$, and add a string of numbers to $A$-so-far so that we wind up within $\epsilon$ of $x$.

Of course, this last step isn't obviously possible: the reason we can do it is that $\mathfrak{T}$ is dense. A second observation is: this procedure only tells us how to make $P_A$ contain countably many points $x\in\mathfrak{T}$; how can we make sure $P_A$ contains all of $\mathfrak{T}$? The answer is that we use a countable dense subset of $\mathfrak{T}$. Finally, how do we know that $P_A$ only consists of points in $\mathfrak{T}$? Well, it turns out we get this for free from the fact that we started our sequence with a point in $\mathfrak{T}$.

So, no stochastic properties of $A$ can be inferred just from knowing that $P_A$ is "nice." For other attractors, the situation is identical.

• this answer and Rahul's comments were very interesting. Thank you for the time you took for this great explanation! If I understood correctly, then for instance applied to the Möbius function, we can not infer the stochastic properties (e.g. randomness) of if just knowing that $P_A=\mathfrak{T}$, right? Please may I ask you one last thing? by looking at the results when applying Möbius to the Chaos Game, is it possible to infer something (any insight) about the properties of the Möbius function or it is just a (let's say) nice graph? Jul 21, 2015 at 3:25
• Neat construction! However, I don't think that the set of limit points of the sequence being the same as the Sierpinski triangle implies that the process generates a nice image of the Sierpinski triangle. It's quite likely that points will not be uniformly distributed over the attractor. In technical terms, the self-similar measure generated by your procedure is very different from that generated by a random procedure. It might very well be concentrated on a line segment and that's image the procedure would generate. Jul 31, 2015 at 10:11