News for hackers. Stuff that matters.
Re:Unbiased Randomization with the Fisher-Yates Shuffle by TheLoneWolfling on Monday August 11, 2014 @04:47PM (#8165202)
Fisher-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 by twisted1827 on Monday August 11, 2014 @05:17PM (#8165355)
Python's Mersenne Twister was first seeded with 32 bytes, changed to 2500 bytes here:

http://hg.python.org/cpython/rev/7b5265752942

Re:Unbiased Randomization with the Fisher-Yates Shuffle by TheLoneWolfling on Tuesday August 12, 2014 @11:11PM (#8171293)
/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...