[comp.compression] Hard to compress string

jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) (04/05/91)

In article <VICTOR.91Apr4102353@irt.watson.ibm.com>
victor@watson.ibm.com writes:

>people thinking is from a paper of Ziv and Lempel:  Construct a
>sequence of bits as follows: first write down in order all 1 digit
>binary numbers (with leading zeroes if they are there), then all two
>digit, etc.  The surprising fact that they prove is that this sequence
>is incompressible by ANY finite-state compressor ...

On a similar line, the sequence of decimal digits below will pass most
tests for randomness.  I first encountered this sequence as an example
of a patently non-random digit stream that passes essentially every test
for randomness you can devise (short of knowing the algorithm).  Indeed,
as Ziv and Lempel point out, it would be quite hard to compress, although
a locally adaptive compressor might be able to adapt to the locally
periodic behavior this string exhibits.

  01234567891011121314151617181920212223242526272829303132333435363738394...

If you didn't catch on, the string consists of the decimal integers, with
no leading zeros except for zero itself, concatenated into an infinite
string.
					Doug Jones
					jones@cs.uiowa.edu

kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (04/06/91)

In article <5299@ns-mx.uiowa.edu> jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) writes:
>  01234567891011121314151617181920212223242526272829303132333435363738394...
>
>If you didn't catch on, the string consists of the decimal integers, with
>no leading zeros except for zero itself, concatenated into an infinite
>string.

Chardenowne's number (sp?).

-kym

em@dce.ie (Eamonn McManus) (04/08/91)

jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) writes:
>On a similar line, the sequence of decimal digits below will pass most
>tests for randomness.  I first encountered this sequence as an example
>of a patently non-random digit stream that passes essentially every test
>for randomness you can devise (short of knowing the algorithm).
...
>  01234567891011121314151617181920212223242526272829303132333435363738394...

At every position after the first, the digit 1 has occurred at least as
often as any other digit.  I would expect some tests to be able to detect
this nonrandomness.

,
Eamonn