THE NUMBER OF WINNERS IN A DISCRETE GEOMETRICALLY DISTRIBUTED SAMPLE

Peter Kirschenhofer and Helmut Prodinger Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

Let the random variable G be geometrically distributed, i.e. ℙ{G = k} = pq^{k−1}, with q = 1 − p. Also, assume that n independent copies are given. Finally, let X count the number of winners, i.e. the number of random variables with highest value. In [1] the probability distribution of X, the expectation EX of X and the asymptotic behaviour of ℙ{X = 1} (probability of a single winner) for n → ∞ was to be determined. In the solution [2] it was remarked that – surprisingly – this probability does not converge as n → ∞ but rather has an oscillating behaviour. At the same time, Eisenberg, Stengle and Strang [5] discussed this problem and related topics, exhibiting the structure of the periodic fluctuation, for which an explicit Fourier expansion was given. Also about this time, Brands, Steutel and Wilms [3] came independently to roughly the same results. A recent paper due to Baryshnikov, Eisenberg and Stengle [4] deals with the existence of the limiting probability of a tie for first place.

In fact, a fluctuating behaviour in asymptotic expansions is not at all uncommon. There are numerous results of that type, e.g. in the analysis of divide–and–conquer recursions [7, 8, 16] or digital sums [6], to mention just some examples, that play a prominent role in the probabilistic analysis of algorithms.

Our aim in this paper is to some extent tutorial: The asymptotic technique that yields the Fourier expansions of the fluctuating functions very comfortably is called The Number of Winners 2 “Rice’s method”, see the recent survey [9]. In order to convince the reader of the advantages of this method we will rederive some results on the initially mentioned problem in the sequel, and afterwards present some new results concerning higher moments of distribution as well as the number of persons reaching a specified level beyond the winner.

1991 Mathematics Subject Classification. 60 C 05.

Key words and phrases. Geometric distribution, generating functions, Rice’s method.

Let us abbreviate Q := 1/q and L := log Q. Let further p_{m} denote the probability p_{m} = ℙ{X = m}, i.e. the probability to have m winners (amongst n players). Then

p_{m} = p^{m}\binom{n}{m} ∑_{j≥1} q^{(j−1)m}(1 − q^{j−1})^{n−m}.

This follows from the observation that m out of n people have a (winning) value j, while the other ones have a smaller value. Now we set N := n − m, expand the binomial and sum over j to get the alternative

p_{m} = p^{m}\binom{n}{m} ∑_{k=0}^{N} \binom{N}{k}(−1)^{k} \frac{1}{1 − Q^{−k−m}} .  (1)

The key point in analyzing this alternating sum asymptotically is the following Lemma.

Lemma. [9] Let f(z) be a function that is analytic on [n_{0}, +∞[. Assume that f(z) is meromorphic in the whole of ℂ and analytic on Ω = ⋃_{j=1}^{∞} γ_{j} where the γ_{j} are concentric circles whose radius tends to infinity. Let f(z) be of polynomial growth on Ω. Then, for n large enough,

∑_{k=n_{0}}^{n} \binom{n}{k} (−1)^{k}f(k) = ∑_{z} Res[n; z]f(z) ,  (2)

where

[n; z] = \frac{(−1)^{n−1}n!}{z(z − 1) … (z − n)} = \frac{Γ(n + 1)Γ(−z)}{Γ(n + 1 − z)} □

and the sum is extended to all poles not on [n_{0}, +∞[.

Extending the contour of integration to the left it turns out that, under suitable growth conditions on f(z) (which are fulfilled in all our examples), an asymptotic equivalent of (2) is given by the residues of [n; z]f(z) at the additional poles.

In our example we only have to consider the residues of

[N; z]\frac{1}{1 − Q^{−z−m}}

left of the line ℜz = 0. They are at z = −m+χ_{j}, with χ_{j} = \frac{2jπi}{L}. The computation of the residues is simple;

Res_{z=−m+χ_{j}} = n^{χ_{j}} \frac{Γ(N + 1)Γ(N + 1 + m − χ_{j})}{m!} \frac{1}{L},

whence we have (after multiplication by the factor p^{m}\binom{n}{m} and going back to n instead of N) the asymptotic formulæ (for m fixed and n → ∞)

p_{m} = \frac{1}{L} \frac{p^{m}}{m!} ∑_{j∈ℤ} \frac{Γ(n + 1)}{Γ(n + 1 − χ_{j})}Γ (m − χ_{j}) + smaller order terms.  (3)

It is often convenient to pull out the term with index j = 0 (the “mean”) and give a name to the remaining periodic fluctuation (of mean zero),

δ_{m}(x) = \frac{1}{m!} ∑_{j≠0} Γ(m − χ_{j})e^{2jπix}.

This is a continuous, periodic function of period 1, (integral) mean zero and small amplitude (for m not too large, compare the discussion in [12]), and we can thus write

p_{m} ∼ \frac{1}{L} \frac{p^{m}}{m} + \frac{p^{m}}{L} δ_{m}(log_{Q} n) + O(\frac{1}{n}), m fixed , n → ∞.  (4)

It is interesting to note that the alternating sum (1) can also be rewritten using the partial fraction decomposition of the meromorphic function \frac{1}{1−q^{z+m}}, namely (compare [11, 7.10])

\frac{1}{1 − q^{z+m}} = \frac{1}{2} + \frac{1}{L} ∑_{j∈ℤ} \frac{1}{z + m + χ_{j}} , with χ_{j} = \frac{2jπi}{L}.  (5)

Inserting (4) into (1) we find

p_{m} = p^{m}\binom{n}{m} ∑_{k=0}^{N} \binom{N}{k}(−1)^{k} \frac{1}{2} + \frac{1}{L}p^{m}\binom{n}{m} ∑_{j∈ℤ} ∑_{k=0}^{N} \binom{N}{k}(−1)^{k} \frac{1}{k + m + χ_{j}} .

Now for x ∈ ℂ \ {−N, …, 0}

∑_{k=0}^{N} \binom{N}{k}(−1)^{k} \frac{1}{k + x} = \frac{Γ(N + 1)Γ(x)}{Γ(N + 1 + x)} = \frac{N!}{(N + x)_{N+1}}

(compare [10, (5.41)]), so that (remembering N = n − m)

\begin{aligned}p_{m} & = \frac{p^{m}}{2} δ_{n,m} + \frac{1}{L} \frac{p^{m}}{m!} ∑_{j∈ℤ} \frac{n!}{(m + χ_{j}) … (n + χ_{j})} \\ & = \frac{p^{m}}{2} δ_{n,m} + \frac{1}{L} \frac{p^{m}}{m!} ∑_{j∈ℤ} Γ(m − χ_{j})\frac{Γ(n + 1)}{Γ(n + 1 − χ_{j})}. \end{aligned}  (6)

From (6) we may conclude that the smaller order terms from expansion (3) equal zero in fact.

Now let us consider the expectation,

E_{n} = ∑_{m≥1} mp_{m}

= n ∑_{m≥1} \binom{n − 1}{m − 1}p^{m} ∑_{j≥0} q^{jm} (1 − q^{j})^{n−m}

= \frac{np}{q} ∑_{j≥0} q^{j+1} (1 − q^{j})^{n−1} ∑_{m≥0} \binom{n − 1}{m} (\frac{pq^{j}}{1 − q^{j}} )^{m}

= \frac{np}{q} ∑_{j≥1} q^{j}(1 − q^{j})^{n−1}

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

= Q(p_{1} − pδ_{n,1}).

From (3) we conclude the asymptotic formula

E_{n} = \frac{p}{q} \frac{1}{L}(1 + δ_{1}(log_{Q} n)) + O(\frac{1}{n}).  (7)

This computation was already reported in [2]. Let us now engage in the computation of the variance, which seems to be new.

For this we compute the second factorial moment M_{n} for n ≥ 2:

\begin{aligned}M_{n} & = ∑_{m≥2} m(m − 1)p_{m} \\ & = n(n − 1) ∑_{m≥2} \binom{n − 2}{m − 2}p^{m} ∑_{j≥0} q^{jm} (1 − q^{j})^{n−m} \\ & = \frac{n(n − 1)p^{2}}{q^{2}} ∑_{j≥1} q^{2j} (1 − q^{j})^{n−2} \\ & = \frac{n(n − 1)p^{2}}{q^{2}} ∑_{k=0}^{n−2} \binom{n − 2}{k}(−1)^{k} \frac{1}{Q^{k+2} − 1} \\ & = 2Q^{2}p_{2} − 2\frac{p^{2}}{q^{2}} δ_{n,2} = 2Q^{2}(p_{2} − p^{2}δ_{n,2}). \end{aligned}  (8)

The variance is obtained in the usual way by computing V_{n} = M_{n}+E_{n}−E_{n}^{2}. Hence

V_{n} = \frac{p^{2}}{q^{2}} \frac{1}{L} + \frac{p}{q} \frac{1}{L} − \frac{p^{2}}{q^{2}} \frac{1}{L^{2}} + τ(log_{Q} n) + O(\frac{1}{n}).  (9)

This time τ(x) = \frac{p^{2}}{q^{2}} \frac{2}{L}δ_{2}(x) + \frac{p}{q} \frac{1}{L}δ_{1}(x) − \frac{p^{2}}{q^{2}} \frac{1}{L^{2}} δ_{1}^{2}(x) has (integral) mean different from zero! While this quantity is quite small, it can be extracted using the methods described in [13], and we find the alternative

V_{n} = \frac{p}{q^{2}} \frac{1}{L} − \frac{p^{2}}{q^{2}} \frac{1}{L}(2 ∑_{j≥1} \frac{Q^{j}}{(Q^{j} + 1)^{2}} + \frac{1}{4}) + τ_{1}(log_{Q} n) + O(\frac{1}{n}),  (10)

where the function τ_{1}(x) has now mean zero.

There is a nice way to derive the explicit forms of the expectation and the second factorial moment, using generating functions. Let the coefficient of z^{k} in F_{n}(z) denote the probability that n player produce k winners. We get the following recursion

F_{n}(z) = ∑_{k=1}^{n} \binom{n}{k}p^{n−k}q^{k}F_{k}(z) + p^{n}z^{n},  n ≥ 1.  (11)

It is convenient to set F_{0}(z) = 1. This recursion is almost selfexplanatory. When at a certain level the remaining players all fail, we label each of them by a “z” and leave the recursion. The expectation E_{n} is obtained via F′_{n}(1); therefore

E_{n} = ∑_{k=1}^{n} \binom{n}{k}p^{n−k}q^{k}E_{k} + np^{n}, n ≥ 1.

Define the exponential generating function

E(z) = ∑_{n≥0} E_{n} \frac{z^{n}}{n!} ,

then we obtain

E(z) = e^{pz}E(qz) + pze^{pz},

which will be easier by using the “Poisson transform”

Ê(z) = e^{−z}E(z) = ∑_{n≥0} Ê_{n} \frac{z^{n}}{n!} ;

Ê(z) = Ê(qz) + pze^{−qz}.

Equating coefficients we see, that, for n ≥ 1,

Ê_{n} = \frac{np}{q}(−1)^{n−1} \frac{q^{n}}{1 − q^{n}}

and furthermore for n ≥ 1

E_{n} = ∑_{k=0}^{n} \binom{n}{k}Ê_{k}

= ∑_{k=1}^{n} \binom{n}{k}\frac{kp}{q}(−1)^{k−1} \frac{1}{Q^{k} − 1}

= \frac{np}{q} ∑_{k=0}^{n−1} \binom{n − 1}{k}(−1)^{k} \frac{1}{Q^{k+1} − 1}.

For the second factorial moment we have to derive twice, and evaluate at z = 1. An almost identical computation gives the same expression that we obtained already.

This approach was used by Knuth in [15] under the name “binomial transform” and subsequently used by many people, see for instance [17].

Finally we want to produce some new results which shed some additional light on the original question about the number of winners.

Assume that the winners have reached the level j. We are interested in the number of people who reached the level j − d, where d is a parameter. (d = 0 is the case that was just considered.) Call the random variable in question X_{d}. Then we have

\begin{matrix}ℙ\{X_{d} = m_{d}\} \\ = ∑ ∑_{j≥d+1} \binom{n}{m_{0}, …, m_{d}, μ}(pq^{j−1})^{m_{0}} … (pq^{j−d−1})^{m_{d}}(1 − q^{j−d−1})^{μ}, \end{matrix} (12)

where the first sum runs over all m_{0} ≥ 1, m_{1} ≥ 0, …, m_{d−1} ≥ 0 and μ = n − m_{0} − ⋯ − m_{d}. The expected value is just the sum of m_{d} times this quantity. We get

E_{n}^{(d)} = n ∑_{j≥d+1} pq^{j−d−1}[(pq^{j−1} + ⋯ + pq^{j−d−1} + 1 − q^{j−d−1})^{n−1}
− (pq^{j−2} + ⋯ + pq^{j−d−1} + 1 − q^{j−d−1})^{n−1}]

= pn ∑_{j≥d+1} q^{j−d−1} [(1 − q^{j})^{n−1} − (1 − q^{j−1})^{n−1}]

= \frac{p^{2}}{q^{d+1}} n ∑_{j≥d} q^{j}(1 − q^{j})^{n−1} − \frac{p}{q}n(1 − q^{d})^{n−1}.

This formula holds only for d ≥ 1. Since

E_{n}^{(0)} = E_{n} = n\frac{p}{q} ∑_{j≥1} q^{j}(1 − q^{j})^{n−1},

we find

E_{n}^{(d)} = \frac{p}{q^{d}} E_{n}^{(0)} − \frac{p^{2}}{q^{d+1}} n ∑_{j=1}^{d−1} q^{j}(1 − q^{j})^{n−1} − \frac{p}{q}n(1 − q^{d})^{n−1},  (13)

and, since the extra terms are exponentially small, we can use the asymptotic result for E_{n}^{(0)} and have

\begin{aligned}E_{n}^{(d)} & = \frac{p}{q^{d+1}} p_{1}  (n ≥ 2) \\ & = \frac{1}{L} \frac{p^{2}}{q^{d+1}} + \frac{1}{L} \frac{p^{2}}{q^{d+1}} δ_{1}(log_{Q} n) + O(\frac{1}{n})  (n → ∞). \end{aligned}  (14)

The second factorial moment M_{n}^{(d)} is computed analogously as (d ≥ 1)

M_{n}^{(d)} = n(n − 1) ∑_{j≥d+1} (pq^{j−d−1)})^{2} [(1 − q^{j})^{n−2} − (1 − q^{j−1})^{n−2}]

= \frac{p^{3}}{q^{2d+2}} n(n − 1) ∑_{j≥d} q^{2j} (1 − q^{j})^{n−2} − \frac{p^{2}}{q^{2}} n(n − 1) (1 − q^{d})^{n−2}

= \frac{p}{q^{2d}} + exponentially small terms in n, n → ∞.

(15)

The Number of Winners 8

(with M_{n}^{(0)} = M_{n} from above). Altogether we find for the variance

V_{n}^{(d)} = \frac{p^{2}}{q^{2d+2}} \frac{1}{L} (1 + q^{d+1})− \frac{p^{4}}{q^{2d+2}} \frac{1}{L}(2 ∑_{j≥1} \frac{Q^{j}}{(Q^{j} + 1)^{2}} + \frac{1}{4})+τ_{1}^{(d)}(log_{Q} n)+O(\frac{1}{n}).

(16)

References

1. E3436 (Problem), American Mathematical Monthly 99 (1991), 366.

2. E3436 (Solution), American Mathematical Monthly 101 (1994), 78–80.

3. J.J.A.M.Brands, F.W.Steutel, and R.J.G.Wilms, On the number of maxima in a discrete sample, Statistics and Probability Letters 20 (1994), 209–217.

4. Y. Baryshnikov, B.Eisenberg, and G.Stengle, A necessary and sufficient condition for the existence of the limiting probability of a tie for first place, Statistics and Probability Letters (1995), 203–209.

5. B.Eisenberg, G.Stengle, and G.Strang, The asymptotic probability of a tie for first place, Annals of Applied Probability 3 (1993), 731–745.

6. P.Flajolet, P. Grabner, P.Kirschenhofer, H.Prodinger and R.F.Tichy, Mellin Transforms and Asymptotics: Digital Sums, Theoretical Computer Science 123 (1994), 291–314.

7. P.Flajolet and L.B.Richmond, Generalized Digital Trees and Their Difference-Differential Equations, Random Structures and Algorithms 3 (1992), 305–320.

8. P. Flajolet and R. Sedgewick, Digital Search Trees Revisited, SIAM J.Comput. 15 (1986), 748–767.

9. P.Flajolet and R.Sedgewick, Mellin transforms and asymptotics: Finite differences and Rice’s integrals, Theoret. Comput. Sci. (1994) (to appear).

10. R.Graham, D.E.Knuth, and O.Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

11. P. Henrici, Applied and Computational Complex Analysis, vol.1, J. Wiley, New York, 1977.

12. P. Kirschenhofer and H.Prodinger, A Result in Order Statistics Related to Probabilistic Counting, Computing 51 (1993), 15–27.

13. P.Kirschenhofer and H.Prodinger, On Some Applications of Formulæof Ramanujan in the Analysis of Algorithms, Mathematika 38 (1991), 14–33.

14. P.Kirschenhofer, H.Prodinger and W.Szpankowski, On the Variance of the External Pathlength in a Symmetric Digital Trie, Discrete Applied Mathematics 25 (1989), 129–143.

15. D.E.Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, 1973.

16. H.M.Mahmoud, Evolution of Random Search Trees, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1992.

17. H.Prodinger and W.Szpankowski, A note on binomial recurrences arising in the analysis of algorithms (Letter to the Editor), Information Processing Letters 46 (1993), 309–311.

18. W. Szpankowski, The Evaluation of an Alternative Sum with Applications to the Analysis of Some Data Structures, Information Processing Letters 28 (1988), 13–19.

TU Vienna Wiedner Hauptstrasse 8-10 A-1040 Vienna Austria