ProbCraft

Appearance

抓阄与洗牌 ​

“抓阄”是一种古老的随机抽取方法，它的原理是将预先做好记号的纸卷团或折叠后，放入一个容器中，然后由抽签者从中抽取一张纸卷，上面的记号就是抽中的结果。抓阄是一种公平的随机抽取方法，因为每个纸卷的概率是相等的，所以每个结果的概率也是相等的。比如我们抓取一个有3个纸卷的容器，每个纸卷上分别写有“中奖”、“无”、“无”，那么抽到“中奖”的概率就是1/3。

假设有三个人依次抽取，每次抽取后放回，那么每个人抽到“中奖”的概率都是1/3，但根据前文结果可知，放回式抓阄有可能出现多个中奖者，同时也可能出现没人中奖的情况。

计算两种情况的概率都不困难，命题 “3个人都未中奖的概率” = (1−1/3)3(1-1/3)^3 = 8/27 ≈ 29.63%，而“至少有一个人中奖的概率” = 1 - 8/27 = 19/27 ≈ 70.37%。“至少两个人中奖的概率” = 1−(1−1/3)3−3×1/3×(1−1/3)21 - (1-1/3)^3 - 3 \times 1/3 \times (1-1/3)^2 = 7/27 ≈ 25.93%。

其中 (1−1/3)3(1-1/3)^3 是三个人都未中奖的概率，3×1/3×(1−1/3)23 \times 1/3 \times (1-1/3)^2 是恰好两个人中奖的概率，这里的3是指从3个人中选出2个人的组合数。

不难看出放回式抓阄，并不能满足我们抓阄的初衷：从三个人中公平随机选出一个人。所以我们一般采用不放回式抓阄，即抽取后不放回，这种情况下，每个人抽到“中奖”的概率都是1/3，并且能保证只有一个人中奖，同时也不会出现没人中奖的情况，也就是做到公平随机选出一个人。

可能有人觉得这不对，如果第一个人就抽到了“中奖”，那后面的人抽到的概率就变为0了，就不是1/3了，这还公平么？还有人认为，先抽有优势，中奖的概率更大，真的是这样的么？我们不妨计算一下每个位置的中奖概率：

  • 第一个人中奖的概率 = 1/3
  • 第二个人中奖的概率 = 第一个人不中奖概率 × 第二个人中奖概率 = 2/3 × 1/2 = 1/3
  • 第三个人中奖的概率 = 第一个人不中奖概率 × 第二个人不中奖概率 × 第三个人中奖概率 = 2/3 × 1/2 × 1/1 = 1/3

可以看到，每个位置的中奖概率都是1/3，所以不放回式抓阄是一种公平的随机抽取方法。当然在第一个人抽中的条件下，的确后面的人就不用再抽了，他们中奖的概率因为第一个人抽中的条件已经变为0了，但这并不影响不放回式抓阄的公平性。

TIP

ProbCraft中有一个“翻牌”工具，就是一个抓阄工具，可以公平地在多个选项中随机选出多个结果，你可以试一试。

随机音乐播放器 ​

在音乐播放器中，我们经常会看到“随机播放”这个功能，比如音乐列表中有10首歌，我们可以选择“随机播放”来播放这10首歌，每首歌的播放顺序都是随机的，这样可以让我们在听歌的过程中不会感到单调。

如果让我们来写这个歌曲随机的算法，我们可能会想到，可以生成一个0-9的随机数，然后根据这个随机数来选择播放哪首歌，这样就可以实现随机播放了。但是这种方法有一个问题，就是可能会出现重复播放的情况，比如第一首歌播放完后，下一首歌又是第一首歌，这样就会让我们感到很不舒服。

这就是我们前文提到的随机抽样存在的问题，每首歌的播放概率是1/10，则播放完10首歌后，每首歌都有 (1−110)10\left(1-\frac{1}{10}\right)^{10} ≈ 34.87% 的概率没有被播放过。

TIP

《乔布斯传》提到，iPod 和 iTunes 早期是采用真随机的，结果经常接到用户投诉说他们的随机播放有问题，经常开了随机却还在顺序播放，甚至会有重复的歌曲。为此，苹果曾专门在官网辟谣：真正的数学随机就是这样的啊！可惜这并没能平息质疑和投诉，无奈之下，苹果干预了随机算法，投诉从此销声匿迹。

引自：知乎用户迷咖的回答

为了解决这个问题，我们可以采用一种更加复合符合人类直觉的算法，比如 Fisher-Yates 洗牌算法，它的原理是：从数组中随机选取一个元素，然后将它与数组的最后一个元素交换位置，然后再从剩下的元素中随机选取一个元素，将它与数组的倒数第二个元素交换位置，以此类推，直到所有元素都被选取过一次。这样就可以保证每首歌都只会被播放一次，而且每首歌的播放顺序都是随机的。

下面是 Fisher-Yates 洗牌算法的javascript代码实现：

javascript
function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

看不懂代码并没有关系，我制作了一个洗牌演示：

A
B
C
D
E
F
G
H
剩余交换 8 次

当你尝试洗牌时，牌序会被打乱，每次洗牌的结果都是随机的，如果你尝试一步一步执行交换，就可以看到洗牌的交换过程。

TIP

有时候点击分步执行，并未出现交换，这是因为随机数生成器生成的随机数和目标下标相同，导致没有交换，这是正常现象。

但说实话，这个看起来非常简单的洗牌算法，究竟能否保证每首歌等概率出现在队列的任意位置上，我心里是没数的。抱着质疑求证的态度，我写了一个简单的模拟程序，来验证 Fisher-Yates 洗牌算法的效果究竟如何。

A出现在每个位置的次数和概率:

位置12345678
次数00000000
概率0.00%0.00%0.00%0.00%0.00%0.00%0.00%0.00%

我们通过模拟测试发现，Fisher-Yates 洗牌算法效果非常好，一首歌出现在任意位置的概率都接近理论概率 1/8 ≈ 12.5%，这说明 Fisher-Yates 洗牌算法是一种非常有效的洗牌算法。

数学证明 ​

Fisher-Yates 洗牌算法的随机性数学证明如下：

假设有n个元素，每个元素被选中的概率都是都是1/n，一个元素m被放入第i个位置的概率P = 前i-1个位置选择元素时没有选中m的概率 x 第i个位置选中m的概率，即：P=n−1n×n−2n−1×...×n−i+1n−i+2×1n−i+1=1nP = \frac{n-1}{n} \times \frac{n-2}{n-1} \times ... \times \frac{n-i+1}{n-i+2} \times \frac{1}{n-i+1} = \frac{1}{n}。

洗牌算法是一种非常常用的伪随机算法，出了前文提到的音乐随机播放，还有各种牌类游戏、麻将游戏的洗牌机制都能用到。