Careful chaos:
taming random sequences in
the chaos game

Danny Heap
danny@gibbs.med.utoronto.ca

The chaos game provides a computationally tractable method for rendering an Iterated Function System (IFS) on a device with a finite resolution, for example a computer monitor. Given a transformation

$$W = w_1 \cup \cdots \cup w_n,$$

Where each $w_i$ is an affine transformation and a contraction. Suppose the largest of the $i$ contractions is $c_j<1$, corresponding to $w_j$. To guarantee that the image of an $N\times N$ square is within $1$ pixel of the fixed point of $W$, you would need to iterate $w_j$ $k$ times so that $N$ $\leq$ $1/c_j^k$, in other words $k$ $\geq$ $\log N/\log(1/c_j)$ (the $log$ of $N$ to the base $1/c_j$). In order to render the entire fractal would require all length-$k$ compositions of the $i$ transformations, or $i^k$ transformations.

However, rendering squares is computationally more expensive than rendering points, but both are compact subsets of $\mathbb{R}^2$, and equally suitable as grist for our IFS mill. Also, rendering two length-$k$ compositions of the $w_i$ is more expensive than using the length-$(k-1)$ suffix of one composition as the prefix of the next. Finally, some of the transformations require fewer iterations than others, if they are composed of transformations with smaller contractions. These ideas form the basis of the chaos game.

    choose point $z_0$ 


while (you have patience...) 


choose transformation $w_i$ 

$z_n$ $=$ 
$w_i(z_{n-1})$ 


end while 

Since the desired fractal $\mathcal{F}$ is the fixed point of $W$, it's not hard to show that this method gets arbitrarily close to to $\mathcal{F}$. Suppose $i_1i_2\cdots i_k$ is a string of digits, $i_j$ $\in$ $\{1,\ldots, n\}$, each $i_j$ occurring with nonzero probability in a random sequence. The chaos game executes the composition $w_{i_k} \circ \cdots\circ w_{i_1}$ with probability $p_{i_1}\cdots p_{i_k}$, where $p_{i_j}$ is the probability of digit $i_j$ appearing. So, for a sufficiently long sequence you can be confident that there is a point near¹address $i_k\cdots i_1$ (the image of $\mathcal{F}$ under $w_{i_k} \circ \cdots\circ w_{i_1}$). Thus, after some $N$ points are chosen, the chaos game ``fills out'' $\mathcal{F}$: every point of $\mathcal{F}$ is within 1 pixel of some $z_i$.

By choosing the probabilities $p_i$ carefully the length of the sequence $N$ may be pretty modest, for example a few tens of thousands to render Sierpinski's gasket on a $512\times 512$ grid, and the chaos game is a reasonable method for rendering fractals. However, it's reasonable to ask what role does the random choice of the $w_i$ play?

I propose that we either modify a random sequence, or use a thoroughly non-random sequence to investigate the effects this has on the resulting fractal-like objects. These modifications may alter one of (a) the resulting object, i.e. the limit of the set of pixels drawn by the chaos game, or (b) the uniformity of rendering the object.