Re: Attention Sean - question about CSI

On 2007-08-01, TomS <TomS_member@xxxxxxxxxxx> wrote:
"On Tue, 31 Jul 2007 19:12:04 -0600, in article
<O4Kdnbhd6Ix7QDLbnZ2dnUVZ_g6dnZ2d@xxxxxxxxxxx>, dkomo stated..."

Bobby Bryant wrote:
If I have a string of 1,000,000 random binary digits -- genuinely
random, not created by a deterministic RNG -- does it have more,
less, or the same CSI as a string of the same length where the
bits have deliberately been set, e.g. by copying a pattern?


Consider the 1,000,000 random binary digits as a file and run it through
the best compression algorithm you have. It should compress very
little. On the other hand, a file which has strong patterns will
compress a lot. Maybe the degree of compression can serve as a measure
of the "pattern-ness" of the file. What relation this would have to CSI
I'm not sure because I haven't been following the raging CSI debates.

If I am allowed to choose the compression algorithm *after*
seeing the million random digits, then I can choose one
which compresses that string to a single bit.

A side note: generally, in this kind of context you need to include
the compression algorithm in your size estimate, ie you need to give
the size of the decompression program plus the compressed data.

Good luck doing that with 1 bit... :-)

--
"Ja pilkut huusivat tuskissaan: 'Lisää vaseliinia, lisää vaseliinia!'"

.

Relevant Pages

  • Re: Attention Sean - question about CSI
    ... Consider the 1,000,000 random binary digits as a file and run it through the best compression algorithm you have. ... What relation this would have to CSI I'm not sure because I haven't been following the raging CSI debates. ... then I can choose one which compresses that string to a single bit. ... there is the whole field of statistical pattern recognition which has been specifically developed to recognize patterns in data. ...
    (talk.origins)
  • Re: Attention Sean - question about CSI
    ... Maybe the degree of compression can serve as a measure ... If I am allowed to choose the compression algorithm *after* ... which compresses that string to a single bit. ... Yet, for a truly random sequence of numbers, you won't find any ...
    (talk.origins)
  • Re: compression algorithm is NP complete problem?
    ... polynomial time) into this problem. ... > I heard someone say compression algorithm is NP complete problem. ... I still don't understand how compression algorithm is NP ... what is the shortest packed string that expands to the desired ...
    (comp.theory)
  • Re: Attention Sean - question about CSI
    ... e.g. by copying a pattern? ... Maybe the degree of compression can serve as a measure ... What relation this would have to CSI ... which compresses that string to a single bit. ...
    (talk.origins)
  • Re: Attention Sean - question about CSI
    ... Maybe the degree of compression can serve as a measure ... What relation this would have to CSI ... If I am allowed to choose the compression algorithm *after* ... which compresses that string to a single bit. ...
    (talk.origins)