9

Im trying to generate random integers with logarithmic distribution. I use the following formula:

idx = Math.floor(Math.log((Math.random() * Math.pow(2.0, max)) + 1.0) / Math.log(2.0));

This works well and produces sequence like this for 1000 iterations (each number represents how many times that index was generated):

[525, 261, 119, 45, 29, 13, 5, 1, 1, 1]

Fiddle

I am now trying to adjust the slope of this distribution so it doesn't drop as quickly and produces something like:

[150, 120, 100, 80, 60, ...]

Blindly playing with coefficients didn't give me what I wanted. Any ideas how to achieve it?

serg
  • 109,619
  • 77
  • 317
  • 330
  • 1
    set every `2.0` in you formula closer to `1.0` e,g. `1.3` – zmii Jun 08 '15 at 22:28
  • @zmii that works well if `max=10`, but if `max=2` it produces even sharper slope: `[830, 170]` vs `[744, 256]` for `2.0` – serg Jun 08 '15 at 22:32
  • I do it like this: [pseudo random numbers with a predefined distribution](http://stackoverflow.com/a/22422035/2521214) – Spektre Jun 09 '15 at 06:26

1 Answers1

6

You mention a logarithmic distribution, but it looks like your code is designed to generate a truncated geometric distribution instead, although it is flawed. There is more than one distribution called a logarithmic distribution and none of them are that common. Please clarify if you really do mean one of them.

You compute floor[log_2 U] where U is uniformly distributed from 1 to (2^max)+1. This has a 1/2^max chance to produce max, but you clamp that to max-1. So, you have a 1/2^max chance to produce 0, 2/2^max chance to produce 1, 4/2^max chance to produce 2, ... up to a 1/2 + 1/2^max chance to produce max-1.

Present in your code, but missing from the description in the question, is that you are flipping the computed index around with 

idx = (max-idx) - 1

After this, your chance to produce 0 is 1/2 + 1/2^max, and your chance to produce a value of k is 1/2^(k+1).

I think it is a mistake to let U be uniform on [1,2^max+1]. Instead, I think you want U to be uniform on [1,2^max]. Then your chance to generate idx=k is 2^(max-k-1)/((2^max)-1). 

idx = Math.floor(Math.log((Math.random()*(Math.pow(2.0, max)-1.0)) + 1.0) / Math.log(2.0));

zmii's comment that you could get a flatter distribution by replacing both 2.0s with a value closer to 1.0 is good. The reason it produced unsatisfactory results for small values of max was that you were sampling uniformly from [1,1.3^max+1] instead of [1,1.3^max]. The extra +1 made a larger difference when max was smaller and the base was smaller. Try the following:

var zmii = 1.3;
idx = Math.floor(Math.log((Math.random()*(Math.pow(zmii, max)-1.0))+1.0) / Math.log(zmii));
Douglas Zare
  • 3,296
  • 1
  • 14
  • 21