Skip to main content
9 of 9
Commonmark migration

Formal justification of the Chaos game in the Sierpinski triangle

I want to justify why the Chaos game works to produce Sierpinski triangle. I use a theorem taken from Massopust Interpolation and Approximation with Splines and Fractals.

Suppose that $(X,d)$ is a compact metric space and $(X,F,P)$ is an IFS with probabilities. Futher assume that $m \in P(X)$ is the invariant fractal measure. Let $x_0 \in X$ be arbitrary and let $x_k = f_i(x_{k-1})$ for $k \in \mathbb{N}$ where $f_i \in F$ is chosen with probability $p_i \in P$.

Then, for almost all random sequences $\{x_k\}$, the following equality holds: $$m(A) = \lim_{k \to \infty} \frac{N(A \cap \{x_l:l = 0,1,\ldots,k)\})}{k+1}$$ for all $A \in B(H(X))$ with $m(fr(A)) = 0$ and where $N(B)$ denotes the number of points in set $B$.

The right hand side of the equation represents the fraction of points that lie on set $A$. So if I choose the IFS generating the Sierpinski triangle such as in this video I would need that $\mu(\mathcal{a}) \sim 1$ where $\mathcal{a}$ is the Sierpinski triangle.

I tried to compute by hand the invariant fractal measure for the IFS that produces the Sierpinski triangle but I was obtaining a wrong results. Is that the right way to go? How can I justify that the chaos game produces the Sierpinski triangle in the limit using this theorem?


Definitions

Given a IFS with probabilities, $(X,\{f_i\})$ formed by a compact metric space $(X,d)$ and a finite number of contractive mappings $f_i:X \to X$ and a set of probabilities $p_i > 0$ with $\sum p_i = 1$, the measure $\mu$ such that $\mu = \sum p_i \cdot \mu \circ f_i ^{-1}$ is called $p$-balanced measure or invariant fractal measure.

Notes

This question gives a formal answer to Sierpinski Triangle and the Chaos Game.

user1868607
  • 439
  • 4
  • 16