c++ - 均匀分布的随机数生成

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;

这里有什么问题？我认为一个简单的 top = 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 的概率出现，只要我们不是那么倒霉以至于循环永远不会终止。

关于您的更新:

I think a simple top = RAND_MAX / n * n would do.

如果RAND_MAX是排他性界限(比实际最大值多一个)，那么那将是正确的。既然是包容性的界限，我们需要加一个来得到排他性的界限；并且由于以下逻辑与 > 进行比较针对包含边界，然后在计算后再次减去一个:

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

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

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