0
$\begingroup$

When I talked with students about pseudo-random number generation, I mentioned that you should not blindly use subsequent outputs of a pseudo-random number generator (PRNG) to form tuples as they may not be uniformly random then; a famous example is RANDU.

The natural follow-up question is: what do you do? I can imagine several strategies.

  1. Choose a PRNG that you know works well for $k$-tuples and sample $(\leq k)$-tuples by using subsequent numbers as components.

    I assume that $k \leq 5$ is probably covered, but are there any for arbitrary $k$?

  2. Use $k$ different PRNGs (different algorithms and/or different seeds) and draw the $i$th component from the $i$th one.

    I seem to remember that mixing PRNGs is not a good idea.

  3. If the domain of your PRNG is big enough, use bits $i,k+i,2k+i, \dots$ for the $i$th component.

    Seems sound and is probably the method of choice assumign real $U(0,1)$-numbers, but does not scale given finite resolution/domains in practice.

  4. Use a bijection from the domain of your PRNG to the $k$-dimensional space you want to sample from, e.g. a generalized version of Cantor's pairing function.

    The sizes of the resp. domains can become a problem here a well.

None of the approaches seems entirely reasonable. So what is the state of the art? What advice would you give a person who needs to sample uniformly random tuples?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Using consecutive outputs from the PRNG to form a tuple is fine if you use a good enough PRNG. So, one reasonable approach is to simply use a good PRNG, and then not waste brain power worrying about issues like this.

One way to get a "good enough" PRNG is to use a cryptographic-quality PRNG.

RANDU is a truly lousy PRNG (for instance, the least significant bit of its output is not random at all), so no surprise that all sorts of bad things happen when you use its output. But the root cause there is not using tuples from RANDU; the root cause is using RANDU.

Improve this answer
$\endgroup$
4
  • $\begingroup$ It would be good to have somewhat rigorous (at least testable) criteria for "good enough". I seem to remember that PRNGs can be absolutely fine for numbers (unlike RANDU) but fail for tuples, anyway. (In case you know something, I think this question is in need of a good answer, too.) $\endgroup$
    – Raphael ♦
    Jan 19, 2016 at 12:57
  • 1
    $\begingroup$ @Raphael, sadly, I don't know of any rigorous or precise criteria, except that a cryptographic-quality PRNG is definitely good enough: the definition of a crypto-strength PRNG is that no polynomial-time adversary can distinguish its output from true random, so it follows immediately that tupling can't hurt (no polytime algorithm can distinguish the resulting pseudorandom tuples from truly random tuples). So, "crypto-strength" is sufficient. The catch is this: we don't know how to prove that any particular PRNG is crypto-strength, without making unproven assumptions. $\endgroup$
    – D.W. ♦
    Jan 19, 2016 at 16:58
  • $\begingroup$ @Raphael, yeah, I saw that question when it was posted. I don't how to give a useful answer (see my comment), otherwise I would try to write one. $\endgroup$
    – D.W. ♦
    Jan 19, 2016 at 16:59
  • $\begingroup$ I see, too bad! (I feel like there should be more knowledge about this, but maybe this is the bottom of the barrel for now?) $\endgroup$
    – Raphael ♦
    Jan 19, 2016 at 17:23
0
$\begingroup$

The spectral test can be used to check if a given linear-congruential PRNG is suitable for sampling $T$-tuples [1, sec. 3.3.4].

The most important randomness criteria seem to rely on properties of the joint distribution of $T$ consecutive elements of the sequence, and the spectral test deals directly with this distribution.

Algorithm S [1, pp101] is too long to reasonably reproduce here, let alone the theory behind it. According to Knuth, it is not quite feasible for $T \geq 9$ (the constant may be different today) because an exhaustive search causes a running time in $\Omega(3^T)$.

So if the distributional properties of a PRNG w.r.t. tuples are really important to you, there are ways to check for them. Knuth later references the work of H. Niederreiter, which seems to contain tests for other kinds of generators.

  1. Seminumerical Algorithms by D.E. Knuth (TAoCP vol. 2; 3rd ed; 1998)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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