1
$\begingroup$

problem of n success before m failures where binomial probability of success is p has a standard textbook solution as follows $$P = \sum_{k=n}^{m+n-1} \binom{m+n-1}k p^k (1-p)^{m+n-1-k}$$

I am however unable to come up with this solution and i am not sure where i deviate and how?

I start with combinatorial logic that for any t trials

(a) last trial has to be a success => probability of p

(b) in t-1 trials before last trial, n-1 have to be success and (t-1)-(n-1) failures => probability of $\binom{t-1}{n-1} p^{n-1} (1-p)^{t-n}$

Combining (a) and (b) gives me probability that t trials have t-n failures before n success $P_{t} = \binom{t-1}{n-1} p^{n} (1-p)^{t-n}$ I understand that this is negative binomial pmf as well.

From here on, i say that total probability is sum of all the probabilities with various t i.e. $P = \sum_{n}^{m+n-1} P_{t}$ that can be written as $$P = \sum_{t=n}^{m+n-1} \binom{t-1}{n-1} p^{n-1} (1-p)^{t-n} $$

I believe something is off with my last step.. may be these events of different $t$ trials are not mutually exclusive but i am not able to see it.

For example: n = 3 success and m = 2 failures; p = binomial probability

(a) I can have a 3 trial solution SSS with probability $p^3$

(b) 4 trial solution {SSFS,SFSS,FSSS} with probability $ \binom{3}{2} p^{3} (1-p)^1$

(c) 5 trial solution is not possible since n=2 would have happened

I would therefore add probabilities from (a) and (b) as solution but that would give $$ P = p^3 + \binom{3}{2} p^{3} (1-p)^1 $$

and of course, this is not right. Can someone help and point out why this is not correct and what can i fix here?

$\endgroup$
3
  • $\begingroup$ This appears to be a question about a negative binomial random variable. There several versions of negative binomial distributions. Please describe the random variable and carefully define $m, n, p.$ $\endgroup$
    – BruceET
    Apr 2, 2018 at 2:00
  • $\begingroup$ I have added some of these details. Please see if you can answer it now? $\endgroup$
    – toing
    Apr 2, 2018 at 2:11
  • $\begingroup$ I found another link to similar problem. Listing here. math.stackexchange.com/questions/915353/… $\endgroup$
    – toing
    Jun 13, 2020 at 19:04

2 Answers 2

1
$\begingroup$

The book answer (or your transcription of it) appears to be incorrect

By the way, it is simpler to count failures, and look at the results in reverse.
With $0 \le k < m$, the last trial must be a success, and the $k$ failures can be distributed any which way in the remaining $(k+n-1)$ trials, thus

$$P = \sum_{k=0}^{m} \binom{k+n-1}k p^n (1-p)^k$$

If you want to count successes (as the book has done), you should now be able to correct the formula you have transcribed.

$\endgroup$
1
$\begingroup$

I actually came across this similar problem in Bertsekas' "Introduction to Probability" 2nd edition (Ch 6 Exercise 4c), where it was making the same mistake. May I ask which textbook are you referring?

Original formula:

$$P = \sum_{k=n}^{m+n-1} \binom{m+n-1}k p^k (1-p)^{m+n-1-k}$$ The problem of this original formula is that

1) as you vary the iterating variable k, the total number of trials should also be changing, but the term $m+n-1$ is kept constant

2) the failure exponent term $m+n-1-k$ will be counting the right number of failure.

With (1) and (2) above, this original formula is actually accumulating the probability of getting k success and the rest failure while running m+n-1 trials for the range of $k>=n$. This is totally not what the question is asking.

Instead,

I would say the following: minor correction to @{true blue anil}'s formula: $$P = \sum_{k=0}^{m-1} [\binom{k+n-1}k p^{n-1} (1-p)^{k} ]p = \sum_{k=0}^{m-1} \binom{k+n-1}k p^n (1-p)^{k} $$ This is saying that we want to accumulate within the range $0<=k<=m-1$, the probability that there are n successes (last trial is forced to be success, the first n-1 success happen within in the k+n-1 trials, the rest of the k trials are failure).

For you example,

n = 3 success, m = 2 failures, p = prob of success

If we do it by hand,

3 trials: XXP => $p^3$

4 trials: XXXP => $\binom{3}{2}p^2 (1-p) p = \binom{3}{2}p^3 (1-p) $

$P = p^3 + \binom{3}{2}p^3 (1-p) = p^3 +3p^3(1-p)$

And if you apply the formula I have above: $\sum_{k=0}^{m-1} \binom{k+n-1}k p^n (1-p)^{k} $

You would be iterating k = 0 to 1.

So $P = \binom{0+3-1}0 p^3 (1-p)^{0} + \binom{1+3-1}1 p^3 (1-p)^{1} = p^3 + 3p^3(1-p)$, which should agree with the solution by hand.

$\endgroup$
4
  • $\begingroup$ Is this your belief that correct formula should be as noted below by you or have your cross referenced other books and literature. You seem to be correct but i wanted to check before i mark your answer as final answer to question. $\endgroup$
    – toing
    Jun 12, 2020 at 23:41
  • $\begingroup$ I feel fairly comfortable that the steps that I am providing should be right. I am asking you where you came across this problem, so that I can trace if they came from the same source. $\endgroup$
    – gdlamp
    Jun 13, 2020 at 2:33
  • $\begingroup$ unfortunately, this question was posed by me more than 2 years ago. I wish i had made a note / refer to book in original post. I dont have recollection of it any more. $\endgroup$
    – toing
    Jun 13, 2020 at 18:54
  • $\begingroup$ i also found another link to similar problem on stack exchange. Should merge it.math.stackexchange.com/questions/915353/… $\endgroup$
    – toing
    Jun 13, 2020 at 19:03

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.