How to test randomness (case in point - Shuffling)

Question

I have a simple universal app I am working on, basically there are 10 images and 10 buttons on the screen. If you click button2, then image2 will disappear, click button2 again and image2 will reappear. My iphone version works perfectly, but I'm having issues with the iPad.

I have the app load MainWindow-iPad.xib, which gets its view from AppNameViewController-iPad.xib. I also have AppNameViewController-iPad.h/.m which has the methods and UIImage objects needed.

Now, if I have nothing linked, I can see the iPad view perfectly. If I link a button with its corresponding method, the view will still load. If I link an Image View with the corresponding UIImage (IE link image2.png with UIImage *image2) and try to run the program, I get this error in the debug field:

2011-04-12 12:46:45.400 AppName[14106:207] * Terminating app due to uncaught exception 'NSUnknownKeyException', reason: '[ setValue:forUndefinedKey:]: this class is not key value coding-compliant for the key image2.'

Xcode then brings me to main.m and gives an error at this line:

int main(int argc, char *argv[]){
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
int retVal = UIApplicationMain(argc, argv, nil, nil); //THIS LINE HERE
[pool release];
return retVal;
}

The error says "Thread 1: Program received signal "SIGABRT".

I'm not sure if it matters, but I have one AppDelegate.h/m for the whole app but a separate ViewController.h/m for iPhone and iPad. I have a feeling I just didn't link something right with my xibs, but I'm a very new developer and I just haven't been able to figure it out. Many thanks if somebody can help me solve this issue.

Solution 1

Statistics. The de facto standard for testing RNGs is the Diehard suite (originally available at http://stat.fsu.edu/pub/diehard). Alternatively, the Ent program provides tests that are simpler to interpret but less comprehensive.

As for shuffling algorithms, use a well-known algorithm such as Fisher-Yates (a.k.a "Knuth Shuffle"). The shuffle will be uniformly random so long as the underlying RNG is uniformly random. If you are using Java, this algorithm is available in the standard library (see Collections.shuffle).

It probably doesn't matter for most applications, but be aware that most RNGs do not provide sufficient degrees of freedom to produce every possible permutation of a 52-card deck (explained here).

Solution 2

Here's one simple check that you can perform. It uses generated random numbers to estimate Pi. It's not proof of randomness, but poor RNGs typically don't do well on it (they will return something like 2.5 or 3.8 rather ~3.14).

Ideally this would be just one of many tests that you would run to check randomness.

Something else that you can check is the standard deviation of the output. The expected standard deviation for a uniformly distributed population of values in the range 0..n approaches n/sqrt(12).

/**
 * This is a rudimentary check to ensure that the output of a given RNG
 * is approximately uniformly distributed.  If the RNG output is not
 * uniformly distributed, this method will return a poor estimate for the
 * value of pi.
 * @param rng The RNG to test.
 * @param iterations The number of random points to generate for use in the
 * calculation.  This value needs to be sufficiently large in order to
 * produce a reasonably accurate result (assuming the RNG is uniform).
 * Less than 10,000 is not particularly useful.  100,000 should be sufficient.
 * @return An approximation of pi generated using the provided RNG.
 */
public static double calculateMonteCarloValueForPi(Random rng,
                                                   int iterations)
{
    // Assumes a quadrant of a circle of radius 1, bounded by a box with
    // sides of length 1.  The area of the square is therefore 1 square unit
    // and the area of the quadrant is (pi * r^2) / 4.
    int totalInsideQuadrant = 0;
    // Generate the specified number of random points and count how many fall
    // within the quadrant and how many do not.  We expect the number of points
    // in the quadrant (expressed as a fraction of the total number of points)
    // to be pi/4.  Therefore pi = 4 * ratio.
    for (int i = 0; i < iterations; i++)
    {
        double x = rng.nextDouble();
        double y = rng.nextDouble();
        if (isInQuadrant(x, y))
        {
            ++totalInsideQuadrant;
        }
    }
    // From these figures we can deduce an approximate value for Pi.
    return 4 * ((double) totalInsideQuadrant / iterations);
}

/**
 * Uses Pythagoras' theorem to determine whether the specified coordinates
 * fall within the area of the quadrant of a circle of radius 1 that is
 * centered on the origin.
 * @param x The x-coordinate of the point (must be between 0 and 1).
 * @param y The y-coordinate of the point (must be between 0 and 1).
 * @return True if the point is within the quadrant, false otherwise.
 */
private static boolean isInQuadrant(double x, double y)
{
    double distance = Math.sqrt((x * x) + (y * y));
    return distance <= 1;
}

Solution 3

First, it is impossible to know for sure if a certain finite output is "truly random" since, as you point out, any output is possible.

What can be done, is to take a sequence of outputs and check various measurements of this sequence against what is more likely. You can derive a sort of confidence score that the generating algorithm is doing a good job.

For example, you could check the output of 10 different shuffles. Assign a number 0-51 to each card, and take the average of the card in position 6 across the shuffles. The convergent average is 25.5, so you would be surprised to see a value of 1 here. You could use the central limit theorem to get an estimate of how likely each average is for a given position.

But we shouldn't stop here! Because this algorithm could be fooled by a system that only alternates between two shuffles that are designed to give the exact average of 25.5 at each position. How can we do better?

We expect a uniform distribution (equal likelihood for any given card) at each position, across different shuffles. So among the 10 shuffles, we could try to verify that the choices 'look uniform.' This is basically just a reduced version of the original problem. You could check that the standard deviation looks reasonable, that the min is reasonable, and the max value as well. You could also check that other values, such as the closest two cards (by our assigned numbers), also make sense.

But we also can't just add various measurements like this ad infinitum, since, given enough statistics, any particular shuffle will appear highly unlikely for some reason (e.g. this is one of very few shuffles in which cards X,Y,Z appear in order). So the big question is: which is the right set of measurements to take? Here I have to admit that I don't know the best answer. However, if you have a certain application in mind, you can choose a good set of properties/measurements to test, and work with those -- this seems to be the way cryptographers handle things.

Solution 4

The only way to test for randomness is to write a program that attempts to build a predictive model for the data being tested, and then use that model to try to predict future data, and then showing that the uncertainty, or entropy, of its predictions tend towards maximum (i.e. the uniform distribution) over time. Of course, you'll always be uncertain whether or not your model has captured all of the necessary context; given a model, it'll always be possible to build a second model that generates non-random data that looks random to the first. But as long as you accept that the orbit of Pluto has an insignificant influence on the results of the shuffling algorithm, then you should be able to satisfy yourself that its results are acceptably random.

Of course, if you do this, you might as well use your model generatively, to actually create the data you want. And if you do that, then you're back at square one.

Solution 5

There's a lot of theory on testing randomness. For a very simple test on a card shuffling algorithm you could do a lot of shuffles and then run a chi squared test that the probability of each card turning up in any position was uniform. But that doesn't test that consecutive cards aren't correlated so you would also want to do tests on that.

Volume 2 of Knuth's Art of Computer Programming gives a number of tests that you could use in sections 3.3.2 (Empirical tests) and 3.3.4 (The Spectral Test) and the theory behind them.

View more solutions

Comments

[August]

Heh. A clarification then. "Assume that you have a algorithm that you believe generates randomness."

[Baltimark]

OK. I wasn't trying to be snarky. I don't really know if you're asking "how to test randomness" which can be asked without referring to card shuffling, or if you're asking "how to test if my shuffling alogrithm has screwed up my good RNG."

[August]

Me likes. Not the solution to the exact shuffle problem, but a good starting point. Have an upvote :)

[jfs]

There is no need for Math.sqrt() in isInQuadrant().

[user3409701]

How is this, aside from all the extra processing, different from just counting higher/lower than 50% of the range of a random number?

[joshclarke]

Hey thanks for the suggestion, I got it working and posted my solution.

[Andrew]

Graphs. Use lots of graphs. Scatter plot to ensure no patterns, and then count how many times each combination occurs to make sure it is (almost) evenly distributed) over time. Use math to determine no patterns more accurately, but maths is hard.

[jgmjgm]

A matrix serves as a good spot check but you can't use that alone. There are non-random patterns that produce even distributions. Simply rotating the deck each time for example (take one of the top and put on bottom).

[Matt]

It looks like FSU has disappeared the Diehard sites. There is a Duke GPL'd distribution of a similar tool called Dieharder

[Ender]

You can see the archieved one web.archive.org/web/20160125103112/http://stat.fsu.edu/pub/…