Chaos game

Last updated June 19, 2024

In mathematics, the term chaos game originally referred to a method of creating a fractal, using a polygon and an initial point selected at random inside it.^[1]^[2] 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. Repeating this iterative process a large number of times, selecting the vertex at random on each iteration, and throwing out the first few points in the sequence, will often (but not always) produce a fractal shape. Using a regular triangle and the factor 1/2 will result in the Sierpinski triangle, while creating the proper arrangement with four points and a factor 1/2 will create a display of a "Sierpinski Tetrahedron", the three-dimensional analogue of the Sierpinski triangle. As the number of points is increased to a number N, the arrangement forms a corresponding (N-1)-dimensional Sierpinski Simplex.

The term has been generalized to refer to a method of generating the attractor, or the fixed point, of any iterated function system (IFS). Starting with any point x₀, successive iterations are formed as x_k+1 = f_r(x_k), where f_r is a member of the given IFS randomly selected for each iteration. The iterations converge to the fixed point of the IFS. Whenever x₀ belongs to the attractor of the IFS, all iterations x_k stay inside the attractor and, with probability 1, form a dense set in the latter.

The "chaos game" method plots points in random order all over the attractor. This is in contrast to other methods of drawing fractals, which test each pixel on the screen to see whether it belongs to the fractal. The general shape of a fractal can be plotted quickly with the "chaos game" method, but it may be difficult to plot some areas of the fractal in detail.

With the aid of the "chaos game" a new fractal can be made and while making the new fractal some parameters can be obtained. These parameters are useful for applications of fractal theory such as classification and identification.^[3]^[4] The new fractal is self-similar to the original in some important features such as fractal dimension.

Optimal value of r for every regular polygon

At each iteration of the chaos game, the point x_k+1 can be placed anywhere along the line connecting the point x_k and the vertex of choice, v. Defining r as the ratio between the two distances d(x_k,x_k+1) and d(x_k,v), it is possible to find the optimal value of r, i.e., r_opt, for every N-sided regular polygon, that produces a fractal with optimal packing, i.e., the subscale polygons are in contact but do not overlap.

The value of r_opt can be calculated as the ratio between the length of the side of the first subscale polygon and the side of the original polygon. This ratio can be calculated geometrically:^[5]

$r_{opt}={\frac {(1+2a)}{(2+2a)}}$

In which a is calculated as:

$a=\sum _{i=1}^{n}\cos[i(\pi -\theta )]$

Where θ is the internal angle of the polygon and n is the index of the most protruding vertex, counted starting from the base, i.e. $n=\lfloor {\frac {N}{4}}\rfloor$ where $\lfloor \rfloor$ represents the integral part of the fraction.

The optimal ratio $r_{opt}$ has also been called the kissing ratio $K_{n}$ . Abdulaziz & Said showed that $K_{n}$ is^[6]

${\frac {1}{1+\tan {\frac {\pi }{n}}}}\qquad {\text{if}}\quad n\equiv 0{\bmod {4}}$

${\frac {1}{1+2\sin {\frac {\pi }{2n}}}}\quad {\text{if}}\quad n\equiv 1,3{\bmod {4}}$

${\frac {1}{1+\sin {\frac {\pi }{n}}}}\qquad {\text{if}}\quad n\equiv 2{\bmod {4}}$

Optimally packed regular polygons

Pentagon (r=0.618)
Hexagon (r=0.667)
Heptagon (r=0.692)
Octagon (r=0.707)
Nonagon (r=0.742)
Decagon (r=0.764)

Expansion of the chaos game for values of r greater than 1

While an optimally packed fractal appears only for a defined value of r, i.e., r_opt, it is possible to play the chaos game using other values as well. If r>1 (the point x_k+1 jumps at a greater distance than the distance between the point x_k and the vertex v), the generated figure extends outside the initial polygon.^[5] When r=2, the algorithm enters in a meta-stable state and generates quasi-symmetric figures. For values of r>2, the points are placed further and further from the center of the initial polygon at each iteration, the algorithm becomes unstable and no figure is generated.

Chaos game played on a heptagon with different values of r>1 (10^5 iterations)

r=1.4
r=1.6
r=2
r=2.1

Restricted chaos game

If the chaos game is run with a square, no fractal appears and the interior of the square fills evenly with points. However, if restrictions are placed on the choice of vertices, fractals will appear in the square. For example, if the current vertex cannot be chosen in the next iteration, this fractal appears:

If the current vertex cannot be one place away (anti-clockwise) from the previously chosen vertex, this fractal appears:

If the point is prevented from landing on a particular region of the square, the shape of that region will be reproduced as a fractal in other and apparently unrestricted parts of the square.

Other restrictions create further fractals:

A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot be 2 places away from the previously chosen vertex.
A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot neighbor the previously chosen vertex if the two previously chosen vertices are the same.
A point inside a pentagon repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot be the same as the previously chosen vertex.
A point inside a pentagon repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot neighbor the previously chosen vertex if the two previously chosen vertices are the same.

Jumps other than 1/2

When the length of the jump towards a vertex or another point is not 1/2, the chaos game generates other fractals, some of them very well-known. For example, when the jump is 2/3 and the point can also jump towards the center of the square, the chaos game generates the Vicsek fractal:

When the jump is 2/3 and the point can also jump towards the midpoints of the four sides, the chaos game generates the Sierpinski carpet:

Chaos game used to represent sequences

With minor modifications to the game rules, it is possible to use the chaos game algorithm to represent any well-defined sequence, i.e., a sequence composed by the repetition of a limited number of distinct elements. In fact, for a sequence with a number N of distinct elements, it is possible to play the chaos game on an N-sided polygon, assigning each element to a vertex and playing the game choosing the vertices following the progression of the sequence (instead of choosing a random vertex). In this version of the game, the generated image is a unique representation of the sequence. This method was applied to the representation of genes (N=4, r=0.5)^[7]^[8] and proteins (N=20, r=0.863).^[5]^[9] Additionally, the representations of protein sequences was used to instruct ML models to predict protein features.^[5]^[10] The expansion of the chaos game using r=2 can be useful to magnify small mutations in the comparison between two (or more) sequences.^[5]

Comparison between the chaos game representations of different genome sequences: "homo sapiens mitochondrion" (GenBank: EU810403.1) in red and "pan troglodytes mitochondrion" (GenBank: NC_001643.1) in black.

r=0.5
r=2

External links

Simulations of chaos games made with Scratch.
Explanation of the chaos game at beltoforion.de.

Related Research Articles

$Sierpiński carpet Plane fractal built from squares$

The Sierpiński carpet is a plane fractal first described by Wacław Sierpiński in 1916. The carpet is a generalization of the Cantor set to two dimensions; another such generalization is the Cantor dust.

The Sierpiński triangle, also called the Sierpiński gasket or Sierpiński sieve, is a fractal attractive fixed set with the overall shape of an equilateral triangle, subdivided recursively into smaller equilateral triangles. Originally constructed as a curve, this is one of the basic examples of self-similar sets—that is, it is a mathematically generated pattern that is reproducible at any magnification or reduction. It is named after the Polish mathematician Wacław Sierpiński, but appeared as a decorative pattern many centuries before the work of Sierpiński.

<span class="mw-page-title-main">Tetrahedron</span> Polyhedron with four faces

In geometry, a tetrahedron, also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertices. The tetrahedron is the simplest of all the ordinary convex polyhedra.

In the context of complex dynamics, a branch of mathematics, the Julia set and the Fatou set are two complementary sets defined from a function. Informally, the Fatou set of the function consists of values with the property that all nearby values behave similarly under repeated iteration of the function, and the Julia set consists of values such that an arbitrarily small perturbation can cause drastic changes in the sequence of iterated function values. Thus the behavior of the function on the Fatou set is "regular", while on the Julia set its behavior is "chaotic".

$Menger sponge Three-dimensional fractal$

In mathematics, the Menger sponge is a fractal curve. It is a three-dimensional generalization of the one-dimensional Cantor set and two-dimensional Sierpinski carpet. It was first described by Karl Menger in 1926, in his studies of the concept of topological dimension.

A dragon curve is any member of a family of self-similar fractal curves, which can be approximated by recursive methods such as Lindenmayer systems. The dragon curve is probably most commonly thought of as the shape that is generated from repeatedly folding a strip of paper in half, although there are other curves that are called dragon curves that are generated differently.

$Iterated function system Method for the construction of fractals$

In mathematics, iterated function systems (IFSs) are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry. They were introduced in 1981.

<span class="mw-page-title-main">Sierpiński curve</span>

Sierpiński curves are a recursively defined sequence of continuous closed plane fractal curves discovered by Wacław Sierpiński, which in the limit $completely fill the unit square: thus their limit curve, also called the Sierpiński curve, is an example of a space-filling curve.$

In geometry, the 120-cell is the convex regular 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol {5,3,3}. It is also called a C₁₂₀, dodecaplex (short for "dodecahedral complex"), hyperdodecahedron, polydodecahedron, hecatonicosachoron, dodecacontachoron and hecatonicosahedroid.

$Buddhabrot Probability distribution over the trajectories of points that escape the Mandelbrot fractal$

The Buddhabrot is the probability distribution over the trajectories of points that escape the Mandelbrot fractal. Its name reflects its pareidolic resemblance to classical depictions of Gautama Buddha, seated in a meditation pose with a forehead mark (tikka), a traditional oval crown (ushnisha), and ringlet of hair.

In mathematics, the T-square is a two-dimensional fractal. It has a boundary of infinite length bounding a finite area. Its name comes from the drawing instrument known as a T-square.

In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes.

In combinatorial mathematics, the Prüfer sequence of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm. Prüfer sequences were first used by Heinz Prüfer to prove Cayley's formula in 1918.

In network theory, a giant component is a connected component of a given random graph that contains a significant fraction of the entire graph's vertices.

In numerical analysis, fixed-point iteration is a method of computing fixed points of a function.

In geometry, a pentagon is any five-sided polygon or 5-gon. The sum of the internal angles in a simple pentagon is 540°.

In mathematics, the pentagram map is a discrete dynamical system on the moduli space of polygons in the projective plane. The pentagram map takes a given polygon, finds the intersections of the shortest diagonals of the polygon, and constructs a new polygon from these intersections. Richard Schwartz introduced the pentagram map for a general polygon in a 1992 paper though it seems that the special case, in which the map is defined for pentagons only, goes back to an 1871 paper of Alfred Clebsch and a 1945 paper of Theodore Motzkin. The pentagram map is similar in spirit to the constructions underlying Desargues' theorem and Poncelet's porism. It echoes the rationale and construction underlying a conjecture of Branko Grünbaum concerning the diagonals of a polygon.

An n-flake, polyflake, or Sierpinski n-gon, is a fractal constructed starting from an n-gon. This n-gon is replaced by a flake of smaller n-gons, such that the scaled polygons are placed at the vertices, and sometimes in the center. This process is repeated recursively to result in the fractal. Typically, there is also the restriction that the n-gons must touch yet not overlap.

In network science, the configuration model is a method for generating random networks from a given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the modeler to incorporate arbitrary degree distributions.

The Ulam–Warburton cellular automaton (UWCA) is a 2-dimensional fractal pattern that grows on a regular grid of cells consisting of squares. Starting with one square initially ON and all others OFF, successive iterations are generated by turning ON all squares that share precisely one edge with an ON square. This is the von Neumann neighborhood. The automaton is named after the Polish-American mathematician and scientist Stanislaw Ulam and the Scottish engineer, inventor and amateur mathematician Mike Warburton.

References

↑ Weisstein, Eric W. "Chaos Game". MathWorld .
↑ Barnsley, Michael F. (1993). Fractals Everywhere. doi:10.1016/C2013-0-10335-2. ISBN 978-0-12-079061-6.^{[ page needed ]}
↑ Jampour, Mahdi; Yaghoobi, Mahdi; Ashourzadeh, Maryam; Soleimani, Adel (September 2010). "A New Fast Technique for Fingerprint Identification with Fractal and Chaos Game Theory". Fractals. 18 (3): 293–300. doi:10.1142/s0218348x10005020.
↑ Jampour, Mahdi; Javidi, Mohammad M.; Soleymani, Adel; Ashourzadeh, Maryam; Yaghoobi, Mahdi (2010). "A New Technique in saving Fingerprint with low volume by using Chaos Game and Fractal Theory". International Journal of Interactive Multimedia and Artificial Intelligence. 1 (3): 27. doi: 10.9781/ijimai.2010.135 .
1 2 3 4 5 Arsiccio, Andrea; Stratta, Lorenzo; Menzen, Tim (December 2023). "Evaluating the chaos game representation of proteins for applications in machine learning models: prediction of antibody affinity and specificity as a case study". Journal of Molecular Modeling. 29 (12): 377. doi:10.1007/s00894-023-05777-0. PMID 37968495.
↑ Abdulaziz, Abdulrahman; Said, Judy (September 2021). "On the contraction ratio of iterated function systems whose attractors are Sierpinski n -gons". Chaos, Solitons & Fractals. 150: 111140. Bibcode:2021CSF...15011140A. doi:10.1016/j.chaos.2021.111140.
↑ Jeffrey, H.Joel (1990). "Chaos game representation of gene structure". Nucleic Acids Research. 18 (8): 2163–2170. doi:10.1093/nar/18.8.2163. PMC 330698 . PMID 2336393.
↑ Jeffrey, H.Joel (January 1992). "Chaos game visualization of sequences". Computers & Graphics. 16 (1): 25–33. doi:10.1016/0097-8493(92)90067-6.
↑ Almeida, Jonas S; Vinga, Susana (December 2009). "Biological sequences as pictures – a generic two dimensional solution for iterated maps". BMC Bioinformatics. 10 (1): 100. doi: 10.1186/1471-2105-10-100 . PMC 2678093 . PMID 19335894.
↑ Zhou, Qian; Qi, Saibing; Ren, Cong (March 2021). "Gene essentiality prediction based on chaos game representation and spiking neural networks". Chaos, Solitons & Fractals. 144: 110649. Bibcode:2021CSF...14410649Z. doi:10.1016/j.chaos.2021.110649.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Weisstein, Eric W. "Chaos Game". MathWorld .

[2] Barnsley, Michael F. (1993). Fractals Everywhere. doi:10.1016/C2013-0-10335-2. ISBN 978-0-12-079061-6.^{[ page needed ]}

[3] Jampour, Mahdi; Yaghoobi, Mahdi; Ashourzadeh, Maryam; Soleimani, Adel (September 2010). "A New Fast Technique for Fingerprint Identification with Fractal and Chaos Game Theory". Fractals. 18 (3): 293–300. doi:10.1142/s0218348x10005020.

[4] Jampour, Mahdi; Javidi, Mohammad M.; Soleymani, Adel; Ashourzadeh, Maryam; Yaghoobi, Mahdi (2010). "A New Technique in saving Fingerprint with low volume by using Chaos Game and Fractal Theory". International Journal of Interactive Multimedia and Artificial Intelligence. 1 (3): 27. doi: 10.9781/ijimai.2010.135 .

[:0-5] 1 2 3 4 5 Arsiccio, Andrea; Stratta, Lorenzo; Menzen, Tim (December 2023). "Evaluating the chaos game representation of proteins for applications in machine learning models: prediction of antibody affinity and specificity as a case study". Journal of Molecular Modeling. 29 (12): 377. doi:10.1007/s00894-023-05777-0. PMID 37968495.

[6] Abdulaziz, Abdulrahman; Said, Judy (September 2021). "On the contraction ratio of iterated function systems whose attractors are Sierpinski n -gons". Chaos, Solitons & Fractals. 150: 111140. Bibcode:2021CSF...15011140A. doi:10.1016/j.chaos.2021.111140.

[7] Jeffrey, H.Joel (1990). "Chaos game representation of gene structure". Nucleic Acids Research. 18 (8): 2163–2170. doi:10.1093/nar/18.8.2163. PMC 330698 . PMID 2336393.

[8] Jeffrey, H.Joel (January 1992). "Chaos game visualization of sequences". Computers & Graphics. 16 (1): 25–33. doi:10.1016/0097-8493(92)90067-6.

[9] Almeida, Jonas S; Vinga, Susana (December 2009). "Biological sequences as pictures – a generic two dimensional solution for iterated maps". BMC Bioinformatics. 10 (1): 100. doi: 10.1186/1471-2105-10-100 . PMC 2678093 . PMID 19335894.

[10] Zhou, Qian; Qi, Saibing; Ren, Cong (March 2021). "Gene essentiality prediction based on chaos game representation and spiking neural networks". Chaos, Solitons & Fractals. 144: 110649. Bibcode:2021CSF...14410649Z. doi:10.1016/j.chaos.2021.110649.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

v t e Fractals
Characteristics	Fractal dimensions Assouad Box-counting Higuchi Correlation Hausdorff Packing Topological Recursion Self-similarity
Iterated function system	Barnsley fern Cantor set Koch snowflake Menger sponge Sierpinski carpet Sierpinski triangle Apollonian gasket Fibonacci word Space-filling curve Blancmange curve De Rham curve Minkowski Dragon curve Hilbert curve Koch curve Lévy C curve Moore curve Peano curve Sierpiński curve Z-order curve String T-square n-flake Vicsek fractal Hexaflake Gosper curve Pythagoras tree Weierstrass function
Strange attractor	Multifractal system
L-system	Fractal canopy Space-filling curve H tree
Escape-time fractals	Burning Ship fractal Julia set Filled Newton fractal Douady rabbit Lyapunov fractal Mandelbrot set Misiurewicz point Multibrot set Newton fractal Tricorn Mandelbox Mandelbulb
Rendering techniques	Buddhabrot Orbit trap Pickover stalk
Random fractals	Brownian motion Brownian tree Brownian motor Fractal landscape Lévy flight Percolation theory Self-avoiding walk
People	Michael Barnsley Georg Cantor Bill Gosper Felix Hausdorff Desmond Paul Henry Gaston Julia Helge von Koch Paul Lévy Aleksandr Lyapunov Benoit Mandelbrot Hamid Naderi Yeganeh Lewis Fry Richardson Wacław Sierpiński
Other	"How Long Is the Coast of Britain?" Coastline paradox Fractal art List of fractals by Hausdorff dimension The Fractal Geometry of Nature (1982 book) The Beauty of Fractals (1986 book) Chaos: Making a New Science (1987 book) Kaleidoscope Chaos theory