## The Markovian State Space of War

When I was a kid, one of my favorite card games was War. In retrospect, I don’t really understand why I got so much enjoyment out of it, given that there is absolutely no strategy to the game whatsoever. If you happened to miss this game during your childhood, the rules are simple:

The deck is divided evenly between the players face-down. Each player reveals his top card, and the player with the higher card puts both the cards on the bottom of his deck. If the cards are of equal value, each player plays three face-down cards and a fourth face-up card, and the higher-valued card wins all the cards on the table. This is known as a war. In the case of another tie, the 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 face-up and still have a chance to stay in the game.

As you can see, since the player has no knowledge of which cards are in their initial hand, and no choice in which cards to play, this game could just as easily be played by a properly trained parakeet. The mechanical gameplay and lack of strategy, however, makes certain questions about the game mathematically interesting.

The other day when this game popped into my head, one of the first things I remembered about it was how many games I left unfinished due to their sheer length. I suddenly became curious about the expected number of turns required to finish a game of War.

It turns out that the answer is “about 277” (which is considerably less than I expected). You see, people on the Internet tend to be pretty big nerds, and certainly I wasn’t the first one to consider writing a War simulation to figure out these kind of statistics. What I didn’t see discussed, though, is any treatment of the structure of a game of war.

## Monty Hall is Falling Down

Today’s entry on Jeff Atwood’s weblog, “Coding Horror” talks about the time-honored probability puzzler known as the Monty Hall problem. If you are unfamiliar with the problem, it deals with devising the optimal strategy for playing a game that was common on the game show “Let’s Make a Deal“, starring Monty Hall, and has a solution that is commonly perceived as unintuitive.

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice? (Whitaker 1990)

This, much like airplane on a treadmill, and 0.999… == 1 are common topics of long, drawn-out arguments on the Internet. But what I want to talk about is not the problem itself (which has been done to death), or Jeff’s post. Rather, I want to discuss a variant problem humorously called the “Monty Fall Problem” proposed by Professor Jeffrey S. Rosenthal of the University of Toronto, which is included in an article titled “Monty Hall, Monty Fall, Monty Crawl”, which was linked from the Coding Horror article.