1

Given that the size of some sets (example, 52! (about 2226 or 8*1067), the number of ways to shuffle a regular deck of cards) exceeds the period of most Pseudorandom Number Generators (PRNG), is it true that some combinations may be unable to be generated by the PRNG?

Does it matter if tries to permutate the array, vs. whether it picks items one by one? What if you re-seeded the generator periodically?

EDIT: Not a duplicate. I do not see how the proposed duplicate answers the question.: Is it true that some sequences cannot be generated, no matter how you use the RNG (including re-seeding)?

2 Answers2

3

Well... yes. If the cycle length of a periodic output of a process is smaller than the number of possible values in the data type, then some of the values of the data type will never be generated. In fact, combinatorial numbers are huge, they are much larger than most data types, so most possible results will never be generated.

But that is not what we use RNGs for. We're not interested in a process that merely permutes the set of all possible values. We want one that mimics a natural, unpredictable process, in which we (or an adversary who works against us) cannot discern any pattern to exploit. For many tasks, periodic RNGs deliver exactly that. The fact that they skip some (or most) values is irrelevant as long as you can't easily predict which of them they skip.

Kilian Foth
  • 109,273
2

To have a chance at generating all sequences you need to use at least log2(n) bits of entropy. For 52! that is 226 bits of entropy.

This means you need to reseed the PRNG so that all 226 bits get used. And even then you can't be fully sure there isn't a potential collision that robbed you of a possible output.

Though in most card games the entire deck is not used so you save a few bits that way.

In most cases the bigger challenge is getting those random bits.

ratchet freak
  • 25,876