主页 / 问题 / 730997
Accepted
Kromster
Asked:2020-10-15 14:11:47 +0000 UTC2020-10-15 14:11:47 +0000 UTC

模除时随机数的分布有多不均匀？

  • 772

在下一个问题中，我们谈到了使用 RNG 和模除法时数字的不均匀分布。文档（ rand ）中提到了相同的内容：

请注意，尽管此模运算不会在跨度中生成均匀分布的随机数（因为在大多数情况下，此运算使较小的数字更有可能发生）。

我们以一个从 0 到 1000 的 RNG 为例，步长为 25：

return 25 * (rand() % 41); // Неравномерное распределение 

return int((40.0 * rand()) / (RAND_MAX + 1.0)) * 25; // Равномерное распределение

等等问题：
- 第一种方法，比第二种方法更不平衡多少？
这种影响如何在实际问题中体现出来？
- 值得担心吗？
- 如果是这样，从什么时候开始？
- 绕过不均匀的选项有哪些（除了上面的例子）？

c++

2 个回答

  1. 第一种方法比第二种方法有多不均衡？

    这些方法的不平衡源于两个来源：

    1. 我们将一个大小的离散范围投影到另一个大小的离散范围上，第一个大小的大小通常不是第二个大小的倍数。在这样的预测中，不可避免地会出现选择某些目标值而不是其他目标值的概率的相同“不均匀性”。在这两个选项中，更有可能的值将在目标范围内以不同的方式分布，但这不是根本区别。

      无论您如何尝试将 7 只鸽子安置在 5 个巢穴中，所有座位选项的不均匀性都是相同的。

      也就是说，从这个角度来看，这两种选择绝对同样不均衡。无论您使用执行这种投影的方法如何旋转，都不会获得任何新的结果——所有的投影都将同样不平衡。

    2. 在第一种情况下，我们从结果的低位中提取“随机性” ，在rand()第二种情况下，从高位中提取“随机性” 。最简单的实现只是受到这样一个事实的困扰，即它们在低位或高位中提供了不均匀或不够“随机”的分布。所以从这个角度来看，在选择如何执行投影时，您应该考虑到您的实现的特点。rand()rand()rand()

      “在码头”中提到带有模块的版本据称“更差”是对这个因素的引用，而不是对上面描述的内容（第 1 点）。然而，这只不过是一种历史好奇心，是程序员民间传说的一个元素，它基于第一个经过深思熟虑的实现rand()，具有非常可预测的低位分布（请参见此处的第一个）。实际上，在不了解特定方法的特性的情况下rand()，无法得出在这方面哪种方法更好的结论。

    您引用的“在码头”这句话专门指第二点，而您的问题似乎专门针对第一点。这些本质上是不同的主题。

    这种影响如何在实际问题中体现出来？
    - 值得担心吗？
    - 如果是这样，从什么时候开始？

    取决于实际任务。很明显，质量rand()不足以完成加密任务。同时，它也绰绰有余，例如为概率数据结构生成随机数，如 SkipList 等。在这种情况下，您根本不需要担心任何事情。

    绕过不均匀性的选项有哪些（除了给出的示例）？

    马上：如上所述，您的“给出的示例”不会以任何方式解决不均匀性。

    由于投影是“固定的”、无状态的：目标范围的相同值总是获得最高的选择概率。这是一个自然的想法，即赋予投影过程本身一种状态，该状态将以某种方式沿着目标范围从调用到调用“移动”投影，即 另外在目标范围内“涂抹”投影不均匀性。

    在最简单的情况下，可以做这样的事情

    // Вместо
return rand() % 41;

// делаем
static unsigned shift = 0;
shift = (shift + 1) % 41;
return (rand() % 41 + shift) % 41;

    但实际上，一个简单的范围扩展rand()（例如，通过连接两个连续调用的结果rand()）将达到几乎相同的“波纹抑制”效果。

    • 3
  2. Best Answer

    对于 RAND_MAX 为 32767 的实现，这可能很明显。例如，如果我们需要获取 0 到 9999 之间的数字，使用

    rand() % 10000

    对于高达 2767 的值，掉出的概率将增加 25%，因为。它们在兰特范围内：

    0..2767, 10000..12767, 20000..22767, 30000..32767

    而对于值 2768..9999 rand 范围：

    2768..9999, 12768..19999, 22768..29999

    如果结果用于选择系列中的中奖彩票，那么我建议购买带有次要号码的彩票。

    相应地，RAND_MAX 越大，除数越小，与模块的方法中的分布越均匀。

    • 1

相关问题