验证Knuth洗牌算法的无偏性

Question

我正在实现一个Knuth shuffle，用于我正在开发的C++项目中。我试图从我的洗牌中获得最不偏倚的结果（我对（伪）随机数生成不是专家）。我只想确保这是最不偏倚的洗牌实现。 draw_t 是一个字节类型（typedef 为 unsigned char）。 items 是列表中项目的数量。下面是random::get( draw_t max )的代码。

for( draw_t pull_index = (items - 1); pull_index > 1; pull_index-- )
{
    draw_t push_index = random::get( pull_index );

    draw_t push_item = this->_list[push_index];
    draw_t pull_item = this->_list[pull_index];

    this->_list[push_index] = pull_item;
    this->_list[pull_index] = push_item;
}

我正在使用的随机函数已被修改以消除模数偏差。 RAND_MAX 被赋值给 random::_internal_max。

draw_t random::get( draw_t max )
{
    if( random::_is_seeded == false )
    {
        random::seed( );
    }

    int rand_value = random::_internal_max;
    int max_rand_value = random::_internal_max - ( max - ( random::_internal_max % max ) );

    do
    {
        rand_value = ::rand( );
    } while( rand_value >= max_rand_value );

    return static_cast< draw_t >( rand_value % max );
}

- Adam Maras

---

附注：C++ STL 包含算法 random_shuffle。以防你不知道。 - rlbond

我不知道STL的实现。我还没有花时间学习STL（我只是一个Win32 / .NET开发人员），而且我希望在这个项目中有最小的学习曲线（时间限制），但我会考虑到这一点的。 - Adam Maras

你的随机数生成器可以有多少不同的状态？如果小于52！，那么就会有一些洗牌是无法产生的（请注意，2^32甚至2^64都比52！小得多！）。如果你想获得无偏差的结果，你需要使用一个拥有比52！更多状态的RNG：也许可以尝试Mersenne Twister。 - user97370

C++ STL现在也包括了非常棒的RNGs，正好可以用于这个目的。 - Mooing Duck

Answer 1

如果我理解正确，你的random::get (max)并没有包括max。

这一行：

draw_t push_index = random::get( pull_index );

然后会产生一个“经典”的一位错误，因为您的pull_index和push_index错误地永远不能相同。这会产生一个微妙的偏差，即您永远无法在洗牌之前将项目放置在原来的位置。在极端情况下，这种“洗牌”下的两个项目列表总是反转的。

- Svante

Answer 2

作为黑盒测试，您可以选择一些相对较小的数组大小，在其上执行大量洗牌操作，计算每个排列观察到的次数，然后执行Pearson's Chi-square检验以确定结果是否均匀地分布在排列空间中。

另一方面，Knuth洗牌，也称为Fisher-Yates洗牌，只要用于索引的随机数生成器是无偏的，就被证明是无偏的。

- dsimcha

---

我会研究排列计数；据我所了解，Pearson卡方检验在数学方面似乎有些超出我的能力范围，但我会继续研究它。 - Adam Maras

你并不需要使用卡方检验来测试洗牌是否存在偏差。像标准差这样简单的方法也可以进行相同类型的测试（随着洗牌次数的增加，你应该会看到标准差趋近于零）。 - Greg Beech

@Adam：我认为使用卡方检验会很容易，因为我之前写过一个执行Pearson's Chi-square的库函数。虽然我已经忘记了它是如何工作的，但我仍然记得如何使用它。唯一的问题是它是用D语言编写的，而不是C++。应该有C++库可以做到这一点，但如果你没有方便地安装好的库（等等），那么可能会有些过度。 - dsimcha

@dsimcha：你愿意分享你的卡方分布D库吗？我相信我可以很容易地将其移植到C++中（仅限个人使用）。你可以通过firstname dot lastname at gmail联系我。 - Adam Maras

但实际上它是一个完整的统计库。实际的卡方函数非常简短，但你需要移植或找到C++等效的许多低级功能，比如不完全伽玛函数。这可能有点过头了，但我想与您分享，以防万一。或者，您可以让您的C++代码打印出这些值，并将它们粘贴到像R这样的统计软件包中，甚至只需用肉眼观察而不进行正式测试，如果这个测试不必完全自动化的话。 - dsimcha

Answer 3

请看Jeff Atwood的这篇文章：

洗牌算法
http://www.codinghorror.com/blog/archives/001008.html

另外还有：

天真的危险
http://www.codinghorror.com/blog/archives/001015.html

- Robert Harvey

---

我知道伪随机数生成器的一般限制；你认为我应该考虑转向Eric Lippert的算法（为每个索引分配一个随机浮点值并排序），还是加强我的随机数生成器，也许通过使用密码学API或实现更好的PRNG，如Mersenne Twister或Blum Blum Shub？ - Adam Maras

其实，我错过了最好的帖子。请看：天真无邪的危险--http://www.codinghorror.com/blog/archives/001015.html - Robert Harvey

Answer 4

Knuth洗牌本身是可证明无偏的：存在一系列操作，可以产生每个可能的洗牌结果。然而，你的PRNG可能没有足够的状态位来表示每个可能的洗牌结果，因此真正的问题在于你的PRNG是否“足够随机”，以及你的种子策略是否足够安全。

只有你自己能够决定这一点，因为它取决于洗牌结果不够随机所带来的后果。例如，如果你正在处理真实货币，我建议切换到使用密码学安全的PRNG并改进你的种子策略。虽然大多数内置PRNG生成良好的随机性，但它们也很容易被逆向工程，而调用不带参数的seed()方法通常会基于当前时间进行种子初始化，这样很容易被预测。

- Nick Johnson

Answer 5

#include <cstdlib> // srand() && rand()

/** Shufle the first 'dim' values in array 'V[]'.
    - Implements the Fisher–Yates_shuffle.
    - Uses the standard function 'rand()' for randomness.
    - Initialices the random sequence using 'seed'.
    - Uses 'dim' swaps.
    \see https://dev59.com/uUrSa4cB1Zd3GeqPUCo8
    \see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
*/
template <class T>
void Fisher_Yates_shuffle( T* V, unsigned dim , unsigned seed ) {
    srand(seed);
    T temp;
    unsigned i,iPP;

    i   = dim-1;
    iPP = dim;
    while ( i>0 ) {
        unsigned j = rand() % iPP;
        if ( i!=j ) { // swap
            temp = V[i]; V[i] = V[j]; V[j] = temp;
        }
        iPP = i;
        --i;
    }
/*
    This implementation depends on the randomness of the random number
    generator used ['rand()' in this case].
*/
}

- Adolfo