Sur quelques algorithmes récursifs pour les probabilités numériques

Pagès, Gilles

ESAIM: Probability and Statistics, Tome 5 (2001), pp. 141-170.

The aim of this paper is to take an in-depth look at the long time behaviour of some continuous time markovian dynamical systems and at its numerical analysis. We first propose a short overview of the main ergodicity properties of time continuous homogeneous Markov processes (stability, positive recurrence). The basic tool is a Lyapunov function. Then, we investigate if these properties still hold for the time discretization of these processes, either with constant or decreasing step (ODE method in stochastic approximation, Euler scheme for diffusions). We point out several advantages of the weighted empirical random measures associated to these procedures, especially with decreasing step, in terms of convergence and of rate of convergence. Several simulations illustrate these results.

Classification : 65C30, 62L20
Mots clés : ergodicity, stability, Markov process, diffusion, stochastic algorithm, ODE method, Euler scheme, empirical measure

[1] S. Aida , S. Kusuoka et D.W. Stroock, On the support of Wiener functionals, dans Asymptotic problems in Probability Theory : Wiener Functionals and Asymptotics, édité par K.D. El Worthy et N. Ikeda. Longman Scient. and Tech., New-York, Pitman Res. Notes Math. Ser. 284 (1993) 3-34. | MR | Zbl

[2] D.G. Aronson, Bounds for the fundamental solution of a parabolic equation. Bull. Amer. Math. Soc. 73 (1967) 890-903. | MR | Zbl

[3] J.G. Attali, Méthodes de stabilité pour les chaînes de Markov non fellériennes, Thèse de l'Université Paris I (1999).

[4] G. Basak et R. Bhattacharya, Stability in distributions for a class of singular diffusions. Ann. Probab. 20 (1992) 312-321. | MR | Zbl

[5] G.K. Basak, I. Hu et C.-Z. Wei, Weak convergence of recursions. Stochastic Process. Appl. 68 (1997) 65-82. | MR | Zbl

[6] M. Benaïm, Recursive Algorithms, Urn process and Chaining Number of Chain Recurrent sets. Ergodic Theory Dynam. Systems 18 (1997) 53-87. | MR | Zbl

[7] M. Benaïm, Dynamics of Stochastic Approximation Algorithms, Séminaire de Probabilités XXXIII, édité par J. Azéma, M. Émery, M. Ledoux et M. Yor. Springer, Lecture Notes in Math. 1709 (1999) 1-68. | Numdam | MR | Zbl

[8] G. Ben Arous et R. Léandre, Décroissance exponentielle du noyau de la chaleur sur la diagonale (II). Probab. Theory Related Fields 90 (1991) 377-402. | MR | Zbl

[9] A. Benveniste, M. Métivier et P. Priouret, Algorithmes adaptatifs et approximations stochastiques. Masson, Paris (1987) 367p. | Zbl

[10] S. Borovkov, Ergodicity and Stability of Stochastic Processes. Wiley Chichester (England), Wiley Ser. Probab. Stat. (1998) 585p. | MR | Zbl

[11] C. Bouton, Approximation gaussienne d'algorithmes à dynamique markovienne. Ann. Inst. H. Poincaré B 24 (1988) 131-155. | Numdam | Zbl

[12] O. Brandière et M. Duflo, Les algorithmes stochastiques contournent-ils les pièges ? Ann. Inst. H. Poincaré 32 (1996) 395-477. | Numdam | MR | Zbl

[13] G.A. Brosamler, An almost everywhere central limit theorem. Math. Proc. Cambridge Philos. Soc. 104 (1988) 561-574. | MR | Zbl

[14] I. Berkes, E. Csáki, A universal result in almost sure central limit theory. Stochastic Process. Appl. 94 (2001) 105-134. | MR | Zbl

[15] F. Chaâbane, F. Maâouia et A. Touati, Versions fortes associées aux théorèmes limites en loi pour les martingales vectorielles. Pré-pub. de l'Université de Bizerte, Tunisie (1996).

[16] S. Cheng et L. Peng, Almost sure convergence in extreme value theory. Math. Nachr. 190 (1998) 43-50. | MR | Zbl

[17] M. Duflo, Random Iterative systems. Springer, Berlin (1998).

[18] N. Dunford et J.T. Schwartz, Linear Operators. Wiley-Interscience, New-York (1958). | Zbl

[19] S. Ethier et T. Kurtz, Markov Processes, characterization and convergence. Wiley, New-York, Wiley Ser. Probab. Math. Statist. (1986) 534p. | MR | Zbl

[20] J.C. Fort et G. Pagès, Asymptotic behaviour of a Markov constant step stochastic algorithm. SIAM J. Control Optim. 37 (1999) 1456-1482. | MR | Zbl

[21] J.C. Fort et G. Pagès, Stochastic algorithms with non constant step : $a.s.$ behaviour of weighted empirical measures. Pré-pub. Université Paris 12 Val-de-Marne (1998, soumis).

[22] A. Fisher, Convex invariant means and a pathwise central limit theorem. Adv. Math. 63 (1987) 213-246. | MR | Zbl

[23] H. Ganidis, B. Roynette et F. Simonot, Convergence rate of some semi-groups to their invariant probability. Stochastic Process. Appl. 79 (1999) 243-264. | MR | Zbl

[24] P. Hall et C.C. Heyde, Martingale Limit Theory and its Application. Academic Press, New-York (1980) 308p. | MR | Zbl

[25] R.Z. Has'Minskii, Stochastic stability of differential equations. Sijthoff & Noordhoff, Alphen aan den Rijn (The Nederlands) (1980) 344p.

[26] I. Karatzas et S. Shreve, Brownian Motion and Stochastic Calculus. Springer-Verlag, New-York (1988) (2nd Ed., 1992) 470p. | MR | Zbl

[27] S. Karlin et H. Taylor, A second course in stochastic processes. Academic Press, New-York (1981) 542p. | MR | Zbl

[28] Y. Kifer, Random perturbations of Dynamical Systems. Birkhaäuser, Progr. Probab. Statist. (1988) 294p. | MR | Zbl

[29] U. Krengel, Ergodic Theorems. de Gruyter Stud. Math. (1989) 357p. | MR | Zbl

[30] H.J. Kushner et D.S. Clark, Stochastic Approximation for Constrained and Unconstrained Systems. Springer, Appl. Math. Sci. 26 (1978) 261p. | MR | Zbl

[31] H.J. Kushner, Approximation and weak convergence methods for random processes and applications to stochastic system theory. MIT Cambridge (1985). | MR | Zbl

[32] H.J. Kushner et H. Huang, Rates of convergence for stochastic approximation type algorithms. SIAM J. Control Optim. 17 (1979) 607-617. | MR | Zbl

[33] D. Lamberton et G. Pagès, Recursive computation of the invariant measure of a diffusion. Bernoulli (à paraître).

[34] M.T. Lacey et W. Philip, A note on the almost sure central limit theorem. Statist. Probab. Lett. 9 (1990) 201-205. | MR | Zbl

[35] S. Meyn et R. Tweedie, Markov chains and Stochastic Stability. Springer (1993) 550p. | MR | Zbl

[36] M. Pelletier, Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann. Appl. Probab. 8 (1998) 10-44. | MR | Zbl

[37] M. Pelletier, An almost sure central limit theorem for stochastic algorithms. J. Multivariate Anal. 71 (1999) 76-93. | MR | Zbl

[38] M. Pelletier, Efficacité asymptotique presque sûre des algorithmes stochastiques moyennisés. C. R. Acad. Sci. Paris Série I 323 (1996) 813-816 ; développé dans Asymptotic almost sure efficiency of averaged stochastic algorithms (soumis). | MR | Zbl

[39] B.T. Polyak, New Stochastic Approximation type procedures. Avtomat. i Telemakh. 7 (1990), in Russian, Automat. Remote Control 51 (1990) 107-118. | MR

[40] D. Revuz et M. Yor, Continuous martingales and Brownian Motion, 2nd Ed. Springer, Berlin (1991) 557p. | MR | Zbl

[41] D. Ruppert, Efficient estimators from a slowly convergent Robbins-Monro Process, Technical Report, School of Operations Research and Industrial, Engineering. Cornell University, Ithaca, NY, No. 781 (1985).

[42] P. Schatte, On strong versions of the central limit theorem. Math. Nachr. 137 (1988) 249-256. | MR | Zbl

[43] D.W. Stroock, Probability Theory : An analytic view. Cambridge University Press (revised edition, 1994) 512p. | MR | Zbl

[44] D. Talay, Second order discretization of stochastic differential systems for the computation of the invariant law. Stochastics Stochastics Rep. 29 (1990) 13-36. | Zbl

[45] D. Talay et L. Tubaro, Expansion of the global error for numerical schemes solving stochastic differential equations. Stochastic Anal. Appl. 8 (1990) 94-120. | MR | Zbl

[46] A. Touati, Sur les versions fortes du théorème de la limite centrale. Pré-pub. de l'Université de Marne-la-Vallée (1995).