均匀分布的随机数生成

Question

为什么这段代码会生成均匀分布的数字？我理解它有些困难.有人能解释一下吗 谢谢.

int RandomUniform(int n) {  
  int top = ((((RAND_MAX - n) + 1) / n) * n - 1) + n;  
  int r;  
  do {  
    r = rand();  
  } while (r > top);  
  return (r % n);  
}

更新:我明白为什么rand()%n不会给你一个均匀分布的序列.我的问题是为什么

top = ((((RAND_MAX - n) + 1) / n) * n - 1) + n;

这里有什么问题？我认为一个简单的顶部= RAND_MAX/n*n就行了.

Answer 1

该函数假定rand()均匀分布; 这是否是一个有效的假设取决于实施rand().

给定一个统一rand(),我们可以[0,n)通过计算得到该范围内的随机数rand()%n.但是,一般来说,这不会很均匀.例如,假设n是3并且RAND_MAX是7:

rand()      0 1 2 3 4 5 6 7
rand() % n  0 1 2 0 1 2 0 1

我们可以看到0和1的概率为3/8,而2只出现2/8的概率:分布不均匀.

您的代码会丢弃任何rand()大于或等于n它可以生成的最大倍数的值.现在每个值的概率相等:

rand()      0 1 2 3 4 5 6 7
rand() % n  0 1 2 0 1 2 X X

所以0,1和2都有1/3的概率,只要我们不那么不幸,循环永远不会终止.

关于你的更新:

我认为一个简单的顶部= RAND_MAX/n*n就行了.

如果RAND_MAX是独占界限(比实际最大值多一个),那么这是正确的.由于它是一个包容性的界限,我们需要添加一个来获得独占界限; 并且由于以下逻辑与>包含边界进行比较,因此在计算后再次减去1:

int top = ((RAND_MAX + 1) / n) * n - 1;

但是,如果RAND_MAX等于INT_MAX,那么计算就会溢出; 为避免这种情况,n在计算开始时减去,并在结尾处再次添加:

int top = (((RAND_MAX - n) + 1) / n) * n - 1 + n;

Answer 2

根本问题是:假设您有一个随机数生成器my_rand(),它生成0到6(含)的值,并且您希望生成0到5之间的值,包括0和5; 如果你运行你的发电机并返回my_rand() % 6,你将无法获得统一的分配.当my_rand()返回0时,你得到0; 当它返回1时,你得到1等,直到my_rand()返回6; 在这种情况下my_rand() % 6是0.总的来说,my_rand() % 6返回0的频率是任何其他值的两倍.解决这个问题的方法是不要使用大于5的值,也就是说,而不是my_rand() % 5你写一个循环并丢弃my_rand()那些太大的值.这基本上就是问题中的代码所做的事情.我没有追踪它,但通常的实现是计算其中的最大倍数n小于或等于RAND_MAX,并且每当rand()返回大于该倍数的值时,返回并获得新值.