1
$\begingroup$

I'm looking for a reference to an algorithm that does the following. Given n, and a range [min, max], generate a random ascending stream of n integers i_1, i_2 .. i_n such that min <= i_1 < i_2 < ... < i_n <= max. And this should be done in constant space.

(So I'm looking for a more efficient alternative to the following simple approach: First generate n random numbers in the desired range, then sort them, and then go over the sorted list in order. This needs O(n) space.)

I could swear I saw a paper describing an algorithm that does exactly this. But I can't find that paper again, no matter what I search for. Am I misremembering? Can you help me?

$\endgroup$
  • $\begingroup$ I don't think you can achieve a sorted stream of i.i.d variables without generating them all first: the next number you generate can always be the smallest! Hence, I think you need to check which exact random model you're supposed to provide there. $\endgroup$ – Raphael Oct 14 '17 at 12:37
  • 1
    $\begingroup$ What might be possible is, given the desired model, to determine Pr[a[i] = k | a[1], ..., a[i-1]] in that model, with a[i] the i-th element in the sorted sequence. (Use order statistics.) Then you can generate one element after another using this distribution. $\endgroup$ – Raphael Oct 14 '17 at 12:39
  • 1
    $\begingroup$ "generating n random numbers normally" -- with what distribution? That's going to be crucial here. $\endgroup$ – Raphael Oct 14 '17 at 14:15
  • 1
    $\begingroup$ @Raphael: Just the uniform distribution between min and max. (Though actually, that can result in duplicates. Haven't thought that part through...) $\endgroup$ – user12186 Oct 14 '17 at 19:58
  • $\begingroup$ D.W.'s answer does uniformly without replacement, so no duplicate. But not i.i.d. uniformly. $\endgroup$ – Raphael Oct 15 '17 at 4:24
2
$\begingroup$

It can be done in $O(1)$ space and $O(n^2)$ time. Let $X_1,\dots,X_n$ denote the numbers in the stream, in sorted order. You can calculate

$$\Pr[X_i = x_i | X_1=x_1,\dots,X_{i-1}=x_{i-1}]$$

and then use that to generate the numbers $X_1,\dots,X_n$ one by one.

Here is the derivation. We have

$$\begin{align*} \Pr[X_1=x_1,\dots,X_{i-1}=x_{i-1}] &= {{\text{max}-x_{i-1} \choose n-i+1} \over {\text{max}-\text{min}+1 \choose n}}\\ \Pr[X_1=x_1,\dots,X_{i-1}=x_i] &= {{\text{max}-x_i \choose n-i} \over {\text{max}-\text{min}+1 \choose n}} \end{align*}$$

so it follows that

$$\Pr[X_i = x_i | X_1=x_1,\dots,X_{i-1}=x_{i-1}] = {{\text{max}-x_i \choose n-i} \over {\text{max}-x_{i-1} \choose n-i+1}}= \Pr[X_i = x_i | X_{i-1}=x_{i-1}].$$

Here the domain of possible values for $X_i$ is $x_{i-1}+1,\dots,\text{max}$; the probability is zero for other values of $X_i$ outside that domain.

Notice that this probability depends only on $x_{i-1},x_i$, so you only need a constant amount of space: you don't need to remember the entire past history.

Thus, the algorithm becomes:

  1. Pick $x_1$ from the distribution $\Pr[X_1=x_1] = {{\text{max}-x_1 \choose n-1} \over {\text{max}-\text{min}+1 \choose n}}$.

  2. For each $i=2,3,\dots,n$, pick $x_i$ from the distribution for $\Pr[X_i = x_i | X_{i-1}=x_{i-1}]$ given above.

This algorithm requires only $O(1)$ space. The running time might be $O(n^2)$ (since it might take $O(n)$ time to draw from a distribution with $n$ possible values). Perhaps further analysis could reduce the running time by finding a more efficient way to draw from these distributions. For instance, if you could find a way to compute the cdf (cumulative distribution function) for these distributions and evaluate it at an arbitrary $x_i$ in $O(1)$ time, then you could reduce the total running time to $O(n \log n)$ by using binary search at each step to draw from the distribution. I don't see how to do that myself, but perhaps someone else will.

This might get a lot easier if you are willing to draw streams of non-decreasing integers rather than a stream of increasing integers (i.e., allow an integer to be repeated), since the formulas for probability for drawing with replacement tend to be a lot simpler than those for drawing without replacement.

$\endgroup$
  • $\begingroup$ So that quick idea of mine actually works out? X-) Cool, thanks! $\endgroup$ – Raphael Oct 14 '17 at 20:30
  • $\begingroup$ "The running time might be O(n²) (since it might take O(n) time to draw from a distribution with n possible values)" -- I think Knuth had something nice in TAOCP on this. $\endgroup$ – Raphael Oct 15 '17 at 4:24
1
$\begingroup$

Original asker here. For anyone else looking at this: the paper I was looking for is Generating Sorted Lists of Random Numbers by Jon Louis Bentley and James B. Saxe. The algorithm in the paper does what I asked.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.