A stochastic algorithm to compute optimal probabilities in the chaos game (Q2749131)

Let \(A\) be a subset of a metric space representing an image one wants to reconstruct. One way to look at the problem is to take \(A\) as a closed recurrent class for a random walk that is built as follows. Contractions for the metric space are chosen successively and independently in a predefined and finite set according to some probability law and applied recursively to an initial point and its successive transforms by the contractions.NEWLINENEWLINENEWLINEThe authors of the paper being reviewed intend to choose in an optimal way the probability law used in the procedure just sketched, the aim being fast approximation. They begin by describing a stochastic algorithm and then study its probabilistic properties. They define a notion of optimality in terms of uniform distribution of mistakes and then proceed to prove the existence of optimal distributions. They are not however able to claim that a unique optimal one exists. They then prove convergence of the proposed algorithm whether the optimal distribution is unique or not. Some applications are described.