We propose a new convergence criterion for the stochastic algorithm for the optimization of probabilities (SAOP) described in an earlier paper. The criterion is based on the dissection principle for irreducible finite Markov chains.

We present a stochastic algorithm which generates optimal probabilities for the chaos game to decompress an image represented by the fixed point of an IFS operator. The algorithm can be seen as a sort of time-inhomogeneous regenerative process. We prove that optimal probabilities exist and, by martingale methods, that the algorithm converges almost surely. The method holds for IFS operators associated with any arbitrary number of possibly overlapping affine contraction maps on the pixels space.

The aim of this paper is to take an in-depth look at the longtime behaviour of some continuous time Markovian dynamical systems and at itsnumerical analysis. We first propose a short overview of the main ergodicity propertiesof time continuous homogeneous Markov processes (stability, positive recurrence). The basictool is a Lyapunov function. Then, we investigate if these properties still hold forthe time discretization of these processes, either with constant or decreasing step (ODE method in stochasticapproximation, Euler scheme for diffusions). We point out severaladvantages of the weighted empirical random measures associated to these procedures, especially withdecreasing step, in terms of convergence and of rate of convergence. Several simulations illustrate theseresults.

We show in a very general framework the a.s. convergence of the one-dimensional Kohonen algorithm–after self-organization–to its unique equilibrium when the learning rate decreases to 0 in a suitable way. The main requirement is a log-concavity assumption on the stimuli distribution which includes all the usual (truncated) probability distributions (uniform, exponential, gamma distribution with parameter ≥ 1, etc.). For the constant step algorithm, the weak convergence of the invariant distributions towards equilibrium as the step goes to 0 is established too. The main ingredients of the proof are the Poincaré-Hopf Theorem and a result of Hirsch on the convergence of cooperative dynamical systems.

In the first part of this paper a global Kushner–Clark theorem about the convergence of stochastic algorithms is proved: we show that, under some natural assumptions, one can ‘read' from the trajectories of its ODE whether or not an algorithm converges. The classical stochastic optimization results are included in this theorem. In the second part, the above smoothness assumption on the mean vector field of the algorithm is relaxed using a new approach based on a path-dependent Lyapounov functional. Several applications, for non-smooth mean vector fields and/or bounded Lyapounov function settings, are derived. Examples and simulations are provided that illustrate and enlighten the field of application of the theoretical results.