Kolmogorov complexity and strong approximation of Brownian motion
HTML articles powered by AMS MathViewer
- by Bjørn Kjos-Hanssen and Tamás Szabados PDF
- Proc. Amer. Math. Soc. 139 (2011), 3307-3316 Request permission
Abstract:
Brownian motion and scaled and interpolated simple random walk can be jointly embedded in a probability space in such a way that almost surely the $n$-step walk is within a uniform distance $O(n^{-1/2}\log n)$ of the Brownian path for all but finitely many positive integers $n$. Almost surely this $n$-step walk will be incompressible in the sense of Kolmogorov complexity, and all Martin-Löf random paths of Brownian motion have such an incompressible close approximant. This strengthens a result of Asarin, who obtained instead the bound $O(n^{-1/6} \log n)$. The result cannot be improved to $o(n^{-1/2}{\sqrt {\log n}})$.References
- E. A. Asarin, Individual random signals: an approach based on complexity, doctoral dissertation, 1988.
- E. A. Asarin and A. V. Pokrovskiĭ, Application of Kolmogorov complexity to the analysis of the dynamics of controllable systems, Avtomat. i Telemekh. 1 (1986), 25–33 (Russian, with English summary). MR 831773
- Richard F. Bass and Krzysztof Burdzy, Stochastic bifurcation models, Ann. Probab. 27 (1999), no. 1, 50–108. MR 1681142, DOI 10.1214/aop/1022677254
- Gregory J. Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22 (1975), 329–340. MR 411829, DOI 10.1145/321892.321894
- Xia Chen, Moderate and small deviations for the ranges of one-dimensional random walks, J. Theoret. Probab. 19 (2006), no. 3, 721–739. MR 2280517, DOI 10.1007/s10959-006-0032-3
- M. Csörgő and P. Révész, Strong approximations in probability and statistics, Probability and Mathematical Statistics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1981. MR 666546
- Richard Durrett, Probability: theory and examples, 2nd ed., Duxbury Press, Belmont, CA, 1996. MR 1609153
- Willem Fouché, Arithmetical representations of Brownian motion. I, J. Symbolic Logic 65 (2000), no. 1, 421–442. MR 1782129, DOI 10.2307/2586546
- Willem L. Fouché, The descriptive complexity of Brownian motion, Adv. Math. 155 (2000), no. 2, 317–343. MR 1794714, DOI 10.1006/aima.2000.1945
- Péter Gács, Exact expressions for some randomness tests, Z. Math. Logik Grundlagen Math. 26 (1980), no. 5, 385–394. MR 589329, DOI 10.1002/malq.19800262502
- J. Komlós, P. Major, and G. Tusnády, An approximation of partial sums of independent $\textrm {RV}$’s and the sample $\textrm {DF}$. I, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 32 (1975), 111–131. MR 375412, DOI 10.1007/BF00533093
- J. Komlós, P. Major, and G. Tusnády, An approximation of partial sums of independent RV’s, and the sample DF. II, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 34 (1976), no. 1, 33–58. MR 402883, DOI 10.1007/BF00532688
- Bjørn Kjos-Hanssen and Anil Nerode, Effective dimension of points visited by Brownian motion, Theoret. Comput. Sci. 410 (2009), no. 4-5, 347–354. MR 2493984, DOI 10.1016/j.tcs.2008.09.045
- P. Lévy, Théorie de l’addition des variables aléatoires, 2nd ed., Gauthier-Villars, Paris, 1954.
- Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, 3rd ed., Texts in Computer Science, Springer, New York, 2008. MR 2494387, DOI 10.1007/978-0-387-49820-1
- André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883, DOI 10.1093/acprof:oso/9780199230761.001.0001
- Claus-Peter Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, Berlin-New York, 1971. MR 0414225, DOI 10.1007/BFb0112458
- Norbert Wiener, Differential space, J. Math. Phys. 2 (1923), 131-174., DOI 10.1002/sapm192321131
Additional Information
- Bjørn Kjos-Hanssen
- Affiliation: Department of Mathematics, University of Hawai‘i at Mānoa, 2565 McCarthy Mall, Honolulu, Hawaii 96822
- Email: bjoern@math.hawaii.edu
- Tamás Szabados
- Affiliation: Department of Mathematics, Budapest University of Technology and Economics, Budapest, Hungary
- Email: szabados@math.bme.hu
- Received by editor(s): February 24, 2009
- Received by editor(s) in revised form: April 4, 2009, and August 16, 2010
- Published electronically: February 1, 2011
- Additional Notes: This material is based upon work supported by the National Science Foundation under Grants No. 0652669 and 0901020. Thanks are due to the anonymous referee for very helpful comments and to Jacob Woolcutt for assistance with the production of Figure 1.
- Communicated by: Julia Knight
- © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 139 (2011), 3307-3316
- MSC (2010): Primary 68Q30, 03D32; Secondary 60F15
- DOI: https://doi.org/10.1090/S0002-9939-2011-10741-X
- MathSciNet review: 2811285