为什么这个简单的shuffle算法会产生偏差的结果呢？什么是一个简单的原因？

Question

似乎这个简单的shuffle算法会产生偏差的结果:

# suppose $arr is filled with 1 to 52

for ($i < 0; $i < 52; $i++) { 
  $j = rand(0, 51);

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

你可以尝试...而不是使用52,使用3(假设只使用3张卡),并运行10,000次并计算结果,你会看到结果偏向某些模式......

问题是......它会发生什么简单的解释？

正确的解决方案是使用类似的东西

for ($i < 0; $i < 51; $i++) {  # last card need not swap 
  $j = rand($i, 51);        # don't touch the cards that already "settled"

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

但问题是......为什么第一种方法,似乎也是完全随机的,会使结果产生偏差？

更新1:感谢这里的人们指出它需要rand($ i,51)才能正确地进行随机播放.

Answer 1

看到:
Naïveté的危险(编码恐怖)

让我们看一下你的三张牌组.使用3张牌组,在洗牌后,牌组只有6种可能的订单: 123, 132, 213, 231, 312, 321.

使用第一个算法,代码有27种可能的路径(结果),具体取决于rand()不同点的函数结果.这些结果中的每一个都是同等可能的(无偏见的).这些结果中的每一个都将映射到上面6个可能的"真实"混洗结果列表中的相同单个结果.我们现在有27个项目和6个桶来装入它们.由于27个不能被6整除,因此这6个组合中的一些必须过度表示.

使用第二种算法,有6种可能的结果可以准确地映射到6种可能的"真实"混洗结果,并且它们都应该随时间平均表示.

这很重要,因为在第一个算法中过度表示的桶不是随机的.为偏差选择的桶是可重复且可预测的. 因此,如果你正在建立一个在线扑克游戏并使用第一种算法,那么黑客可能会发现你使用了天真的排序,并且根据这项工作,某些牌组安排比其他牌更容易发生.然后他们可以相应地下注.他们会失去一些,但他们会赢得比失败更多的东西,并迅速让你破产.

Answer 2

这是这些替换的完整概率树.

让我们假设您从序列123开始,然后我们将枚举所有各种方法来生成随机代码的相关代码.

123
 +- 123          - swap 1 and 1 (these are positions,
 |   +- 213      - swap 2 and 1  not numbers)
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 123      - swap 2 and 2
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 132      - swap 2 and 3
 |       +- 231  - swap 3 and 1
 |       +- 123  - swap 3 and 2
 |       +- 132  - swap 3 and 3
 +- 213          - swap 1 and 2
 |   +- 123      - swap 2 and 1
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 213      - swap 2 and 2
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 231      - swap 2 and 3
 |       +- 132  - swap 3 and 1
 |       +- 213  - swap 3 and 2
 |       +- 231  - swap 3 and 3
 +- 321          - swap 1 and 3
     +- 231      - swap 2 and 1
     |   +- 132  - swap 3 and 1
     |   +- 213  - swap 3 and 2
     |   +- 231  - swap 3 and 3
     +- 321      - swap 2 and 2
     |   +- 123  - swap 3 and 1
     |   +- 312  - swap 3 and 2
     |   +- 321  - swap 3 and 3
     +- 312      - swap 2 and 3
         +- 213  - swap 3 and 1
         +- 321  - swap 3 and 2
         +- 312  - swap 3 and 3

现在,第四列数字,即交换信息之前的数字,包含最终结果,包含27种可能的结果.

让我们计算每个模式出现的次数:

123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
     27 times total

如果运行随机交换无限次的代码,则模式132,213和231将比模式123,312和321更频繁地发生,这仅仅是因为代码交换的方式使得更可能发生.

当然,现在你可以说,如果你运行代码30次(27 + 3),你最终可能会出现5次所有模式,但在处理统计数据时你必须看看长期趋势.

这是C#代码,它探索了每种可能模式之一的随机性:

class Program
{
    static void Main(string[] args)
    {
        Dictionary<String, Int32> occurances = new Dictionary<String, Int32>
        {
            { "123", 0 },
            { "132", 0 },
            { "213", 0 },
            { "231", 0 },
            { "312", 0 },
            { "321", 0 }
        };

        Char[] digits = new[] { '1', '2', '3' };
        Func<Char[], Int32, Int32, Char[]> swap = delegate(Char[] input, Int32 pos1, Int32 pos2)
        {
            Char[] result = new Char[] { input[0], input[1], input[2] };
            Char temp = result[pos1];
            result[pos1] = result[pos2];
            result[pos2] = temp;
            return result;
        };

        for (Int32 index1 = 0; index1 < 3; index1++)
        {
            Char[] level1 = swap(digits, 0, index1);
            for (Int32 index2 = 0; index2 < 3; index2++)
            {
                Char[] level2 = swap(level1, 1, index2);
                for (Int32 index3 = 0; index3 < 3; index3++)
                {
                    Char[] level3 = swap(level2, 2, index3);
                    String output = new String(level3);
                    occurances[output]++;
                }
            }
        }

        foreach (var kvp in occurances)
        {
            Console.Out.WriteLine(kvp.Key + ": " + kvp.Value);
        }
    }
}

这输出:

123: 4
132: 5
213: 5
231: 5
312: 4
321: 4

因此,虽然这个答案确实可以计算,但这不是一个纯粹的数学答案,你只需要评估随机函数可以采用的所有可能方式,并查看最终输出.

Answer 3

从其他的答案您的意见,似乎你正在寻找不只是为何分布不解释的均匀分布(为其整除答案很简单),而且为什么它是一种"直观"的解释实际上远非制服.

这是看待它的一种方式.假设您从初始数组开始[1, 2, ..., n](其中n可能是3或52或其他)并应用这两种算法中的一种.如果所有排列均匀可能,则1保持在第一位置的概率应该是1/n.实际上,在第二个(正确的)算法中 1/n,当1并且仅在第一次没有交换时,它保持在其位置,即iff初始调用rand(0,n-1)返回0.
但是,在第一个(错误的)算法中,1只有在第一次或任何其他时间都没有交换时仍然保持不变- 即,只有当第一次返回0且其他s 都没有返回0时,其概率为(1/n)*(1-1)/n)^(n-1)≈1/(ne)≈0.37/ n,而不是1/n.randrand

这就是"直观"的解释:在你的第一个算法中,早期的项目比后来的项目更有可能被替换掉,所以你得到的排列倾向于早期项目不在原始位置的模式.

(它比这更微妙,例如1可以换成后来的位置,并且最终通过一系列复杂的掉期交换回来,但这些概率相对不太重要.)

Answer 4

我见过这个效果的最佳解释来自Jeff Atwood的CodingHorror博客(Naïveté 的危险).

使用此代码模拟3张牌随机随机播放...

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

...你得到这个发行版.

随机码(上图)导致3 ^ 3(27)个可能的卡组合.但是数学告诉我们真的只有3个!或3张牌组的6种可能组合.因此,一些组合过度代表.

你需要使用Fisher-Yates shuffle来正确(随机)洗牌.