I’d typically assume that after most card games, the cards become at least semi-ordered in some way, necessitating shuffling. However, after a standard game of war, I can’t quite figure out how the arrangement would become less random, since the winning and losing card stay together. If they’re indeed mathematically “less random,” after the game, why?
In: 312
Can’t say this is exactly ELI5, but I have an explicit proof that the result of a game of War is in fact not a uniformly random distribution. Thanks to u/Chromotron for giving me the key fact to come up with a proof. And this proof is neatly independent of how the cards are picked up after a battle so long as that method is deterministic and symmetric; that is so long as each player is picking up the cards in the same way every time and they are picking them up in the same way as each other (either opponent’s card first or your own card first).
First, what it means to be “truly random” is that any given ordering must be equally likely as any other.
The key insight is this:
*In order for every possible order to be exactly likely as any other, every order much be actually possible to arrive at.*
So, this means that for any order of the deck O, there must be one, and exactly one starting order O_s that produces O when used to play a game of War, and one and exactly one final order O_f that would be produced by using O as a deck to play a game of War with. This is because of the assumption that how the cards are picked up are completely deterministic.
So, if there are two different starting orders O_1 and O_2 that produce the same final order, then necessarily, there must exist some O_i for which there does not exist a starting order than can produce O_i after using it to play a game of war. And if there’s an O_i that can’t be produced from any starting order, then the results of games of War are not a random distribution and are in some small way “sorted”.
All that is left is to demonstrate that there are at least 2 different starting orders that produce the same final order.
For that we need to bring in the fact that War is symmetric. Consider a much smaller deck that only contains 4 cards, the 2, 3, 4, and 5 of hearts. If we take the starting order: 2345 and use it to play a game of war (treating numbers earlier in the ordering as being “on top” and the last number being the bottom), we would first divide the deck in half and give a half to player 1, and the other half to player two, so player 1 would receive 23, and player 2 would get 45.
It should be easy to see that the game will only last for 2 rounds with player 2 winning both times. With the resulting deck that player 2 has now looking something like 4253 (in this case assuming players end up putting their own card on the bottom of their deck before their opponent’s). But consider, the final deck would have looked exactly same at the end if instead we had given the top half of the deck to player 2 and the bottom half to player 1. Then realize that therefore, both the starting ordering of 2345 and 4523 will therefor result in the same final ordering since 4523 is just our first game but with the old “bottom half” now given to player 1.
And since we’ve shown 2 different starting orderings results in the same final ordering, therefore not all final orderings are possible and therefore the results of games of War are not a uniformly distributed sample from all possible deck orderings. In fact, we’ve eliminated at least half of all possible orderings from the possible results of final decks after a game of War.
So, if you knew the set of all final orderings after games of War, call it S_w, and a friend handed you 10 decks of cards that they claim are completely randomly shuffled decks that have not been used to play a game of war, you should expect that roughly half of them are in S_w and roughly half are not in S_w. So, if you found that all 10 of them are in S_w, that only has a 1/1024 chance of happening by chance, so your friend is probably lying and probably played a game of war with each of them..
Latest Answers