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