SIAM REVIEW  ◯^{c}1993 Society for Industrial and Applied Mathematics

Vol. 35, No. 2, pp. 294–297, June 1993 005

A COMBINATORIAL IDENTITY AND THE WORLD SERIES*

TAMÁS LENGYEL†

Abstract. In this note the author gives a simple probabilistic proof of a combinatorial identity by calculating the winning probability in the World Series. The winning probabilities and the expected length of the championship series are given by the applications of the identity and its generalization.

Key words. combinatorial identities, asymptotic identities, championship series

AMS(MOS) subject classifications. 60C05, 05A19, 05A15, 05A16, 90D60

1. Introduction. We give a probabilistic proof of a classical combinatorial identity and find the winning probabilities and the expected length of World Series–type games. There are Teams A and B to play no more than 2n − 1 games to decide a champion. Each single game ends in no tie. These rules apply to the World Series and the NBA play–offs as well with n = 4. Suppose that in each game Team A (Team B) has a probability p (q = 1 − p) of winning and the outcomes of the games are independent. The winner is the first team to collect n victories. The length of the series is denoted by the random variable W_{n}(p). The expected length, EW_{n}(p), of the series can be determined by classical combinatorial or hypergeometric summation [2] if p = 1/2. For short, let EW_{n} = EW_{n}(1/2). The problem of determining EW_{4} appears, for example, in [3, Question 3.8.14, p. 162] in the context of the usual best 4 of 7 series. In this note we use a simple method to calculate EW_{n}(p). An asymptotic formula is given for EW_{n}(p) in identity (7). Some related results have been proven in [5].

We start with the classical combinatorial identity [2, (5.20) p. 167]

(1)  ∑_{k=0}^{n} \binom{n + k}{k}2^{−k} = 2^{n} (n ≥ 0)

and prove it by calculating the probabilities of winning a particular championship series. In this series the winner team must accumulate n + 1 victories. Assume that the two teams are equally likely to win in each game, i.e. p = q = 1/2. Let p(n + 1, k) denote the probability that Team A becomes the champion after winning the n + k + 1^{st} game where 0 ≤ k < n + 1. In the first n + k games, Teams A and B accumulate n and k victories, respectively, with probability a(n, k). We have a(n, k) = \binom{n+k}{k}2^{−(n+k)}. Clearly, p(n + 1, k) = \frac{1}{2} a(n, k), therefore Team A wins with probability

(2)  ∑_{k=0}^{n} p(n + 1, k) = ∑_{k=0}^{n} \frac{1}{2}\binom{n + k}{k}2^{−(n+k)}.

Either Team A or B wins; hence the winning probabilities must add up to 1, i.e., ∑_{k=0}^{n} \binom{n+k}{k}2^{−(n+k)} = 1.

*Received by the editors November 29, 1991; accepted for publication (in revised form) July 3, 1992.

†Department of Mathematics, Occidental College, 1600 Campus Dr., Los Angeles, CA 90041.

With little extra effort we can calculate the expected length of the series by using identity (1) again.

Theorem 1. The expected length, EW_{n}, of the series is 2n (1 − \binom{2n}{n}2^{−2n}) if p = q = 1/2.

Proof. By the previous method, the series lasts n + k games with probability \binom{n+k−1}{k}2^{−(n+k−1)}. We get

(3)  EW_{n} = ∑_{k=0}^{n−1}(n + k)\binom{n + k − 1}{k}2^{−(n+k−1)}

for the expected length of the series. We shall use the identity (n+k)\binom{n+k−1}{k} = n\binom{n+k}{k} to rewrite equation (3)

EW_{n} = 2n ∑_{k=0}^{n−1} \binom{n + k}{k}2^{−(n+k)} = 2n \{ ∑_{k=0}^{n} \binom{n + k}{k}2^{−(n+k)} − \binom{2n}{n}2^{−2n}\}.

By identity (1), it follows that the expected value is 2n (1 − \binom{2n}{n}2^{−2n}).

For example, if n = 4 then we get 8(1 − \frac{70}{256}) = 5.8125 games on the average. In general, EW_{n} is asymptotically 2n \{1 − \frac{1}{\sqrt{πn}}\}. Hence, at the end of the series, the winning team will collect n victories while the other one wins asymptotically n − c\sqrt{n} games, on the average, where c = 2/\sqrt{π}. Note that if the number N of games is fixed in advance then after N games the two teams will be asymptotically c\sqrt{N/2} victories apart (cf. [1, Problem 35, p. 241] or [6, Putnam 1974, Problem A-4]), on the average. In fact, if N ∼ EW_{n} then the expected number of victories apart is asymptotically c\sqrt{n} as we noted.

We generalize Theorem 1 for arbitrary p.

Theorem 2. For the probabilities, P_{n}^{A} and P_{n}^{B}, of winning the championship by Teams A and B, respectively, and the expected length, EW_{n}(p), of the series

(4)  P_{n}^{A} = p + \frac{(p − q)}{2} ∑_{k=1}^{n−1} \binom{2k}{k}(pq)^{k},

(5)  P_{n}^{B} = q + \frac{(q − p)}{2} ∑_{k=1}^{n−1} \binom{2k}{k}(pq)^{k},

and

(6)  EW_{n}(p) = 2n \{1 − \binom{2n}{n}(pq)^{n} − \frac{(p − q)^{2}}{4pq} ∑_{k=1}^{n} \binom{2k}{k}(pq)^{k}\}.

Remark. It follows from identity (6) that

(7)  lim_{n→∞} \frac{1}{2n}(EW_{n}(1/2) − EW_{n}(p)) = \frac{|p − q| (1 − |p − q|)}{4pq},

since ∑_{k=0}^{∞} \binom{2k}{k}x^{k} = 1/\sqrt{1 − 4x}, for |x| < 1/4 (see [2]). Similarly, identities (4) and (5) imply that for p > q, lim_{n→∞} P_{n}^{A} = 1 and for p < q, lim_{n→∞} P_{n}^{B} = 1.

If p = q = 1/2 then P_{n}^{A} = P_{n}^{B} = 1/2. Notice that the limit in identity (7) can be expressed as 1 − \frac{1}{2p} if p ≥ 1/2.

Proof. The probability that the series ends at the end of the n + k^{th} game is \binom{n+k−1}{k}(p^{n}q^{k} + q^{n}p^{k}) and

P_{n}^{A} = p^{n} ∑_{k=0}^{n−1} \binom{n + k − 1}{k}q^{k} and P_{n}^{B} = q^{n} ∑_{k=0}^{n−1} \binom{n + k − 1}{k}p^{k}.

Now P_{n}^{A} + P_{n}^{B} = 1 which gives a generalization of identity (1). Obviously, P_{1}^{A} = p and P_{1}^{B} = q. Similarly to the proof of Theorem 1,

(8)  EW_{n}(p) = np^{n} ∑_{k=0}^{n−1} \binom{n + k}{k}q^{k} + nq^{n} ∑_{k=0}^{n−1} \binom{n + k}{k}p^{k}.

Let EW_{n}^{A} denote the first part of the sum on the right hand side of equation (8). The simple relation between P_{n}^{A} and EW_{n}^{A} is given by

EW_{n}^{A} = \frac{n}{p}P_{n+1}^{A} − n \binom{2n}{n}(pq)^{n}

which implies that

(9)  EW_{n}(p) = n \{\frac{P_{n+1}^{A}}{p} + \frac{P_{n+1}^{B}}{q} \} − 2n\binom{2n}{n}(pq)^{n}.

We obtain the relation (4) for P_{n}^{A} by taking the difference P_{n+1}^{A} − P_{n}^{A}. This step is motivated by a similar one used in the solution to Problem 44, “winning an unfair game,”in [4]. The difference expresses the advantage of Team A in the terms of the probability of winning the championship if two extra games are played. The status of Team A as a winner or loser does not differ at the end of the extended series from that in the original series if Team A has already won more than n games (winner) or less than n − 1 games (loser) in the first 2n − 1 games. The difference comes from two sources. The probability that Team A becomes the champion after winning only n − 1 of the 2n − 1 games and then winning the next two games will increase the winning probability. On the other hand, Team A will finish as the loser if it has accumulated exactly n victories and then it falls behind by losing the last two games. We use the identity \binom{2n}{n} = 2\binom{2n−1}{n−1} and obtain

P_{n+1}^{A} − P_{n}^{A} = p^{2}\binom{2n − 1}{n − 1}p^{n−1}q^{n} − q^{2}\binom{2n − 1}{n − 1}p^{n}q^{n−1} = (p − q)\binom{2n − 1}{n − 1}(pq)^{n}

= \frac{p − q}{2} \binom{2n}{n}(pq)^{n}.

This yields relation (4) and identity (5) follows similarly. Since (1 − (p/q + q/p)/2) = −\frac{(p−q)^{2}}{2pq} , the formula (9) implies identity (6).

REFERENCES

[1] W. Feller, An Introduction to Probability Theory and Its Applications, vol. I, 3^{rd} edition, Wiley, New York, 1968.

4 tamás lengyel

[2] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 1988.

[3] R. J. Larsen and M. L. Marx, An Introduction to Mathematical Statistics and Its Applications, Prentice-Hall, 1986.

[4] F. Mosteller, Fifty Challenging Problems in Probability with Solutions, Addison-Wesley, Reading, MA, 1965.

[5] P. Tannenbaum, Handicapping a championship series with elementary symmetric polynomials, UMAP Journal, (10)1989, pp. 115–135.

[6] The William Putnam Mathematical Competition, Problems and Solutions: 1965-1984, Eds. G. L. Alexanderson, L. F. Klosinski, and L. C. Larson, MAA, Washington, 1980.