29

这可能比 C# 更与数学相关，但我需要一个 C# 解决方案，所以我把它放在这里。

我的问题是关于随机数生成器的概率，更具体地说，是否以相等的概率返回每个可能的值。

我知道有Random.Next(int, int)方法返回第一个整数和最后一个整数之间的一个数字（最后一个是排他的）。

Random.Next()[无重载] 将返回一个介于 0 和 Int32.MaxValue（即 2147483647）之间的值 - 1，即 2147483646。

如果我想要一个 1 到 10 之间的值，我可以调用Random.Next(1, 11)来执行此操作，但是 1 到 10 之间的每个值是否具有相同的发生概率？

例如，范围是 10，所以 2147483646 不能完全被 10 整除，所以值 1-6 出现的概率略高（因为2147483646 % 10 = 6）。这当然是假设Random.Next()[没有重载] 中的每个值都以相等的概率返回 0 到 2147483646 之间的值。

如何确保一个范围内的每个数字都有相同的出现概率？假设对于彩票类型系统，某些人比其他人拥有更高的概率是不公平的，我并不是说我会为此使用 RNG 中内置的 C#，我只是将其用作示例。

4

4 回答 4

17

我注意到没有人真正回答了您帖子中的重要问题：

例如，范围是 10，因此 2147483646 不能完全被 10 整除，因此值 1-6 出现的概率稍高（因为 2147483646 % 10 = 6）。这当然是假设 Random.Next() [没有重载] 中的每个值都以相等的概率返回 0 到 2147483646 之间的值。

如何确保一个范围内的每个数字都有相同的出现概率？

是的，所以你只需丢弃导致不平衡的值。例如，假设您有一个可以在 上产生均匀分布的 RNG { 0, 1, 2, 3, 4 }，并且您想用它来在 上产生均匀分布{ 0, 1 }。天真的实现是：从中提取{0, 1, 2, 3, 4}然后返回值% 2；然而，这显然会产生有偏差的样本。发生这种情况是因为，正如您所注意到的，5（项目的数量）不能被 2 整除。因此，相反，抛出任何产生 value 的平局4。因此，该算法将是

 draw from { 0, 1, 2, 3, 4 }
 if the value is 4, throw it out
 otherwise, return the value % 2

您可以使用这个基本思想来解决一般问题。

但是，1 到 10 之间的每个值是否具有相同的发生概率？

是的，它确实。来自MSDN：

从一组有限的数字中以相等的概率选择伪随机数。

编辑：显然文档与 .NET 中的当前实现不一致。文档说明抽签是统一的，但代码表明它不是。但是，这并不能否定这是一个可以解决的问题，我的方法是解决它的一种方法。

于 2012-04-16T17:47:28.673 回答
11

如您所料，RNG 中内置的 C# 是一个均匀分布的 C#。给定您为 指定的范围，每个数字都有相同的发生可能性Next(min, max)。

您可以自己测试（我有），例如，采集 1M 个样本并存储每个数字实际出现的次数。如果你绘制它，你会得到一条几乎平坦的曲线。

另请注意，每个数字具有相同的可能性并不意味着每个数字将出现相同的次数。如果您正在查看从 1 到 10 的随机数，在 100 次迭代中，它不会是每个数字出现 10 次的均匀分布。有些数字可能出现 8 次，而另一些数字可能出现 12 或 13 次。然而，随着更多的迭代，这往往会有所平衡。

此外，由于评论中提到了它，我会补充一点：如果你想要更强大的东西，请查找加密 PRNG。Mersenne Twister 在我所见的情况下特别好（速度快、计算成本低、周期长），并且它在 C# 中具有开源实现。

于 2012-04-16T17:37:05.930 回答
9

测试程序：

var a = new int[10];
var r = new Random();
for (int i = 0; i < 1000000; i++) a[r.Next(1, 11) - 1]++;
for (int i = 0; i < a.Length; i++) Console.WriteLine("{0,2}{1,10}", i + 1, a[i]);

输出：

1 99924
 2 100199
 3 100568
 4 100406
 5 100114
 6 99418
 7 99759
 8 99573
 9 100121
10 99918

结论：

每个值都以相等的概率返回。

于 2012-04-16T17:37:22.623 回答
3

Ashes 和 dtb 是不正确的：您怀疑某些数字比其他数字更有可能发生是正确的。

当您调用 时.Next(x, y)，有 y - x 个可能的返回值。.NET 4.0Random类根据的返回值计算返回值NextDouble()（这是稍微简化的描述）。

显然，可能的 double 值的集合是有限的，而且，正如您所注意到的，它可能不是 的可能返回值集合的大小的倍数.Next(x, y)。因此，假设这组输入值是均匀分布的，那么一些输出值出现的概率会稍大一些。

我不知道有多少数字双精度值（即，不包括无穷大和 NaN 值），但它肯定大于 2^32。在您的情况下，如果我们假设 2^32 个值，那么我们必须将 4294967296 个输入映射到 10 个输出。某些值的发生概率会大 429496730 / 429496729，或者大 0.00000023283064397913028110629%。事实上，由于输入状态的数量大于2^32，因此概率差异会更小。

于 2012-04-16T17:56:33.613 回答