Perl: the Markov chain saw  
PerlMonks 
FisherYates theory... does this prove that it is invalid?by MarkM (Curate) 
on Jul 25, 2003 at 01:00 UTC ( #277764=note: print w/replies, xml )  Need Help?? 
UPDATE: As pointed out by others, I made an error when translating the code. See their summaries for good explanations. Cheers, and thanks everyone. (tail between legs) In a previous article, I was challenged for doubting the effectiveness of the FisherYates shuffle as described in perlfaq. Below, I have written code that exhausts all possible random sequences that could be used during a particular FisherYates shuffle. Statistically, this should be valid, as before the shuffle begins, there is an equal chance that the random sequence generated could be 0 0 0 0 0 as 0 1 2 3 4 as 4 4 4 4 4. By exhaustively executing the FisherYates shuffle, and calculating the total number of occurrences that each result set is produced, we can determine whether the FisherYates shuffle has the side effect of weighting the results, or whether the shuffle is truly random, in that it should be approximately well spread out.
With the above code, I was able to determine that with a deck size of 5, and an initial set of 1 2 3 4 5, there is three times the probability that the resulting set will be 3 1 2 5 4 than the probability that the resulting set will be 2 3 4 5 1. To me, this indicates that this theory is flawed. If anybody needs to prove to themselves that the test is exhaustive, print out "@$rand" in the shuffle subroutine. Please analyze the code carefully, pull out your school books, and see if I have made a mistake. Cheers,
In Section
Meditations

