2
$\begingroup$

How likely is for a pseudorandom number generator to generate a long sequence of similar numbers? "Similar numbers" could be same numbers, or numbers from a given range.

For example, if we consider PRNG algorithm being a simple counter counting from 0 tom MAX, the distribution is uniform and there's a guarantee of not repeating numbers in a sequence. So, not repeating numbers does not break uniformness. But probably it breaks randomness, does it? To what extent? If so, does it mean, that the better the algorithm, the less guarantee we have to not generate similar numbers in sequence?

I'm particularly interested in the answers regarding Mersenne Twister as a most popular PRNG in programming languages implementations. It'd also be great to know how things are in operating systems' crypto-secure PRNGs – Yarrow (macOS), Fortuna (FreeBSD) or ChaCha20 (Linux).

$\endgroup$

3 Answers 3

3
$\begingroup$

Given the same internal state, a pseudorandom number generator (PRNG) must produce the same output. PRNGs have a period: if you run one long enough, it will start repeating the same sequence. (For good PRNGs, the period is long enough that you don't have to worry about it.) For very simple PRNGs such as a simple linear congruent generator of the form

new number = old number $\times$ constant $+$ another constant

the state is just the previous value. In that case, it's impossible to generate the same number twice in a row unless the constants are poorly chosen and the PRNG gets stuck in a short loop. (This has been known to happen, and you don't want to use such a PRNG!) However, you will sometimes generate numbers that are similar (not the same) in various respects. The tests that vonbrand's answer mentioned are designed to verify that such similarities occur with relative frequencies that are close to what should be found if each number had equal probability.

The most common version of a Mersenne Twister (MT) has a 624$\times$32-bit internal state. If the MT is being used to generate 32-bit numbers, it uses up 32 bits of its state each time it outputs a number, and when all 624 internal state words have been used, the MT generates a new 624-word state from its old state. (The number that is output is not the same as the state word that's used; it's a function of the state word, though.) I suppose an MT could theoretically sometimes output the same number in two successive calls on the MT, although I am not certain that that is possible. I think that would require that two successive words in the generated 624-word state were identical (unless it happened because you seeded the MT with a bad state that included the same number multiple times). I don't know whether this is possible; I suspect that it is. But it should be very, very, very rare in the sense that the relative frequency of successive duplicates across the entire period of MT should be small.

For 32-bit numbers, ideally, the relative frequency of choosing the same number twice in a row should be $1/2^{32} \times 1/2^{32} = 2^{-64}$. That would be very rare. On the other hand, the period of the widely-used version of MT, versions of MT19937, is $2^{19937}-1$. This is the number of successive pairs that could, theoretically, contain duplicates, and $2^{-64} \times 2^{19937}-1 = 2^{19873}$ is a large number. However, any use of MT will only make use of a small fraction of the period. At this point, if I wanted to know how common or rare duplicates are, I would look at the test in TestU01 or another test suite that checks the frequency of duplicates. I wouldn't test the entire period, though, unless I had a lot of computing power and was patient. I don't know whether it's possible to assess the frequency of duplicates analytically from the design of MT19937.

I listed some other relevant resources in this answer and said more about Mersenne Twisters in this answer.

$\endgroup$
3
  • $\begingroup$ "very, very, very rare" – the question is whether it's 1 / MAX_INT probability or less? $\endgroup$ Commented Mar 4, 2020 at 7:59
  • $\begingroup$ @MaciekŁoziński, probability of what, exactly? $\endgroup$
    – vonbrand
    Commented Mar 4, 2020 at 11:47
  • $\begingroup$ I intended "rare" to refer to the relative frequency of pairs of identical numbers across the entire period of MT. I'll update the answer to clarify this. $\endgroup$
    – Mars
    Commented Mar 4, 2020 at 18:06
1
$\begingroup$

The likelihood of, e.g. a string "000000" should be exactly the same as every other six-bit strings, i.e. $2^{-6}$ for each. To see if a particular PRNG satisfies such properties requires either hairy math (see for example the exhaustive discussion of congruential generators in Knuth's "Seminumerical Algorithms", it has a chapter on random numbers, other generators like the Mersenne twister you mention have their own analysis) and lots of computer time, or just run a battery of statistical tests (see for example the discussion on random.org's generator, Dwyyer and Wiliams "Testing Random Number Generators", or Cook's "Testing a random number generator"). Cryptographically strong random number generators have other, more stringent requirements (even knowing how the generator works, and a very long history of previous results, it should be computationally unfeasible to predict the next output).

$\endgroup$
1
$\begingroup$

Define what you mean by similar (any way you like).

For a given, fixed x let the probability that a random number y is similar to x be p. Then the probability that n consecutive random numbers $y_1$ to $y_n$ are all similar to x is $p^n$.

Now let the numbers x and $y_1$ to $y_n$ be numbers generated by a PRNG. Then either the probability that $y_1$ to $y_n$ are all similar to x is $p^n$, or we found a statistical test that the PRNG fails.

(I was careful how to state this. The situation is different if x is not fixed. For example if x, y are similar if -0.1 < x-y < +0.1 then for some x (say 0.001) the probability that n other numbers are all similar to x can be as low as $0.1^n$, while for 0.1 ≤ x ≤ 0.9 the probability is $0.2^n$. The probability that all numbers are similar to each other is different again. And if I define "x and y are similar if the first digit is the same, but the second is different", then you can't have 11 similar numbers).

$\endgroup$
1
  • $\begingroup$ As in my question, similar means from a given range. In particular, this could be range like [x, x], then similar means equal. $\endgroup$ Commented Mar 5, 2020 at 12:13

Your Answer

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

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