验证Knuth shuffle算法尽可能无偏

Question

我正在为我正在研究的C++项目实现一个Knuth shuffle.我试图从我的shuffle获得最无偏见的结果(我不是(伪)随机数生成的专家).我只是想确保这是最无偏见的shuffle实现.

draw_t是字节类型(typedef'd to 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 );
}

Answer 1

那么,你可以做一件黑盒测试就是采用一些相对较小的阵列大小,在其上执行大量的随机播放,计算你观察每个排列的次数,然后执行Pearson的卡方检验以确定是否结果均匀分布在置换空间上.

另一方面,只要指数来自的随机数发生器是无偏的,Knuth shuffle,AKA the Fisher-Yates shuffle,被证明是无偏的.

Answer 2

如果我看到了,你random::get (max)就不包括在内max.

这一行:

draw_t push_index = random::get( pull_index );

然后产生一个"经典的"一个一个错误,因为你pull_index和push_index错误的永远不会是一样的.这产生了一种微妙的偏见,你可以永远不会有一个项目在洗牌之前.在一个极端的例子中,这种"洗牌"下的两项列表总是会颠倒过来.