如何证明洗牌算法的正确性？

cs.stackexchange https://cs.stackexchange.com/questions/2152

题

我有两种方法可以随机顺序制作项目列表，并想确定它们是否同样公平（无偏见）。

我使用的第一种方法是构建整个元素列表，然后在其上进行洗牌（例如Fisher-Yates Shuffle）。第二种方法更多的是一种迭代方法，可以使列表在每个插入时均匀。在伪代码中，插入函数为：

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

我对一个人如何展示这种特殊的改组的公平感兴趣。使用该算法的优点足以使即使略微不公平也可以。为了决定我需要一种评估公平性的方法。

我的第一个想法是，我需要以这种方式计算可能的总排列，而不是最终长度的总排列。但是，我有点损失，但是如何计算该算法产生的排列。我也不能确定这是最好或最简单的方法。

有帮助吗？

解决方案

首先，让我们做两个明显但重要的假设：

  1. _.random_item 可以选择最后一个位置。
  2. _.random_item 使用概率$ frac {1} {n+1} $选择每个位置。

为了证明您的算法的正确性，您需要一个类似于使用的参数 这里:

  • 对于Singleton列表，只有一种可能性，因此可以统一选择。
  • 假设有$ n $元素的列表是统一选择的（从所有排列中），则表明您技术获得的$ n+1 $元素的列表是均匀选择的。

从这里开始，证明是错误的。请参阅下面的正确证明；我在这里留下这一点，因为错误和以下步骤（合理）可能是教育意义的。

得出必须拥有的本地（IE元素）属性是有用的，因为对整个排列的争论是痛苦的。观察到，如果每个元素在每个位置都具有相等的概率，则可以均匀地选择置换

$ qquad displayStyle mathop { forall} limits _ { pi in mathrm {perm} _n} propatorAtorName {pr}（pr}（l = pi）= pi）= frac {1} {1} {n！} {n！} {n！} { quad mathop { forall} limits_ {i = 1}^n m artop { forall} limits_ {j = 1}^n propatatorname {pr}（pr}（l_i = j）= frac {1} {1} {1} {1} {1} {1} { n} qquad（1）$

其中$ n = | l | $，我们假设为了简单起见，我们将$ {1， dots，n } $插入列表中。

现在，让我们看看您的技术在插入$ n+1 $ st元素时的作用。我们必须考虑三个案例（交换后）：

  1. 列表中的元素之一，未交换，即$ i in {1， dots，n } $和$ j in {1， dots，n } $
  2. 列表中的一个元素之一，即交换，即$ i = n+1 $和$ j in {1， dots，n } $
  3. 新元素，即$ i in {1， dots，n+1 } $和$ j = n+1 $

对于每种情况，我们计算元素$ j $的概率为位置$ i $；所有这些都必须是$ frac {1} {n+1} $（由于$（1）$）就足够了。令$ p_n = frac {1} {n} $是旧列表中任何位置的第一个$ n $元素之一（归纳假设）和$ p_s = frac {1} {n+ 1} $由任何位置选择的概率 random_item （假设1，2）。请注意，列表的coice带有$ n $元素并选择交换位置是 独立事件, ，因此联合事件因素的概率，例如

美元$

对于$ i，j in {1， dots，n } $。现在进行计算。

  1. 我们仅考虑旧的$ n $元素。这样的元素$ j $在position $ i $时，仅当它在上次插入之前就在那里，而不是选择$ i $作为交换位置，那就是

    $ quad displayStyle operatorName {pr}（l_i = j）= p_n（1-p_s）= frac {1} {n} {n} {n} cdot frac frac {n} {n+1} = frac {1} n+1} $。

  2. 在这里，我们认为其中一个旧元素换成了最后一个位置。元素$ j $都可以在任何旧位置上都处于

    $ quad displayStyle operatorName {pr}（l_ {n+1} = j）= sum_ {i = 1}^n p_np_s = sum_ {i = 1}^n frac {1}^n frac {1} cdot frac {1} {n+1} = frac {1} {n+1} $。

  3. The new element ends up at position $i$ if and only if $i$ is chosen as swap position, that is

    $ quad displayStyle operatAtorName {pr}（l_i = j）= p_s = frac {1} {n+1} $。

一切都很好，您的插入策略确实确实保留了统一性。通过归纳的力量，证明您的算法会产生均匀分布的排列。

一个警告：如果插入的元素不是成对的不同，此证明会崩溃。可以区分的，因为那时第一个方程式不再有效。但是您的算法仍然有效； 每一个 重复的置换由相同数量的随机执行生成。您可以通过标记重复（即使它们区分），在上述证明并删除标记（实际上）来证明这一点；最后一步将相等尺寸的排列集崩溃为相同。

作为 史蒂文 在评论中正确地评论了上述证据从根本上有缺陷，因为$（1）$不存在；您可以在满足右手但不能左侧的一组排列上构造分布。

因此，我们将必须处理排列的概率，事实证明这并不是那么糟糕。假设 random_item 并且在职位的一开始，概述的电感结构仍在原位，我们从那里继续。 $ {1， dots，k } $已被插入，令$ l^{（k）} $表示列表。

令$ pi' in mathrm {perm} _ {n+1} $ $ {1， dots，n+1 } $的任意排列。可以写 独特 作为

$ qquad displayStyle pi'=（ pi（1）， pi（2）， dots， pi（i-1），n+1， pi（i+1）， dots， pi， pi （n）， pi（i））$

对于某些$ pi in mathrm {perm} _n $和$ i in {1， dots，n+1 } $。通过归纳假设，$ operatatorName {pr}（l^{（n）} = pi）= frac {1} {n！} $。此外， random_item 通过假设选择位置$ i $，带有概率$ frac {1} {n+1} $。由于$ pi $和$ i $的随机选择是（随机）独立的，我们得到了

$ qquad displayStyle operatorName {pr}（l^{（n+1）} = pi'）= propatatorName {pr}（l^{（n）} = pi） （i text {交换}）= frac {1} {（n+1）！} $

我们必须展示。通过归纳的力量，证明您的算法会产生均匀分布的排列。

  1. 例如，分配$ {（1，2，3，4），（2，3，4，1），（3，4，1，2），（4，1，1，2，3） } $概率$ frac {1} {4} $和所有其他$ 0 $。还有一些示例将每个排列分配为非零概率。
许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top