生成 Zipf 分发的随机数

Question

Zipf 概率分布 通常用于对文件大小分布进行建模或P2P 系统中项目的项目访问分布。例如“Web 缓存和 Zip 之类的分布证据和含义”，但两者都不是Boost 或 GSL（Gnu 科学库） 提供了使用此分布生成随机数的实现。我还没有找到使用常见搜索引擎的（值得信赖的）实现。

如何使用 U(0,1) 随机生成器（例如 梅森扭曲者？

Answer 1

下面是一个类似 Python Zipf 的分布生成器，适用于参数 alpha >= 0 的 n 项：

import random 
import bisect 
import math 

class ZipfGenerator: 

    def __init__(self, n, alpha): 
        # Calculate Zeta values from 1 to n: 
        tmp = [1. / (math.pow(float(i), alpha)) for i in range(1, n+1)] 
        zeta = reduce(lambda sums, x: sums + [sums[-1] + x], tmp, [0]) 

        # Store the translation map: 
        self.distMap = [x / zeta[-1] for x in zeta] 

    def next(self): 
        # Take a uniform 0-1 pseudo-random value: 
        u = random.random()  

        # Translate the Zipf variable: 
        return bisect.bisect(self.distMap, u) - 1

Answer 2

zipfR 是一个使用 R 实现的免费开源库。VGAM 是另一个也实现 Zipf 的 R 包。

还值得注意的是 Gnu 科学库 有一个 Pareto 分布 它实际上是离散 Zipf 分布的连续模拟。

此外，Zeta 分布 相当于无限N 的 Zipf。 GSL 有一个实现黎曼 zeta 函数 的 >，因此您可以使用它自己构建分布。

Answer 3

numpy.random.zipf 使用以下命令生成 Zipf 样本Python。

Answer 4

最近为 Apache Commons Math 库的下一个版本 (>= 3.6) 开发了一种非常有效的算法来生成 Zipf 分布式随机变量（请参阅代码 此处）。它利用拒绝反转采样，并且也适用于小于 1 的指数。它不需要预先计算 CDF 并将其保存在内存中。此外，生成一个样本的成本是恒定的，不会随着项目数量的增加而增加。

Answer 5

我们正在此帖子中讨论 @stanga 的答案。他的算法有一些很好的优化建议。