Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-09T01:20:14.506Z Has data issue: false hasContentIssue false
  • English
  • Français

Sur quelques algorithmes récursifspour les probabilitésnumériques

Published online by Cambridge University Press:  15 August 2002

Gilles Pagès
Gilles Pagès*
Affiliation:
Laboratoire de Probabilités et Modèles Aléatoires, UMR 7599, Université Pierre et Marie Curie, Université Paris 6, Case 188, 4 place Jussieu, 75252 Paris Cedex 05, France ; [email protected].
Get access

Abstract

The aim of this paper is to take an in-depth look at the longtime behaviour of some continuous time Markovian dynamical systems and at itsnumerical analysis. We first propose a short overview of the main ergodicity propertiesof time continuous homogeneous Markov processes (stability, positive recurrence). The basictool is a Lyapunov function. Then, we investigate if these properties still hold forthe time discretization of these processes, either with constant or decreasing step (ODE method in stochasticapproximation, Euler scheme for diffusions). We point out severaladvantages of the weighted empirical random measures associated to these procedures, especially withdecreasing step, in terms of convergence and of rate of convergence. Several simulations illustrate theseresults.

Keywords

ErgodicitystabilityMarkov processdiffusionstochastic algorithmODE methodEulerschemeempirical measure.
Type
Research Article
Information
ESAIM: Probability and Statistics , Volume 5 , 2001 , pp. 141 - 170
Copyright
© EDP Sciences, SMAI, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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.
Aronson, D.G., Bounds for the fundamental solution of a parabolic equation. Bull. Amer. Math. Soc. 73 (1967) 890-903. CrossRef
J.G. Attali, Méthodes de stabilité pour les chaînes de Markov non fellériennes, Thèse de l'Université Paris I (1999).
Basak, G. et Bhattacharya, R., Stability in distributions for a class of singular diffusions. Ann. Probab. 20 (1992) 312-321. CrossRef
Basak, G.K., Hu, I. et Wei, C.-Z., Weak convergence of recursions. Stochastic Process. Appl. 68 (1997) 65-82. CrossRef
Benaïm, M., Recursive Algorithms, Urn process and Chaining Number of Chain Recurrent sets. Ergodic Theory Dynam. Systems 18 (1997) 53-87. CrossRef
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.
Ben Arous, G. et Léandre, R., Décroissance exponentielle du noyau de la chaleur sur la diagonale (II). Probab. Theory Related Fields 90 (1991) 377-402. CrossRef
A. Benveniste, M. Métivier et P. Priouret, Algorithmes adaptatifs et approximations stochastiques. Masson, Paris (1987) 367p.
S. Borovkov, Ergodicity and Stability of Stochastic Processes. Wiley Chichester (England), Wiley Ser. Probab. Stat. (1998) 585p.
Bouton, C., Approximation gaussienne d'algorithmes à dynamique markovienne. Ann. Inst. H. Poincaré B 24 (1988) 131-155.
O. Brandière et M. Duflo, Les algorithmes stochastiques contournent-ils les pièges ? Ann. Inst. H. Poincaré 32 (1996) 395-477.
Brosamler, G.A., An almost everywhere central limit theorem. Math. Proc. Cambridge Philos. Soc. 104 (1988) 561-574. CrossRef
Berkes, I., Csáki, E., A universal result in almost sure central limit theory. Stochastic Process. Appl. 94 (2001) 105-134. CrossRef
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).
Cheng, S. et Peng, L., Almost sure convergence in extreme value theory. Math. Nachr. 190 (1998) 43-50. CrossRef
M. Duflo, Random Iterative systems. Springer, Berlin (1998).
N. Dunford et J.T. Schwartz, Linear Operators. Wiley-Interscience, New-York (1958).
S. Ethier et T. Kurtz, Markov Processes, characterization and convergence. Wiley, New-York, Wiley Ser. Probab. Math. Statist. (1986) 534p.
Fort, J.C. et Pagès, G., Asymptotic behaviour of a Markov constant step stochastic algorithm. SIAM J. Control Optim. 37 (1999) 1456-1482. CrossRef
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).
Fisher, A., Convex invariant means and a pathwise central limit theorem. Adv. Math. 63 (1987) 213-246. CrossRef
Ganidis, H., Roynette, B. et Simonot, F., Convergence rate of some semi-groups to their invariant probability. Stochastic Process. Appl. 79 (1999) 243-264. CrossRef
P. Hall et C.C. Heyde, Martingale Limit Theory and its Application. Academic Press, New-York (1980) 308p.
R.Z. Has'minskii, Stochastic stability of differential equations. Sijthoff & Noordhoff, Alphen aan den Rijn (The Nederlands) (1980) 344p.
I. Karatzas et S. Shreve, Brownian Motion and Stochastic Calculus. Springer-Verlag, New-York (1988) (2nd Ed., 1992) 470p.
S. Karlin et H. Taylor, A second course in stochastic processes. Academic Press, New-York (1981) 542p.
Y. Kifer, Random perturbations of Dynamical Systems. Birkhaäuser, Progr. Probab. Statist. (1988) 294p.
U. Krengel, Ergodic Theorems. de Gruyter Stud. Math. (1989) 357p.
H.J. Kushner et D.S. Clark, Stochastic Approximation for Constrained and Unconstrained Systems. Springer, Appl. Math. Sci. 26 (1978) 261p.
H.J. Kushner, Approximation and weak convergence methods for random processes and applications to stochastic system theory. MIT Cambridge (1985).
Kushner, H.J. et Huang, H., Rates of convergence for stochastic approximation type algorithms. SIAM J. Control Optim. 17 (1979) 607-617. CrossRef
D. Lamberton et G. Pagès, Recursive computation of the invariant measure of a diffusion. Bernoulli (à paraître).
Lacey, M.T. et Philip, W., A note on the almost sure central limit theorem. Statist. Probab. Lett. 9 (1990) 201-205. CrossRef
S. Meyn et R. Tweedie, Markov chains and Stochastic Stability. Springer (1993) 550p.
Pelletier, M., Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann. Appl. Probab. 8 (1998) 10-44.
Pelletier, M., An almost sure central limit theorem for stochastic algorithms. J. Multivariate Anal. 71 (1999) 76-93. CrossRef
Pelletier, M., 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).
B.T. Polyak, New Stochastic Approximation type procedures. Avtomat. i Telemakh. 7 (1990), in Russian, Automat. Remote Control 51 (1990) 107-118.
D. Revuz et M. Yor, Continuous martingales and Brownian Motion, 2nd Ed. Springer, Berlin (1991) 557p.
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).
Schatte, P., On strong versions of the central limit theorem. Math. Nachr. 137 (1988) 249-256. CrossRef
D.W. Stroock, Probability Theory: An analytic view. Cambridge University Press (revised edition, 1994) 512p.
Talay, D., Second order discretization of stochastic differential systems for the computation of the invariant law. Stochastics Stochastics Rep. 29 (1990) 13-36. CrossRef
Talay, D. et Tubaro, L., Expansion of the global error for numerical schemes solving stochastic differential equations. Stochastic Anal. Appl. 8 (1990) 94-120. CrossRef
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).