Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension

International audienceConsider 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]