×

Kolmogorov complexity and strong approximation of Brownian motion. (English) Zbl 1244.68043

The authors start from some results due to E. A. Asarin, A. V. Pokrovskii and W. Fouché on algorithmic randomness in the context of Brownian motion, i.e., Wiener measure on the space of continuous functions \(C[0,1]\). As they affirm the goal is to strengthen and explain a theorem of E. A. Asarin relating Brownian motion and random walks to Kolmogorov complexity. To this end they use strong approximation of Brownian motion. i.e., the joint realization of Brownian motion and random walks on the same probability space in such a way that the Brownian path and a scaled and interpolated random walk with \(n\) steps in the unit interval are almost surely within a \(d\)-distance \(O(n^{-1/2}\log n)\). The paper consists of 5 sections. In the last, entitled “Future works”, the authors emphasize three problems: “Further narrowing of the bounds”, “Rate distortion theory” and “Schnorr randomness”. It is a useful and instructive paper.

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
03D32 Algorithmic randomness and dimension
60F15 Strong limit theorems
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[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. 1 (1986), 25 – 33 (Russian, with English summary).
[3] Richard F. Bass and Krzysztof Burdzy, Stochastic bifurcation models, Ann. Probab. 27 (1999), no. 1, 50 – 108. · Zbl 0943.60087 · doi:10.1214/aop/1022677254
[4] Gregory J. Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22 (1975), 329 – 340. · Zbl 0309.68045 · doi:10.1145/321892.321894
[5] Xia Chen, Moderate and small deviations for the ranges of one-dimensional random walks, J. Theoret. Probab. 19 (2006), no. 3, 721 – 739. · Zbl 1123.60015 · doi:10.1007/s10959-006-0032-3
[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-London, 1981. · Zbl 0539.60029
[7] Richard Durrett, Probability: theory and examples, 2nd ed., Duxbury Press, Belmont, CA, 1996. · Zbl 0709.60002
[8] Willem Fouché, Arithmetical representations of Brownian motion. I, J. Symbolic Logic 65 (2000), no. 1, 421 – 442. · Zbl 0944.60087 · doi:10.2307/2586546
[9] Willem L. Fouché, The descriptive complexity of Brownian motion, Adv. Math. 155 (2000), no. 2, 317 – 343. · Zbl 0971.68077 · doi:10.1006/aima.2000.1945
[10] Péter Gács, Exact expressions for some randomness tests, Z. Math. Logik Grundlag. Math. 26 (1980), no. 5, 385 – 394. · Zbl 0464.60004 · doi:10.1002/malq.19800262502
[11] M. Csörgő and P. Révész, A new method to prove Strassen type laws of invariance principle. I, II, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 31 (1974/75), 255 – 259; ibid. 31 (1974/75), 261 – 269. , https://doi.org/10.1007/BF00532865 J. Komlós, P. Major, and G. Tusnády, An approximation of partial sums of independent \?\?’s and the sample \?\?. I, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 32 (1975), 111 – 131. · Zbl 0308.60029 · doi:10.1007/BF00533093
[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. · Zbl 0307.60045 · doi:10.1007/BF00532688
[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. · Zbl 1158.68017 · doi:10.1016/j.tcs.2008.09.045
[14] P. Lévy, Théorie de l’addition des variables aléatoires, 2nd ed., Gauthier-Villars, Paris, 1954. · Zbl 0056.35903
[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. · Zbl 1185.68369
[16] André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. · Zbl 1169.03034
[17] 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. · Zbl 0232.60001
[18] Norbert Wiener, Differential space, J. Math. Phys. 2 (1923), 131-174.
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.