×

Statistical properties of dynamical systems – Simulation and abstract computation. (English) Zbl 1293.37001

Summary: We survey an area of recent development, relating dynamics to theoretical computer science. We discuss some aspects of the theoretical simulation and computation of the long term behavior of dynamical systems. We will focus on the statistical limiting behavior and invariant measures. We present a general method allowing the algorithmic approximation at any given accuracy of invariant measures. The method can be applied in many interesting cases, as we shall explain. On the other hand, we exhibit some examples where the algorithmic approximation of invariant measures is not possible. We also explain how it is possible to compute the speed of convergence of ergodic averages (when the system is known exactly) and how this entails the computation of arbitrarily good approximations of points of the space having typical statistical behaviour (a sort of constructive version of the pointwise ergodic theorem).

MSC:

37-02 Research exposition (monographs, survey articles) pertaining to dynamical systems and ergodic theory
37C50 Approximate trajectories (pseudotrajectories, shadowing, etc.) in smooth dynamics
37F50 Small divisors, rotation domains and linearization in holomorphic dynamics
37A50 Dynamical systems and their relations with probability theory and stochastic processes
03D45 Theory of numerations, effectively presented structures
03D78 Computation over the reals, computable analysis
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Ambrosio, L.; Gigli, N.; Savare, G.: Gradient flows: in metric spaces and in the space of probability measures. Lectures in mathematics ETH zü rich (2005) · Zbl 1090.35002
[2] Avigad, J.; Gerhardy, P.; Towsner, H.: Local stability of ergodic averages. Trans. am. Math. soc. 362, 261-288 (2010) · Zbl 1187.37010
[3] Bienvenu, L.; Merkle, W.: Effective randomness for computable probability measures. Electr. notes theor. Comput. sci. 167, 117-130 (2007) · Zbl 1262.03064
[4] Binder, I.; Braverman, M.; Yampolsky, M.: Filled Julia sets with empty interior are computable. J. focm 7, 405-416 (2007) · Zbl 1160.37013
[5] Binder, I.; Braverman, M.; Yampolsky, M.: On computational complexity of Siegel Julia sets. Commun. math. Phys. 264, 317-334 (2006) · Zbl 1233.68138
[6] I. Binder, M. Braverman, C. Rojas, M. Yampolsky, Computability of Brolin – Lyubich measure, Commum. Math. Phys. doi:10.1007/s00220-011-1363-1. · Zbl 1246.37070
[7] Blank, M. L.: Pathologies generated by round-off in dynamical systems. Physica D 78, 93-114 (1994) · Zbl 0816.58026
[8] Blank, M. L.: Small perturbations of chaotic dynamical systems. Russian math. Surveys 44, 1-33 (1989) · Zbl 0702.58063
[9] Brattka, V.; Hertling, P.; Weihrauch, K.: A tutorial on computable analysis. New computational paradigms: changing conceptions of what is computable, 425-491 (2008) · Zbl 1145.03037
[10] M. Braverman, Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly- Time Computable, Thesis, University of Toronto, 2004, and Proc. CCA 2004, in: ENTCS, vol. 120, pp. 17 – 30.
[11] Braverman, M.: Parabolic Julia sets are polynomial time computable. Nonlinearity 19, No. 6, 1383-1402 (2006) · Zbl 1190.37049
[12] Braverman, M.; Yampolsky, M.: Non-computable Julia sets. J. am. Math. soc. 19, 551-578 (2006) · Zbl 1099.37042
[13] Braverman, M.; Yampolsky, M.: Computability of Julia sets. Algorithms comput. Math. 23 (2008) · Zbl 1161.37035
[14] Braverman, M.; Yampolsky, M.: Computability of Julia sets. Moscow math. J. 8, 185-231 (2008) · Zbl 1161.37035
[15] Brolin, H.: Invariant sets under iteration of rational functions. Ark. mat. 6, 103-144 (1965) · Zbl 0127.03401
[16] Dellnitz, M.; Junge, O.: Set oriented numerical methods for dynamical systems. Handbook of dynamical systems. 2 (2002) · Zbl 1036.37030
[17] Dellnitz, M.; Junge, O.: On the approximation of complicated dynamical behavior. SIAM J. Numer. anal. 36, 491-515 (1999) · Zbl 0916.58021
[18] Ding, J.; Du, Q.; Li, T. Y.: High order approximation of the Frobenius – Perron operator. Appl. math. Comput. 53, 151-171 (1993) · Zbl 0769.65025
[19] Ding, J.; Zhou, A.: The projection method for computing multidimensional absolutely continuous invariant measures. J. statist. Phys. 77, 899-908 (1994) · Zbl 0972.28501
[20] Froyland, G.: On Ulam approximation of the isolated spectrum and eigenfunctions of hyperbolic maps. Dcds 17, No. 3, 203-221 (2007) · Zbl 1144.37037
[21] Froyland, G.: Extracting dynamical behaviour via Markov models. Nonlinear dynamics and statistics: Proceedings, 283-324 (1998)
[22] Froyland, G.: Computer-assisted bounds for the rate of decay of correlations. Commun. math. Phys. 189, No. 1, 237-257 (1997) · Zbl 0892.58047
[23] P. Gács, M. Hoyrup, C. Rojas, Randomness on computable probability spaces – a dynamical point of view, in: Susanne Albers, Jean-Yves Marion (Eds.), 26th International Symposium on Theoretical Aspects of Computer Science, (STACS 2009), pp. 469 – 480. · Zbl 1236.68110
[24] Galatolo, S.; Hoyrup, M.; Rojas, C.: A constructive Borel – cantelli lemma. Constructing orbits with required statistical properties. Theor. comput. Sci. 410, 2207-2222 (2009) · Zbl 1171.60002
[25] Galatolo, S.; Hoyrup, M.; Rojas, C.: Effective symbolic dynamics, random points, statistical behavior, complexity and entropy. Inf. comput. 208, 23-41 (2010) · Zbl 1185.68368
[26] Galatolo, Stefano; Hoyrup, Mathieu; Rojas, Cristóbal: Dynamics and abstract computability: computing invariant measures. Disc. cont. Dyn. sys. 29, No. 1, 193-212 (2011) · Zbl 1217.37076
[27] S. Galatolo, M. Hoyrup, C. Rojas, Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems, in: Proceedings of the 7th International Conference on Computability and Complexity in Analysis, 2010. <http://www.arxiv.org/abs/1006.0392v1>. · Zbl 1185.68368
[28] S. Galatolo, I. Nisoli, A simple approach to rigorous approximation of invariant measures Preprint: arXiv:1109.2342.
[29] Grüne, L.: Asymptotic behavior of dynamical and control systems under perturbation and discretization. Lect. not. Math. 1783 (2002) · Zbl 0991.37001
[30] M. Hoyrup, C. Rojas, An application of M artin – Löf randomness to effective probability theory, in: LNCS. Proceedings of CiE’09. · Zbl 1268.03055
[31] Hoyrup, M.; Rojas, C.: Computability of probability measures and martin – löf randomness over metric spaces. Inf. comput. 207, 830-847 (2009) · Zbl 1167.68023
[32] Isola, S.: On systems with finite ergodic degree. Far east J. Dynam. syst. 5, 1-62 (2003) · Zbl 1063.37006
[33] Hasselblatt, Boris; Katok, Anatole: Introduction to the modern theory of dynamical systems. Encyclopedia of mathematics and its applications 54 (1995) · Zbl 0878.58020
[34] Iii, O. E. Lanford: Informal remarks on the orbit structure of discrete approximations to chaotic maps. Exp. math. 7, 317-324 (1998) · Zbl 0922.58042
[35] Lasota, A.; Yorke, J.: On the existence of invariant measures for piecewise monotonic transformations. Trans. am. Math. soc. 186, 481-488 (1973) · Zbl 0298.28015
[36] Lax, P. D.: Mathematics and computing. J. statist. Phys. 43, No. 5 – 6, 749-756 (1986) · Zbl 0628.00019
[37] Liverani, C.: Rigorous numerical investigations of the statistical properties of piecewise expanding maps – a feasibility study. Nonlinearity 14, 463-490 (2001) · Zbl 0991.37002
[38] Luzzatto, S.: Stochastic-like behaviour in non-uniformly expanding maps. Handbook of dynamical systems 1B, 265-326 (2006) · Zbl 1130.37353
[39] Lyubich, M.: The measure of maximal entropy of a rational endomorphism of a Riemann sphere. Funktsional. anal. I prilozhen. 16, 78-79 (1982)
[40] Pollicott, M.; Jenkinson, O.: Computing invariant densities and metric entropy. Commun. math. Phys. 211, 687-703 (2000) · Zbl 0962.37002
[41] Miernowski, T.: Discrétisations des homé omorphismes du cercle. Ergodic theory dynam. Syst. 26, 1867-1903 (2006) · Zbl 1125.37030
[42] J. Milnor, Dynamics in one complex variable. Introductory lectures, Friedr. Vieweg & Sohn, Braun- schweig, 1999.
[43] R. Rettinger, A fast algorithm for Julia sets of hyperbolic rational functions, in: Proceedings of CCA 2004, in ENTCS, vol. 120, pp. 145 – 157.
[44] Turing, A.: On computable numbers, with an application to the entscheidungsproblem. Proc. lond. Math. soc. 2, No. 42, 230-265 (1936) · Zbl 0016.09701
[45] M. Viana, Stochastic Dynamics of Deterministic Systems, Brazillian Math, IMPA, Colloquium 1997.
[46] Weber, J.; Haake, F.; Braun, P. A.; Manderfeld, C.; Seba, P.: Resonances of the Frobenius – Perron operator for a Hamiltonian map with a mixed phase space. J. phys. A 34, No. 36, 7195-7721 (2001) · Zbl 0988.37008
[47] Weihrauch, K.: Computable analysis. An introduction. (2000) · Zbl 0956.68056
[48] Young, Lai-Sang: What are SRB measures, and which dynamical systems have them?. J. statist. Phys. 108, 733-754 (2002) · Zbl 1124.37307
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.