按Zipf分布生成随机数

Question

Zipf概率分布常被用于建模P2P系统中文件大小分布或项目访问分布，例如“Web Caching and Zip like Distribution Evidence and Implications”，但是Boost和GSL（Gnu Scientific Library）都没有提供使用该分布生成随机数的实现。我没有在常见搜索引擎上找到（可信赖的）实现。

如何使用U（0,1）随机生成器（例如Mersenne Twister）生成遵循Zipf分布的随机数？

- dmeister

---

最近的一篇论文（Maurizio Naldi，2015）提出了一种近似算法，其中包含一个参数，可以权衡时间和准确性。对于合理范围内的alpha值（0 <= alpha <= 2），误差从未超过0.1％。请参见https://arxiv.org/pdf/1511.01480.pdf。 - Paul Chernoch

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

- stanga

---

非常好的答案。对于Python 3.x，请添加“from functools import *”。 - Daniel Lemire

或者，from functools import reduce - Michael Mior

self.distMap = [math.pow(float(x), alpha) / zeta[-1] for x in zeta] 自我.distMap = [math.pow(float(x), alpha) / zeta[-1] for x in zeta] - xunzhang

Answer 2

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

值得注意的是，Gnu Scientific Library有一个Pareto分布的实现，它实际上是离散Zipf分布的连续模拟。

此外，Zeta分布对于无限大的N等同于Zipf。 GSL有一个Riemann zeta函数的实现，因此您可以使用它来构建分布。

- ire_and_curses

---

对于VGAM加1。它的“dzipf”函数将为您提供每个等级的概率列表，您可以使用它来生成项目访问。 - Mihai Capotă

Answer 3

numpy.random.zipf使用Python生成Zipf样本。

- Yuval F

---

很不幸，它使用黎曼ζ函数，因此只适用于指数大于1的情况，而许多P2P人口最好采用指数小于1的模型。 - Mihai Capotă

Answer 4

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

- otmar

Answer 5

我们正在讨论这个帖子中@stanga的答案。对于他的算法，有一些不错的优化建议。

- hayesti

---

目前这几乎不能算作一个答案。你应该在这里包含你的解决方案，而不仅仅是提到它。 - Peter O.