Expected total number of flips for a game.

expected valueprobability

Consider there's a game:

  • Player A flips a fair coin until a tail comes up.
  • Player B flips a fail coin until getting the same number of heads as A in a row.

Question: what is the expected number of flips in the game?

My thought: If A flips $a$ times and get the first tail, B needs to get $a-1$ consecutive heads, denote the number of times B flips as $b$, it is known that $E_a[B] = 2^a-2$.
To calculate the expected total flips,
$$E[a+b] = \sum_{i=1}^{\infty}\frac{1}{2^i}(i+2^i-2)$$
which is divergent.

Is that correct?

Best Answer

Let $N$ denote the total number of flips in the game, $N_A$ the number of flips of player $A$ and $N_B$ the number of flips of $B$. Furthermore, denote with $H_A$ the number of heads flipped by $A$. We seek

$$\mathbb{E}[N]=\mathbb{E}[N_A+N_B]=\mathbb{E}[N_A]+\mathbb{E}[N_B].$$

Note that $N_A\sim\text{Geom}\,(1/2)$ so $\mathbb{E}[N_A]=1/(1/2)=2$. Also, $$ \mathbb{E}[N_B]=\mathbb{E}[\mathbb{E}[N_B\vert H_A]]=\sum_{n=1}^\infty\mathbb{E}[N_B\vert H_A=n]\mathbb{P}(H_A=n)=\sum_{n=1}^\infty\mathbb{E}[N_B\vert H_A=n]\left(\frac12\right)^{n+1}. $$ To compute $\mathbb{E}[N_B\vert H_A=n]$, consider the trivial case $n=2$. How many flips does $B$ need to make to obtain $2$ heads? The first head follows a geometric distribution and so does the second. In general, the sum of geometric R.V.s is a Negative Binomial with parameter $n$ and $p$, therefore the desired expectation is the mean of a NBD, $$\mathbb{E}[N_B\vert H_A=n]=n/(1/2)=2n.$$ It follows $$\mathbb{E}[N_B]=\sum_{n=1}^\infty2n\left(\frac12\right)^{n+1}=\sum_{n=1}^\infty n\left(\frac12\right)^n=\underbrace{\sum_{n=1}^\infty n\left(\frac12\right)^{(n-1) }\frac12}_{\text{mean of Geom(1/2)}}=2.$$ Thus, $$\mathbb{E}[N]=\mathbb{E}[N_A]+\mathbb{E}[N_B]=2+2=4.$$

Edit:

I misread the problem, the above works for player $B$ flipping $H_A$ heads in total, not in a row. It suffices to make a small adjustment. Let us make a slight generalization. Denote with $X_i$ the total number of successes attained up to the first time there have been $i$ consecutive successes, and with $A_{k-1,k}$ the number of additional successes aftet there have been $k-1$ successes in a row until there have been $k$ in a row. It follows $$X_k=X_{k-1}+A_{k-1,k}\implies \mathbb{E}[X_k]=\mathbb{E}[X_{k-1}]+\mathbb{E}[A_{k-1,k}].$$ Now, note that if we have accumulated $k-1$ successes and if the next one is a success (with probability $p$) then we are done, if not, we start all over again. So $$\mathbb{E}[A_{k-1,k}] = 1\cdot p+(1-p)\mathbb{E}[X_{k}+1]$$ substituting and simplfying yields

$$\mathbb{E}[X_k]=\frac1p+\frac{\mathbb{E}[X_{k-1}]}p.$$ Using the fact that $\mathbb{E}[X_1] = 1/p$, we have that the expectation of $k$ successes is $$\mathbb{E}[X_k]=\frac1p+\frac1{p^2}+\cdots+\frac1{p^k}.$$

Now, going back to our problem we have

$$\mathbb{E}[N_B\vert H_A=n]=\sum_{i=1}^n2^i=2^{n+1}-2.$$ So $$\mathbb{E}[N_B]=\sum_{n=1}^\infty\left(2^{n+1}-2\right)\left(\frac12\right)^{n+1}=\infty.$$

Edit 2:

I wrote a really basic simulation of the exercise in python to test the result above. It indeed seems to diverge.

import random


for i in range(1,7):
    sumNs = 0
    sims = 10**i
    
    for j in range(sims):
        N_A = 0
        N_B = 0
        H_A = 0
        N = 0
        #counts the heads in a row
        count_head = 0

        while True:
            # 0 = Tails, 1 = Heads
            coin_flip = int(2*random.uniform(0, 1))
            N_A += 1
            if coin_flip == 0:
                break
            else:
                H_A += 1

        if H_A != 0:
            while True:
                coin_flip = int(2*random.uniform(0, 1))
                N_B += 1
                if coin_flip == 1:
                    count_head += 1
                    if count_head == H_A:
                      break
                else:
                    count_head = 0
            
        else:
            continue

        N = N_A + N_B
        sumNs += N

    print(str(i)+". Simulations: "+str(sims)+". E[N]: "+str(sumNs/sims))

output

Related Question