Independent trials resulting in a success with probability $p$ and a failure with probability
$1 − p$ are performed. What is the probability that $n$ successes occur before $m$
failures?
Given solution :
$$P = \sum_{k=n}^{m+n-1} \binom{m+n-1}k p^k (1-p)^{m+n-1-k}$$
Explanation given : Fermat argued that, in order for $n$ successes to occur before $m$ failures, it is necessary
and sufficient that there be at least $n$ successes in the first $m + n − 1$ trials.
(Even if the game were to end before a total of $m + n − 1$ trials were completed, we
could still imagine that the necessary additional trials were performed.) This is true,
for if there are at least $n$ successes in the first $m + n − 1$ trials, there could be at
most $m − 1$ failures in those $m + n − 1$ trials; thus, $n$ successes would occur before
$m$ failures. If, however, there were fewer than n successes in the first $m + n − 1$
trials, there would have to be at least $m$ failures in that same number of trials; thus, $n$
successes would not occur before $m$ failures. Hence the probability is as above.
My solution :
$$P = \sum_{k=0}^{m-1} \binom{n+k}n p^n (1-p)^k$$
I consider all the possible permutations where the $n$ success occur before $m$ failures. I really can't see what's wrong here.
This is the same as interpretation C here and no interpretation of that answer matches the given solution.
So, how is the given solution correct in comparison to mine?
Best Answer
The events represented by the terms of your summation are not pairwise disjoint. Consider, for example, the outcome in which the first $n$ trials are successes; that situation is counted both in the $k=0$ term and in the $k=1$ term, since the latter includes the sequence of $n$ successes followed by $1$ failure.
We can also use the fact that
$$\sum_{k\ge 0}\binom{n+k}nx^k=\frac1{(1-x)^{n+1}}$$
to observe that if $p=\frac12$, then
$$\sum_{k\ge 0}\binom{n+k}np^n(1-p)^k=\frac1{2^n}\cdot\frac1{(1/2)^{n+1}}=2\;,$$
so your summation must be greater than $1$ for sufficiently large $m$; this doesn’t explain why it’s wrong, but it does show that it can’t be right.