Microsoft Fix Their Non-Random Browser Choice Screen

Here’s an interesting mathematics and computer science question: how random is Microsoft’s new EU browser choice screen? It’s not, according to several statistical analysis articles published during the past week.

IBM engineer Rob Weir has produced one of the better reports about the browser ordering on browserchoice.eu. The non-randomness is quite complex and it didn’t necessarily favor Internet Explorer; IE appeared last half the time and Chrome was more likely to appear in the first 3 positions.

Bringing Chaos from Order

Generating random numbers on a digital device is not easy. Most implementations use a mathematical function which returns a pseudo-random number. It may appear random, but the sequence is predictable. However, this is not the issue Microsoft encountered.

There are various algorithms to ‘randomly’ shuffle an array of items but, according to Rob Weir, Microsoft chose the worst one. They used the following JavaScript comparison function for array.sort():

function RandomSort(a,b)
{
	return (0.5 - Math.random());
}

Since the comparison function returns a random result, the sorting process would receive inconsistent information regarding its progress. It could perform no swaps or, in theory, it could continue indefinitely. Ultimately, the results are not uniformly random.

Weir suggests Microsoft should have used the Fisher-Yates shuffle. In essence, this randomly picks an item from the source array and moves it to the end of a destination array. The process continues until all items from the original array have been moved.

Does it Matter?

In my opinion — no. Most individuals will see the screen once or twice. Shuffling inconsistencies do not become apparent until you examine population samples containing thousands of users.

But do Microsoft need further legal wrangles? For all you lawyers excitedly anticipating a long-winded technical case about browser bias — you’re too late. Microsoft has changed their array shuffling algorithm:

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;

	}

}


Given a five-element array, the function will loop through elements 4 to 0 (variable b). A random number is generated between 0 and b (variable c). Elements b and c are then swapped. It’s not the Fisher-Yates algorithm, but it’s much better and will certainly end after 5 iterations (although it could end after 4 since the last element will always be swapped with itself).
I suspect it will result in a more uniform random distribution of browser positions. Eager statisticians will certainly be scrutinizing the results!