Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Kolmogorov complexity and strong approximation of Brownian motion

Authors: Bjørn Kjos-Hanssen and Tamás Szabados
Journal: Proc. Amer. Math. Soc. 139 (2011), 3307-3316
MSC (2010): Primary 68Q30, 03D32; Secondary 60F15
Published electronically: February 1, 2011
MathSciNet review: 2811285
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] E. A. Asarin, Individual random signals: an approach based on complexity, doctoral dissertation, 1988.
  • [2] E. A. Asarin and A. V. Pokrovskiĭ, Application of Kolmogorov complexity to the analysis of the dynamics of controllable systems, Avtomat. i Telemekh. (1986), no. 1, 25-33 (Russian, with English summary). Automat. Remote Control 47 (1986), no. 1, part 1, 21-28. MR 831773 (87e:93096)
  • [3] Richard F. Bass and Krzysztof Burdzy, Stochastic bifurcation models, Ann. Probab. 27 (1999), no. 1, 50-108. MR 1681142 (2000b:60201)
  • [4] Gregory J. Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22 (1975), 329-340. MR 0411829 (53:15557)
  • [5] 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 (2007k:60075)
  • [6] 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, 1981. MR 666546 (84d:60050)
  • [7] Richard Durrett, Probability: Theory and examples, 2nd ed., Duxbury Press, Belmont, CA, 1996. MR 1609153 (98m:60001)
  • [8] Willem Fouché, Arithmetical representations of Brownian motion. I, J. Symbolic Logic 65 (2000), no. 1, 421-442. MR 1782129 (2002b:68038)
  • [9] Willem L. Fouché, The descriptive complexity of Brownian motion, Adv. Math. 155 (2000), no. 2, 317-343. MR 1794714 (2002e:68044)
  • [10] Péter Gács, Exact expressions for some randomness tests, Z. Math. Logik Grundlag. Math. 26 (1980), no. 5, 385-394. MR 589329 (82c:65004)
  • [11] J. Komlós, P. Major, and G. Tusnády, An approximation of partial sums of independent RV's and the sample DF. I, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 32 (1975), 111-131. MR 0375412 (51:11605b)
  • [12] 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 0402883 (53:6697)
  • [13] 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 (2009k:68100)
  • [14] P. Lévy, Théorie de l'addition des variables aléatoires, 2nd ed., Gauthier-Villars, Paris, 1954.
  • [15] 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 (2010c:68058)
  • [16] André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883
  • [17] Claus-Peter Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, Berlin, 1971. MR 0414225 (54:2328)
  • [18] Norbert Wiener, Differential space, J. Math. Phys. 2 (1923), 131-174.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 68Q30, 03D32, 60F15

Retrieve articles in all journals with MSC (2010): 68Q30, 03D32, 60F15

Additional Information

Bjørn Kjos-Hanssen
Affiliation: Department of Mathematics, University of Hawai‘i at Mānoa, 2565 McCarthy Mall, Honolulu, Hawaii 96822

Tamás Szabados
Affiliation: Department of Mathematics, Budapest University of Technology and Economics, Budapest, Hungary

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
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society