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

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?)

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