Is it possible to prove, if a sequence is random?

Question

Consider following inputs:

1,1,2,3,5,8 - it isn't random

2,4,8,16,32 - this neither

4,1,2,11,5,9- this one looks like random-sequence

I would like to ask if is there such algorithm to prove if input is random or it isn't?

Answer 1

No, there is no such prove - if you have perfectly random numbers, the probability of each sequence of length n is equal. However, there are statistical tests to asses the quality of a random number generator, which is probably what you are looking for. See Diehard tests.

Answer 2

As others have mentioned, you cannot prove that a sequence was generated randomly or not. In addition to what @timos suggested, it looks like you might have some additional requirements. It seems as though you desire to ensure that the sequence does not come from some hypothetical list of well-known, "non-random" sequences. If that is the case, you may be interested in learning of the On-Line Encyclopedia of Integer Sequences.

If you have a particular sequence in mind, you can check it against their database. For instance, 1,1,2,3,5,8 comes up in a number of sequences, but most prominantly in A000045 (Fibonacci numbers). A sequence like 4,1,2,11,5,9 does not show up in a search there.

None of this proves anything, but perhaps this is more in-line with your goals in this instance.