Find the expected number of tosses to win a game

Question

A friend and I play a game. We each start with two coins. We take it in turns to toss a coin; if it comes down heads, we keep it, if tails, we give it to the other. I always go first, and the game ends when one of us wins by having all four coins. What is the expected number of tosses for me to win this game? (From the simulation, the expected number is 40/3)

Answer 1

Since there are many answers in this thread, I just want to note that the right answer is 40/3, which can be viewed as a consequence of optional stopping theorem; as done in @drobin's self-answer, you can view this as a symmetric random walk on $\{0, ..., 7\}$ with $X_0 = 3$. You can then observe that

• $(X_n)_{n \geq 0}$ is a martingale $\implies$ P(win) = 3/7.
• $(X_n^3 - 3nX_n)_{n \geq 0}$ is a martingale $\implies$ Expected length of a win = $\frac{7^2 - 3^2}{3} = \frac{40}{3}$. (See: Proving a property of hitting times of a simple random walk on $\mathbb{Z}$ for a more thorough walkthrough)

Answer 2

Thanks for trying to answer this question. Here is my solution. In the diagram below,

there are 8 states $p_0, p_1, \cdots, p_7$. The transition matrix with these 8 states is $$ T = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0\\ 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0\\ 0 & 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0\\ 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 & 0\\ 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0\\ 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{bmatrix} $$ Its steady state is [0.04395604, 0.08791209, 0.17582418, 0.26373626, 0.1978022, 0.13186813, 0.06593407, 0.03296703]. As 0.03296703/0.04395604 = 3/4, the chance for me to win this game is 3/7.

To find the expected number of tosses before I win the game I construct another transition matrix after merging $p_0$ and $p_7$ into one state $p_0$: $$ T_2 = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0\\ 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0\\ 0 & 0 & 1/2 & 0 & 1/2 & 0 & 0\\ 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0\\ 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2\\ 1/2 & 0 & 0 & 0 & 0 & 1/2 & 0 \end{bmatrix} $$ To find the expected number of steps from $p_3$ to $p_0$, remove the first row and first column of $T_2$, by letting $$ T_3 = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1/2 & 0 & 0 & 0 & 0\\ 1/2 & 0 & 1/2 & 0 & 0 & 0\\ 0 & 1/2 & 0 & 1/2 & 0 & 0\\ 0 & 0 & 1/2 & 0 & 1/2 & 0\\ 0 & 0 & 0 & 1/2 & 0 & 1/2\\ 0 & 0 & 0 & 0 & 1/2 & 0 \end{bmatrix} $$ we get $(I-T_3)^{-1}\cdot [1, 1, \cdots, 1]^T = [ 6, 10, 12, 12, 10, 6]$. Solving the equation $\frac{3}{7}x + \frac{4}{7}y = 12$, $x>12$ and $y<12$, we have $x = 40/3$ (the expected number of tosses for me to win this game) and $y = 11$ (the expected number of tosses for me to lose this game) which are consistent with the outcome from simulation.