范围内的随机数,概率相等

Question

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

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

我知道有Random.Next(int,int)方法,它返回第一个整数和最后一个之间的数字(最后一个是独占的).

Random.Next() [without overloads]将返回介于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#,我只是以它为例.

Answer 1

我注意到在你的帖子中没有人真正回答过这个问题:

例如,范围是10,因此2147483646不能完全被10整除,因此值1-6具有稍高的发生概率(因为2147483646%10 = 6).这当然是假设Random.Next()[without overloads]中的每个值都以相等的概率返回0到2147483646之间的值.

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

是的,所以你只是抛出导致不平衡的价值.例如,假设您有一个可以产生均匀分布的RNG { 0, 1, 2, 3, 4 },并且您希望使用它来产生均匀分布{ 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中的当前实现不一致.文档说明抽奖是统一的,但代码表明它不是.然而,这并不否定这是一个可溶性问题的事实,我的方法是解决它的一种方法.

Answer 2

正如您所期望的那样,内置于RNG中的C#是均匀分布的.根据您指定的范围,每个数字都有相同的可能性Next(min, max).

您可以自己测试一下(我有),比如说采集1M样本并存储每个数字实际出现的次数.如果你绘制它,你会得到一条几乎是平线的曲线.

还要注意,具有相同似然性的每个数字并不意味着每个数字将出现相同的次数.如果您正在查看1到10之间的随机数,则在100次迭代中,对于每个数字,它将不是10次出现的均匀分布.有些数字可能会出现8次,有些则可能出现12次或13次.但是,随着迭代次数的增加,这往往会有所偏差.

此外,由于在评论中提到,我将补充:如果你想要更强大的东西,请查找加密PRNG.Mersenne Twister从我所看到的特别好(快速,便宜到计算,时间很长)并且它在C#中具有开源实现.

Answer 3

测试程序:

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

结论:

以相等的概率返回每个值.