# If I have a set of numbers, how can I prove that they are random?

If someone gives me a list of numbers and says they are entirely and completely random, how I can I verify this?

EDIT: Let's suppose that a well-known string theorist told me he can produce a list of numbers that is truly, genuinely random. If I can't prove that they're really random, then who am I supposed to believe: him, or the mathematicians?

(Don't hurt me; I'm just trying to learn.)

• You can’t. For any finite sequence of numbers $\langle x_1,\dots,x_n\rangle$ there is a polynomial $p$ of degree $n-1$ such that $p(k)=x_k$ for $k=1,\dots,n$. – Brian M. Scott Dec 8 '12 at 7:31
• – Rahul Dec 8 '12 at 7:33
• Wait, it's not quite a duplicate. I need to get some answers first and then I'll add an edit to my post. But I don't want to influence the answers I get with additional information. – Nick Dec 8 '12 at 7:34
• "I don't want to influence the answers I get with additional information." That sounds like a really bad idea. Why would anyone want to answer if (a) they don't know what you're looking for that's different from the already existing previous questions and answers, and (b) after they've put in all the effort to write a nice answer, you might change the question rendering their answer irrelevant? Tell us what your question really is, please. – Rahul Dec 8 '12 at 7:47
• See my edit above. – Nick Dec 8 '12 at 7:52

## 1 Answer

Every proof in the world, no matter how certain, will always be associated with a certain degree of uncertainty. For example, it can be proven that something is true with 50% or with 90% certainty, but never with 100% certainty.

In a completely random series, all combinations will occur equally often. This means that if you have a series of letters, AA will occur as often as AX or AP or any other two-letter combination.

If the series begins with AAAAAAAA, it might lead you to think it is not random. But then you should consider that the 8-letter combination AAAAAAAA has the same probability of occurence as e.g. PQXLSTUW or BVMDNPEH.

In the same manner, AAAAAAAAAAAAAAAA has the same chance of occurence, as any other 16-letter combination.

However, the probability of AAAAAAAAAAAAAAAA being a coincidence is much smaller than the probability of say AAAAAAAA being a coincidence.

Any pattern (that is, non-randomness) in a series can be defined as an uneven distribution of single values, or combinations of values (which in themselves constitute values).

The probability of a certain distribution being a coincidence as opposed to a true pattern, can be computed in the following way (I'll describe it in words rather than through mathematical language):

Let's say you have the series ABBBDCCACC of letters from A to D. The distribution of letters is as follows: A:2 B:3 C:4 D:1

Now you have to ask yourself... if you go through all possible 10-letter combinations beginning in the following way:

AAAAAAAAAA
AAAAAAAAAB
AAAAAAAAAC
AAAAAAAAAD
AAAAAAAABA
AAAAAAAABB
AAAAAAAABC
AAAAAAAABD
AAAAAAAACA
AAAAAAAACB.... And so on.

How many of these combinations would have the same distribution as the series above, that is, one letter occuring four times, one occuring three times, and two other letters occuring two and one time respectively? (Which letter has which frequency of occurence doesn't matter.) You take the the number of combinations having these properties, and divide by the total number of 10-letter combinations you arrive at the probability of a series having this distribution.

Now that you know the probability of this, you go through all possible distributions, and you add up the probability of all distributions having equal or less probability of occurence as the first distribution we discussed. The sum thus obtained measures the likeliness of the distribution occuring by chance.