How long is the chaos game?

DOI10.1112/BLMS.12539MaRDI QIDQ6175064zbMATH OpenFDO

Authors Ian D. Morris, Natalia Jurga

Publication date 17 August 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2007.11517

Mathematics Subject Classification ID

Recreational mathematics (00A08) Fractals (28A80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: In the 1988 textbook "Fractals Everywhere" M. Barnsley introduced an algorithm for generating fractals through a random procedure which he called the "chaos game". Using ideas from the classical theory of covering times of Markov chains we prove an asymptotic formula for the expected time taken by this procedure to generate a $delta$-dense subset of a given self-similar fractal satisfying the open set condition.

Recommendations

• On the Convergence Rate of the Chaos Game
• The chaos game on a general iterated function system
• The chaos game revisited: Yet another, but a trivial proof of the algorithm's correctness
• The generalized Sierpiński problem
• A chaos game algorithm for generalized iterated function systems

Cites work

• A MULTIFRACTAL ANALYSIS OF IFSP INVARIANT MEASURES WITH APPLICATION TO FRACTAL IMAGE GENERATION
• A proof of Furstenberg's conjecture on the intersections of \(\times p\)- and \(\times q\)-invariant sets
• An ergodic theorem for iterated maps
• Covering problems for Markov chains
• Hausdorff dimension of planar self-affine sets and measures
• scientific article; zbMATH DE number 3964277 (Why is no real title available?)
• scientific article; zbMATH DE number 194082 (Why is no real title available?)
• Iterated function systems and the global construction of fractals
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On Furstenberg's intersection conjecture, self-similar measures, and the \(L^q\) norms of convolutions
• On self-similar sets with overlaps and inverse theorems for entropy
• Random walks in the group of Euclidean isometries and self-similar measures
• Random walks on homogeneous spaces and Diophantine approximation on fractals
• Separation Properties for Self-Similar Sets
• The Hausdorff and dynamical dimensions of self-affine sponges: a dimension gap result

Cited in

(1)

• Quantitative covering and equidistribution

This page was built for publication: How long is the chaos game?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6175064)