A very interesting article since I have been wanting to write my own card game app for a while.
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 :)
You should next make a bet with him that for any deterministic shuffling algorithm that does not consider the value of the cards, the cards will return to their original state eventually.
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.
And any non-deterministic algorithm (that ignores the values of cards) will return to its original state with probability 1...? Do you need to add an extra caveat to this?
Not bad... but unfortunately the part it leaves out is critical (at least for me). How do you get that formula at the end?
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.
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 :)
http://jazzychad.com/cards/