随机数发生器产生幂律分布？

Question

我正在为C++命令行Linux应用程序编写一些测试.我想生成一堆具有幂律/长尾分布的整数.意思是,我经常得到一些数字,但大多数都是相对不频繁的.

理想情况下,我可以使用rand()或其中一个stdlib随机函数.如果没有,一个易于使用的C/C++块将是伟大的.

谢谢!

Answer 1

Wolfram MathWorld的这个页面讨论了如何从均匀分布中获得幂律分布(这是大多数随机数生成器提供的).

简短的回答(在上面的链接推导):

x = [(x1^(n+1) - x0^(n+1))*y + x0^(n+1)]^(1/(n+1))

其中y是一个均匀变量,n是分布函数,x0和x1定义分布范围,x是幂律分布变量.

Answer 2

如果您知道所需的分布(称为概率分布函数(PDF))并将其正确归一化,则可以将其集成以获得累积分布函数(CDF),然后反转CDF(如果可能)以获得转换需要从均匀[0,1]分布到你想要的.

因此,您首先要定义所需的分布.

P = F(x)

(对于[0,1]中的x)然后积分给出

C(y) = \int_0^y F(x) dx

如果这可以倒置你得到

y = F^{-1}(C)

所以在最后一行调用rand()并插入结果C并使用y.

这个结果被称为采样的基本定理.由于归一化要求和分析反转功能的需要,这是一个麻烦.

或者,您可以使用拒绝技术:在所需范围内均匀地抛出一个数字,然后抛出另一个数字并与第一次投掷所在位置的PDF进行比较.如果第二次投掷超过PDF则拒绝.对于具有大量低概率区域的PDF来说效率低下,例如那些长尾的...

中间方法涉及通过强力反转CDF:将CDF存储为查找表,并执行反向查找以获得结果.

这里真正的问题是简单的x^-n分布在范围内是不可规范化的[0,1],所以你不能使用抽样定理.尝试(x + 1)^ - n而不是......

Answer 3

我只是想进行一个实际的模拟，作为对（正确地）接受的答案的补充。尽管在 R 中，代码非常简单，以至于成为（伪）伪代码。

公认答案中的Wolfram MathWorld 公式与其他可能更常见的方程之间的一个微小差异是幂律指数 n（通常表示为 alpha）不带有明确的负号。所以选择的 alpha 值必须是负数，通常在 2 到 3 之间。

x0并x1代表分布的下限和上限。

所以这里是：

set.seed(0)
x1 = 5           # Maximum value
x0 = 0.1         # It can't be zero; otherwise X^0^(neg) is 1/0.
alpha = -2.5     # It has to be negative.
y = runif(1e7)   # Number of samples
x  = ((x1^(alpha+1) - x0^(alpha+1))*y + x0^(alpha+1))^(1/(alpha+1))
plot(density(x), ylab="log density x", col=2)

或以对数刻度绘制：

plot(density(x), log="xy", ylab="log density x", col=2)

以下是数据摘要：

> summary(x)
   Min.   1st Qu.  Median    Mean   3rd Qu.    Max. 
  0.1000  0.1208  0.1584    0.2590  0.2511   4.9388