Random Data Compressed 100:1 (Guffaw)

[Tim May]

On Wednesday, January 9, 2002, at 02:39 PM, Tim May wrote:
>
> You are missing the big picture. About 1 / 1^(N-1) bit strings of 
> length N will have descriptions shorter than the bit string.

A typo. "1 / 2^(N-1)" is what I meant to type. If N = 100, about 1/2^99 
of the bit strings have "short" (catchy, memorable, loosely speaking) 
descriptions. Most of the rest actually take more bits to describe if 
described in terms of "words" (small patterns, runs). This is what we 
mean when we say they are their own shortest descriptions.

This is similar, by the way, to poker or bridge hands. In a fair deal, 
all hands are equally likely. However, because of our naming conventions 
and interest in "all hearts" or "a sequential run of spades from 10 to 
Ace," we are fooled into thinking some of these hands are "rarer" than 
"random hands."

Again, this is just one facet of a very interesting topic.




--Tim May