entropy example 5

From Scholarpedia

< Entropy | connections between different meanings of entropy
Tomasz Downarowicz (2007), Scholarpedia, 2(11):3901. revision #25687 [link to/cite this article]

Curator: Tomasz Downarowicz, Institute of Mathematics Computer Science, Wroclaw University of Technology, Poland

Consider the infinite string obtained by concatenating consecutively all words of length 1, then of length 2, etc, each time ordered lexicographically:

B=0,1,\,00,01,10,11,\,000,001,010,011,100,101,110,111,\,0000,0001\dots

It is not hard to see that this string generates by frequencies the uniform measure, whose Kolmogorov-Sinai entropy equals 1. So, according to the assertion of the Compression Theorem, B should not allow for any compression. On the other hand, since B can be completely determined by a finite set of instructions (as is done above), its Kolmogorov complexity is zero. This phenomenon follows from the fact that the Compression Theorem takes into account only frequency-based data compression codes, while Kolmogorov complexity allows one to use any algorithmic regularity in the structure of the message. Nevertheless, the Compression Theorem says that the collection of messages with regularities undetected by frequency-based algorithms has measure zero.


Invited by: Dr. Eugene M. Izhikevich, Editor-in-Chief of Scholarpedia, the peer-reviewed open-access encyclopedia
Action editor: Dr. Eugene M. Izhikevich, Editor-in-Chief of Scholarpedia, the peer-reviewed open-access encyclopedia
Retrieved from "http://www.scholarpedia.org/article/Entropy/connections_between_different_meanings_of_entropy/entropy_example_5"
For authors