# Sierpinski Triangle and the Chaos Game

The chaos game is a way to construct (an approximation) of Sierpinski triangle. It's clear (using Thales' theorem!) that if we begin with a point on the sierpinski triangle, then we will never leave it. However, the choice of the beginning point is not important! The final shape will be quite like the real triangle, even if the first point is not on the triangle! Why?

Thanks!

P.S. I'm still working on my tomorrow's lecture!

• For almost any sequence of randomizations, the set of limit points is the full S. triangle. BUT: This Q doesn't belong here - try math.stackexchange.com – Anthony Quas Apr 21 '13 at 20:25
• If your starting point is at distance $d$ from $P \in T$, and you move half-way toward the vertex $A$, the result is $d/2$ from the image of $P$. So if you start at distance $d$ from the triangle, after $n$ steps you are at distance at most $2^{−n}$ from Sierpinski's triangle. – Douglas Zare Apr 21 '13 at 20:34
• Thanks for your comments. Is this question too elementary to be asked here? – Behzad Apr 21 '13 at 21:30
• I think @Douglas Zare's answer is half of the answer. It explains why any limit points belong to the Sierpinksi triangle. You presumably also want to say that every point on the Sierpinksi triangle is the limit point of some subsequence of your $x_n$'s? In this case, given any point of the triangle, it belongs to some level $k$ sub-triangle. Code that sub-triangle by the sequence of $k$ vertices that you have to choose to fall into it. Then with probability 1, you choose that sequence of $k$ vertices infinitely many times, so you fall in the sub-triangle inf many times. – Anthony Quas Apr 21 '13 at 22:01

Because the iterated function system that defines the Sierpinski gasket is a contraction mapping in the metric space of non-empty compact subsets of $\mathbb{R}^{2}$ with the Sierpinski gasket as its only fixed point. So if you start with any non-empty compact set it will "get closer" to the Sierpinski triangle each time you apply the iterated function system. Here the "getting closer" is in the sense of the Hausdorff metric on subset of $\mathbb{R}^{2}$. (Yes I know the metric is definable in considerably more generality but we only use this instance here.)
• I don't think this answers the question. This assumes you're applying the operation $S\mapsto f_1(S)\cup f_2(S)\cup f_3(S)$. The OP was asking about the chaos game, which is where you choose your favourite $x_0$ and define $x_{k+1}=f_{N_{k+1}}(x_k)$, where $N_{k+1}$ takes values in the set $\lbrace 1,2,3\\}$ with equal probability. – Anthony Quas Apr 21 '13 at 21:57
• If you choose some initial point $x_0$ and then applying some sequence of the three maps is equivalent to picking one of the points in the image of the IFS which by the Hausdorff convergence must approaching the Sierpinski gasket. So my original answer was not quite complete. – BSteinhurst Apr 21 '13 at 23:52