Generate N random numbers within a range with a constant sum

by

In case you want the sample to follow a uniform distribution, the problem reduces to generate N random numbers with sum = 1. This, in turn, is a special case of the Dirichlet distribution but can also be computed more easily using the Exponential distribution. Here is how:

  1. Take a uniform sample v1 … vN with all vi between 0 and 1.
  2. For all i, 1<=i<=N, define ui := -ln vi (notice that ui > 0).
  3. Normalize the ui as pi := ui/s where s is the sum u1+…+uN.

The p1..pN are uniformly distributed (in the simplex of dim N-1) and their sum is 1.

You can now multiply these pi by the constant C you want and translate them by summing some other constant A like this

qi := A + pi*C.

EDIT 3

In order to address some issues raised in the comments, let me add the following:

  • To ensure that the final random sequence falls in the interval [a,b] choose the constants A and C above as A := a and C := b-a, i.e., take qi = a + pi*(b-a). Since pi is in the range (0,1) all qi will be in the range [a,b].
  • One cannot take the (negative) logarithm -ln(vi) if vi happens to be 0 because ln() is not defined at 0. The probability of such an event is extremely low. However, in order to ensure that no error is signaled the generation of v1 … vN in item 1 above must treat any occurrence of 0 in a special way: consider -ln(0) as +infinity (remember: ln(x) -> -infinity when x->0). Thus the sum s = +infinity, which means that pi = 1 and all other pj = 0. Without this convention the sequence (0…1…0) would never be generated (many thanks to @Severin Pappadeux for this interesting remark.)
  • As explained in the 4th comment attached to the question by @Neil Slater it is logically impossible to fulfill all the requirements of the original framing. Therefore any solution must relax the constraints to a proper subset of the original ones. Other comments by @Behrooz seem to confirm that this would suffice in this case.

EDIT 2

One more issue has been raised in the comments:

Why rescaling a uniform sample does not suffice?

In other words, why should I bother to take negative logarithms?

The reason is that if we just rescale then the resulting sample won’t distribute uniformly across the segment (0,1) (or [a,b] for the final sample.)

To visualize this let’s think 2D, i.e., let’s consider the case N=2. A uniform sample (v1,v2) corresponds to a random point in the square with origin (0,0) and corner (1,1). Now, when we normalize such a point dividing it by the sum s=v1+v2 what we are doing is projecting the point onto the diagonal as shown in the picture (keep in mind that the diagonal is the line x + y = 1):

enter image description here

But given that green lines, which are closer to the principal diagonal from (0,0) to (1,1), are longer than orange ones, which are closer to the axes x and y, the projections tend to accumulate more around the center of the projection line (in blue), where the scaled sample lives. This shows that a simple scaling won’t produce a uniform sample on the depicted diagonal. On the other hand, it can be proven mathematically that the negative logarithms do produce the desired uniformity. So, instead of copypasting a mathematical proof I would invite everyone to implement both algorithms and check that the resulting plots behave as this answer describes.

(Note: here is a blog post on this interesting subject with an application to the Oil & Gas industry)

More Related Contents:

  1. Random generation of numbers? [closed]
  2. Generate random numbers using C++11 random library
  3. Create Random Number Sequence with No Repeats
  4. Need for predictable random generator
  5. Generating m distinct random numbers in the range [0..n-1]
  6. How to find number of words in a phrase with spaces removed by checking v. dictionary
  7. How do I prevent program from running BOTH an IF and ELSE statement with C++?
  8. Generate random numbers uniformly over an entire range
  9. Using stdlib’s rand() from multiple threads
  10. Fast exact bigint factorial
  11. Best way to extract a subvector from a vector?
  12. Generating combinations in c++
  13. How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag’s value]?
  14. Finding duplicates in O(n) time and O(1) space
  15. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  16. Emulate “double” using 2 “float”s
  17. If we seed c++11 mt19937 as the same on different machines, will we get the same sequence of random numbers
  18. How often should I call srand() in a C++ application?
  19. Multiplication of two integers in C++
  20. Searching in a sorted and rotated array
  21. Consistent pseudo-random numbers across platforms
  22. Getting big random numbers in C/C++
  23. srand(time(NULL)) generating similar results [duplicate]
  24. `std::list::sort()` – why the sudden switch to top-down strategy?
  25. Easiest way of using min priority queue with key update in C++
  26. Edges on polygon outlines not always correct
  27. Counting number of bits: How does this line work ? n=n&(n-1); [duplicate]
  28. Good C++ solutions to the “Bring all the zeros to the back of the array” interview challenge
  29. Order Statistic Tree in C++
  30. What difference between rand() and random() functions?

Leave a Comment