List::Util [1], part of Perl 5 standard library, offers shuffle function which implements Fisher-Yates [2].
[1]: https://metacpan.org/pod/List::Util#values-shuffle-values [2]: http://www.perlmonks.org/?node_id=1869
Unbiased Randomization with the Fisher-Yates Shuffle
11–14 of 14 posts
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#12Fisher-Yates is only unbiased in the event of a "true" RNG as opposed to a PRNG with a less than absurd seed length.
In practice, say you're shuffling a 52-card deck - that's 52! orderings. Even if you have a 128-bit random seed, that's still nowhere near enough. You need at least a log2(52!) = 226 bit seed to cover all orderings, even assuming every seed produces a unique sequence of numbers, by the pigeonhole principle.
And it's even worse than that. Say you have a 226 bit seed. Well, you still won't have a uniform distribution. Why? Because 52! does not evenly divide 2^226. Even assuming a "perfect" PRNG (again: where every seed produces a unique sequence of numbers), you'll end up hitting some deck orderings less than others. In this case, it's a difference between some deck orderings being hit once and others being hit twice - which can make a big difference! You can mitigate this by either discarding and reinitializing your PRNG if the initial seed is >= 52!, or just choosing a bit length long enough that the effect becomes minimal.
It's like trying to pick a number between 0 and 45 with a 100 sided die - if you just take the number rolled mod 45, you'll end up with 0 through 9 picked more often than they should be. Instead, you have to roll until you get a number between 0 and 89, inclusive, then take mod 45.
(Oh, and as for the response of "just pick a larger seed", say you have a card game played with 4 decks (for example Shanghai rum with a bunch of players). Then you need a seed length of >=1307 bits. I cannot think of any PRNGs with a seed that large.)
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#13Fisher-Yates is only unbiased in the event of a "true" RNG as opposed to a PRNG with a less than absurd seed length. In practice, say you're shuffling a 52-card deck - that's 52! orderings. Even if you have a 128-bit random seed, that's still nowhere near enough. You need at least a log2(52!) = 226 bit seed to cover all orderings, even assuming every seed produces a unique sequence of numbers, by the pigeonhole princ…
Python's Mersenne Twister was first seeded with 32 bytes, changed to 2500 bytes here:
Re: Unbiased Randomization with the Fisher-Yates Shuffle
#14Fisher-Yates is only unbiased in the event of a "true" RNG as opposed to a PRNG with a less than absurd seed length. In practice, say you're shuffling a 52-card deck - that's 52! orderings. Even if you have a 128-bit random seed, that's still nowhere near enough. You need at least a log2(52!) = 226 bit seed to cover all orderings, even assuming every seed produces a unique sequence of numbers, by the pigeonhole princ…
Python's Mersenne Twister was first seeded with 32 bytes, changed to 2500 bytes here: http://hg.python.org/cpython/rev/7b5265752942
/dev/urandom on Linux only has an internal state of 1024 bits [1]
As Python's Mersenne Twister is seeded with urandom...
[1] https://pthree.org/2014/07/21/the-linux-random-number-genera...