Re:Unbiased Randomization with the Fisher-Yates Shuffle
by kiyoto on Monday August 11, 2014 @04:14PM
(#8165020)
On second read, I realized that OP didn't even prove Fisher-Yates. I blogged about this several weeks back, and here is an excerpt from it. Some of you might find it useful.
"This is easy to verify for N = 2: You are just flipping a coin to decide if you swap 1 with 2. For N > 2, you just need to show that each of 1 through N has an equal chance of getting the k-th slot for 1 through N. In the first step, every number has a 1/N probability of getting into the first slot. For all other slots: the number has (1-1/N) chance of getting/staying there, then by induction, all slots are equally likely, hence (1-1/N)*1/(N-1) = 1/N. This completes the proof."
"This is easy to verify for N = 2: You are just flipping a coin to decide if you swap 1 with 2. For N > 2, you just need to show that each of 1 through N has an equal chance of getting the k-th slot for 1 through N. In the first step, every number has a 1/N probability of getting into the first slot. For all other slots: the number has (1-1/N) chance of getting/staying there, then by induction, all slots are equally likely, hence (1-1/N)*1/(N-1) = 1/N. This completes the proof."