MAXIMUM STATISTICS OF N RANDOM VARIABLES

DISTRIBUTED BY THE

NEGATIVE BINOMIAL DISTRIBUTION

Peter J. Grabner and Helmut Prodinger

Department of Mathematics Technical University of Graz, Austria and Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

Abstract. The lifetime of a player is defined to be the time where he gets his bth hit, where a hit will occur with probability p. We consider the maximum statistics of N independent players. For b ≠ 1 this is significantly more difficult than the known instance b = 1. The average value of this parameter is given by log_{Q} N + (b −

1) log_{Q} log_{Q} N+ smaller order terms, where Q = 1/(1 − p).

1. Introduction

Consider a geometrically distributed random variable X, i.e. ℙ{X = k} = pq^{k−1} (q = 1 − p). If we have N independent copies X_{1}, …, X_{N}, the maximum of them is well understood, compare [7] and [5].

Now if X is the sum of two independent geometric random variables (with the same parameter), the corresponding maximum of N such variables is surprisingly more complicated. In the present note we will work out this case and indicate how the more general case of sums of b copies can be handled. Also, we give analytic indications why the asymptotic evalution of the expectated value is more complex.

In the sequel, we will use the suggestive notation of a “player” who “dies” at the second “hit”. In this context, we will concentrate on the expected value of the maximum lifetime of N independent players. To be precise, if a player gets his second hit at time k, we say that his lifetime is k. Such a waiting time distribution is generally known to be a negative binomial distribution (cf. [4]). Now we compute the probability that a particular player has lifetime > k. This is the same as to say that he is still alive at time k, which means that he obtained either zero or one hit. Hence

ℙ{X > k} = q^{k} + kpq^{k−1}.

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 05A15.

This research was supported by the Austrian-Hungarian cooperation 10U3

Thus we have for the expectation of the maximum lifetime of N players

(1.1)  𝔼_{N} = 𝔼 max(X_{1}, …, X_{N}) = ∑_{k≥0} (1 − (1 − (pk + q)q^{k−1})^{N}) .

The usual procedure for the analysis of such sums would proceed as follows: Using the binomial theorem we would obtain

(1.2)  𝔼_{N} = ∑_{m=1}^{N}(−1)^{m−1}\binom{N}{m} ∑_{k≥0} ((pk + q)q^{k−1})^{m} .

Then we would have to write this sum as a contour integral (cf. [3]). But following Rice’s method would require deformation of the contour of integration and therefore analytic continuation of the function

(1.3)  f(s) = ∑_{k≥0} ((pk + q)q^{k−1})^{s}

beyond the line ℜs = 0. We tried hard to get such continuation but did not succeed. We will explain after the analysis of 𝔼_{N}, why this is so difficult.

2. Asymptotic Evaluation of the Sum

As we have indicated in the introduction the asymptotic expansion of 𝔼_{N} cannot be obtained by standard methods. Further analysis can be done by using some approximation techniques. Our first (“exponential”) approximation will give us a more suitable form of 𝔼_{N}. In the following we will use the notations lq x to indicate log_{\frac{1}{q}} x and Q = \frac{1}{q}.

Let us define

(2.1)  𝔼̃_{N} = ∑_{k≥0} (1 − exp ( − N(pk + q)q^{k−1})).

Then we have

(2.2)

𝔼_{N} − 𝔼̃_{N} = ( ∑_{k≤lq N} + ∑_{lq N<k≤lq N+2 lq lq N} + ∑_{k>lq N+2 lq lq N})

(exp (−(pk + q)q^{k−1}N) − (1 − (pk + q)q^{k−1})^{N}) .

We have split the sum into three parts and will give estimates for each part. (1) k ≤ lq N: In this range we have (pk + q)q^{k−1} ≥ \frac{p lq N}{qN} + \frac{1}{N}. Thus we obtain

exp (−(pk + q)q^{k−1}N) ≤ N^{− \frac{p}{q log Q}} and (1 − (pk + q)q^{k−1})^{N} ≤ N^{− \frac{p}{q log Q}}

and consequently we have N^{− \frac{p}{q log Q}} lq N as an upper bound for this first sum.

MAXIMUM STATISTICS … 3

(2) lq N < k ≤ lq N + 2 lq lq N: Using the Taylor expansions of exp(−Nu) and (1 − u)^{N} we obtain

exp(−Nu) − (1 − u)^{N} = \frac{Nu^{2}}{2} exp(−Nu)

+ O(Nu^{3} exp(−Nu)) + O(N^{2}u^{4} exp(−Nu)) = O (\frac{log^{2} N}{N} )

for u = (pk +q)q^{k−1}. This yields an estimate O (\frac{log^{2} N log log N}{N} ) for the sum in this range.

(3) k > lq N + 2 lq lq N: Again we use Taylor expansion to obtain

exp(−Nu) − (1 − u)^{N} = O (N(pk + q)^{2}q^{2k−2})

for u = (pk + q)q^{k−1}. This yields an upper bound

O (N ∑_{k>lq N+2 lq lq N}(pk + q)^{2}q^{2k−2}) = O (\frac{log^{2} N}{N} )

for the sum in this range. Combining the three estimates yields

𝔼_{N} − 𝔼̃_{N} = O (\frac{log^{2} N log log N}{N} ) .

The standard technique for deriving asymptotic estimates for 𝔼̃_{N} uses Mellin transform and therefore again the analytic continuation of f(s). Thus we use a second approximation to 𝔼_{N} which finally yields the desired asymptotic expansion.

For this purpose we define

(2.3)  𝔼_{N}^{∗} = ∑_{k≥0} (1 − exp ( − (p lq N + q)Nq^{k−1})).

Now we have to give estimates for 𝔼̃_{N} − 𝔼_{N}^{∗}. We compute (2.4)

𝔼̃_{N} − 𝔼_{N}^{∗} = ∑_{k≤lq N} exp (−(pk + q)q^{k−1}N) ( exp (−p(lq N − k)q^{k−1}N) − 1)

+ ∑_{k>lq N} exp (−(p lq N + q)q^{k−1}N) (1 − exp (−p(k − lq N)q^{k−1}N) ).

As above we get the estimate O(N^{− \frac{p}{q log Q}} log N) for the first sum. For the second sum we use the estimate

1 − exp (−p(k − lq N)q^{k−1}N) = O (p(k − lq N)q^{k−1}N) .

We split the range of summation into two parts:

(1) lq N < k ≤ lq N + lq lq N + lq p + 1: let k = lq N + x and estimate the summand by O(xq^{x} exp(−(\frac{p}{q} lq N + 1)q^{x})). This function is monotonically increasing in the interval 0 ≤ x ≤ lq lq N + lq p + 1, thus the summand can be estimated by O(\frac{lq lq N}{lq N}) which yields a O(\frac{(lq lq N)^{2}}{lq N}) contribution to the second sum.

(2) k > lq N + lq lq N + lq p + 1: in this range we have N lq N ≤ q^{−k} and thus the remaining sum can be estimated using the summation formula for the geometric series

O ( ∑_{k>lq N+lq lq N} p(k − lq N)q^{k−1}N) = O (\frac{log log N}{log N} ) .

Therefore we arrive at the final estimate

𝔼_{N} − 𝔼_{N}^{∗} = O (\frac{(log log N)^{2}}{log N} ) .

Notice now that 𝔼_{N}^{∗} is the sum

S(T) = ∑_{k≥0} (1 − exp (−T q^{k}) )

evaluated at T = \frac{p}{q}N lq N + N. This sum occurred in many asymptotic investigations, e.g. [6]. By Mellin’s inversion formula [1,2] we have

S(T) = \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}Γ(s)\frac{T^{−s}ds}{Q^{s} − 1}.

Hence we get the asymptotic expansion of S(T) by shifting the line of integration to the right and taking residues into account

S(T) = lq T + \frac{1}{2} + \frac{γ}{log Q} + F (lq T) + O(\frac{1}{T} ),

where F is an infinitely differentiable periodic function. Thus we have proved

Theorem 1. (2.5)

𝔼_{N}^{∗} = lq N +lq lq N +lq p+ \frac{3}{2} + \frac{γ}{log Q} +F (lq N + lq lq N + lq p)+O (\frac{(log log N)^{2}}{log N} )

where F is a C^{∞} periodic function of period 1 and mean value 0 whose Fouriercoefficients are given by

F̂(k) = −\frac{1}{log Q}Γ (−\frac{2kπi}{log Q}) for k ∈ ℤ \ \{0\}.

3. Concluding Remarks

If we translate the asymptotics of 𝔼_{N}^{∗} back to analytic properties of the Mellintransform of S(T lq T), we encounter logarithmic singularities (corresponding to the log log-terms) at s = \frac{2kπi}{log Q} for all k ∈ ℤ. These singularities would give us an infinity of branch-cuts which are the reason for the difficulties mentioned in the introduction. Notice, that this is not a proof for the existence of an analytic continuation of the function f(s) in (1.3).

The method used above to find an asymptotic expansion for the sum

(3.1)  ∑_{k≥0} (1 − (1 − (pk + q)q^{k−1})^{N})

can be immediately extended to find the expansion for

S_{g}(N) = ∑_{k≥0} (1 − (1 − g(k)q^{k})^{N})

where g(k) ∼ βk^{α} and g(k) > 0 for k ≥ 0. The resulting asymptotic expansion is given by

(3.2) S_{g}(N) = lq N +α lq lq N +lq β + \frac{1}{2} + \frac{γ}{log Q} +F (lq N +α lq lq N +lq β)+o(1)

where F is the periodic function of Theorem 1.

This general result can be used to compute the expected maximal lifetime of N players who die after b hits. It is quite plain to see that

ℙ\{X > k\} = q^{k} + kpq^{k−1} + ⋯ + \binom{k}{b − 1}p^{b−1}q^{k−b+1}.

Hence the g(k) from before is

g(k) = 1 + k \frac{p}{q} + ⋯ + \binom{k}{b − 1}(\frac{p}{q})^{k−1} ∼ \frac{k^{b−1}}{(b − 1)!}(\frac{p}{q})^{k−1}

Therefore this expectation is given by

(3.3)

𝔼_{N}^{(b)} = lq N + (b − 1) lq lq N + (b − 1) lq p + (b − 1) − lq(b − 1)! + \frac{1}{2} + \frac{γ}{lq Q}
+ F (lq N + (b − 1) lq N + (b − 1) lq p − lq(b − 1)!) + o(1).

This result tells us that, if we allow an additional hit, the maximum of N players will roughly increase by lq lq N.

References

1. G.Doetsch, Handbuch der Laplace-Transformation, Birkhäuser, Basel, 1950.

2. P.Flajolet, M.Régnier, and R.Sedgewick, Some Uses of the Mellin Integral Transform in the Analysis of Algorithms, Combinatorics on Words, Springer NATO ASI Series F, Volume 12, Berlin, 1985.

3. P.Grabner and H.Prodinger, The Fibonacci Killer, The Fibonacci Quarterly (1994) (to appear).

4. N.L.Johnson and S.Kotz, Urn models and Their Applications, John Wiley and Sons, New York, 1977.

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

6. D.E.Knuth, The Art of Computer Programming, Vol.3, Addison–Wesley, Reading, MA, 1973.

7. W.Szpankowski and V.Rego, Yet another application of a binomial recurrence: Order Statistics, Computing 43 (1990), 401–410.

P. Grabner

Institut für Mathematik A

Steyrergasse 30

A–8010 Graz, Austria H. Prodinger Institut für Algebra und Diskrete Mathematik Wiedner Hauptstraße 8–10 A–1040 Wien, Austria

E-mail address: grabner@ftug.dnet.tu–graz.ac.at, proding@email.tuwien.ac.at