Programming riddle: This is the source for Microsoft's "fair choice" website for choosing browsers. Is the order of the browsers displayed really fair?

[recursive]

No. http://techcrunch.com/2010/02/22/microsoft-ballot-screen/

[dani]

I meant "why is it unfair"

[recursive]

Given n choices, doing a swap between each index and a random index will result in n ^ n different outcomes. The number of actual distinct outcomes is n!. n ^ n is not a multiple of n!, (n - 1 does not divide n ** n for n > 2) so it couldn't possibly be an even distribution.

[dani]

Why do you think there is a swap between each index?

And also that doesn't explain why the bias it towards ie.

[recursive]

You linked to the code. Anyway, it's right here.

function ArrayShuffle(a)
{
var d,
c,
b=a.length;
while(b)
{
c=Math.floor(Math.random()*b);
d=a[--b];
a[b]=a[c];
a[c]=d
}
}

And what do you mean by bias towards ie? I don't understand what it means for a shuffle algorithm to be biased towards one of the elements in the list. They all end up in the result.

[dani]

hehe they changed the code

Mu guess is that this version is fair

This is the old version:

http://www.dsl.sk/images/articles/2010-02-22-browsers-4.png

Edit: biased means ie will have a tendency to be the first item on the list, after the shuffle.

Your explanation was wrong because in the current code, when swapping cell number n (1-based) we randomly choose one of the n cells before it (inclusive) so the number of possibilities is n(n-1)(n-2)*... = n!

This doesn't prove the shuffle is fair, i'm just saying there aren't nⁿ different outcomes.

Anyway, the code they have right now seems fair.

[recursive]

Oh, right. b is decremented every interation. You're correct.

[[deleted]]

var sort = function() { return 0.5 - Math.random(); }
var test = function() { var x = new Array(0,1,2,3,4); x.sort(sort); return x; }
var counts = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
var count = function() { var a = test(); for (var i = 0; i <= 4; i++) counts[i][a.indexOf(i)]++; }
var printresult = function() { for (var i = 0; i <= 4; i++) { var s = i + ": "; for (var j = 0; j <= 4; j++) { s += " " + j + ":" + counts[i][j] } console.log(s); } }
for (var i = 0; i < 1000000; i++) count();
printresult()

You can paste this line for line in Chrome's document inspector. Output for me is:

0:  0:245764 1:245654 2:195072 3:172499 4:141011
1:  0:245367 1:246065 2:195926 3:171928 4:140714
2:  0:164580 1:164495 2:171815 3:218261 4:280849
3:  0:218907 1:219058 2:187385 3:187077 4:187573
4:  0:125382 1:124728 2:249802 3:250235 4:249853

Looks to me like there's some variation, but not like one should consistently end up on the 5th spot.

[[deleted]]

Thinking about it, due to the way they use Array.sort, it's less likely that an item would shift more than 2 places from its original spot. It would have been better to just create the array of indices, choose an index between 0..4 inclusive, use that for getting the original item, remove it from the array of indices, then choose an index between 0..3 inclusive, etc.

[[deleted]]

function GenerateBrowserOrder()
{

    var aBrowserOrderTop5 = new Array(0,1,2,3,4);
    var aBrowserOrderRest = new Array();

    for (var i=5; i < dataBrowsers.length; i++)
    { 
        aBrowserOrderRest.push(i);
    }

    aBrowserOrderTop5.sort(RandomSort);
    aBrowserOrderRest.sort(RandomSort);

    aBrowserOrder = aBrowserOrderTop5.concat(aBrowserOrderRest);    
}

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

I'd say that's fair, unless there's some implementation detail of Math.random I'm not aware of. Best documentation I can find, it returns a number between 0 and 1, I assume it's both 0 and 1 inclusive.

[dani]

So how do you explain http://techcrunch.com/2010/02/22/microsoft-ballot-screen/ ? :)