Skip to Main content Skip to Navigation
Conference papers

Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension

Gleb Posobin 1 Alexander Shen 2
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Consider a bit string x of length n and Kolmogorov complexity αn (for some α < 1). It is always possible to increase the complexity of x by changing a small fraction of bits in x [2]. What happens with the complexity of x when we randomly change each bit independently with some probability τ ? We prove that a linear increase in complexity happens with high probability, but this increase is smaller than in the case of arbitrary change considered in [2]. The amount of the increase depends on x (strings of the same complexity could behave differently). We give exact lower and upper bounds for this increase (with o(n) precision). The same technique is used to prove the results about the (effective Hausdorff) dimension of infinite sequences. We show that random change increases the dimension with probability 1, and provide an optimal lower bound for the dimension of the changed sequence. We also improve a result from [5] and show that for every sequence ω of dimension α there exists a strongly α-random sequence ω such that the Besicovitch distance between ω and ω is 0. The proofs use the combinatorial and probabilistic reformulations of complexity statements and the technique that goes back to Ahlswede, Gács and Körner [1].
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download
Contributor : Alexander Shen <>
Submitted on : Friday, March 29, 2019 - 6:27:37 PM
Last modification on : Friday, November 8, 2019 - 3:48:02 PM
Long-term archiving on: : Sunday, June 30, 2019 - 4:22:24 PM


Files produced by the author(s)




Gleb Posobin, Alexander Shen. Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension. STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.57:1--57:14, ⟨10.4230/LIPIcs.STACS.2019.57⟩. ⟨lirmm-02084843⟩



Record views


Files downloads