4
$\begingroup$

I found statement in an article "Good Practice in ( Pseudo ) Random Number Generation for Bioinformatics Applications" that you should not use too many random variables in a single simulation. Authors says that it maximum number of random values taken from PRNG should be $\frac{p}{1000}$ or even better $\frac{1}{200}\sqrt{p}$. $p$ is the period.

But I cannot see any references in other articles.

Do you know any reasons why not to use more values ?

$\endgroup$
3
  • $\begingroup$ An excellent reference for pseudo random number generators is the first Chapter of Volume 2 of "The Art of Computer Programming" by Donald Knuth. I would take a peek at it to see if if answers your question, but my copy is in my office and I am...in my pyjamas... $\endgroup$
    – user1729
    May 2, 2012 at 10:02
  • 3
    $\begingroup$ (Roughly speaking, say $x_1$ is the first random value you got given, then the way a PRNG works means that you will not get (or at least are very unlikely to get, depending on the generator you are using) given $x_1$ again. However, that isn't very random, is it? If it was truly random then $x_1$ would have the same likelihood of appearing at the $i^{th}$ iteration as every other number!) $\endgroup$
    – user1729
    May 2, 2012 at 10:08
  • $\begingroup$ @user1729: that's conceptually a good start. But the output of a PRNG can be much smaller than its internal state -which is related to the period, so it can return consecutive repeated values (think of a PRNG that gives you one bit in each try). $\endgroup$
    – leonbloy
    May 2, 2012 at 10:59

1 Answer 1

4
$\begingroup$

Assuming $p$ is the period of the PRNG, this is good advice, because after $p$ values are taken the PRNG will repeat.

To avoid the issue, just use a PRNG with a very large period. It will barely take $O(\log p)$ time to extract each pseudorandom bit, so you can make $p$ much larger than the number of values you will ever need to extract.

$\endgroup$
7
  • $\begingroup$ Yes by why to limit number of values taken to only fraction of period. $\endgroup$
    – Darqer
    May 2, 2012 at 10:32
  • $\begingroup$ see user1729 second comment to the question: a number can't repeat twice in the period, so you can predict future value (or you can predict what value can not appear again). $\endgroup$
    – carlop
    May 2, 2012 at 10:38
  • $\begingroup$ I don't know why $\frac{1}{1000}$ of the period is suggested; also I don't know why it is better to limit to $O(\sqrt{p})$, but I guess that many values may give enough information to bust the hash and predict future values. $\endgroup$ May 2, 2012 at 10:38
  • $\begingroup$ @Darqer: Assuming you are using a very simple PRNG (say, you're using multiplication mod $p$, $p$ prime) then for $x$ such that $0<x<p$ at the $i^{th}$ iteration either $x$ will have been picked already and so have zero probability of being picked or $x$ will have a one-in-($p-i$) chance of being picked. For this to be random every number should have a on-in-($p-1$) chance of being picked. So, as the number of iteration increase the randomness of the PRNG decreases. So, you should pick a point to stop. $\endgroup$
    – user1729
    May 2, 2012 at 10:39
  • $\begingroup$ Truly random numbers do not have a period. PRNGs do, so to ensure this doesn't negatively affect your simulations, you want to avoid too many repeats - or, ideally, avoid any repeats! Most common PRNGs are very poor (e.g., the C rand() function). But there are lots of good quality generators out there, if you specifically look for one. $\endgroup$ May 2, 2012 at 10:40

You must log in to answer this question.

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