概率相等范围内的随机数

本文关键字：随机数 范围内 概率 | 更新日期: 2023-09-27 18:31:13

这可能比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#，我只是使用它作为一个例子。

概率相等范围内的随机数

我注意到没有人真正回答你帖子中的肉问题：

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

如何确保范围内每个数字都有相等的发生概率？

对，所以你只是抛弃导致不平衡的值。例如，假设您有一个可以在{ 0, 1, 2, 3, 4 }上产生均匀分布的RNG，并且您想使用它来产生{ 0, 1 }上的均匀分布。朴素的实现是：从{0, 1, 2, 3, 4}中抽取，然后返回值% 2;然而，这显然会产生一个有偏见的样本。这是因为，正如您所注意到的，5（项目数）不能被 2 整除。因此，相反，抛出任何产生值的抽奖 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中的当前实现不一致。文档指出抽奖是统一的，但代码表明它不是。然而，这并不能否定这是一个可解决的问题，我的方法是一种解决它的方法。

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

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

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

另外，由于评论中提到了它，我将补充：如果您想要更强大的功能，请查找加密PRNG。 Mersenne Twister从我所看到的情况来看特别好（快速，计算成本低，周期长），并且它具有C#中的开源实现。

测试程序： 

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     10012110      99918

结论：

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

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

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

显然，可能的双精度值集是有限的，并且，正如您所注意到的，它可能不是 .Next(x, y) 的可能返回值集大小的倍数。 因此，假设一组输入值是均匀分布的，某些输出值的发生概率会稍大一些。

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

相关文章：