Card shuffling, mathematical modeling, and Markov chains
davidson.edu
davidson.edu
On a side note, a friend once bet me $5 that you could perfectly shuffle a deck of cards indefinitely (where "perfectly" means break the deck in two and alternate cards from each stack), and the deck would never return to its original state.
I disagreed and decided to write some code to prove it :)
I've seen it done.
http://mathworld.wolfram.com/RiffleShuffle.html
1. The number of permutations of the cards is finite (52!).
2. Therefore, by the pigeonhole principle, if you shuffle the cards 52! + 1 times, at least two of the card orders will be the same. Let those two decks be A and B.
3. Take a blue deck of cards and place them in the order of A. Take a red deck of cards and tape them to the blue deck, so the red ace of spades is taped to the first blue card, the red two of spades to the second blue card, and so on.
4. Shuffle this deck however many times it took to get from A to B.
5. Since A and B are identical, the blue cards at the end of this shuffling are in the same positions as they were when the shuffling started. And since the red cards started out in order and traveled identically with the blue cards, the resulting deck is in order.
6. Since, by hypothesis, the shuffling algorithm does not consider the value of the cards, we can just throw out the blue cards and shuffle the red cards alone however many times it took to get from A to B, and if they started in order, the cards will return to their original order.
This, unfortunately, is the problem with a lot of "make math easy" articles. The topic itself is not easy, so at some point, you need to bring in tough math. What I dislike is that the article doesn't make it clear how critical that bit is.