Saturday, June 1, 2013

When the game ends? (I)

Question: Consider a two-players' game.  Both players have equal chance of winning at each round. The game ends if one player wins two more rounds than the other.  What is the probability function for the number of rounds?

AA
BB
ABAA
ABBB
BAAA
BABB
ABABAA
ABABBB
ABBAAA
ABBABB
BAABAA
BAABBB
BABAAA
BABABB
......
Possible scenarios

Answer: Let $N$ be the number of rounds. $N$ cannot be odd, otherwise the difference of rounds won by the two players could not be 2.
Therefore $N$ is even, say $N=2k$. Each player has to win exactly one of $2r-1$-th and $2r$-th round for $1\le r\le k-1$ and then one player has to win the last two games.
In other words, the pattern should be $[..][..]...[..](..)$, the first $k-1$ $[..]$'s should be AB or BA, and the last $(..)$ is AA or BB.
Summing up, we know

$P(N=2k-1)=0, P(N=2k)=(1/2)^k$ for $k=1,2,\ldots$

The game most likely ended in 2 rounds, but the expected number of rounds is $\sum_{k=1}^\infty\frac{2k}{2^k}=4$.