Markovian perturbations of discrete iterations: Lyapunov functions, global minimization, and associative memory

The aim of this paper is twofold. First, we shall focus on Lyapunov functions for discrete dynamical systems. We shall propose a methodology for building Lyapunov functions. This methodology will be based upon the introduction of small random perturbations in the deterministic dynamics. Then we shall deal with concentration results for the perturbed dynamics. Our ultimate goal is to force the convergence of the perturbed process towards a set of specified attractors of the deterministic system. We shall illustrate our results on the paradigms of global minimization and associative memory. Our formalism will be illustrated on new algorithms for which the asymptotic analysis can be done rigorously.