Consider a binary string x of length n whose Kolmogorov complexity is αn for some α<1. We want to increase the complexity of x by changing a small fraction of bits in x. This is always possible: Buhrman, Fortnow, Newman and Vereshchagin showed [1] that the increase can be at least δn for large n (where δ is some positive number that depends on α and the allowed fraction of changed bits).
We consider a related question: what happens with the complexity of x when we randomly change a small fraction of the bits (changing 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. We note that the amount of the increase depends on x (strings of the same complexity could behave differently), and give exact lower and upper bounds for this increase (with o(n) precision).
The proof uses the combinatorial and probabilistic technique that goes back to Ahlswede, Gács and Körner [2]. For the reader's convenience (and also because we need a slightly stronger statement) we provide a simplified exposition of this technique, so the paper is self-contained.
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 [3] and show that for every sequence ω of dimension α there exists a strongly α-random sequence ω' such that the Besicovitch distance between ω and ω' is 0.
This is joint work with Alexander Shen.
[1] Rudolf Ahlswede, Peter Gács, and János Körner. Bounds on conditional probabilities with applications in multi-user communication. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 34(2):157–177, 1976.
[2] Harry Buhrman, Lance Fortnow, Ilan Newman, and Nikolai K. Vereshchagin. Increasing Kolmogorov complexity. In Volker Diekert and Bruno Durand, editors, STACS 2005, Stuttgart, Germany, February 24-26, volume 3404 of Lecture Notes in Computer Science, pages 412–421. Springer, 2005.
[3] Noam Greenberg, Joseph S. Miller, Alexander Shen, and Linda Brown Westrick. Dimension 1 sequences are close to randoms. Theoretical Computer Science, 705:99–112, 2018.