Q.7.26 - A First Course in Probability

Question

A coin that comes up heads with probability p is flipped until either a total of n heads or of m tails is amassed. Find the expected number of flips. Hint: Imagine that one continues to flip even after the goal is attained. Let X denote the number of flips needed to obtain n heads, and let Y denote the number of flips needed to obtain m tails. Note that max(X, Y) + min(X, Y) = X + Y. Compute E[max(X, Y)] by conditioning on the number of heads in the first n + m − 1 flips. 

Step-by-Step Solution

Answer

The expected number of flips will be $E[min(X,Y\left)\right]=\frac{n}{p}+\frac{m}{1-p}-E\left[M\right]$.

Step 1: Given information

A coin that comes up heads with probability p is flipped until either a total of n heads or of m tails is amassed. 

Step 2: Solution

From the given information we need to calculate the results,

$min(X,Y)+max(X,Y)=X+Y$

$min(X,Y)=X+Y-max(X,Y)$

$E[min(X,Y\left)\right]=E\left[X\right]+E\left[Y\right]-E[max(X,Y\left)\right]$

The expectation values of X and Y are given as follows:

$E\left[X\right]=\frac{n}{p}$

$E\left[Y\right]=\frac{m}{1-p}$

conditioning on N, E[M] is given below,

$E\left[M\right]=\sum E[M\mid N=i]P\{N=i\}$

Step 3: Solution

If $i<n$ then $n-i$ heads need to be obtained,

If $i>n$ then $m-(n+m-1-i)$ tails need to be obtained.

So,

$E\left[M\right]=\sum _i E[M\mid N=i]P\{N=i\}$

$=\sum _{i=0}^{n-1} E[M\mid N=i]P\{N=i\}+\sum _{i=n}^{n+m-1} E[M\mid N=i]P\{N=i\}$

$=\sum _{i=0}^{n-1} \left(n+m-1+\frac{n-i}{p}\right)P\{N=i\}+\sum _{i=n}^{n+m-1} \left(n+m-1+\frac{i+1-n}{1-p}\right)P\{N=i\}$

Now simplify the equation we get,

$E\left[M\right]=n+m-1+\sum _{i=0}^{n-1} \frac{n-i}{p}\left(\begin{array}{c}n+m-1\\ i\end{array}\right)p^i(1-p{)}^{n+m-1-i}+\sum _{i=n}^{n+m-1} \frac{i+1-n}{1-p}{p}^i(1-p{)}^{n+m-1-i}$

Step 4: Solution

now we need to solve by using the above results,

$E[min(X,Y\left)\right]=E\left[X\right]+E\left[Y\right]-E[max(X,Y\left)\right]$

$=\left(\begin{array}{l}\frac{n}{p}+\frac{m}{1-p}-n-m+1-\sum _{i=0}^{n-1} \frac{n-i}{p}\left(\begin{array}{c}n+m-1\\ i\end{array}\right)p^i(1-p{)}^{n+m-1-i}\\ -\sum _{i=n}^{n+m-1} \frac{i+1-n}{1-p}{p}^i(1-p{)}^{n+m-1-i}\end{array}\right)$

$=\frac{n}{p}+\frac{m}{1-p}-E\left[M\right]$

Thus the result is 

$E[min(X,Y\left)\right]=\frac{n}{p}+\frac{m}{1-p}-E\left[M\right]$

Step 5: Final answer

The expected number of flips will be $E[min(X,Y\left)\right]=\frac{n}{p}+\frac{m}{1-p}-E\left[M\right]$.