[Solved]: How do incompressible strings and random strings share the same properties?

ignougroup
Problem Detail: I came across the following theorem in Sipser’s about incompressible strings.

Let $;f$ be some computable function which holds for almost all strings. The for any $b > 0 $, the property $;f$ is false only on finitely many strings that are incompressible by $b;$.

where “almost all strings” means that as $n$ grows the fraction of strings of length $n$ for which $f$ is false approaches $0$. The book proves the above theorem and says that if we select some sufficiently long string at random, it’s likely that property $f$ would hold true for it. Thus incompressible strings and random strings share this property. Though I understand the proof for the theorem, I am unable to understand its meaning. How does this show there is some sort of relation between incompressible strings and random strings? Also how does this theorem help us? Although I can generate random strings, there is no method to generate incompressible strings in general.

Asked By : sashas

Answered By : Yuval Filmus

The theorem says, in effect, that incompressible strings are a deterministic model of random strings. If you have some property that you can prove using random strings, you can also prove it using incompressible strings instead. If you have some construction involving a random string, you can make it somewhat more explicit using an incompressible string. Another deterministic model of randomness, which is very useful in theoretical computer science, is expanders. These are models of random graphs with respect to a lot of properties. In many cases, instead of using a random graph you can use an expander. Since we can construct expanders explicitly, this allows us to derandomize many randomized constructions. While the same cannot be said for incompressible strings, they are useful in some circumstances. Their use in lower bounds is known as the incompressibility method, which I encourage you to look up.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49998