Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-08T13:20:14.838Z Has data issue: false hasContentIssue false
  • English
  • Français

Dynamics of Morse-Smale urn processes

Published online by Cambridge University Press:  14 October 2010

Michel Benaïm  and
Morris W. Hirsch
Michel Benaïm
Affiliation:
Department of Mathematics, University of California, Berkeley, CA 94720 USA
Morris W. Hirsch
Affiliation:
Department of Mathematics, University of California, Berkeley, CA 94720 USA
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider stochastic processes {xn}n≥0 of the form

where F: ℝm → ℝm is C2, {λi}i≥1 is a sequence of positive numbers decreasing to 0 and {Ui}i≥1 is a sequence of uniformly bounded ℝm-valued random variables forming suitable martingale differences. We show that when the vector field F is Morse-Smale, almost surely every sample path approaches an asymptotically stable periodic orbit of the deterministic dynamical system dy/dt = F(y). In the case of certain generalized urn processes we show that for each such orbit Γ, the probability of sample paths approaching Γ is positive. This gives the generic behavior of three-color urn models.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 15 , Issue 6 , December 1995 , pp. 1005 - 1030
Copyright
Copyright © Cambridge University Press 1995

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

REFERENCES

Arthur, B. W. (1988). Self-reinforcing mechanisms in economics. In The Economy as an Evolving Complex System, SFI Studies in the Sciences of Complexity, Anderson, P. W, Arrow, K. J and Pines, D. eds. Addison-Wesley, New York.Google Scholar
Arthur, B., Ermol'ev, Y. and Kaniovskii, Y. (1983). A generalized urn problem and its applications. Cybernetics 19 61–71.CrossRefGoogle Scholar
Benaïm, M. (1993). A dynamical system approach to stochastic approximations. Preprint. University of California at Berkeley. SIAM J. Control and optimization (1996), in press.Google Scholar
Beneveniste, A., Métivier, M. and Priouret, P. (1990). Stochastic Approximations and Adaptive Algorithms. Springer; Berlin, Heidelberg, New York. Translated from Algorithmes adaptatifs et approximations stochastiques. Masson; Paris (1987).CrossRefGoogle Scholar
Conley, C. C. (1978). Isolated Invariant Sets and the Morse Index, Providence: Published for the Conference Board of the Mathematical Sciences by the American Mathematical Society, Regional Conference series in Mathematics, No. 38.CrossRefGoogle Scholar
Hall, D. and Heyde, C. C. (1980). Martingale Limit Theory and Applications. Academic Press, New York.Google Scholar
Hill, B. M., Lane, D. and Sudderth, W. (1980). A strong law for some generalized urn processes. Ann. Probab. 8 214–226.CrossRefGoogle Scholar
Hartman, P. (1964). Ordinary Differential Equations. John Wiley & Sons, New York.Google Scholar
Hirsch, M. W. (1976). Differential Topology. Springer-Verlag, New York, Heidelberg, Berlin.CrossRefGoogle Scholar
Hirsch, M. W. and Pugh, C. (1970). Stable manifolds for hyperbolic sets. In Proc. Symposia in Pure Mathematics 14, Global Analysis, American Mathematical Society, Providence, Rhode Island, pp. 133–163.Google Scholar
Hirsch, M. W., Pugh, C. and Shub, M. (1977). Invariant Manifolds. Springer Lecture Notes in Mathematics, 583. Springer-Verlag, New York, Heidelberg, Berlin.CrossRefGoogle Scholar
Kushner, H. J. and Clark, D. S. (1978). Stochastic Approximation Methods for Constrained and Unconstrained Systems.. Springer; Berlin, Heidelberg, New York.CrossRefGoogle Scholar
Métivier, M. and Priouret, P. (1987). Théorèmes de convergence presque sure pour une classe d'algorithmes stochastiques à pas décroissant. Probability Theory and Related Fields 74 403–428.CrossRefGoogle Scholar
Morse, M. (1960). The existence of polar nondenerate functions on differentiable manifolds. Ann. Math. 71 352–383.CrossRefGoogle Scholar
Palis, J. (1969). On Morse-Smale dynamical systems. Topology 8 385–405.CrossRefGoogle Scholar
Palis, J. and Smale, S. (1968). Structural stability theorems. in Proc. Sympo. Pure Math. 14. Global Analysis, Chern, S. -S. and Smale, S. eds. American Mathematical Society, Providence, RI.Google Scholar
Pemantle, R. (1990). Nonconvergence to unstable points in urn models and stochastic approximations. Ann. Probab. 18 698–712.CrossRefGoogle Scholar
Pemantle, R. (1992). Vertex-reinforced random walk. Probability Theory and Related Fields 92 117–136.CrossRefGoogle Scholar
Peixoto, M. M. (1962). Structural stability on two-dimensional manifolds. Topology 1 101–120.CrossRefGoogle Scholar
Pugh, C. and Shub, M. (1970). The omega stability theorem for flows. Invent. Math. 11 150–158.CrossRefGoogle Scholar
Smale, S. (1961a). Generalized Poincaré conjecture in dimensions greater than four. Ann. Math. 74 391–406.CrossRefGoogle Scholar
Smale, S. (1961b). On gradient dynamical systems. Ann. Math. 74 199–206.CrossRefGoogle Scholar
Wilson, W. (1969). Smoothing derivatives of functions and applications. Trans. Amer. Math. Soc. 139 413–428.CrossRefGoogle Scholar