# How to optimally adjust the probabilities for the random IFS algorithm?

Most fractals can be seen as attractors of a given set of affine transformations $\{T_1,\cdots,T_N \}$. There are different ways one can generate a fractal by using this information. The most two common methods are the Deterministic IFS algorithm and the Random IFS algorithm.

The Random IFS Algorithm is a generalization of the Chaos game and essentially works as follows:

Determine the affine transformations $T_1,\cdots,T_N$ that characterize the fractal, and given an initial point $P_0$, iteratively compute $$P_n= T_i(P_{n-1}),$$ where $i$ is randomly and uniformly chosen among the set $\{1,\cdots,N \}$.

This is quite a slow process, but it can be improved by adjusting the probabilities $p(T_i)$ of choosing transformation $T_i$ at each iteration. More specifically, it is known that the following probabilities are very efficient to speed up convergence: $$p(T_i) = \frac{\det(M_{T_i})}{\sum_{j=1}^N\det(M_{T_j})} \tag{1}$$

Here, $M_{T_i}$ denotes the matrix of transformation $T_i$, and $det$ is the determinant operator of a matrix. Roughly speaking, this guarantees $p(T_i)$ to be the fraction of the fractal $F$ occupied by $T_i(F)$.

My question(s):

Is there a better strategy ? Is there an optimal one? Is this an open problem ?

• On behalf of @Andres Iglesias: Here, you can find the reference that answers your question at full extent: J.M. Gutiérrez, A. Iglesias, M.A. Rodríguez: "A multifractal analysis of IFSP invariant measures with application to fractal image generation". Fractals, vol. 4, Issue 1, pp. 17-27 (1996). Last sentence of the abstract reads: Finally, as an application to fractal image generation, we show how this analysis can be used to obtain the most efficient choice for the probabilities to render the attractor of an IFS by applying the probabilistic algorithm known as “chaos game”. Dec 8, 2018 at 0:01

I don't think this determinant based formula is really the best way to pick the probabilities. As a concrete example, let's consider the IFS with functions \begin{align} f_1(\vec{x}) &= 0.98\;R(137.5^{\circ})\;\vec{x} \\ f_2(\vec{x}) &= 0.1\,\vec{x}+\langle 1,0 \rangle. \end{align} Note that $R(\theta)$ represents a rotation matrix through the angle $\theta$ so that $f_1$ represents a rotation and slight contraction centered at the origin while $f_2$ represents a strong contraction and shift to right. The result, as we'll see, is a nice self-similar spiral.

Now, the determinants are $0.98^2=0.9604$ and $0.1^2=0.01$ and their sum is $0.9704$. For the probabilities, this yields \begin{align} p_1 &= 0.9604/0.9704 \approx 0.989695 \\ p_2 &= 0.01/0.9704 \approx 0.010305 \end{align} If we apply the Random IFS Algorithm to generate 30000 points approximating the attractor using these choices of probabilities, we get the following image:

Definitely, much better than choosing equal probabilities (which yields this image) but it now seems to be too heavily weighted towards the center and too light on the edges.

A better approach accounts for the fractal dimension of the object. If you have an IFS that satisfies the open set condition and consists of similarities with ratios $\{r_1,r_2,\ldots,r_m\}$, then the similarity dimension of the object is the unique number $s$ such that $$r_1^s + r_2^s +\cdots+ r_m^s = 1.$$ As a result, $\{r_1^s,r_2^s,\ldots,r_m^s\}$ is a good probability list and, in fact, is the correct choice of probabilities if you want a uniform distribution of points throughout the attractor. In the example above with $r_1=0.98$ and $r_2=0.1$, we get $s\approx 1.51953$ and \begin{align} p_1 &= r_1^s \approx 0.969768 \\ p_2 &= r_2^s \approx 0.0302322 \end{align} Note that this scheme weights $f_2$ about three times heavier than the determinant based scheme so that we expect to trace the outer portion out more. The resulting picture looks much better:

The reason this works is rooted in the proof that the similarity dimension agrees with the Hausdorff dimension. Central to that proof is the construction of a self-similar measure on the attractor that is uniformly distributed in terms of density and it is exactly this choice of probability weights that work.

• Fascinating! I love the fact that it uses another characteristic of the fractal (its dimension). Thanks for the detailed answer. Aug 23, 2016 at 0:30
• Would you mind giving a reference for this please? Aug 23, 2016 at 1:21
• How about theorem 9.3 of the first edition of Falconer's Fractal Geometry or theorem 6.5.4 of the second edition of Edgar's Measure, Topology, and Fractal Geometry. I don't think that either of these address the specific question of the choice of the probabilities in this algorithm but they do discuss the construction of a well distributed measure on the attractor, which is really the essential issue. Aug 23, 2016 at 2:11