Slashdot Mirror
Schooling Microsoft On Random Browser Selection
Rob Weir got wind that a Slovakian tech site had been discussing the non-randomness of Microsoft's intended-to-be-random browser choice screen, which went into effect on European Windows 7 systems last week. He did some testing and found that indeed the order in which the five browser choices appear on the selection screen is far from random — though probably not intentionally slanted. He then proceeds to give Microsoft a lesson in random-shuffle algorithms. "This computational problem has been known since the earliest days of computing. 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. Microsoft appears to have picked the bad approach. But I do not believe there is some nefarious intent to this bug. It is more in the nature of a 'naive algorithm,' like the bubble sort, that inexperienced programmers inevitably will fall upon when solving a given problem. I bet if we gave this same problem to 100 freshmen computer science majors, at least 1 of them would make the same mistake. But with education and experience, one learns about these things. And one of the things one learns early on is to reach for Knuth. ... The lesson here is that getting randomness on a computer cannot be left to chance. You cannot just throw Math.random() at a problem and stir the pot and expect good results."
Hmm, there's a nice shuffle implementation in Java that Microsoft could use... Oh, wait...
Rgds
Damon
http://m.earth.org.uk/
Why not? Is the author suggesting that random functions in use today are somewhat deficient? What is his solution?
You know, it's really too bad that the author of the article the summary linked to didn't write up an article answering exactly that. Then maybe Slashdot could have linked to it.
(In a nutshell, the answers are, respectively: "because plopping a 'rand()' into your code doesn't mean that what you'll get out is uniform", "no", and "use a shuffling algorithm that works.")
A Google search on:
gives exactly the bogus answer that Microsoft used in the top hit.
Unfortunately for Microsoft, a bing search gives the same top hit.
What the problem actually seems to be is not that they're using random, but how they're using it.
What they essentially did was use something like qsort() to sort the list, but in their comparator function, instead of returning which of the two strings comes first, they return some random crap instead. qsort() or whatever they used was designed to have results that are consistent, and with input like that it could potentially abort and leave the list entirely unsorted. Or if you're really unlucky it could sit there sorting them forever.
No, Math.random is not the problem, the problem is how it is used. They used it as random input to a sorting algorithm without considering how the sorting algorithm works. The assumption that any sorting algorithm with inconsistently random input = random order is wrong. If they had assigned a random value to each element and sorted by that value the result would have been truly random as the value associated with each element would have been consistent.
Here's the problem - consider the results again. Safari will almost always (almost 50% of the time) be put in the bottom two elements. In fact depending on the algorithm used it's 40-50% chance of being put in one exact slot (either choice four or five).
When the whole point of the list is promote browser competition, it makes no sense to accept a list which is that skewed for ANY browser result from the list. You need to have it properly shuffled so that no one browser has a statistical advantage or disadvantage - if you are going to claim it doesn't matter then why not let Microsoft set an arbitrary fixed order for the list?
That is not what the legal injunction against them says they can do, therefore the randomness of the results DO matter. Just as in most things in life, correctness of results is actually important.
"There is more worth loving than we have strength to love." - Brian Jay Stanley
You are missing the point. As the author of the article pointed out, this technique can cause an infinite loop.
No, the point was that no one browser got unfairly pushed to the top all the time. This algorithm does push a certain browser higher more often than not, and hence is not fit for it's job.
Even with a very high quality entropy source, the algorithm Microsoft used will result in a very non-uniform distribution.
Clearly, Microsoft didn't care about this enough to assign one of their experienced coders to it, which is odd given the legal involvement. Either the technical side of MS ignored the legal department's explanation of the importance of the browser ballot to MS's ability to do business on a particularly profitable continent, or someone powerful in MS decided to spite the EU by assigning low quality programmers to the project.
While in Microsoft's native browser (which would happen the first time), Internet Explorer is given a full %64 chance of receiving one of the coveted 2 edge positions. Considering that antitrust courts were involved in the creation of this screen, you'd think that getting "random" right would be a development priority, especially considering it should have taken a competent programmer exactly the same amount of time to do it right as to do it wrong. If this takes even one hour of lawyer time to ponder, it would have been much cheaper to send the programmer back to fix it.
A 50% chance of getting a particular slot that should be %20 is not "99.99% random." It's just wrong. And when you're talking about the cost of antitrust regulation, it's really, really wrong.
I'm glad this is being brought up on Slashdot. There is a lot of misunderstanding about how to create randomness in systems. Even on a basic level, people frequently ask for "random" when they actually want jukebox random. In this case, though, it just seems like a basic misunderstanding of statistics, which is not surprising given the moderate code complexity and likelihood this screen was given to an intern or jr programmer.
The ______ Agenda
The relevant code is in their Javascript:
aBrowserOrderTop5.sort(RandomSort); (they repeat this twice for some reason) ...
function RandomSort (a,b)
{
return (0.5 - Math.random());
}
This takes the browser's built-in sorting function, tells it to sort by an essentially random criteria, and hopes that it all works out. Unfortunately, this is highly dependent on the implementation of the built-in sort function, and that's up to the browser designer to create. The only constraint on the structure of sort is that it must successfully order comprehensible data, which does not mean that it will properly randomize data when provided. Essentially, they overloaded a black-box function that wasn't designed for randomization in the hopes that it would work.
For an instance of why this wouldn't work, consider the case of the last item. Say that you're sorting a list of 5 letters. Now say that you're most of the way through the list, having properly sorted the first 4 letters into "A, B, D, E", with just the 5th letter C left. So you step through.
Does C come before E? Yes.
Does C come before D? Yes.
Does C come before B? No.
C must go between B and D, and the list will look like "A , B , C , D , E." It will be sorted correctly every time.
Now let's throw that randomization into the middle there. Let's start again with the list, though since we're randomizing let's call them item 1, 2, 3, and 4. If we're properly randomly sorting the last item 5 into the list, it should have equal chances of showing up everywhere. But remember, we're still using the sorting algorithm from above, we're just flipping a coin at each question instead of actually comparing. So what we get is:
Does 5 come before 4? 50% yes, or stop
Does 5 come before 3? 50% yes, or stop
Does 5 come before 2? 50% yes, or stop
etc. But because it's iterative, those 50% chances stack. You only get to the second question half of the time, so you only get to the third question half of that half of the time. And essentially what you wind up with is a % chance of the last number being sorted into each of the slots as: 3%, 6%, 12%, 25%, 50%. This is obviously not a random distribution curve.
This is not necessarily the sort algorithm that Microsoft uses in I.E. (The 50% chance of staying as the last element is a bit suspicious, though, as is running their code twice). But it does point out unequivocably that you can't overload an off-the-shelf sort algorithm with a randomizing comparator and expect the outcome to follow a genuinely random distribution curve. They really ought to have an in-house random sort algorithm that their developers can pull from.
(Thanks to another poster for finding the first google hit that describes this method.).
The ______ Agenda
You know, your post just made me realize that Microsoft has made a good entry for perhaps next year's Underhanded C Contest: write some innocent-looking code that is supposed to randomize a selection, but fails to do so fairly and favors certain selections over others.
If you had bothered to read the article, you'd see that the author has done JUST that. Not only did he prove (using proper statistical methods) that the results are significantly not random, he also dug up the exact javascript source code that does the shuffling and explained why it is faulty. RTFA!
Loban Amaan Rahman ==> Anagram of ==> Aha! An Abnormal Man!