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

Gilles Pagès

ESAIM: Probability and Statistics (2010)

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

Abstract

top
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

top

Pagès, Gilles. "Sur quelques algorithmes récursifs pour les probabilités numériques." ESAIM: Probability and Statistics 5 (2010): 141-170. <http://eudml.org/doc/197755>.

@article{Pagès2010,
abstract = { 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. },
author = {Pagès, Gilles},
journal = {ESAIM: Probability and Statistics},
keywords = {Ergodicity; stability; Markov process; diffusion; stochastic algorithm; ODE method; Euler scheme; empirical measure.; ergodicity; diffusion; Euler scheme; empirical measure},
language = {eng},
month = {3},
pages = {141-170},
publisher = {EDP Sciences},
title = {Sur quelques algorithmes récursifs pour les probabilités numériques},
url = {http://eudml.org/doc/197755},
volume = {5},
year = {2010},
}

TY - JOUR
AU - Pagès, Gilles
TI - Sur quelques algorithmes récursifs pour les probabilités numériques
JO - ESAIM: Probability and Statistics
DA - 2010/3//
PB - EDP Sciences
VL - 5
SP - 141
EP - 170
AB - 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.
LA - eng
KW - Ergodicity; stability; Markov process; diffusion; stochastic algorithm; ODE method; Euler scheme; empirical measure.; ergodicity; diffusion; Euler scheme; empirical measure
UR - http://eudml.org/doc/197755
ER -

References

top
  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.  
  2. D.G. Aronson, Bounds for the fundamental solution of a parabolic equation. Bull. Amer. Math. Soc.73 (1967) 890-903.  
  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.  
  5. G.K. Basak, I. Hu et C.-Z. Wei, Weak convergence of recursions. Stochastic Process. Appl.68 (1997) 65-82.  
  6. M. Benaïm, Recursive Algorithms, Urn process and Chaining Number of Chain Recurrent sets. Ergodic Theory Dynam. Systems18 (1997) 53-87.  
  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.  
  8. G. Ben Arous et R. Léandre, Décroissance exponentielle du noyau de la chaleur sur la diagonale (II). Probab. Theory Related Fields90 (1991) 377-402.  
  9. A. Benveniste, M. Métivier et P. Priouret, Algorithmes adaptatifs et approximations stochastiques. Masson, Paris (1987) 367p.  
  10. S. Borovkov, Ergodicity and Stability of Stochastic Processes. Wiley Chichester (England), Wiley Ser. Probab. Stat. (1998) 585p.  
  11. C. Bouton, Approximation gaussienne d'algorithmes à dynamique markovienne. Ann. Inst. H. Poincaré B24 (1988) 131-155.  
  12. O. Brandière et M. Duflo, Les algorithmes stochastiques contournent-ils les pièges ? Ann. Inst. H. Poincaré 32 (1996) 395-477.  
  13. G.A. Brosamler, An almost everywhere central limit theorem. Math. Proc. Cambridge Philos. Soc.104 (1988) 561-574.  
  14. I. Berkes, E. Csáki, A universal result in almost sure central limit theory. Stochastic Process. Appl.94 (2001) 105-134.  
  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.  
  17. M. Duflo, Random Iterative systems. Springer, Berlin (1998).  
  18. N. Dunford et J.T. Schwartz, Linear Operators. Wiley-Interscience, New-York (1958).  
  19. S. Ethier et T. Kurtz, Markov Processes, characterization and convergence. Wiley, New-York, Wiley Ser. Probab. Math. Statist. (1986) 534p.  
  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.  
  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.  
  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.  
  24. P. Hall et C.C. Heyde, Martingale Limit Theory and its Application. Academic Press, New-York (1980) 308p.  
  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.  
  27. S. Karlin et H. Taylor, A second course in stochastic processes. Academic Press, New-York (1981) 542p.  
  28. Y. Kifer, Random perturbations of Dynamical Systems. Birkhaäuser, Progr. Probab. Statist. (1988) 294p.  
  29. U. Krengel, Ergodic Theorems. de Gruyter Stud. Math. (1989) 357p.  
  30. H.J. Kushner et D.S. Clark, Stochastic Approximation for Constrained and Unconstrained Systems. Springer, Appl. Math. Sci. 26 (1978) 261p.  
  31. H.J. Kushner, Approximation and weak convergence methods for random processes and applications to stochastic system theory. MIT Cambridge (1985).  
  32. H.J. Kushner et H. Huang, Rates of convergence for stochastic approximation type algorithms. SIAM J. Control Optim.17 (1979) 607-617.  
  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.  
  35. S. Meyn et R. Tweedie, Markov chains and Stochastic Stability. Springer (1993) 550p.  
  36. M. Pelletier, Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann. Appl. Probab.8 (1998) 10-44.  
  37. M. Pelletier, An almost sure central limit theorem for stochastic algorithms. J. Multivariate Anal.71 (1999) 76-93.  
  38. M. Pelletier, Efficacité asymptotique presque sûre des algorithmes stochastiques moyennisés. C. R. Acad. Sci. Paris Série I323 (1996) 813-816 ; développé dans Asymptotic almost sure efficiency of averaged stochastic algorithms (soumis).  
  39. B.T. Polyak, New Stochastic Approximation type procedures. Avtomat. i Telemakh. 7 (1990), in Russian, Automat. Remote Control 51 (1990) 107-118.  
  40. D. Revuz et M. Yor, Continuous martingales and Brownian Motion, 2nd Ed. Springer, Berlin (1991) 557p.  
  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.  
  43. D.W. Stroock, Probability Theory: An analytic view. Cambridge University Press (revised edition, 1994) 512p.  
  44. D. Talay, Second order discretization of stochastic differential systems for the computation of the invariant law. Stochastics Stochastics Rep.29 (1990) 13-36.  
  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.  
  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 ?

top

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.