产生幂律分布的随机数生成器？

Question

我正在为 C++ 命令行 Linux 应用程序编写一些测试。我想生成一堆具有幂律/长尾分布的整数。意思是，我非常频繁地收到一些数字，但大多数数字相对较少。

理想情况下，我可以将一些神奇的方程与 rand() 或 stdlib 随机函数之一一起使用。如果没有，一个易于使用的 C/C++ 块会很棒。

谢谢！

Answer 1

在钨MathWorld这页面讨论如何从一个均匀分布的幂律分布（这是大多数随机数生成器提供）。

简单的回答（推导在上面的链接）：

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

其中的ý是均匀的变量，<强>名词与配电，的 X0 和<强> X1 定义的范围内分布，以及 X 是您的幂律分布的变量。

Answer 2

如果你知道你想要的分布（称为概率分布函数（PDF）），并有它正确归一化，就可以整合它来获得累积分布函数（CDF），然后反转CDF（如果可能的话），以获得改造从均匀分布[0,1]需要你想要的。

所以，你通过定义你想要的分布开始。

P = F(x)

（在X [0,1]），那么积分以得到

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

如果这可以被倒你。

y = F^{-1}(C)

于是呼rand()和在最后一行插结果在作为C和使用收率

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

可替换地可以使用抑制技术：在期望的范围内均匀地抛出数，则抛出另一个号码，并在通过您的第一掷indeicated位置比较的PDF。如果第二掷超过PDF拒绝。往往是低效率的用于PDF文件有很多低概率区域，如那些具有长尾巴...

这是中间体的方法涉及通过蛮力反转CDF：您存储CDF为查找表，并做反向查找来获取结果

。

---

这里真正的臭鬼是简单x^-n分布是在范围[0,1]非normalizable，所以可以不使用采样定理。尝试（X + 1）^ - N的，而不是...

Answer 3

我无法评论生成幂律分布所需的数学（其他帖子有建议），但我建议您熟悉 TR1 C++ 标准库随机数工具 <random>. 。这些提供的功能比 std::rand 和 std::srand. 。新系统为发电机、引擎和分配器指定了模块化 API，并提供了一系列预设。

包含的分发预设有：

• uniform_int
• bernoulli_distribution
• geometric_distribution
• poisson_distribution
• binomial_distribution
• uniform_real
• exponential_distribution
• normal_distribution
• gamma_distribution

当您定义幂律分布时，您应该能够将其与现有的发电机和发动机相连接。这本书 C++ 标准库扩展 皮特·贝克尔（Pete Becker）有一个很棒的章节 <random>.

这是一篇文章 关于如何创建其他分布（以 Cauchy、Chi-squared、Student t 和 Snedecor F 为例）

Answer 4

我只是想进行实际模拟作为补充，（理所当然）接受的答案。虽然在R，该代码是简单得是（伪） - 伪代码。

在接受的答案和其它，或许多个钨MathWorld式之间的一个微小的差常见的，方程的事实是，在幂律指数 n（其通常表示为阿尔法）不携带一个明确的负号。这样所选择的α值必须是负的，且通常2和3之间。

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

所以在这里，它是：

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(1e5)   # Number of samples
x = ((x1^(alpha+1) - x0^(alpha+1))*y + x0^(alpha+1))^(1/(alpha+1))
hist(x, prob = T, breaks=40, ylim=c(0,10), xlim=c(0,1.2), border=F, 
col="yellowgreen", main="Power law density")
lines(density(x), col="chocolate", lwd=1)
lines(density(x, adjust=2), lty="dotted", col="darkblue", lwd=2)

或在对数标度绘制：

h = hist(x, prob=T, breaks=40, plot=F)
     plot(h$count, log="xy", type='l', lwd=1, lend=2, 
     xlab="", ylab="", main="Density in logarithmic scale")

下面是数据的总结：

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