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$.

  • $\begingroup$ 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. $\endgroup$ – 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)}$$

  • $\begingroup$ There is no $n$ in your answer. $\endgroup$ – Lord Shark the Unknown Aug 4 '18 at 5:30
  • $\begingroup$ Thanks for the response. It is not negative binomial because we stop either when we get n ones or k zeros. $\endgroup$ – Cihan T Aug 4 '18 at 23:30
  • $\begingroup$ Ahh that is unfortunate.. $\endgroup$ – воитель Aug 5 '18 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.