Let $T_{n,m}(p)=\sum_{j=0}^{m-1} \binom{n+j-1}{j}p^j$. In answering a recent question, I discovered the identity

$$ (1-p)^n T_{n,m}(p)+ p^m T_{m,n}(1-p)=1 \tag{1} $$

Is there a nice combinatorial proof or interpretation of (1) ? ($p$ looks a lot like the probablity of something in this formula, doesn't it.) I've got a feeling that this question is a duplicate of an already existing question, but my search was unsuccessful.

UPDATE : as explained in orangeskid's answer to the abovelinked question, (1) can be nicely derived by expanding Newton's binomial in $(p+(1-p))^{n+m-1}=1$. But this is still more computational than really combinatoric/probabilistic, I'm still waiting for a more direct interpretation of $T_{n,m}(p)$ and (1).


If we take $p$ as the probability of success of a sequence of i.i.d. Bernoulli trials, then

$$ (1 - p)^nT_{n, m}(p) = \sum_{j=0}^{m-1} \binom {n + j - 1} {j}p^j(1-p)^n$$

is the probability that having less than $m$ successes before the $n$-th failures. Similarly,

$$ p^mT_{m, n}(1 - p) = \sum_{j=0}^{n-1} \binom {m + j - 1} {j}(1-p)^jp^m$$

is the probability that having less than $n$ failures before the $m$-th successes.

These two are complementary events - you either reach the $m$-th success first, or the $n$-th failure first, and you cannot have them together in the same trial. So their probabilities sum up to $1$.

P.S. These are well known negative binomial CDFs.

  • $\begingroup$ Could you elaborate a little more ? Your interpretations are not obvious from the formulas. For example, what does the $j$ index represent in each situation ? $\endgroup$ – Ewan Delanoy Mar 15 '18 at 11:58
  • $\begingroup$ It depends on $j$ is in the exponent of $p$ or $1 - p$. For example, for the first term, each summand is a pmf of a negative Binomial, which can be interpreted as the probability of having exactly $j$ success before the $n$-th failure. To see this, write the summand as $\displaystyle \binom {n + j - 1} {j} p^j (1-p)^{n-1} \times (1 - p)$. Note that the $n$-th failure must be located at the $n+j$-th trial. Then the number of ways to arrange $j$ successes and $n-1$ failures in the first $n+j-1$ trials is the leading binomial coefficient, and hence the summand is derived. $\endgroup$ – BGM Mar 15 '18 at 15:23

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.