Fiber entropy and algorithmic complexity of random orbits

Elias Zimmermann

doi:10.3934/dcds.2022098

Article Contents

2022, Volume 42, Issue 11: 5289-5308. Doi: 10.3934/dcds.2022098

This issue Previous Article Non-synchronized solutions to nonlinear elliptic Schrödinger systems on a closed Riemannian manifold Next Article Mingled hyperbolicities: Ergodic properties and bifurcation phenomena (an approach using concavity)

Fiber entropy and algorithmic complexity of random orbits

Elias Zimmermann^,

University of Leipzig, Mathematical Institute, Augustusplatz 10, 04109 Leipzig, Germany

^*Corresponding author: Elias Zimmermann
^*Corresponding author: Elias Zimmermann

Received: December 2021

Revised: May 2022

Early access: July 2022

Published: November 2022

The author is supported by GIF grant I-1485-304.6/2019.

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

Let $ \Theta $ be a finite alphabet. We consider a bundle of measure preserving transformations $ (T_{\theta})_{\theta \in \Theta} $ acting on a probability space $ (X,\mu) $, which are chosen randomly according to an ergodic stochastic process $ (\Xi,\nu,\sigma) $ with state space $ \Theta $. This describes a paradigmatic case of a random dynamical system (RDS). Considering a finite partition $ \mathcal{P} $ of $ X $ we show that the conditional algorithmic complexity of a random orbit $ x, T_{\alpha_{0}}(x),T_{\alpha_{1}}\circ T_{\alpha_{0}}(x),... $ in $ X $ along a sequence $ \alpha = \alpha_{0}\alpha_{1}\alpha_{2}... $ in $ \Xi $ equals almost surely the fiber entropy of the RDS with respect to $ \mathcal{P} $, whenever the latter is ergodic. This extends a classical result of A. A. Brudno connecting algorithmic complexity and entropy in deterministic dynamical systems.

Keywords:

Mathematics Subject Classification: Primary: 37H12, 28D20, 94A17, 68Q30.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	L. M. Abramov and V. A. Rokhlin, Entropy of a skew product of mappings with invariant measure, Vestnik Leningrad. Univ., 17 (1962), 5-13.
[2]	A. Alpeev, Kolmogorov complexity and entropy of amenable group actions, preprint, 2018, arXiv: 1809.01634.
[3]	L. Arnold, Random Dynamical Systems, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-662-12878-7.
[4]	F. Benatti, Entropy and algorithmic complexity in quantum information theory, Nat. Comput., 6 (2007), 133-150. doi: 10.1007/s11047-006-9017-5.
[5]	F. Benatti, T. Krüger, M. Müller, R. Siegmund-Schultze and A. Skzoła, Entropy and quantum Kolmogorov complexity: A quantum Brudno's theorem, Commun. Math. Phys., 265 (2006), 437-461. doi: 10.1007/s00220-006-0027-z.
[6]	T. Bogenschütz, Entropy for Random Dynamical Systems, Report, 235, University of Bremen, Bremen, 1990.
[7]	T. Bogenschütz, Entropy, pressure and a variational principle for random dynamical systems, Random Comput. Dynam., 1 (1992/93), 99-116.
[8]	L. Bowen, Examples in the entropy theory of countable group actions, Ergodic Theory Dyn. Syst., 40 (2020), 2593-2680. doi: 10.1017/etds.2019.18.
[9]	A. A. Brudno, Entropy and the complexity of trajectories of a dynamical system, Trudy Moskov. Mat. Obshch., 44 (1982), 124–49;
[10]	A. I. Bufetov, Operator ergodic theorems for actions of free semigroups and groups, Funct. Anal. Appl., 34 (2000), 239-251. doi: 10.1023/A:1004116205980.
[11]	A. I. Bufetov, Skew products and ergodic theorems for group actions, J. Math. Sci., 113 (2003), 548-557. doi: 10.1023/A:1021138024468.
[12]	T. Downarowicz, Entropy in Dynamical Systems, New Mathematical Monographs, 18. Cambridge University Press, Cambridge, 2011. doi: 10.1017/CBO9780511976155.
[13]	R. G. Downey and D. R. Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010. doi: 10.1007/978-0-387-68441-3.
[14]	T. Fuda and M. Tonozaki, Brudno's theorem for $\mathbb{Z}^{d}$ (or $\mathbb{Z}^{d}_{+}$) subshifts, Inf. Comput., 253 (2017), 155-162. doi: 10.1016/j.ic.2017.01.011.
[15]	S. Galatolo, M. Hoyrup and C. Rojas, Effective symbolic dynamics, random points, statistical behavior, complexity and entropy, Inf. Comput., 208 (2010), 23-41. doi: 10.1016/j.ic.2009.05.001.
[16]	R. I. Grigorchuk, Ergodic theorems for the actions of a free group and a free semigroup, Math. Notes, 65 (1999), 654-657. doi: 10.1007/BF02743176.
[17]	S. Kakutani, Random ergodic theorems and Markoff processes with a stable distribution, Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Berkeley-Los Angeles, Calif., (1950), 247–261.
[18]	D. Kerr and H. Li, Ergodic Theory. Independence and Dichotomies, Springer Monographs in Mathematics. Springer, Cham, 2016. doi: 10.1007/978-3-319-49847-8.
[19]	Y. Kifer and P.-D. Liu, Random dynamics, Handbook of Dynamical Systems, Elsevier B. V., Amsterdam, 1B (2006), 379-499. doi: 10.1016/S1874-575X(06)80030-5.
[20]	N. Moriakov, Computable Følner monotilings and a theorem of Brudno. I, preprint, 2015, arXiv: 1509.07858.
[21]	N. Moriakov, Computable Følner monotilings and a theorem of Brudno, Ergodic Theory Dyn. Syst., 41 (2021), 3389-3416. doi: 10.1017/etds.2020.110.
[22]	T. Morita, Entropy of random dynamical systems, Proc. Japan Acad. Ser. A Math. Sci., 62 (1986), 121-124.
[23]	A. Nevo and F. Pogorzelski, The SMB theorem along geodesics, manuscript in preparation.
[24]	V. I. Oseledets, Markov chains, skew products and ergodic theorems for "general" dynamic systems, Teor. Veroyatn. Primen, 10 (1965), 551-557.
[25]	W. Parry, Entropy and Generators in Ergodic Theory, W. A. Benjamin, Inc., New York-Amsterdam, 1969.
[26]	S. Roman, Coding and Information Theory, Graduate Texts in Mathematics, 134. Springer-Verlag, New York, 1992.
[27]	S. G. Simpson, Symbolic dynamics: entropy = dimension = complexity, Theory Comput. Syst., 56 (2015), 527-543. doi: 10.1007/s00224-014-9546-8.
[28]	F. Spitzer, Principles of Random Walk, Second edition, Graduate Texts in Mathematics, Vol. 34. Springer-Verlag, New York-Heidelberg, 1976.
[29]	S. M. Ulam and J. von Neumann, Random ergodic theorems, Bull. Amer. Math. Soc., 51 (1945), 660.
[30]	H. S. White, On the Algorithmic Complexity of Trajectories of Points in Dynamical Systems, Ph.D thesis, University of North Carolina at Chapel Hill, 1991, 65 pp.
[31]	H. S. White, Algorithmic complexity of points in dynamical systems, Ergodic Theory Dyn. Syst., 13 (1993), 807-830. doi: 10.1017/S0143385700007653.
[32]	R. Zweimüller, Asymptotic orbit complexity of infinite measure preserving transformations, Discrete Contin. Dyn. Syst., 15 (2006), 353-366. doi: 10.3934/dcds.2006.15.353.