为什么这种随机播放算法没有偏差

Question

我的同事和我正在争论为什么在这个JS提示和技巧列表中给出的随机算法不会产生偏见的结果,就像杰夫阿特伍德描述的天真洗牌一样.

提示中的数组shuffle代码是:

list.sort(function() Math.random() - 0.5);

Jeff的天真洗牌代码是:

for (int i = 0; i < cards.Length; i++)
{
  int n = rand.Next(cards.Length);
  Swap(ref cards[i], ref cards[n]);
}

我写了这个JS来测试shuffle:

var list = [1,2,3];
var result = {123:0,132:0,321:0,213:0,231:0,312:0};
function shuffle() { return Math.random() - 0.5; }
for (var i=0; i<60000000; i++) {
    result[ list.sort(shuffle).join('') ]++;
}

为此我获得了结果(来自Firefox 5),如:

Order   Count          %Diff True Avg
123      9997461       -0.0002539
132     10003451        0.0003451
213     10001507        0.0001507
231      9997563       -0.0002437
312      9995658       -0.0004342
321     10004360        0.000436

据推测,Array.sort正在行走list阵列并执行类似于Jeff的示例的(相邻)元素的交换.那么为什么结果看起来没有偏见呢？

Answer 1

我找到了它显得不偏不倚的原因。

Array.sort() 不仅返回数组，还更改数组本身。如果我们为每个循环重新初始化数组，我们会得到如下结果：

123 14941
132 7530
321 7377
213 15189
231 7455
312 7508

这表明存在非常显着的偏差。

对于那些感兴趣的人，这里是修改后的代码：

var result = {123:0,132:0,321:0,213:0,231:0,312:0};
var iterations = 60000;
function shuffle() { 
    comparisons++;
    return Math.random() - 0.5;
}
for (var i=0; i<iterations; i++) {
    var list = [1,2,3];
    result[ list.sort(shuffle).join('') ]++;
}
console.log(result);