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

Gilles Pagès

ESAIM: Probability and Statistics (2001)

  • Volume: 5, page 141-170
  • ISSN: 1292-8100


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.

How to cite


Pagès, Gilles. "Sur quelques algorithmes récursifs pour les probabilités numériques." ESAIM: Probability and Statistics 5 (2001): 141-170. <>.

author = {Pagès, Gilles},
journal = {ESAIM: Probability and Statistics},
keywords = {ergodicity; stability; Markov process; diffusion; stochastic algorithm; ODE method; Euler scheme; empirical measure},
language = {fre},
pages = {141-170},
publisher = {EDP-Sciences},
title = {Sur quelques algorithmes récursifs pour les probabilités numériques},
url = {},
volume = {5},
year = {2001},

AU - Pagès, Gilles
TI - Sur quelques algorithmes récursifs pour les probabilités numériques
JO - ESAIM: Probability and Statistics
PY - 2001
PB - EDP-Sciences
VL - 5
SP - 141
EP - 170
LA - fre
KW - ergodicity; stability; Markov process; diffusion; stochastic algorithm; ODE method; Euler scheme; empirical measure
UR -
ER -


  1. [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. Zbl0790.60047MR1354161
  2. [2] D.G. Aronson, Bounds for the fundamental solution of a parabolic equation. Bull. Amer. Math. Soc. 73 (1967) 890-903. Zbl0153.42002MR217444
  3. [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. [4] G. Basak et R. Bhattacharya, Stability in distributions for a class of singular diffusions. Ann. Probab. 20 (1992) 312-321. Zbl0749.60073MR1143422
  5. [5] G.K. Basak, I. Hu et C.-Z. Wei, Weak convergence of recursions. Stochastic Process. Appl. 68 (1997) 65-82. Zbl0923.60026MR1454579
  6. [6] M. Benaïm, Recursive Algorithms, Urn process and Chaining Number of Chain Recurrent sets. Ergodic Theory Dynam. Systems 18 (1997) 53-87. Zbl0921.60061MR1609499
  7. [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. Zbl0955.62085MR1767993
  8. [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. Zbl0734.60027MR1133372
  9. [9] A. Benveniste, M. Métivier et P. Priouret, Algorithmes adaptatifs et approximations stochastiques. Masson, Paris (1987) 367p. Zbl0639.93002
  10. [10] S. Borovkov, Ergodicity and Stability of Stochastic Processes. Wiley Chichester (England), Wiley Ser. Probab. Stat. (1998) 585p. Zbl0917.60005MR1658404
  11. [11] C. Bouton, Approximation gaussienne d’algorithmes à dynamique markovienne. Ann. Inst. H. Poincaré B 24 (1988) 131-155. Zbl0643.60038
  12. [12] O. Brandière et M. Duflo, Les algorithmes stochastiques contournent-ils les pièges ? Ann. Inst. H. Poincaré 32 (1996) 395-477. Zbl0849.62043MR1387397
  13. [13] G.A. Brosamler, An almost everywhere central limit theorem. Math. Proc. Cambridge Philos. Soc. 104 (1988) 561-574. Zbl0668.60029MR957261
  14. [14] I. Berkes, E. Csáki, A universal result in almost sure central limit theory. Stochastic Process. Appl. 94 (2001) 105-134. Zbl1053.60022MR1835848
  15. [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. [16] S. Cheng et L. Peng, Almost sure convergence in extreme value theory. Math. Nachr. 190 (1998) 43-50. Zbl0932.60028MR1611675
  17. [17] M. Duflo, Random Iterative systems. Springer, Berlin (1998). 
  18. [18] N. Dunford et J.T. Schwartz, Linear Operators. Wiley-Interscience, New-York (1958). Zbl0084.10402
  19. [19] S. Ethier et T. Kurtz, Markov Processes, characterization and convergence. Wiley, New-York, Wiley Ser. Probab. Math. Statist. (1986) 534p. Zbl0592.60049MR838085
  20. [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. Zbl0954.60057MR1710228
  21. [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. [22] A. Fisher, Convex invariant means and a pathwise central limit theorem. Adv. Math. 63 (1987) 213-246. Zbl0627.60034MR877784
  23. [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. Zbl0962.60073MR1671843
  24. [24] P. Hall et C.C. Heyde, Martingale Limit Theory and its Application. Academic Press, New-York (1980) 308p. Zbl0462.60045MR624435
  25. [25] R.Z. Has’minskii, Stochastic stability of differential equations. Sijthoff & Noordhoff, Alphen aan den Rijn (The Nederlands) (1980) 344p. 
  26. [26] I. Karatzas et S. Shreve, Brownian Motion and Stochastic Calculus. Springer-Verlag, New-York (1988) (2nd Ed., 1992) 470p. Zbl0638.60065MR917065
  27. [27] S. Karlin et H. Taylor, A second course in stochastic processes. Academic Press, New-York (1981) 542p. Zbl0469.60001MR611513
  28. [28] Y. Kifer, Random perturbations of Dynamical Systems. Birkhaäuser, Progr. Probab. Statist. (1988) 294p. Zbl0659.58003MR1015933
  29. [29] U. Krengel, Ergodic Theorems. de Gruyter Stud. Math. (1989) 357p. Zbl0575.28009MR797411
  30. [30] H.J. Kushner et D.S. Clark, Stochastic Approximation for Constrained and Unconstrained Systems. Springer, Appl. Math. Sci. 26 (1978) 261p. Zbl0381.60004MR499560
  31. [31] H.J. Kushner, Approximation and weak convergence methods for random processes and applications to stochastic system theory. MIT Cambridge (1985). Zbl0551.60056MR741469
  32. [32] H.J. Kushner et H. Huang, Rates of convergence for stochastic approximation type algorithms. SIAM J. Control Optim. 17 (1979) 607-617. Zbl0418.93093MR540841
  33. [33] D. Lamberton et G. Pagès, Recursive computation of the invariant measure of a diffusion. Bernoulli (à paraître). Zbl1006.60074
  34. [34] M.T. Lacey et W. Philip, A note on the almost sure central limit theorem. Statist. Probab. Lett. 9 (1990) 201-205. Zbl0691.60016MR1045184
  35. [35] S. Meyn et R. Tweedie, Markov chains and Stochastic Stability. Springer (1993) 550p. Zbl0925.60001MR1287609
  36. [36] M. Pelletier, Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann. Appl. Probab. 8 (1998) 10-44. Zbl0965.62065MR1620405
  37. [37] M. Pelletier, An almost sure central limit theorem for stochastic algorithms. J. Multivariate Anal. 71 (1999) 76-93. Zbl0951.62071MR1721961
  38. [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). Zbl0865.60020MR1416182
  39. [39] B.T. Polyak, New Stochastic Approximation type procedures. Avtomat. i Telemakh. 7 (1990), in Russian, Automat. Remote Control 51 (1990) 107-118. MR1071220
  40. [40] D. Revuz et M. Yor, Continuous martingales and Brownian Motion, 2nd Ed. Springer, Berlin (1991) 557p. Zbl0731.60002MR1083357
  41. [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. [42] P. Schatte, On strong versions of the central limit theorem. Math. Nachr. 137 (1988) 249-256. Zbl0661.60031MR968997
  43. [43] D.W. Stroock, Probability Theory : An analytic view. Cambridge University Press (revised edition, 1994) 512p. Zbl0925.60004MR1267569
  44. [44] D. Talay, Second order discretization of stochastic differential systems for the computation of the invariant law. Stochastics Stochastics Rep. 29 (1990) 13-36. Zbl0697.60066
  45. [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. Zbl0718.60058MR1091544
  46. [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). 

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.