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.
Mots clés : ergodicity, stability, Markov process, diffusion, stochastic algorithm, ODE method, Euler scheme, empirical measure
@article{PS_2001__5__141_0, author = {Pag\`es, Gilles}, title = {Sur quelques algorithmes r\'ecursifs pour les probabilit\'es num\'eriques}, journal = {ESAIM: Probability and Statistics}, pages = {141--170}, publisher = {EDP-Sciences}, volume = {5}, year = {2001}, mrnumber = {1875668}, zbl = {0998.60073}, language = {fr}, url = {http://www.numdam.org/item/PS_2001__5__141_0/} }
Pagès, Gilles. Sur quelques algorithmes récursifs pour les probabilités numériques. ESAIM: Probability and Statistics, Tome 5 (2001), pp. 141-170. http://www.numdam.org/item/PS_2001__5__141_0/
[1] 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
, et ,[2] Bounds for the fundamental solution of a parabolic equation. Bull. Amer. Math. Soc. 73 (1967) 890-903. | MR | Zbl
,[3] Méthodes de stabilité pour les chaînes de Markov non fellériennes, Thèse de l'Université Paris I (1999).
,[4] Stability in distributions for a class of singular diffusions. Ann. Probab. 20 (1992) 312-321. | MR | Zbl
et ,[5] Weak convergence of recursions. Stochastic Process. Appl. 68 (1997) 65-82. | MR | Zbl
, et ,[6] Recursive Algorithms, Urn process and Chaining Number of Chain Recurrent sets. Ergodic Theory Dynam. Systems 18 (1997) 53-87. | MR | Zbl
,[7] 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] Décroissance exponentielle du noyau de la chaleur sur la diagonale (II). Probab. Theory Related Fields 90 (1991) 377-402. | MR | Zbl
et ,[9] Algorithmes adaptatifs et approximations stochastiques. Masson, Paris (1987) 367p. | Zbl
, et ,[10] Ergodicity and Stability of Stochastic Processes. Wiley Chichester (England), Wiley Ser. Probab. Stat. (1998) 585p. | MR | Zbl
,[11] Approximation gaussienne d'algorithmes à dynamique markovienne. Ann. Inst. H. Poincaré B 24 (1988) 131-155. | Numdam | Zbl
,[12] Les algorithmes stochastiques contournent-ils les pièges ? Ann. Inst. H. Poincaré 32 (1996) 395-477. | Numdam | MR | Zbl
et ,[13] An almost everywhere central limit theorem. Math. Proc. Cambridge Philos. Soc. 104 (1988) 561-574. | MR | Zbl
,[14] A universal result in almost sure central limit theory. Stochastic Process. Appl. 94 (2001) 105-134. | MR | Zbl
, ,[15] Versions fortes associées aux théorèmes limites en loi pour les martingales vectorielles. Pré-pub. de l'Université de Bizerte, Tunisie (1996).
, et ,[16] Almost sure convergence in extreme value theory. Math. Nachr. 190 (1998) 43-50. | MR | Zbl
et ,[17] Random Iterative systems. Springer, Berlin (1998).
,[18] Linear Operators. Wiley-Interscience, New-York (1958). | Zbl
et ,[19] Markov Processes, characterization and convergence. Wiley, New-York, Wiley Ser. Probab. Math. Statist. (1986) 534p. | MR | Zbl
et ,[20] Asymptotic behaviour of a Markov constant step stochastic algorithm. SIAM J. Control Optim. 37 (1999) 1456-1482. | MR | Zbl
et ,[21] Stochastic algorithms with non constant step : behaviour of weighted empirical measures. Pré-pub. Université Paris 12 Val-de-Marne (1998, soumis).
et ,[22] Convex invariant means and a pathwise central limit theorem. Adv. Math. 63 (1987) 213-246. | MR | Zbl
,[23] Convergence rate of some semi-groups to their invariant probability. Stochastic Process. Appl. 79 (1999) 243-264. | MR | Zbl
, et ,[24] Martingale Limit Theory and its Application. Academic Press, New-York (1980) 308p. | MR | Zbl
et ,[25] Stochastic stability of differential equations. Sijthoff & Noordhoff, Alphen aan den Rijn (The Nederlands) (1980) 344p.
,[26] Brownian Motion and Stochastic Calculus. Springer-Verlag, New-York (1988) (2nd Ed., 1992) 470p. | MR | Zbl
et ,[27] A second course in stochastic processes. Academic Press, New-York (1981) 542p. | MR | Zbl
et ,[28] Random perturbations of Dynamical Systems. Birkhaäuser, Progr. Probab. Statist. (1988) 294p. | MR | Zbl
,[29] Ergodic Theorems. de Gruyter Stud. Math. (1989) 357p. | MR | Zbl
,[30] Stochastic Approximation for Constrained and Unconstrained Systems. Springer, Appl. Math. Sci. 26 (1978) 261p. | MR | Zbl
et ,[31] Approximation and weak convergence methods for random processes and applications to stochastic system theory. MIT Cambridge (1985). | MR | Zbl
,[32] Rates of convergence for stochastic approximation type algorithms. SIAM J. Control Optim. 17 (1979) 607-617. | MR | Zbl
et ,[33] Recursive computation of the invariant measure of a diffusion. Bernoulli (à paraître).
et ,[34] A note on the almost sure central limit theorem. Statist. Probab. Lett. 9 (1990) 201-205. | MR | Zbl
et ,[35] Markov chains and Stochastic Stability. Springer (1993) 550p. | MR | Zbl
et ,[36] Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann. Appl. Probab. 8 (1998) 10-44. | MR | Zbl
,[37] An almost sure central limit theorem for stochastic algorithms. J. Multivariate Anal. 71 (1999) 76-93. | MR | Zbl
,[38] 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] New Stochastic Approximation type procedures. Avtomat. i Telemakh. 7 (1990), in Russian, Automat. Remote Control 51 (1990) 107-118. | MR
,[40] Continuous martingales and Brownian Motion, 2nd Ed. Springer, Berlin (1991) 557p. | MR | Zbl
et ,[41] 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] On strong versions of the central limit theorem. Math. Nachr. 137 (1988) 249-256. | MR | Zbl
,[43] Probability Theory : An analytic view. Cambridge University Press (revised edition, 1994) 512p. | MR | Zbl
,[44] Second order discretization of stochastic differential systems for the computation of the invariant law. Stochastics Stochastics Rep. 29 (1990) 13-36. | Zbl
,[45] Expansion of the global error for numerical schemes solving stochastic differential equations. Stochastic Anal. Appl. 8 (1990) 94-120. | MR | Zbl
et ,[46] Sur les versions fortes du théorème de la limite centrale. Pré-pub. de l'Université de Marne-la-Vallée (1995).
,