# Expected Number of Flips to Obtain n heads and m tails

I am trying to work through this problem from Sheldon's 10th Ed., 7.61. It states

A coin that comes up heads with probability p is continually flipped. Let N be the number of flips until there have been both at least n heads and at least m tails. Derive an expression for E[N] by conditioning on the number of heads in the first n + m flips.

Following their suggestion, if we let H be the number of heads obtained in the first $$n+m$$ flips, then $$E[N]=\sum_{j=0}^{n+m} E[N|H=j]P\{H=j\} = \sum_{j=0}^{n+m} E[N|H=j]\binom{n+m}{j}p^j(1-p)^{n+m-j}$$ Clearly, $$n+m$$ is the minimum number of flips required to obtain n heads and m tails, and if we assume that we have already obtained h heads, then we need $$n-h$$ more, while we must already have $$n+m-h$$ tails, so we need $$m-(n+m-h)=h-n$$ more. However, at that point I am stuck; it seems to me that I have not reduced the complexity of the problem since in obtaining $$n-h$$ more heads, we may or may not obtain $$h-n$$ more tails, and vice versa. I have access to the answer, and it states that $$\sum_{j=0}^{n+m} E[N|H=j]\binom{n+m}{j}p^j(1-p)^{n+m-j}=\sum_{j=0}^n \left(n+m+\frac{n-j}{p}\right)\binom{n+m}{j}p^j(1-p)^{n+m-j} + \sum_{j=n+1}^{n+m} \left(n+m+\frac{j-n}{1-p}\right)\binom{n+m}{j}p^j(1-p)^{n+m-j}$$ However, I cannot make the mental leap and see how $$E[N|H=j]=\left(n+m+\frac{n-j}{p}\right)$$ when $$0≤j≤n$$ and $$E[N|H=j]=\left(n+m+\frac{j-n}{1-p}\right)$$ when $$n+1≤j≤n+m$$.

• Note that, with $n+m$ trials you must have completed one of your tasks and either you completed the other one on the last toss or you still have more to go on that one.
– lulu
Commented Mar 3, 2023 at 0:25
• should say: it's hard to follow what you wrote since you have $h$ as the summation variable but then your expressions depend on the undefined variable $j$. Perhaps you meant $h=j$?
– lulu
Commented Mar 3, 2023 at 0:27
• My apologies, when I worked it I used h as the number of heads, but Ross used j. I will fix it. Also, why would we necessarily be close to finishing a task? Suppose we had n+m-1 heads and only one tail? We would still have at least m-1 tails to go? Commented Mar 3, 2023 at 0:49
• If the number of Heads is $<n$ and the number of Tails is $<m$ then you can't have tossed the coin $n+m$ times.
– lulu
Commented Mar 3, 2023 at 0:50
• Take $h<n$. Then you have finished Tails but need $n-h$ more Heads. We know how long we expect it to take to do that...
– lulu
Commented Mar 3, 2023 at 0:56

I finally understood what lulu was trying to tell me (see the comments on the original post). If $$j, then we can be sure that $$n+m-j>m$$, so we have enough tails and we need only consider how many trials to get $$n-h$$ more heads. This is a negative binomial random variable and therefore has an expected value of $$\frac{n-j}{p}$$, so the expected number of total flips – which is $$E[N|H=j]$$ – is $$n+m+\frac{n-j}{p}$$.
Likewise, if $$j≥n$$, then we can be sure that we have enough tails and we need only consider how many trials to get $$h-n$$ more tails. The expected value of the additional number of flips is $$\frac{j-n}{1-p}$$ for a total number of flips $$n+m+\frac{j-n}{1-p}$$.