co.combinatorics - Does War have infinite expected length?

Dear Joel David,
I will try to explain it, but I have to note that article is quite primitive, and is written in a readable English. Moreover there are many figures. But I will try:
I will make a list of statements and then You can mention the number of the non clear one:

1. By our assumption (players do not have strategy and do not have fixed rules how to return cards) the game is a Markov chain.




2. Absorbing (final) state is a state where you stay forever :)
   For us it means the end of the game i.e. the state when one of players has got all cards.

3A. In finite Markov chain, assuming arbitrary initial state, you are absorbed with probability ONE If And Only If "for each vertex of the Markov chain graph there is a way to an absorbing state."

3B. So we have to prove that for the graph of our game of war, there no exists such initial state that players do not have any chance to reach the end.

1. To prove it we should consider first the simplification. Consider the game with cards {1,...,n} i.e. every value meets only once.

We call a vertex attaining if it has got terminal states as its descendants, and wandering otherwise. It is obvious that a descendant of a wandering vertex is again wandering, and an ancestor
of attaining is again attaining.
For an arbitrary oriented graph it is possible that an attaining vertex has got wandering vertices among its descendants. We show that for our graph G it is not so. For that, we need to understand some properties of the graph G.

LEMMA 1.
A: Let state be such that one of the players has got only one
card in his hand, then this state has got exactly one ancestor.

B: If both players have got at least two cards, then this state has got exactly two ancestors.

LEMMA 2. For the graph of the game it holds that a descendant of an attaining vertex is again an attaining vertex.
(Page 5 of the article)

Lemma 3. The states in which one of the players has got only one card are attaining. (page 6)

Lemma 4. Every vertex has got an ancestor that corresponds to the state in which one of the players has got only one card.

Therefore, we have shown that each vertex has got an ancestor that corresponds to the state in which each player has got exactly one card. This state is attaining by Lemma 3. By Lemma 2 descendants of attaining vertices are again attaining, therefore, the initial state is again attaining, and we have proved

Theorem: Graph G does not have any wandering vertices.

---

Now how to apply it to the standard GAME:
We use the following obvious fact: If a subgraph of an oriented graph does not have wandering vertices, then the original graph does not have any wandering vertices either.

Now the proof is similar.

I hope it is better to read the article, I am sorry.
and I want to note once more time, that question of strategy is never been discussed.

---

[Added by J.O'Rourke:]
The paper has appeared: "On Finiteness in the Card Game of War,"
Evgeny Lakshtanov and Vera Roshchina,
The American Mathematical Monthly,
Vol. 119, No. 4 (April 2012) (pp. 318-323).
JSTOR link.