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 (2005) showed 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 $τ$)? It turns out 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 an 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 (1976). 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.