Generar números aleatorios distribuidos por Zipf

El modelo Zipf probability distribution se usa a menudo para modelar distribuciones de tamaño de archivo o distribuciones de acceso a elementos en elementos de sistemas P2P. p.ej. "Web Caching and Zip like Distribution Evidence and Implications", pero ni Boost ni GSL (Gnu Scientific Library) proporcionan una implementación para generar números aleatorios utilizando esta distribución. No he encontrado una implementación (confiable) que use los motores de búsqueda comunes.Generar números aleatorios distribuidos por Zipf

¿Cómo pueden los números aleatorios que se distribuyen de acuerdo con la distribución de Zipf utilizando un generador aleatorio U (0,1), p. el Mersenne twister?

Fuente

2009-09-02 dmeister

Un documento reciente (Maurizio Naldi, 2015) propone un algoritmo de aproximación con un parámetro que cambia el tiempo y la precisión. Para un rango razonable de alfa (0 <= alpha <= 2) el error nunca excede 0.1%. Consulte https://arxiv.org/pdf/1511.01480.pdf –

zipfR es una biblioteca de fuente abierta y gratuita implementada con R. VGAM es otro paquete R que también implementa Zipf.

También vale la pena señalar que el Gnu Scientific Library tiene un implementation del Pareto distribution que es efectivamente el análogo continuo de la distribución discreta de Zipf.

Además, el Zeta distribution es equivalente a Zipf para infinito N. El GSL tiene un implementation del Riemann zeta function, por lo que podría usarlo para construir la distribución usted mismo.

Fuente

2009-09-02 11:05:45

+1 para VGAM. Su función 'dzipf' le dará una lista de probabilidades para cada rango, que puede usar para generar accesos de elementos. –

numpy.random.zipf genera muestras de Zipf con python.

Fuente

2009-09-02 11:15:47

Desafortunadamente, usa la función zeta de Riemann, por lo que solo toma exponentes superiores a 1, mientras que muchas poblaciones P2P se modelan mejor con exponentes inferiores a 1. –

Aquí es un generador de distribución Python-Zipf como por n elementos con parámetros alpha >= 0:

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

Fuente

2012-01-09 12:48:16 stanga

Excelente respuesta. Para Python 3.x, agregue "from functools import *" –

O tal vez, 'from functools import reduce ' –

¡Exactamente lo que necesitaba, muchas gracias! – hayesti

Estábamos hablando de la respuesta de @stanga en this thread. Hay algunas buenas optimizaciones sugeridas para su algoritmo.

Fuente

2015-06-24 20:20:25 hayesti

Actualmente esto apenas pasa por una respuesta. Debería incluir su solución aquí, no se limite a consultarla. –

Recientemente se desarrolló un algoritmo muy eficiente para generar variables aleatorias distribuidas de Zipf para las próximas versiones (> = 3.6) de la biblioteca Apache Commons Math (vea el código here). Utiliza el muestreo de inversión de rechazo y también funciona para exponentes de menos de 1. No es necesario precalcular el CDF y mantenerlo en la memoria. Además, los costos para generar una muestra son constantes y no aumentan con la cantidad de elementos.

Fuente

2015-10-18 16:38:26 otmar

Generar números aleatorios distribuidos por Zipf

Respuesta

Cuestiones relacionadas