<antirez>

antirez 6145 days ago. 20437 views.
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]}"
    }

Originally published on oldblog.antirez.com on 19 January 2010.

2 comments from the original post

brufus 9 Jun 2010
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!!!
blog comments powered by Disqus
: