Randomness test

[chandra chowdhury]

Hi,
  I have sequence like

{57,  44,  40,  57,  50,  53,  17,  24,  20,  3,  8,  51,  62,  56,  2, ..}, where
each value is between 0 to 63.  I want to check its randomness. Is there

any function in Sage for this? 

[Jori Mäntysalo]

How do you define "random"? Sometimes a perfect random number generator
will generate the sequence 1,2,3,.... Only definition of "random" I can
invent is "Can not be compressed." So can we do that?

I think that no. That would need some kind of heuristic, as the numbers
might have infinite number of generating functions. For example this is
not random at all: 92, 65, 35, 89, 79, 32, 38, 46: I got it from
str(pi.n(digits=30))[10:].

Suppose that your list has 1000 integers. Now we make a program "print 57,
44, 40". That program is, say, 1010 characters long. Is there any program
of at most 1009 characters that prints those numbers? Theoretically we can
just generate all strings up to 1009 characters, run them, and see what
happens. But if some program of 453 characters has been run for a day, has
produced first ten numbers of your list, and is still running, we do not
know if it will eventually produce other 990 numbers.

So, do you have some kind of guess about those numbers, something that
they might be produced from a

--
Jori Mäntysalo