The Elusive Nature of Randomness and Random shuffles

After a lengthy legal battle, Microsoft and the European antitrust officials recently agreed on the implementation of a so-called ballot or choice screen, to be included in the rollout of Windows 7.

This approach will give European Windows 7 users an opportunity to download their prferred browser from a list of Microsoft's rivals.

These choices include Google's Chrome, Apple's Safari, Mozilla's Firefox and Opera, as possible alternatives to Microsoft’s own Internet Explorer.

Randon Shuffle
The browser choice screen requires what we call a “random shuffle”. You start with an array of values and return those same values, but in a randomised order but how can you guarantee a 'truly random' result. Well, this computational problem has been known to programmers since the earliest days of computing.

Known approaches
There are 5 well-known approaches: 3 good solutions, 1 acceptable solution that is slower than necessary and 1 bad approach that doesn’t really work. Ubfortunately from this selection Microsoft appears to have picked the bad approach but it more likely to have been caused by inexperience or bad judgement rather than any ill-intention.

It is more in the nature of a “naive” algorithm, akin to the simple bubble sort. Something that inexperienced programmers inevitably fall headlong into when attempting to solve a given problem.

Inevitably, if we gave this same problem to 100 newly qualified computer scienctists, 1 or more of them would make the same basic mistake. Fortunately, with education and experience, programmers can learn about these things and certainly, one of the things they should learn about early on, is to reach for Donald Knuth's book on algorithms, programming and random shuffles.

The Art of Computer Programming, Vol. 2, section 3.4.2 “Random sampling and shuffling” describes two solutions:

1. If the number of items to sort is small, then simply put all possible orderings in a table and select one ordering at random. In our case, with 5 browsers, the table would need 5! = 120 rows.
2. “Algorithm P” which Knuth attributes to Moses and Oakford (1963), but is now known to have been anticipated by Fisher and Yates (1938) so it is now called the Fisher-Yates Shuffle.
   

Random Generators - The Fisher-Yates Shuffle

The Fisher–Yates shuffle, named after Ronald Fisher and Frank Yates, also known as the Knuth shuffle, after Donald Knuth, is an algorithm for generating a random permutation of a finite set—in plain terms, for randomly shuffling the set.

A variant of the Fisher–Yates shuffle, known as Sattolo's algorithm, may be used to generate random cycles of length n instead.

Unbiased
Properly implemented, the Fisher–Yates shuffle is unbiased, so that every permutation is equally likely. The modern version of the algorithm is also rather efficient, requiring only time proportional to the number of items being shuffled and no additional storage space.

The process
The basic process of Fisher–Yates shuffling is similar to randomly picking numbered tickets out of a hat, or cards from a deck, one after another until there are no more left. What the specific algorithm provides is a way of doing this numerically in an efficient and rigorous manner that, properly done, guarantees an unbiased result.

The original Fisher and Yates' method
Their method was designed to be implemented using pencil and paper, with a precomputed table of random numbers as the source of randomness.

The basic method given for generating a random permutation of the numbers 1–N goes as follows: in their book The Fisher–Yates shuffle, in its original form, was described in 1938 by Ronald A. Fisher and Frank Yates; Statistical tables for biological, agricultural and medical research. (Later editions describe a somewhat different method attributed to C. R. Rao.)

1. Write down the numbers from one to N.
2. Pick a random number k between one and the number of unstruck numbers remaining (inclusive).
3. Counting from the low end, strike out the kth number not yet struck out, and write it down elsewhere.
4. Repeat from step 2 until all the numbers have been struck out.
5. The sequence of numbers written down in step 3 is now a random permutation of the original numbers.

Provided that the random numbers picked in step 2 above are truly random and unbiased, so will the resulting permutation be. Fisher and Yates took care to describe how to obtain such random numbers in any desired range from the supplied tables in a manner which avoids any bias.

They also suggested the possibility of using a simpler method — picking random numbers from one to N and discarding any duplicates—to generate the first half of the permutation, and only applying the more complex algorithm to the remaining half, where picking a duplicate number would otherwise become frustratingly common.