3

If I set the seed to 0 in C, I will get this sequence after calling rand() three times:

38, 7719, 21238, ...,

If I set seed to 1 (srand(1)) I will get this other sequence:

41, 18467, 6334, ...,

I know that is's very improbable, but will the sequence of srand(1) be present in the sequence of srand(0) at some point? I mean, using srand(0) will I get:

38, 7719, 21238, ..., ..., ..., 41, 18467, 6334, ...,?

Thanks!

Daniel Bonetti
  • 2,306
  • 2
  • 24
  • 33
  • 2
    It depends. A PRNG can form one or multiple cycles. If 0 and 1 are in the same cycle, then yes, you will eventually see the sequence you get using `srand(0)` with `srand(1)`; in fact, both sequences will be the same, but shifted some amount. On the other hand, if they're in different cycles, you won't ever see any of the numbers in common. – rlbond Sep 23 '15 at 19:13
  • 1
    This is not defined by the standard. – too honest for this site Sep 23 '15 at 19:18

3 Answers3

3

For rand, it's not specified by the standard, but the example implementation suggested in the C standard certainly does produce overlapping sequences (actually there's only one sequence and the seed is just the starting point).

If you need stronger properties you need to choose an appropriate PRNG rather than just using rand. A guarantee of no overlapping length-N subsequences would be very hard to prove for a decent PRNG, and an easy proof or even truth of that statement for reasonable-size N would indicate a very bad PRNG. But it's easy to guarantee, for a good PRNG with sufficiently large state, that different seeds do not produce completely identical sequences, just starting at different points.

R.. GitHub STOP HELPING ICE
  • 208,859
  • 35
  • 376
  • 711
  • Unless I misunderstand the second paragraph, I don't think this it is correct. Non-overlapping sequences can be produced by PRNGs independent of any other qualities. All that is needed is a function that advances the internal state N times, without actually requiring O(N) computation. In many cases this is possible in O(log(n)) time using matrix exponentiation, or even O(1) time in the case of PRNGs based on encryption of a counter value, e.g. Philox. Knowing the period of the generator and the advancing function then allows production of multiple non-overlapping sequences of specified length. – njuffa Sep 23 '15 at 23:39
  • What I'm saying is that if you never want the subsequence `{ 42, 12345, 98 }` to appear in your sequence for more than one seed, this (1) means your PRNG has bad statistical properties, and (2) is hard to achieve unless your PRNG has properties that make it bad (like low period relative to the number of possible outputs). – R.. GitHub STOP HELPING ICE Sep 24 '15 at 00:54
3

Though it is not defined by standard - The answer to your question is yes, it depends upon the algorithm being used, which is usually Linear Congruential Generators (LCG). LCG is considered to be high on cross-autocorrelation. Looking at how rand is implemented in your platform will let you characterize it better. Here is an example Rand Implementation

Community
  • 1
  • 1
abRao
  • 2,787
  • 1
  • 25
  • 37
2

The actual answer is that it depends on the implementation of the generator, which is not defined in the standard. This is true even for Linear Congruential Generators (LCGs), which are often used as a default implementation for rand.

An LCG is a recurrence relationship of the form

state = (A * state + B) % M

for suitable integer-valued constants A, B, and M. Setting the seed initializes the state.

Some choices of A, B, and M will not achieve full cycle (relative to the modulus M), in which case the LCG can produce two or more non-overlapping subsequences. For example, for A = 3, B = 0, and M = 11 you'll find yourself on one of two non-overlapping subcycles depending on your seed value. Seeding with 1 will produce the following sequence:

3,9,5,4,1,3,9,5,4,1,3,9...

and seeding with 2 will produce:

6,7,10,8,2,6,7,10,8,2,6,7...

Other choices of the coefficients can attain full cycle. in either case the seed value corresponds to picking an entry point to a cycle or subcycle.

For other classes of generators which maintain a larger state space and collapse the state to produce each reported value, you can get repeats of individual values without repeating the identical sequence until you have enumerated the entire (not visible) state space. That's how a generator such as Mersenne Twister achieves cycle lengths such as 219937-1. Different (very large) states can collapse down to the same 32 or 64 bit quantity for an individual observation, but will lead to entirely different states being calculated (and collapsed) for the next value, so you will see repeats of individual values without seeing a repeat of the sequence of values.

pjs
  • 18,696
  • 4
  • 27
  • 56