[p2p-hackers] zipf's law

[John Casey]

On 6/17/05, "Hal Finney" <hal at finney.org> wrote:
> John Casey writes:
> > I was wondering if any one might help explain what is the best way to
> > generate random variables that are distributed according to a zipf
> > distribution with a slope of -1 and an output range of 1 to 30.
> 
> Maybe I'm misunderstanding...
> 
> The standard method for generating random values according to any given
> distribution is to generate a uniform random value and map it to the
> desired distribution.
> 
> In this case, if you want the 30 output values to have proportions
> 1, 1/2, 1/3, 1/4, ... 1/30, you would first sum these values.  Let
> S = 1 + 1/2 + 1/3 + 1/4 + ... + 1/30.  Then generate a uniform random
> value x in the range [0,S].  Then map it to your 30 bins by testing
> it against the ranges [0,1], [1, 1+1/2], [1+1/2, 1+1/2+1/3], and so on.
> The bin number is then your output variable.
> 
> Sorry about providing the obvious if you already knew this!

Thanks Hal I have just tried the binning technique but it doesn't seem
to give very good results. On sorting the random numbers the
distribution still seems to be very skewed which I am guessing is due
to the integer nature of the binning process.

http://www3.it.deakin.edu.au/~jacasey/bin-transform.gif

I might go back to my older idea of using cern's zipf random generator
save all the variables and then normalize them all by the largest
number generated into the range [0,1]

I have attached inline the java code that I used to generate that
graph. Are there any obvious or not so obvious errors ??

public class zipf3
{
		public static double harmonic(int N, int exponent) {
			
			double sum = 0.0;
			for (int i = 1; i <= N; i++)
			     sum += 1.0 / Math.pow(i,exponent);
			return sum;
		}
	
       public static void main(String[] args)
       {
		      double sum = harmonic(100,1);
		  
			  for(int i=0;i<10000;i++)
			  {
			  	double tmp=Math.random()*sum;			
				
				double range=0;
				for(int j=1;j<101;j++)
				{
					double upper=harmonic(j,1);
					
					if((tmp>=range) && (tmp<=upper))
					{
						System.out.println(j);
						break;
					}
					else
					{
						range=upper;
					}
					
				}
			  }
       }
}