The Problem of the Points 計點問題

Example (The Problem of the Points)
Independent trials, resulting in a success with probability p and a failure with probability 1-p, are performed. What is the probability that nsuccesses occur before m failures? If we think of A and B as playing a game such that A gains 1 point when a success occurs and B gains 1 point when a failure occurs, then the desired probability is the probability that A would win if the game were to be continued in a position where A needed n and B needed m more points to win.
Solution:
Here, we present two solutions.
(i)
Let Pn,m the probability that n successes occur before m failures. By conditioning on the outcome of the first trial we obtain:
$P_{n,m}=pP_{n,m-1}+(1-p)P_{n,m-1}\qquad n\geq 1, m\geq 1$
By using the obvious boundary conditions Pn,0=0, P0,m=1, these equations can be solved for Pn,m.
(ii)
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.
On the other hand, if there were fewer than n successes in the first m+n-1trials, 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 nsuccesses would not occur before m failures.
Hence, as the probability of exactly k successes in m+n-1 trials is, ${m+n-1 \choose k}p^k(1-p)^{m+n-1-k}$, we see that the desired probability of n successes before m failures is
$\displaystyle P_{n,m}=\sum_{k=n}^{m+n-1}{m+n-1\choose k}p^k(1-p)^p{m+n-1-k}$         $\rule[0.02em]{1.0mm}{1.5mm}$

Example
As an illustration of the problem of the points suppose that 2 players each put up $\$A$ and each of them has an equal chance of winning each point (p=1/2). If n points are required to win and the first player has 1 point and the second none, then the first player is entitled to

$\displaystyle2AP_{n-1,n}=2A\sum_{k=n-1}^{2n-2}{2n-2\choose k} \left (\frac{1}{2}\right )^{2n-2}$
Now,
$\begin{array}{rcl} \displaystyle\sum_{k=n-1}^{2n-2}{2n-2\choose k}&=& \sum_{k=n... ...n-2}{2n-2\choose 2n-2-k} \\ \\ &=&\sum_{i=0}^{n-1}{2n-2\choose i} \end{array}$
where the last identity follows from the substitution i=2n-2-k.Thus
$\begin{array}{rcl} \displaystyle2\sum_{k=n-1}^{2n-2}{2n-2\choose k}&=& \sum_{k=... ...hoose k}+{2n-2\choose n-1} \\ \\ &=&(1+1)^{2n-2}{2n-2\choose n-1} \end{array}$
and so the first player is entitled to
$\displaystyle A\left [ 1+\left (\frac{1}{2}\right )^{2n-2}{2n-2\choose n-1}\right ]$         $\rule[0.02em]{1.0mm}{1.5mm}$