My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers.
The question is: Is the expected length of the game infinite?
The Rules. (from http://en.wikipedia.org/wiki/War_(card_game)) The deck is divided evenly among the two players, giving each a face-down stack. In unison, each player reveals the top card on his stack (a "battle"), and the player with the higher card takes both the cards played and moves them to the bottom of his stack. If the two cards played are of equal value, each player lays down three face-down cards and a fourth card face-up (a "war"), and the higher-valued card wins all of the cards on the table, which are then added to the bottom of the player's stack. In the case of another tie, the war process is repeated until there is no tie. A player wins by collecting all the cards. If a player runs out of cards while dealing the face-down cards of a war, he may play the last card in his deck as his face-up card and still have a chance to stay in the game.
Let us assume that the cards are returned to the deck in a well-defined manner. For example, in the order that the cards are played, with the previous round's winner's cards going first (and a first player selected for the opening battle).
On the Wikipedia page, they tabulate the results of 1 million simulated random games, reporting an average length game of 248 battles. But this does not actually answer the question, because it could be that there is a devious initial arrangement of the cards leading to a periodic game lasting forever. Since there are only finitely many shuffles, this devious shuffle will contribute infinitely to the Expected Value. Thus, the question really amounts to:
Question. Is there a devious shuffle in War, which leads to an infinitely long game?
Of course, the game described above is merely a special case of the more general game that might be called Universal War, played with N players using a deck of cards representing elements of a finite partial pre-order. Any strictly dominating card wins the trick; otherwise, there is war amongst the players whose cards were not strictly dominated. Does any instance of Universal War have infinite expected length?
