Unbalanced random number generator

Question

I have to pick an element from an ascending array. Smaller elements are considered better. So if I pick an element from the beginning of the array it's considered a better choice. But at the same time I don't want the choice to be deterministic and always the same element. So I'm looking for

a random numbers generator that produces numbers in range [0, n], but the smaller the number is, the more chance of it being produced.

This came to my mind:

num = n;
while(/*the more iteration the more chance for smaller numbers*/)
  num = rand()%num;

I was wondering if anyone had a better solution.
I did look at some similar questions but they have details about random number generation generally. I'm looking for a solution to this specific type of random number generation, either an algorithm or a library that provides it.

http://stackoverflow.com/questions/4207545/weighted-random-number-generation — Robert Harvey, Dec 13 '11 at 08:02

vidit · Accepted Answer · 2011-12-13T08:26:24.687

3

Generate a Random number, say x, between [0,n) and then generate another Random floating point number, say y, between [0,1]. Then raise x to the power of y and use floor function, you'll get your number.

int cust(int n)
{
  int x;
  double y, temp;
  x = rand() % n;
  y = (double)rand()/(double)RAND_MAX;
  temp = pow((double) x, y);
  temp = floor(temp);
  return (int)temp;
}

Update: Here are some sample results of calling the above function 10 times, with n = 10, 20 and 30.

2 5 1 0 1 0 1 4 1 0

1 2 4 1 1 2 3 5 17 6

1 19 2 1 2 20 5 1 6 6

edited Dec 13 '11 at 08:26

answered Dec 13 '11 at 07:59

vidit

6,293
3
32
50

Thanks, this might work however, one quetion: How do I generate a number in range [0,1] in c++? `(rand()%n)/(float)n`? – atoMerz Dec 13 '11 at 08:05
Number from 0 to n: (double)rand() / ((double)RAND_MAX * n) – Tomas Dec 13 '11 at 08:19
@AtoMerZ- This will generate Random numbers with high probability. – vidit Dec 13 '11 at 08:30
Thanks again. This seems like a better solution since it only calls rand() once. I'll wait a bit for more answers, if nothing better comes up I'll accept. – atoMerz Dec 13 '11 at 08:40
Note that, regardless of `n`, `n - 1` will occur only once every `RAND_MAX` trials on average, which may be much smaller than you want (`RAND_MAX` is `2**31-1` on my machine, or about 2 billion). You may wish to look into ways of fixing this exceedingly steep drop-off. – Aaron Dufour Dec 13 '11 at 09:36

default locale · Answer 2 · 2011-12-13T08:10:26.633

3

Simple ad-hoc approach that came to my mind is to use standard random generators, but duplicate indices. So in the array:

0, 0, 0, 1, 1, 2, 3

odds are good that smaller element will be taken.
I dont' know exactly what do you need. You can also define your own distribution or maybe use some random number generation libraries. But suggested approach is simple and easy to configure.
UPDATE2: You don't have to generate array explicitly. For array of size 1000, you can generate random number from interval: [0,1000000] and then configure your own distribution of selected values: say, intervals of length 1200 for smaller values (0-500) and intervals of length 800 for larger (500-1000). The main point that this way you can easily configure the probability and you don't have to re-implement random number generator.

edited Dec 13 '11 at 08:10

answered Dec 13 '11 at 07:59

default locale

13,035
13
56
62

What you provide is almost impossible to implement if I have like 1000 numbers in my array. – atoMerz Dec 13 '11 at 08:02
Array was just an example. The main point is to change the interval for smaller values. See Update2. – default locale Dec 13 '11 at 08:11
This is by far the best solution to implement a non-even distribution (especially weighted distribution). It takes minimal computation time and gives complete flexibility. – Neowizard Dec 13 '11 at 08:19
So bigger interval = more chance? – atoMerz Dec 13 '11 at 08:20
+1 Thanks, This is a good solution in general, but I think for this special case, mine is simpler and needs less configuration. – atoMerz Dec 13 '11 at 08:28
Thanks, I just made a suggestion and I have no idea what's more appropriate in this special case. – default locale Dec 13 '11 at 08:42

thiton · Answer 3 · 2011-12-13T08:59:58.840

1

Use an appropriate random distribution, e.g. the rounded results of an exponential distribution. Pick a distribution that fits your needs, document the distribution you used, and find a nice implementation. If code under the GNU Public License is an option, use the excellent GNU Scientific Library (GSL), or try Boost.Random.

edited Dec 13 '11 at 08:59

answered Dec 13 '11 at 07:54

thiton

35,651
4
70
100

I'm pretty sure I **only** understood Boost.Random. What's everything else? – atoMerz Dec 13 '11 at 07:59
@AtoMerZ: I expanded the acronyms. – thiton Dec 13 '11 at 09:01

score 1 · Answer 4 · edited May 23 '17 at 12:20

Two tools will solve many random distribution needs

1) A uniform random number generator which you have

2) and a function which maps uniform values onto your target distribution

I've gotta head to the city now, but I'll make note to write up a couple of examples with a drawing when I get back.

There are some worthwhile methods and ideas discussed in this related question (more about generating a normal pseudo random number)

Unbalanced random number generator

4 Answers4

Two tools will solve many random distribution needs

Linked