Chaos game

Short description: Method of creating a fractal, using a polygon and an initial point selected at random inside it

Animated creation of a Sierpinski triangle using a chaos game method The way the "chaos game" works is illustrated well when every path is accounted for.

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 x0, successive iterations are formed as xk+1 = fr(xk), where fr is a member of the given IFS randomly selected for each iteration. The iterations converge to the fixed point of the IFS. Whenever x0 belongs to the attractor of the IFS, all iterations xk 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.

## Contents

* 1 Optimal value of r for every regular polygon
* 2 Expansion of the chaos game for values of r greater than 1
* 3 Restricted chaos game
* 4 Jumps other than 1/2
* 5 Chaos game used to represent sequences
* 6 See also
* 7 External links
* 8 References

## Optimal value of r for every regular polygon

Optimal value of r for every N-sided regular polygons, with N going from 5 to 20.

At each iteration of the chaos game, the point xk+1 can be placed anywhere along the line connecting the point xk and the vertex of choice, v. Defining r as the ratio between the two distances d(xk,xk+1) and d(xk,v), it is possible to find the optimal value of r, i.e., ropt, 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 ropt 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]

ropt=(1+2a)(2+2a)

In which a is calculated as:

a=∑i=1ncos⁡[i(π−θ)]

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=⌊N4⌋ where ⌊⌋ represents the integral part of the fraction.

The optimal ratio ropt has also been called the kissing ratio Kn. Abdulaziz & Said showed that Kn is[6]

11+tan⁡πnifn≡0mod4

11+2sin⁡π2nifn≡1,3mod4

11+sin⁡πnifn≡2mod4

Optimally packed regular polygons

* Pentagon (r=0.618)

Pentagon (r=0.618)

* Hexagon (r=0.667)

* Heptagon (r=0.692)

Heptagon (r=0.692)

* Octagon (r=0.707)

* Nonagon (r=0.742)

Nonagon (r=0.742)

* Decagon (r=0.764)

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., ropt, it is possible to play the chaos game using other values as well. If r>1 (the point xk+1 jumps at a greater distance than the distance between the point xk 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

* r=2.1

## Restricted chaos game

A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex. No fractal appears. However, this is an illusion, in fact this is a very special view of a Sierpiński tetrahedron that makes it look like a flat square.[7]

If the chaos game is run with a square, the fractal is not visible 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:

A point inside a square 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.

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

A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot be 1 place away (anti-clockwise) from the previously chosen vertex.

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:

A Vicsek fractal generated by the chaos game

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:

A Sierpinski carpet generated by the chaos game

## Chaos game used to represent sequences

Chaos game representation of the homo sapiens mitochondrion genome complete sequence(GenBank: EU810403.1) (r=0.5) Chaos game representation of the homo sapiens mitochondrion genome complete sequence(GenBank: EU810403.1) (r=2)

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)[8][9] and proteins (N=20, r=0.863).[5][10] Additionally, the representations of protein sequences was used to instruct ML models to predict protein features.[5][11] 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

r=2

## See also

* Chaos theory

## External links

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

## References

1. ↑ Weisstein, Eric W.. "Chaos Game". http://mathworld.wolfram.com/ChaosGame.html.
2. ↑ Barnsley, Michael F. (1993). Fractals Everywhere. doi:10.1016/C2013-0-10335-2. ISBN 978-0-12-079061-6.
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.
5. ↑ 5.0 5.1 5.2 5.3 5.4 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. doi:10.1016/j.chaos.2021.111140. Bibcode: 2021CSF...15011140A.
7. ↑ Tsuiki, Hideki (2022). "Projected images of the Sierpinski tetrahedron and other layered fractal imaginary cubes". arXiv:2205.13065 [math.DS].
8. ↑ Jeffrey, H.Joel (1990). "Chaos game representation of gene structure". Nucleic Acids Research 18 (8): 2163–2170. doi:10.1093/nar/18.8.2163. PMID 2336393.
9. ↑ Jeffrey, H.Joel (January 1992). "Chaos game visualization of sequences". Computers & Graphics 16 (1): 25–33. doi:10.1016/0097-8493(92)90067-6.
10. ↑ 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. PMID 19335894.
11. ↑ Zhou, Qian; Qi, Saibing; Ren, Cong (March 2021). "Gene essentiality prediction based on chaos game representation and spiking neural networks". Chaos, Solitons & Fractals 144. doi:10.1016/j.chaos.2021.110649. Bibcode: 2021CSF...14410649Z.

* v
* t
* e

Fractals

Characteristics|

* Fractal dimensions
* Assouad
* Box-counting
* Correlation
* Hausdorff
* Packing
* Topological
* Recursion
* Self-similarity

Iterated function
system|

* Barnsley fern
* Cantor set
* Koch snowflake
* Menger sponge
* Sierpinski carpet
* Sierpinski triangle
* Space-filling curve
* Blancmange curve
* De Rham curve
* Dragon curve
* Koch curve
* Lévy C curve
* Peano curve
* Sierpiński curve
* T-square
* n-flake

Strange attractor|

* Multifractal system

L-system|

* Fractal canopy
* Space-filling curve
* H tree

Escape-time
fractals|

* Burning Ship fractal
* Julia set
* Filled
* Newton fractal
* Lyapunov fractal
* Mandelbrot set
* Misiurewicz point
* Newton fractal
* Tricorn
* Mandelbox
* Mandelbulb

Rendering techniques|

* Buddhabrot
* Orbit trap
* Pickover stalk

Random fractals|

* Brownian motion
* Brownian tree
* Fractal landscape
* Lévy flight
* Percolation theory
* Self-avoiding walk

People|

* Georg Cantor
* Felix Hausdorff
* Gaston Julia
* Helge von Koch
* Paul Lévy
* Aleksandr Lyapunov
* Benoit Mandelbrot
* Lewis Fry Richardson
* Wacław Sierpiński

Other|

* "How Long Is the Coast of Britain?"
* Coastline paradox
* List of fractals by Hausdorff dimension
* The Beauty of Fractals (1986 book)
* Fractal art
* Making a New Science (1987 book)
* The Fractal Geometry of Nature (1982 book)
* Kaleidoscope
* Chaos theory

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Chaos game. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Chaos_game&oldid=3980631"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template