math - Generating sorted random ints without the sort? O(n)

Question

Just been looking at a code golf question about generating a sorted list of 100 random integers. What popped into my head, however, was the idea that you could generate instead a list of positive deltas, and just keep adding them to a running total, thus:

deltas: 1 3 2  7  2
ints:   1 4 6 13 15

In fact, you would use floats, then normalise to fit some upper limit, and round, but the effect is the same.

Although it wouldn't make for shorter code, it would certainly be faster without the sort step. But the thing I have no real handle on is this: Would the resulting distribution of integers be the same as generating 100 random integers from a uniformly distributed probability density function?

Edit: A sample script:

import random,sys
running = 0
max = 1000
deltas = [random.random() for i in range(0,11)]
floats = []
for d in deltas:
    running += d
    floats.append(running)
upper = floats.pop()
ints = [int(round(f/upper*max)) for f in floats]
print(ints)

Whose output (fair dice roll) was:

[24, 71, 133, 261, 308, 347, 499, 543, 722, 852]

UPDATE: Alok's answer and Dan Dyer's comment point out that using an exponential distribution for the deltas would give a uniform distribution of integers.

Answer 1

So you are asking if the numbers generated in this way are going to be uniformly distributed.

You are generating a series:

y_j = ∑_i=0^j ( x_i / A )

where A is the sum of all x_i. x_i is the list of (positive) deltas.

This can be done iff x_i are exponentially distributed (with any fixed mean). So, if x_i are uniformly distributed, the resulting y_j will not be uniformly distributed.

Having said that, it's fairly easy to generate exponential x_i values.

One example would be:

sum := 0
for I = 1 to N do:
    X[I] = sum = sum - ln(RAND)
sum = sum - ln(RAND)
for I = 1 to N do:
    X[I] = X[I]/sum

and you will have your random numbers sorted in the range [0, 1).

Reference: Generating Sorted Lists of Random Numbers. The paper has other (faster) algorithms as well.

Of course, this generates floating-point numbers. For uniform distribution of integers, you can replace sum above by sum/RANGE in the last step (i.e., the R.H.S becomes X[I]*RANGE/sum, and then round the numbers to the nearest integer).