A quick update on my post from last week on the “Microsoft Shuffle“, where I looked at how Microsoft’s “random” browser ballot was far from random.
First, I’d like to thanks those who commented on that post, or sent me notes, offering additional analysis. I think we nailed this one. Within a few days of my report Microsoft updated their JavaScript on the browserchoice.eu website, fixing the error. But more on that in a minute.
Some random observations
Several commenters mentioned that if you search Google for “javascript random array sort” the first link returned will be a JavaScript tutorial that has the same offending code as Microsoft’s algorithm. This is not surprising. As I said in my original post, this is a well-known mistake. But it is no less a mistake. If you use Google Code Search for the query “0.5 – Math.random()” lang:javascript you will find 50 or so other instances of the faulty algorithm. So if anyone else is using this same algorithm, they should evaluate whether it is really sufficiently random for their needs. In some case, such as a children’s game, it might be fine. But know that there are better and faster algorithms available that are not much more complicated to code.
Another thing to note is that the Microsoft Shuffle algorithm is bad enough with 5-elements in the array, but the non-randomness gets more pronounced as you increase the length of the array. Regardless of the size of the array, it appears that on Internet Explorer the 1st element will end up in last place 50% of the time. There are other pronounced patterns as well. You can see this yourself this this test file, which allows you to specify the size of the array as well as the number of iterations. Try a 50-element array for 10,000 iterations to get a good sense of how non-random the results can be.
I used that script to run a large test of 1,000,000 iterations of a 1024-element array. The raw results are here. I took that table, and using R’s image() function produced a rendering of that matrix. You can see here the clear over-representation at some positions, including (in the lower left) the flip of the first position to last place. (I’m not quite satisfied with this rendering. Maybe someone can get a better-looking visualization of this same data.)
Evaluating Microsoft’s new shuffle
Sometime last week — I don’t know the exact date — Microsoft updated the code for the browser choice website with a new random shuffle algorithm. You see the code, in situ, here. The core of it is in this function:
function ArrayShuffle(a)
{
var d, c, b=a.length;
while(b)
{
c=Math.floor(Math.random()*b);
d=a[--b];
a[b]=a;
a=d
}
}
This looks fine to me. I created a new test driver for this routine, which you can try out here. Aside from being much faster, it is gives much better results. Here is a run with a million iterations:
Raw counts
| Position | I.E. | Firefox | Opera | Chrome | Safari |
|---|---|---|---|---|---|
| 1 | 199988 | 200754 | 199944 | 199431 | 199883 |
| 2 | 200320 | 200016 | 199838 | 199752 | 200074 |
| 3 | 199702 | 199680 | 199911 | 200865 | 199842 |
| 4 | 200408 | 200286 | 199740 | 199861 | 199705 |
| 5 | 199582 | 199264 | 200567 | 200091 | 200496 |
Fraction of total
| Position | I.E. | Firefox | Opera | Chrome | Safari |
|---|---|---|---|---|---|
| 1 | 0.2000 | 0.2008 | 0.1999 | 0.1994 | 0.1999 |
| 2 | 0.2003 | 0.2000 | 0.1998 | 0.1998 | 0.2001 |
| 3 | 0.1997 | 0.1997 | 0.1999 | 0.2009 | 0.1998 |
| 4 | 0.2004 | 0.2003 | 0.1997 | 0.1999 | 0.1997 |
| 5 | 0.1996 | 0.1993 | 0.2006 | 0.2001 | 0.2005 |
And the results of the Chi-square test:
X-squared = 18.9593, df = 16, p-value = 0.2708
Final thoughts
In the end I don’t think it is reasonable to expect every programmer to memorize the Fisher-Yates algorithm. These things belong in our standard libraries. But what I would expect every programmer to know is:
- That the problem here is one that requires a “random shuffle”. If you don’t know what it is called, then it will be difficult to lookup the known approaches. So this is partially a vocabulary problem. We, as programmers, have a shared vocabulary which we use to describe data structures and algorithms; binary searches, priority heaps, tries, and dozens of other concepts. I don’t blame anyone for not memorizing algorithms, but I would expect a programmer to know what types of algorithms apply to their work.
- How to research which algorithm to use in a specific context, including where to find reliable information, how to evaluate the classic trade-offs of time and space, etc. There is almost always more than one way to solve a problem.
- That where randomized outputs are needed, the outputs should be statistically tested. I would not expect the average programmer to know how to do a chi-square test, or even to know what one is. But I would expect a mature programmer to know either find this out or seek help.
Yes, the ArrayShuffle(a) procedure that is now used is an implementation of Algorithm 3.4.2P (Shuffling) in [D.E.Knuth. The Art of Computer Programming, vol.2: Seminumerical Algorithms. ed.3 pp.145-146]. The ECMAScript version is a tidy little thing.
Knuth also reports that the (effective) modulus of the random number generator is a factor, since that can prevent all possible n! permutations from appearing in the list of n selections (or a shuffled deck of n cards, where the problem can be serious).
For n=5 I wouldn’t expect trouble. Of course, the random number generator quality can be a factor in other ways.
While it may be a simple mistake, Microsoft are supposed to be professionals. At least they claim they are.
Thanks for the articles, they were an interesting read. Since I don’t use Windows or do Javascript I wouldn’t have seen this myself.
The analysis is done well, I like it. Only a minor problem: The link to the shuffle2.html is currently broken (mixed in a semicolon…).
I supposed they didn’t think they needed a rocket scientist to create a randomized list of five items on demand.
What is even funnier is that the improved method does two shuffles when one has to be enough. (shuffle the indexes and the rest follows). It doesn’t seem to matter, but it does obscure what is being done and inspecting to confirm that what is being done is sufficient.
I guess deciding that if shuffling one list is good, shuffling another one too must be better, is an indication that the rocket scientist has left the building (or decided to leave things alone the parts that don’t matter anyhow).
@orcmid, you don’t to be a genius to get it right. But you do need access to a compendium of algorithms written by geniuses of the past. We stand on the shoulders of giants: Hoare, Dijkstra, Knuth, etc.
Hmmm… maybe knowledge of algorithms is more widespread than I realized. See, for example, this:
Strange – running both of your tests in Chrome yielded a much more even results. I haven’t checked their p-value, but even with the 50/10000, most table cells are between 180 and 230. I wonder how Chrome manages to run the “wrong” algorithm in a somewhat more random way.
Noam Gal, if you mean that the old 0.5-rand() algorithm appears to have a more even distribution from the trials (is this what you mean?), it could be because the quicksort routine does produce an even distribution for it. It would not be unusual that Chrome would use quicksort (although other algorithms could also exhibit this property). This observation was covered in a number of comments in the first article. There was even a link to someone that ran a bunch of trials with the old algorithm on various standard sorts, and you can clearly see that quicksort has an even distribution (the others did not).
@Noam, I think we should put to bed the idea that Microsoft’s original random shuffle algorithm is acceptable in any browser. It may work better in some than others, or with some sort algorithm than others, but I have yet to see it actually produce reasonably random results.
In the case of the browser ballot case I tested only the simplest quality of the outcomes, namely whether each browser occurred equally often in each position. I tested whether the positions were uniformly distributed.
That is a necessary condition of a good random shuffle — and in the case of the browser ballot might be all that is needed — but it is not a sufficient condition for a good general purpose random shuffle. What you want in the general case is that all possible combinations are equally likely. Otherwise, I could just treat the array as a circular array and rotate it in order: 01234, 12340, 23410, 34012, 40123, and have perfectly uniform distribution of positions with only 5 different unique permutations. Now that might be fine for a browser ballot, but imagine the trouble if you did a random shuffle of a card deck that way! (In other words, take the top card and place it at the bottom of the deck and call it good enough.)
What you really want is for all of the N! (in our case 120) different permutations to have an equal chance of occurring. So uniform distribution of all possible orderings of the array.
I did a quick test of 1,000,000 iterations, looking at how often each of the 120 orderings occurred, and it is clear that the Microsoft shuffle is not doing a good job, even in Chrome. I also added a column for the Fisher-Yates shuffle on Internet Explorer, for comparison.
Combination IE Firefox Chrome Fisher-Yates
01234 508 66200 15645 8467
01243 3327 3939 15654 8356
01324 3449 33188 15651 8232
01342 22644 1869 15710 8306
01423 1946 7636 15501 8359
01432 2938 3900 15712 8326
02134 701 32996 7890 8301
02143 5665 1982 7818 8303
02314 5556 16625 7759 8247
02341 11109 956 7797 8367
02413 788 3876 7924 8384
02431 1457 1940 7881 8202
03124 1956 16483 15696 8235
03142 18477 995 15663 8414
03214 3383 8478 7676 8460
03241 6876 474 7761 8192
03412 9648 1970 15485 8321
03421 3888 995 7776 8403
04123 3394 15433 7705 8356
04132 2871 7713 7798 8197
04213 488 7702 3789 8371
04231 949 3912 3915 8447
04312 13749 3946 7910 8336
04321 6783 1944 3993 8289
10234 497 66488 15657 8328
10243 3346 3905 15633 8310
10324 3548 33155 15510 8366
10342 22446 1947 15520 8171
10423 1878 7621 15552 8385
10432 2943 3903 15798 8509
12034 717 33495 7800 8247
12043 4623 1960 7827 8337
12304 3287 16637 7864 8317
12340 44916 968 7829 8317
12403 2468 3857 7949 8401
12430 5604 1907 7873 8366
13024 2424 16611 15612 8389
13042 13596 996 15752 8406
13204 1976 8260 7916 8441
13240 27321 470 7781 8439
13402 7779 1887 15457 8165
13420 15609 948 7864 8310
14023 2441 15738 7762 8351
14032 1998 7638 7827 8329
14203 1958 7999 3917 8401
14230 3854 3927 3762 8254
14302 13617 3839 7547 8239
14320 27391 1953 3887 8270
20134 750 33267 7806 8429
20143 5689 2030 7679 8240
20314 5648 16630 7859 8344
20341 11326 994 7872 8386
20413 728 3818 7781 8255
20431 1458 1929 7975 8365
21034 720 33345 7806 8232
21043 4715 1896 7738 8360
21304 3418 16677 7863 8236
21340 45101 983 7846 8465
21403 2430 3894 7710 8120
21430 5914 1967 7877 8273
23014 4679 8338 7696 8263
23041 9371 501 7838 8330
23104 2426 8377 7913 8332
23140 37102 464 7894 8315
23401 4836 965 7850 8401
23410 19535 931 7777 8175
24013 713 7913 3892 8106
24031 1497 3891 3874 8472
24103 3384 8018 3862 8331
24130 5829 3947 3894 8514
24301 6880 1938 4001 8463
24310 27276 1948 4074 8383
30124 2004 16620 15642 8217
30142 18677 977 15598 8083
30214 3409 8358 7822 8484
30241 7066 487 7882 8412
30412 9888 1924 15554 8238
30421 3924 987 7724 8273
31024 2429 16573 15690 8225
31042 13381 1010 15565 8413
31204 2066 8257 7725 8382
31240 27326 513 7806 8301
31402 7912 1999 15530 8359
31420 15493 1067 7975 8409
32014 4612 8302 7814 8412
32041 9434 508 7766 8342
32104 2400 8345 7730 8362
32140 37043 466 7875 8406
32401 4919 1002 7743 8353
32410 19341 987 7630 8426
34012 7749 3950 7889 8307
34021 4780 1985 3947 8292
34102 9866 3945 7862 8393
34120 19658 1908 3816 8351
34201 3860 1991 3761 8220
34210 15367 1916 3946 8448
40123 3478 31351 7719 8296
40132 2800 15675 8029 8380
40213 478 15780 4021 8320
40231 1006 7823 3892 8350
40312 13676 7915 7800 8344
40321 6850 3928 3945 8413
41023 2449 31019 7730 8224
41032 2025 15620 7736 8401
41203 1901 15444 3865 8446
41230 3924 7959 3838 8383
41302 13743 7858 7737 8417
41320 27417 3871 3949 8293
42013 688 15562 3971 8336
42031 1446 7942 3912 8209
42103 3548 15564 3778 8311
42130 5895 7807 3913 8385
42301 6815 3881 4015 8187
42310 27509 3838 3981 8328
43012 7716 7808 7751 8389
43021 4906 3952 3890 8369
43102 9640 7779 7900 8249
43120 19477 3865 3940 8360
43201 3931 3886 3966 8309
43210 15746 3754 3928 8362
And it doesn’t end there. There are other tests you might want to apply, a whole battery of them, to fully test a random shuffle algorithm. The browser ballot case only required (IMHO) the simplest quality — uniform distribution of browser positions. Other uses might require additional qualities, including lack of correlation across shuffles. (Otherwise I could just repeat the same 120 permutations in order, over and over again.) Because of that I would always recommend to use a tried-and-true algorithm like Fisher-Yates over something that “seems to work” but has not been rigorously characterized.
Each party fetches the script separately from Microsoft. There are a couple of opportunities for bias in this situation:
1. What is stopping a man-in-the-middle attack from altering the ballot script?
2. It’s impossible to be sure that every single instance of the script served to clients is the same. The script could be varied based on knowledge of the geography of the requestor (mined from the IP number), or perhaps just alter a small percentage of the scripts that are served to introduce a bias.
I’d be astonished if Microsoft was practicing Item 2 (because of the risk to their reputation if caught, relative to the small potential for benefit), but thought I’d mention it anyway as part of trying to explore the entire infrastructure, looking for points at which fraud could be practiced.
— recherche
I wonder why MS is allowed to control the ballot screen, shouldn’t it be ran by someone else, EU itself perhaps?
Well it’s more than a year after the browserchoice ‘incident’ and I may point out that the copy of the algorithm in your blog post has the var names mixed up (see ‘c’) :D
@mistacko, Wow, that was a mess. It looks like that got scrambled somewhere along the way. I suspect the syntax highlighter plugin. I updated the snippet so it correctly shows what Microsoft used, and what I tested.
Thanks!
-Rob