Pseudo Random Number Generator with power law (long tail-alike) distribution

Tuesday, 19 January 10
Today I needed a PRNG with a bised distribution, specifically following the Power Law distribution in order to simulate the "long tail" often seen in things like social networks data, search, and so forth.

I was not able to find ready to use code, but just a few formulas, so I wrote one in Ruby (I'm going to port this to C for Redis).

Maybe this will be useful to somebody else: 

# Power law (log tail) distribution
# Copyright(C) 2010 Salvatore Sanfilippo
# this code is under the public domain

# min and max are both inclusive
# n is the distribution power: the higher, the more biased
def powerlaw(min,max,n)
    max += 1
    pl = ((max**(n+1) - min**(n+1))*rand() + min**(n+1))**(1.0/(n+1))
    (max-1-pl.to_i)+min
end

freq = {}
100000.times {
    n = powerlaw(0,100,2).to_i
    freq[n] = 0 if !freq[n]
    freq[n] += 1
}
(0..100).each{|x|
    puts "#{x} => #{freq[x]}"
}
18787 views*
Posted at 17:02:24 | permalink | 2 comments | print
Do you like this article?
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.

Note: you'll not see this box again if you are a usual reader.

Comments

1
brufus writes:
09 Jun 10, 16:56:10
Hi,

I was actually looking for some "random number generator with power law distribution" and i found you! However, I'm programming in C, I've seen that you're pretending to do it in C as well? Have you done it?
I was trying to program it in C by myself, however I'm not familiar with Ruby...I've guessed that ** is the exponent function, isn't it? However, I cannot figured out what do you do with, (max-1-pl.to_i)+min ...Could you help me?

Thank you!!!
2
cheap Hugo Boss shoes writes:
23 Dec 10, 03:17:55
More please, this information helped me consider a few more things, keep up the good work. http://www.sunglassescool.com/hugo-boss-shoes.html...
comments closed