slopfront
preferences

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

0 points · submitted Mar 2010 by u/dani

11 comments · 20% upvoted · source · other discussions

comments

recursive 2 points · Mar 2010

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

dani [OP] 1 points · Mar 2010

I meant "why is it unfair"

recursive 2 points · Mar 2010

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 [OP] 1 points · Mar 2010

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

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

recursive 1 points · Mar 2010

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 [OP] 1 points · Mar 2010

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 nn different outcomes.

Anyway, the code they have right now seems fair.

recursive 1 points · Mar 2010

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

[deleted] 1 points · Mar 2010 
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] 1 points · Mar 2010

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] 0 points · Mar 2010 
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 [OP] 1 points · Mar 2010

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