# The probability distribution of the number of coin flips needed to get $n$ heads or $k$ tails

Suppose we are flipping a fair coin. Let n,k be fixed numbers. We flip the coin until we get a total of n heads or a total of k tails. What is the probability distribution of the number of coin flips needed to get n heads or k tails? If it is easier, what is the expectation? The support of this discrete distribution is from the min(n,k) to n+k-1.

The probability of getting the $n$-th head on the $r$-th toss, is that of the $r$-th toss being a head, and exactly $n-1$ of the first $r-1$ tosses being heads, that is $p_r= 2^{-r}\binom{r-1}{n-1}$. In this case this probability is only relevant if $r-n<k$. There is a similar formula for the probability that the $k$-th tail occurs on the $r$-th toss, that is $q_r=2^{-r}\binom{r-1}{k-1}$. So the probability you seek is $p_r+q_r$ if $n\le r<k+n$ and $k\le r<k+n$, is $p_r$ if $n\le r<k+n$ and $k>r$ and is $q_r$ if if $k\le r<k+n$ and $r>k$.

• Thank you! I think this is right. Is there a name for this distribution? I want to find a closed form for its expectation. Also, is there a way to find a multinomial version. By that I mean instead of a coin flip, we can have a roll of a die. We stop if we get k1 ones, or k2 twos etc until k6 sixes. It is probably elementary to figure it all out, but I was wondering if it had a name so that I can lookup properties, asymptotics etc. Thanks again. – Cihan T Aug 4 '18 at 23:34

This is a negative binomial distribution.

Suppose that $X \sim NegBin(r;p)$

The probability mass function is given as

$$f(k;r,p) \equiv Pr(X=k) = \binom{k+r-1}{k}p^{k}(1-p)^{r}$$

where $k$ is the number of successes and $r$ is the number of failures with probability $p$

We have

$$E(X) = \frac{r}{p}$$

In your specific case we have

$$X \sim NegBin(k;p)$$

Then our mass function is $$f(n;k,p) \equiv Pr(X=n) = \binom{n+k-1}{n}p^{n}(1-p)^{k}$$

where we have $n$ heads and $k$ tails. Given that you said it was fair $p =\frac{1}{2}$

$$f(n;k,p) \equiv Pr(X=n) = \binom{n+k-1}{n}(\frac{1}{2})^{n}(\frac{1}{2})^{k}$$ $$f(n;k,p) \equiv Pr(X=n) = \binom{n+k-1}{n}(\frac{1}{2})^{n+k}$$ $$f(n;k,p) \equiv Pr(X=n) = \binom{n+k-1}{n}2^{-(n+k)}$$

• There is no $n$ in your answer. – Angina Seng Aug 4 '18 at 5:30
• Thanks for the response. It is not negative binomial because we stop either when we get n ones or k zeros. – Cihan T Aug 4 '18 at 23:30
• Ahh that is unfortunate.. – user3417 Aug 5 '18 at 0:18