7
$\begingroup$

I'm doing (with Java) a very simple simulator (Queueing Systems..) that needs many random numbers (more than $10^5$).

I know that Java Random class would give me all the random numbers I need, and they pass all the test I'm doing, but.. they are pseudo-random! I don't like it.

I know that random number web site gives real random numbers from atmospheric noise (or something like that) but it limits the download. In particular you cannot download more than 10000 numbers with one HTTP request.

So the question is: is there a way to generate more than $X$ random numbers with $X$ random numbers and infinite (...) pseudo-random?

$\endgroup$
3
  • 4
    $\begingroup$ Would seeding the pseudo-random number generator with a real random number be insufficient? Perhaps seed it, grab a real-random number of pseudo-random numbers, re-seed it, etc.? $\endgroup$
    – Isaac
    May 22, 2011 at 21:41
  • 1
    $\begingroup$ I'm not familiar with the literature, but there are known methods used in computer science and other fields for "amplifying" randomness: see en.wikipedia.org/wiki/Randomized_algorithm#Derandomization . $\endgroup$
    – Qiaochu Yuan
    May 22, 2011 at 21:43
  • 1
    $\begingroup$ @Isaac: Just don't use RC4... $\endgroup$
    – Yuval Filmus
    May 22, 2011 at 21:51

2 Answers 2

Reset to default
15
$\begingroup$

There's absolutely no reason to use "real" random numbers. Furthermore, those "real" random numbers may be worse that pseudorandom ones. For example, it could happen that for some physical reasons, the "real" random bits are slightly skewed or have slight correlations. That can be corrected using a "randomness extractor" but then, why not just use the same techniques without all the hassle?

There are surely some reasons not to settle for pseudorandomness, but none of them apply in your case. For example, you don't mind that your numbers are deterministic. You don't care if they're cryptographically secure. And you'd want all your experiments to be reproducible (though that's still possible under your "real" model).

As to your concrete final question, yes, it's possible to use outside "real" random bits to influence a cryptographic model generating random numbers. You can probably find some methods in the literature (don't try to invent anything yourself, though). Just keep it mind that instead of focusing on the simulation itself, this will change your focus to something which, in my mind, is completely bogus.

$\endgroup$
3
  • $\begingroup$ I think you're right, but i was curious if there were any methods in literature.. like to expand the period of a pseudo-random with two pseudo-random (using one as a cursor). Thank you for the advice. $\endgroup$
    – Fabio Filippi
    May 22, 2011 at 21:50
  • $\begingroup$ Regarding this last technique (the cursor thing). I seem to remember that this does NOT work. Think I read that in "numerical recipes". $\endgroup$
    – Sebastien
    May 23, 2011 at 4:47
  • 1
    $\begingroup$ This is all the territory of cryptology, and as non-experts on the subject, you are certain to make mistakes, so don't even try. Instead, carefully skim the literature for some "popular" design which seems to be well-regarded - though that can be hard to tell, and it's much better to ask some expert. $\endgroup$
    – Yuval Filmus
    May 23, 2011 at 14:30
4
$\begingroup$

I understand your concerns, however: As Yuval already pointed out, there is no guarantee that numbers from noisy real world systems are "better" for your application that the numbers generated from a pseudo-random number generator.

IID random variables are a mathematical idealization. Simplifying a little bit, for every real physical system and every random number generator there is a statistical test that will reveal that the generated numbers are not IID. The "bad" random number generators are those where such a test is already known, the "good" ones are those where such a test is not known. In particular, every pseudo-random number generator will generate numbers with some kind of correlation. The question is, if the generated artefacts will produce wrong results when your application eats them. In this sense, all random number generators are "bad", but with regard to a specific application, some will produce artefacts and some will not. In practice, it is most often not possible to determine which random number algorithms will produce artefacts for a given application, and which won't. So, the best advice that I can give you is

1) Use random number generators only that pass the usual statistical tests. Don't use implementations that you don't understand.

For tests for random number generators see e.g.

CSIS.

2) Run your application with at least two different random number generators.

"Different" means of course different algorithms, not e.g. two different linear congruence generators. This will give you a good fighting chance that the results that you get aren't artefacts of your random number generator.

Some literature:

  • William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery: Numerical Recipes, The Art of Scientific Computing (3rd edition, chapter 7)

  • James E. Gentle: Random Number Generation and Monte Carlo Methods (Springer, 2nd edition)

$\endgroup$
1
  • 1
    $\begingroup$ Re 2, you can always XOR the output of those two PRNGs. $\endgroup$
    – Yuval Filmus
    May 23, 2011 at 14:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .