# Are Strings Kolmogorov-Random Actually Random?

• Tiiba
In summary, a Kolmogorov-random string is an incompressible string that is guaranteed to contain a copy of your post.
Tiiba
Are strings that are Kolmogorov-random actually random in the usual sense?

An incompressible string probably won't contain this post anywhere in it, but a random one can.

If you have a long string in which your post does not appear, you could compress it (very slightly) by using that fact. If your post has N characters, and the string (and post) are drawn from an alphabet of length A, it could be compressed by (100/A^N)%.* So if your post was "11" out of a binary alphabet, a string not containing it could be compressed by 25% by encoding in trinary: 0 = 00, 1 = 01, 2 = 10.

So I would actually expect your post to appear in a long-enough Kolmogorov-random string.

* Actually, depending on the post, probably a fair bit more, maybe as much as (100N/A^N)%.

Suppose your post was 171 characters long out of a 7-bit (128-character) alphabet. Then a Kolmogorov-random string of length 128171 = 2.15... x 10360 would be expected to have one copy of your post.

Tiiba said:
Are strings that are Kolmogorov-random actually random in the usual sense?
What is the "usual sense"? A Kolmogorov-random string certainly isn't a probability measure on a topological space -- and most peoples' intuitive notion of probability is notoriously ill-defined.

An incompressible string probably won't contain this post anywhere in it, but a random one can.
On the contrary, "almost all" strings contain a copy of your post -- therefore there exists a length L such that every incompressible string longer than L contains a copy of your post.

Last edited:
By "random in the usual sense" I mean that any substring - including a trillion repetitions of the letter "g" - can appear in the string.

As I understand, Kolmogorov randomness is produced by simply compressing a non-random string. But if I have a random string generator, I could create a program that works as follows:

1 Read a string from the generator
2 Compress the chunk
3 If the chunk gets bigger due to the compression algorithm, place it in the output as is and prepend it with a 0; If it proves compressible, place the compressed version in the output and prepend it with a 1
4 If the amount of space saved through compression exceeds the size of the decompressor, halt.

So a truly random string would be compressible. But a Kolmogorov-random string is incompressible by definition. So is my logic wrong, or did I misunderstand a definition somewhere?

Tiiba said:
1 Read a string from the generator
2 Compress the chunk
3 If the chunk gets bigger due to the compression algorithm, place it in the output as is and prepend it with a 0; If it proves compressible, place the compressed version in the output and prepend it with a 1
4 If the amount of space saved through compression exceeds the size of the decompressor, halt.

So a truly random string would be compressible.

I think you'll find that the average of min(size(chunk), size(compress(chunk))) + 1 bit is actually greater than size(chunk) for uniformly random bitstrings and any compression algorithm, even though min(size(chunk), size(compress(chunk))) will of course be no larger than size(chunk).

Okay... Then I do this:

1) Place the whole random string in a file F.
2) Define a header of length A that instructs the decompressor to decompress the following string and insert the result at its original position.
3) Cut out all detected compressible chunks from F and place them in another file (as long as the compression saves more space than the header uses).
4) If the amount of space saved through compression exceeds the size of the decompressor, halt.

This way, there is no overhead for the incompressible chunks.

## 1. What is Kolmogorov randomness?

Kolmogorov randomness, also known as algorithmic randomness, is a measure of the unpredictability of a sequence of symbols. It is based on the concept of Kolmogorov complexity, which measures the amount of information needed to describe a string in the most concise way possible.

## 2. How is Kolmogorov randomness different from other notions of randomness?

Kolmogorov randomness is a more strict definition of randomness compared to other concepts such as statistical randomness. It focuses on the shortest possible description of a string, rather than the frequency of certain symbols appearing in the string.

## 3. Can strings be proven to be truly Kolmogorov-random?

No, it is impossible to prove that a string is truly Kolmogorov-random. This is because the concept is based on a measure of unpredictability, which cannot be proven with certainty.

## 4. How is Kolmogorov randomness used in computer science?

Kolmogorov randomness is used in computer science as a way to measure the complexity of algorithms and data structures. It is also used in areas such as cryptography and data compression.

## 5. Are strings that are Kolmogorov-random actually random?

From a mathematical perspective, strings that are Kolmogorov-random are considered to be truly random. However, this concept of randomness may not align with our intuitive understanding of randomness in everyday life.

Replies
11
Views
1K
Replies
5
Views
1K
Replies
2
Views
2K
Replies
6
Views
2K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
8
Views
451
Replies
1
Views
4K
Replies
1
Views
1K
Replies
10
Views
973