Test the randomness of a black box that outputs random 64-bit floats

Question

I got this interview question and need to write a function for it. I failed.

Because it is a phone interview question, I don't think what I am supposed to code really need to be perfect random tester.

Any ideas?

How to write some code to be a reasonable randomness tester within like 30 minutes during an interview?

edit

The distribution in this question is uniformly distributed

Answer 1

As this is an interview question, I think the interviewers are looking to assess in two ways:

1. Ability to understand what the requirements of the problem really are.
2. Ability to think of some code that would address those requirements.

This could be a really good interview question in certain settings, especially if the interviewer were willing to prompt the candidate with questions as and when necessary.

In terms of understanding the requirements of the question, it helps if you know that this is a really difficult problem, witness the Diehard tests mentioned in pjs's answer. Fundamentally I think a candidate would need to demonstrate appreciation of two things:

(a) The overall distribution of the numbers should match the desired distribution (I'm assuming it is uniform in this case, but as @pjs points out in comments this assumption should be made explicit).

(b) Each number drawn should be independent from the previous numbers drawn.

With half an hour to code something up in a phone interview, you can't go very far. If I were answering this question I would try to suggest something like:

(a) To test the distribution, come up with a set of equal-sized bins for the floating point numbers, and count the numbers that fall into each bin. Plot a histogram and eyeball it (plotting the data is always a good idea). To extend this, you could use a chi-squared test, as described in amit's answer.

However, as discussed in the comments, and here

The main problem with chi squared test is the choice of number and size of the intervals. Although rules of thumb can help produce good results, there is no panacea for all kinds of applications.

To this end, the Kolmogorov-Smirnov test can be used. The idea behind this test is that if you a plot of the ordered data should be a good fit against the perfect ordered data (known as the cumulative distribution). For a uniform distribution the perfect ordered data is a straight line: you expect the 10th percentile of the data to be 10% of the way through the range, the 20th to be 20% of the way through the range and so on. So, programmatically, you could sort the data, plot it against the ideal value and you should get a straight line. There is also a formal, quantitative statistical test you can apply, which is based on the differences between the actual and ideal values.

(b) To test independence, there are multiple approaches. Autocorrelation at various time lags is one fairly obvious one: to what extent is the value at time t similar to the value at time t+1, for example. The runs test is another nice one: you convert all the numbers into 1 or 0 depending on whether they fall above or below the median, and then the distribution of the length of runs can be used to construct a statistical test. The runs test can also be used to test for runs in one direction or another, as described here and here (this might be more useful in your case). Both of these have fairly straightforward implementations so long as you have the formulas to hand!

Apart from the diehard tests, other good sources discussing random number generators include here and here.