High Stakes Coin Flipping

At some point, let the number of coins that Xavier has be x , the number of coins that Yvonne has be y and the number of coins that Zac has be z . When someone has 0 coins, the product of the number of coins of the players will be 0. Therefore let's calculate the expected product at the beginning of the turn after $(x,y,z)$ . The probability that all are heads or all are tails is $\frac{1}{4}$ and the remaining 3 options are all equally likely, and thus each must also have probability of $\frac{1}{4}$ . Therefore the expected product, E, is: $E = (\dfrac{1}{4})(xyz + (x-1)(y-1)(z+2) + (x-1)(y+2)(z-1) + (x+2)(y-1)(z-1))$ Simplifying this whole thing we achieve: $E = xyz + \dfrac{1}{4}(6-3(x+y+z))$ But we know that $x+y+z=102$ irrespective of their product. Therefore $E = xyz + \dfrac{1}{4}(6-306)$ so $E = xyz - 75$ . Therefore the expected change of the product is 75, irrespective of what the product is at any point in the game. Since the initial product is 33,000 and the product is expected to decrease by 75 every turn, it will take $\dfrac{33000}{75} = \fbox{440}$ turns until we expect the product to first be zero and thus until we expect the game to end.

Assume the random variables $X_n,Y_n,Z_n$ denote their respective number of coins after $n$ plays. We have the invariant $X_n+Y_n+Z_n=50+30+22=306$ , valid for all $n\geq 1$ .

Define a new sequence of random variables $\zeta_n=X_nY_nZ_n + 75n$ , $n\geq 1$ . Now we'll show that $\{\zeta_n\}_{n\geq 1}$ is a Martingale sequence , w.r.t. the natural filtration $\mathcal{F}_n = \sigma ( X_1,X_2,\ldots X_n; Y_1,Y_2, \ldots Y_n; Z_1,Z_2,\ldots Z_n), n\geq 1$

Since $X_n, Y_n, Z_n$ are non-negative w.p. 1, A.M.-G.M inequality tells us that $X_n Y_n Z_n \leq (102)^3$ w.p. 1. Hence, $\mathbb{E}\zeta_n < \infty$ $,\forall n \geq 1$ .

Also, $\mathbb{E}(\zeta_{n+1}| \mathcal{F}_n) = \mathbb{E} (X_{n+1}Y_{n+1}Z_{n+1} + 75(n+1) | \mathcal{F}_n)$ $= \frac{1}{4} (X_nY_nZ_n + (X_n+2)(Y_n-1)(Z_n-1) + (X_n-1)(Y_n+2)(Z_n-1)$ $+ (X_n-1)(Y_n-1)(Z_n+2))$

$= \frac{1}{4} (4X_nY_nZ_n -3(X_n+Y_n+Z_n)+6)$ $= X_nY_nZ_n + 75n = \zeta_n$

The above steps show that indeed $\{\zeta_n\}_{n\geq 1}$ is a Martingale sequence.

Let $T$ be the random time denoting the length of this game. Now, it is easy to see that $T$ is a stopping time w.r.t. the filtration $\mathcal{F}_n$ defined above.

Finally we can use the Optional Stopping Theorem (assuming finite expectation for $T$ , the condition (b) is satisfied here) to conclude that $\mathbb{E}(\zeta_T) = \mathbb{E}(\zeta_0) = X_0Y_0Z_0 = 50\times 30 \times 22$

However, we know that at time $T$ at least one of $X_T, Y_T, Z_T$ is zero. Hence, $\mathbb{E}(\zeta_T)=0+75 \mathbb{E}(T)$ . Hence, we get

$\mathbb{E}(T) = \frac{50\times 30 \times 22}{75}= 440$

First observe that there is $6/8$ chance of progress and a $2/8$ chance of no-progress (triple head or triple tail). WLOG, reduce the problem to look at the successful tosses only and then correct the answer by multiplying with $8/6$ .

Let $E(i;j;k)$ denote the expected number of tosses, starting with respectively $i, j,$ and $k$ coins, where $i,j,k$ denote non-negative integers and $i+j+k>2$ .

Theorem $E(i;j;k)=\frac{i.j.k}{i+j+k-2}$

Proof

If a player has zero coins, the game is finished and the expected number of (successful) tosses equals $0$ : $E(i;j;0)=\frac{i.j.0}{i+j-2}=0$

and similar for $i=0$ or $j=0$ .

If two of the players are left with a single coin, there will remain exactly one successful toss with probability $1$ . This is in accordance with the suggested formula: $E(i;1;1)=\frac{i.1.1}{i+1+1-2}=1;$

$E(1;j;1)=\frac{1.j.1}{1+j+1-2}=1;$

$E(1;1;k)=\frac{1.1.k}{1+1+k-2}=1$

For all other combinations of coins: $E(i;j;k) =$

$=1+\frac{E(i+2;j-1;k-1)+E(i-1;j+2;k-1)+E(i-1;j-1;k+2)}{3}$

$= 1+\frac{(i+2)(j-1)(k-1)+(i-1)(j+2)(k-1)+(i-1)(j-1)(k+2)}{3(i+j+k-2)}$

$= 1+\frac{ijk-ij-ik+2jk+i-2j-2k+2+ijk-ij+2ik-jk-2i+j-2k+2+ijk+2ij-ik-jk-2i-2j+k+2}{3(i+j+k-2)}$

$=1+\frac{3ijk-3i-3j-3k+6}{3(i+j+k-2)}$

$=1+\frac{ijk}{i+j+k-2}-1=\frac{ijk}{i+j+k-2}$

So, all the possible situations and their 3 possible sequels after a (successful) toss are in accordance with the formula.

Therefore, $E(50;30;22)=\frac{50*30*22}{50+30+22-2}=5*3*22=330$ . The solution of this problem is, as described in the first alinea, $\frac{8}{6}*330=440$ .

$$ This problem is basically a gambler's ruin problem. I've spent a day to learn this topic in my college library and solve this problem by using standard Markov chain methods. Since that method seems sophisticated, I wouldn't explain it here. Actually, there is already a solution of gambler's ruin for $3$ players. Let $a$ , $b$ , and $c$ be the initial capitals, then the expected of the game duration $T_1$ if each player has probability of win $\dfrac{1}{3}$ (without draw system) is $$ $\text{E}[T_1]=\frac{abc}{a+b+c-2}.$ $$ If the draw system is also included, then each player has probability of win $\dfrac{1}{4}$ . Let us turn attention to the symmetric $3$ -player game: $$ $(a,b,c) \mapsto \left\{ \begin{array}{l l} (a,b,c) & \quad \text{if the game is draw with probability}\frac{1}{4},\\ (a+2,b-1,c-1)& \quad \text{if player 1 wins with probability}\frac{1}{4},\\ (a-1,b+2,c-1)& \quad \text{if player 2 wins with probability}\frac{1}{4},\\ (a-1,b-1,c+2)& \quad \text{if player 3 wins with probability}\frac{1}{4}.\\ \end{array} \right.$ $$ Or you can see the total possible outcomes if we throw $3$ coins: $$ $\text{{HHH,TTT, HTT, THH, HTH, THT, HHT, TTH}}$ $$ The probability of draw is $\frac{2}{8}$ , $\text{HHH}$ and $\text{TTT}$ , and the probability of each player wins is $\frac{2}{8}$ , $\text{HTT, THH}$ or $\text{HTH, THT}$ or $\text{HHT, TTH}$ . The expected number of rounds until one of the gamblers is ruined or goes broke for the symmetric $3$ -player is simply $$ $\text{E}[T_2]=\frac{4}{3}\left(\frac{abc}{a+b+c-2}\right).$ $$ The formula above can be seen as this simple inversely proportion: if the symmetric $3$ -player game where each player has chance to win the game $\dfrac{1}{3}$ its expected of the game duration is $\text{E}[T_1]$ , then for the symmetric $3$ -player game where each player has chance to win the game $\dfrac{1}{4}$ its expected of the game duration is $\text{E}[T_2]$ , therefore $$ $\dfrac{1}{3}\cdot\text{E}[T_1]=\dfrac{1}{4}\cdot\text{E}[T_2].$ $$ Logically, when the draw system is included, the game duration tends to be longer than without using draw system. Thus, based on the formula above, the expected of the game duration is $$ $\text{E}[T]=\frac{4}{3}\left(\frac{50\cdot30\cdot22}{50+30+22-2}\right)=\boxed{440}.$ $$ For advance study and to understand more comprehensive this problem, I really recommend you to read a very nice article "A game with three players" by D. Sandell, 1988 and also see $3$ -tower problem (or Hanoi tower problem ). Anyway, you can try the gambler's ruin simulation for $2$ players with this Wolfram Demonstrations Project . Have fun! $$

The Gambler's Ruin Simulation

$\text{\# }\mathbb{Q.E.D.}\text{ \#}$

In a move there are 8 possibilities in 2 of which there is no change(all heads or all tails), and 2 cases each where one of the 3 picks up 3 coins. 1/4 probability of no change, 1/4 for X picking 3, 1/4 for Y picking 3, 1/4 for Z picking 3. if initially they have i,j,k coins, after n moves X has 1/4 probability of having i, 1/2 probability of having (i-n), 1/2 probability of having (i+2n) Expectation value of i after n moves is 1/4 i + 1/2 (i-1)+1/4 (i+2) = i....no change ! same for j and k. They appear to be expected not to change at all. But the product ijk is expected to change. after n moves expected ijk = 1/4 (ijk) + 1/4 (i-n)(j-n)(k+2n) + 1/4 (i-n)(j+2n)(k-n) + 1/4 (i+2n)(j-n)(k-n) = ijk + 1/4 (6n - 3n(i+j+k))=ijk + n/4(6-306)=ijk-75n if the expectation value is zero, ijk-75n = 0 Initial ijk = 33000. so n= 440