An Ars Technica “etc” post linked to a TechCrunch article (apparently based on a Slovakian article, but I didn’t look into the Slovakian article to be sure) that talks about the ordering of the browsers in Microsoft’s EU Browser Ballot not being uniformly distributed. At a glance at the Javascript that does the randomizing of the browsers (randomly orders the top 5, and randomly orders the rest), it appears to randomize by calling the Javascript array sort with a comparison function that returns < half the time and > the other half of the time. I believe that this is likely the underlying cause of the non-uniformity of the orderings.
The second result in a google search for “javascript sort” says:
To randomize the order of the elements within an array, what we need is the body of our sortfunction to return a number that is randomly <0, 0, or >0, irrespective to the relationship between “a” and “b”. The below will do the trick:
//Randomize the order of the array: var myarray=[25, 8, "George", "John"] myarray.sort(function() {return 0.5 - Math.random()}) //Array elements now scrambled
This is almost exactly the method of randomization used in the browser ballot javascript.
To test the results of this randomization technique, I applied it 1,000,000 times to the list {0,1,2,3,4} in Mathematica and tabulated the relative frequencies of each number in each position. (Rounded to the nearest whole %).
| position/number | 0 | 1 | 2 | 3 | 4 |
| first | 18% | 12% | 12% | 12% | 47% |
| second | 18% | 24% | 18% | 18% | 24% |
| third | 20% | 21% | 27% | 20% | 12% |
| fourth | 22% | 22% | 22% | 28% | 6% |
| fifth | 22% | 22% | 22% | 22% | 12% |
At a glance, it appears that the distribution is far from uniform. My quick attempt at re-learning how to use the Χ2 test gave a probability less than 1×10-100000 that this data matched a uniform distribution (if someone can confirm/fix that, please comment).
I used the Mathematica Sort[] command to do the sorting. I don’t know what algorithm that uses. It appears that the algorithm used by Javascript’s sort() varies from browser to browser, though the browser ballot would be displayed in IE8 by default. I suspect that the distribution is highly dependent on the sorting algorithm used, though I cannot readily verify it [edit: I verified it]. Regardless, this seems to be a very poor way to generate a random ordering.
Trackbacks & Pingbacks 1
[...] I posted the results of my quick exploration of whether sorting the list {0,1,2,3,4} using a comparison function that randomly returns < or [...]