1
$\begingroup$

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)

$\endgroup$
9
  • 4
    $\begingroup$ Not sure this is clear. Are you asking for the conditional expectation (conditioned on you being the winner)? Beyond that, this is a variant of the standard Gambler's Ruin $\endgroup$
    – lulu
    Commented Jun 28, 2023 at 12:57
  • $\begingroup$ Also, not sure what "going first" means here. It seems that each turn is entirely symmetric between the two players, right? At each turn, each player either gains or loses a coin with equal chances. $\endgroup$
    – lulu
    Commented Jun 28, 2023 at 13:04
  • $\begingroup$ @lulu Some turns there is no change. $\endgroup$
    – aschepler
    Commented Jun 28, 2023 at 13:05
  • $\begingroup$ @aschepler Ah, thanks. So I misread. If it is $A's$ turn then $A$ can not gain a coin, $A$ either loses it or gets to retain it with equal chances. So, this is not the standard Gambler's Ruin, though the analysis is similar. $\endgroup$
    – lulu
    Commented Jun 28, 2023 at 13:08
  • 2
    $\begingroup$ What does your transition matrix look like? $\endgroup$ Commented Jun 28, 2023 at 13:11

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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.

$\endgroup$
1
  • $\begingroup$ Cheers ! $\;\;$ :) $\endgroup$ Commented Jun 30, 2023 at 6:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .