1
$\begingroup$

For fun (relatively speaking), I'd like to do a little research on probabilities related to a pseudo-random number generator.

Specifically, how would I get started figuring out "what is the probability that a prng will generate the same random number twice?"

This is part of an investigation into a larger issue, but I'm not sure where to begin (or if my question is even relevant).

Edited to add:

After reading the comments and answers I see that my question isn't clear. As an example: the rng outputs a 5 What is the probability that another 5 will be the next output? How many "rolls" of the RNG must I make before I see another 5?

If we assume a good rng has uniform distribution, then is it 1 out of (2^32) (assuming 32bit integers)?

For a larger example, lets say I use the RNG to generate numbers that are used as an index into an array of characters. The array is 25 numbers long, so the output of the RNG is mod 25 I will generate a sequence of 5 characters.

How would I determine the probability of generating the same 5 character sequence?

If we assume that we have a uniform distribution of output numbers from the RNG, then the RNG's output shouldn't factor into the probability of generating the same character sequence.

However, is my assumption valid?

  • 0
    The probability that a prng will generate the same random number twice is one, if you let it run long enough.2011-05-14
  • 1
    Which prng? There are more than one.2011-05-14
  • 0
    Huh, why the downvote? It's not like the periodicity of a PRNG is common knowledge...2011-05-14
  • 0
    @J.M.: I didn't downvote, but just to be precise: the question isn't about periodicity; it's slightly more trivial that eventually the same number will be generated twice than that they will all be generated again in the same sequence.2011-05-14
  • 0
    @quanta: Please let me know what isn't clear and I'll update it.2011-05-14
  • 0
    @mhum: I don't think it should matter which rng, as I'd like to have a general understanding.2011-05-14
  • 0
    @Alan, I just don't understand the question. Do you have in mind a definition of "prng" and when are they considered to generate the same number twice?2011-05-14
  • 0
    @Gerry Myerson: Yes. That makes this question kind of silly.2011-05-14
  • 0
    @Alan, I think you should ask a much more specific question before trying to understand this very general case.2011-05-14
  • 0
    "I don't think it should matter which RNG" - actually it does.2011-05-14
  • 0
    @J.M. I've updated the original question. What isn't clear to me, is how the period relates to the uniform distribution of output.2011-05-14

3 Answers 3