Techniques for determining how "random" a sample is?

Question

What techniques exist to determine the "randomness" of a sample?

For instance, say I have data from a series of $1200$ six-sided dice rolls. If the results were

1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, ...

Or:

1, 1, 1, ..., 2, 2, 2, ..., 3, 3, 3, ...

The confidence of randomness would be quite low.

Is there a formula where I can input the sequence of outcomes and get back a number that corresponds to the likelihood of randomness?

Thanks

UPDATE: awkward's answer was the most helpful. Some Googling turned up these two helpful resources:

Statistical analysis of Random.org - an overview of the statistical analyses used to evaluate the random numbers generated by the website, www.random.org
Random Number Generation Software - a NIST-funded project that provides a discussion on tests that can be used against random number generators, as well as a free software package for running said tests.

Kolmogorov-Smirnov test comes to mind: http://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test — gt6989b, Jul 09 '13 at 15:52
Your second sequence may also appear in a "perfectly random" sample. In fact, both are as random as you want them to be. — Lord Soth, Jul 09 '13 at 15:59
Also, entropy might be of interest. http://en.m.wikipedia.org/wiki/Information_entropy — Daniel R, Jul 09 '13 at 16:00
First of all, you should check wikipedia Secondly, have your heard about Mauler's second theorem? I deals with exactly this kind of thing. Given a samble of data which is normally distributed about a central point, to computed deviance, all you need to know are the (P-1)th moments of each data point, computed against the standard distribution. This suffices to determine exactly how random data $\mathbb{is}$. — , Jul 09 '13 at 16:24
I would say the "randomness" is the standard deviation and/or the variance. — rurouniwallace, Jul 09 '13 at 16:51
@PyotorH. Your lnik does not work and google gives no result for "Mauler's second theorem". — Michael Greinecker, Jul 09 '13 at 17:20
That was discussed in the article by A. Kolmogorov and V. Uspenskii. — user64494, Jul 09 '13 at 17:24

score 2 · Accepted Answer · answered Jul 09 '13 at 23:28

Computer scientists have developed a large array of tests for testing pseudo-random number generators. These can be adapted to testing other sources o random numbers, such as rolling dice. One source of information is Section 3.3, "Statistical Tests", of The Art of Computer Programming, Volume 2 (Seminumerical Algorithms) by Donald Knuth. It's too large a subject to be summarized concisely, but the tests discussed by Knuth include--

(1) Equidistribution test (frequency test): numbers are uniformly distributed.

(2) Serial test: pairs of successive numbers should be uniformly distributed in an independent manner.

(3) Gap test: gaps between occurrences of a given number should follow an appropriate distribution.

(4) Poker test (Partition test): if you use the random numbers to generate poker hands, they should follow the known distribution of poker hands.

(5) Permutation test: the input sequence is divided into groups of fixed length $t$; each ordering of the elements should appear with probability $1/t!$.

(6) Run test: the lengths of increasing or decreasing sequences should follow an appropriate distribution.

And several others ...

Many of these tests involve Chi-square or Kolomogorov-Smirnov tests for their computations.

I am sure you can find many resources on-line as well; just search for "testing random number generators".

Thanks! Googling for "testing random number generators" turned up this free software from NIST, which I am looking into using to evaluate the "randomness" of my samples - http://csrc.nist.gov/groups/ST/toolkit/rng/index.html — Scott Mitchell, Jul 15 '13 at 22:25

score 1 · Answer 2 · answered Jul 09 '13 at 16:06

It depends on what you mean by "randomness". You can measure the standard deviation of values placed before it and determine how many standard deviations lies a value with respect to the normal. If a value lies too far outside the norm, you could label it an outlier. This would be best suited for finding values which "don't belong."

Alternatively, you could create a projectory of previous points and measure the distance of the current value with respect to this projectory. This would work better for increasing or decreasing values.

Otherwise, it really depends on what you mean by "randomness". A math professor at the beginning of the semester of one of my classes once asked all his students to do one of two things: A) Flip a coin 100 times and record the results or B) Make up random results 100 times. What was important is that we did exactly one or the other and didn't mix methodology.

The professor was able to guess with 100% precision the ones who flipped a coin and the ones who made up random results, and it was based purely on the principal that if flipping a coin 100 times were truly random, then it would be extremely improbable that heads or tails wouldn't come up 7 times in a row. Most human beings think 7 consecutive heads or tails is not random enough, and we therefore tend to "make it more random" even if we're doing the opposite.

My point behind this story is that randomness is not a metric which can easily be measured. It may be that 1,1,1,2,2,2,3,3,3 is entirely random and it has just as much possibility of occurring as any other series of dice roll for the same amount of rolls.

score 1 · Answer 3 · answered Jul 09 '13 at 16:41

It depends on your deduction of randomness. If by randomness you mean being noise-like you can compare it's statistics with statistics of a gaussian noise. If you have p.d.f. of a reference random variable and you want to see whether this sequence is realization of that random variable, you can compare statistics of this sequence with statistics of random variable you are considering. Most used statistics are histogram, higher order statistics such as kurtosis, skewness, ... .

1

Nice to see you on here. + – Mikasa Jul 09 '13 at 18:02

score 0 · Answer 4 · answered Jul 09 '13 at 16:40

0

I would argue that the two examples you have given would be just as random as any other set of data points. Perhaps you might try looking for a repeating sequence instead of a level of "randomness".

answered Jul 09 '13 at 16:40

ajdigregorio

126

score 0 · Answer 5 · answered Jul 09 '13 at 16:58

What I would do is to first take the samples one by one, and check to see whether it is uniform (You assign some value depending on how far the distribution is from uniform and the way you calculate this value depends on your application). I would then take the samples two by two and do the same thing above, and then three by three and so on. With proper weighting, your second sequence will e.g. be flagged as "not random" with this technique. This is also what Neil's professor (in one of the answer to this question) is doing to see whether the sequence of his/her student's are really random or human generated.

score 0 · Answer 6 · answered Jul 09 '13 at 17:04

There are two underlying issues here:

The prevalence of each number, i.e. we expect the number of fours to be one sixth of the total.
The order of the items should be "random".

To test the second issue, one way would be to address this a Markov chain, where if the series is truly random, the transfer probabilities should all be $1/6$. That is, count the number of cases where $1$ is followed by $1, 2, 3..$ and so on. You should get a histogram with 36 bins, which for large $n$ you expect all bins will have a value of $n/36$.

Techniques for determining how "random" a sample is?

6 Answers6