NUMBER THEORY, BALLS IN BOXES, AND THE ASYMPTOTIC UNIQUENESS OF MAXIMAL DISCRETE ORDER STATISTICS

Jayadev S. Athreya

Department of Mathematics, Iowa State University, Ames, Iowa 50011, U.S.A.

Lukasz M. Fidkowski

Department of Mathematics, Harvard University, Cambridge, Massachusetts 02138, U.S.A.

Received: 12/14/99, Accepted: 2/25/00, Published: 5/19/00

Abstract

We investigate the asymptotic uniqueness of the maximal order statistic of X_{1}, X_{2}, …, X_{n}, i.i.d. positive integer random variables, by casting the problem in a balls in boxes setting. We give a necessary and sufficient condition on the distribution of the X_{i}’s for the convergence of the probability of uniqueness as n → ∞. We describe the connection to an interesting problem in number theory. The main techniques used are altering the sample to have random size, specifically, Poisson(n), and Karamata’s Tauberian Theorem.

1. Introduction And Main Results

Let X_{1}, X_{2}, …, X_{n} be i.i.d. random variables taking values on the positive integers, with P (X = i) = p_{i}. Denote by ρ_{n} the probability that the largest value in the sample is unique, which, in order statistics notation, reads

P (X_{(n)} > X_{(n−1)}).

What is the asymptotic behavior of ρ_{n}? The problem can be thought of in the following intuitive manner: Let n balls be thrown independently into an infinite number of boxes, numbered 1, 2, 3, … according to the distribution {p_{i}}_{i=1}^{∞}. Then ρ_{n} is the probability that the highest non-empty box has exactly one ball in it. Denote by ρ_{n,t} the probability that t is the highest box with a ball and that it has exactly one ball in it. Clearly,

ρ_{n,t} = np_{t}(p_{1} + p_{2} + … + p_{t−1})^{n−1}

so that

ρ_{n} = ∑_{t=1}^{∞} ρ_{n,t} = ∑_{t=1}^{∞} np_{t}(1 − p̄_{t})^{n−1}

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000) #A03 2

where

p̄_{t} = ∑_{j=t}^{∞} p_{j} = P (X ≥ t).

The question(s) we would like to answer is (are): What is lim_{n→∞} ρ_{n} ? For what distributions {p_{i}}_{i=1}^{∞} does the limit exist? The case p_{i} = 2^{−i} was investigated by Shuguang Li [2]. He showed that lim_{n→∞} ρ_{n} does not exist in this case. Before we investigate the asymptotic behaviour of ρ_{n} we consider a slight modification which illustrates the techniques that we use. The modification is as follows: Instead of a sample of fixed size n, let our sample be of random size, specifically, Poisson(n). Then the number of balls in the boxes become independent Poisson random variables with mean {np_{i}}_{i=1}^{∞} respectively (see Ross [3]). So denoting by ρ′_{n} the probability that the highest box has only one ball, we have:

ρ′_{n} = ∑_{t=1}^{∞} np_{t}e^{−np̄_{t}}.

Before stating our main theorem, we recall a key lemma: Karamata’s Tauberian Theorem, as found, e.g., in Bingham et al. [1], pp. 37-8:

Lemma 1 Let U be non-decreasing on the reals, with U(x) = 0 for x < 0, and such that Û(s) (the Laplace transform) < ∞ for all large s. Let l be a slowly varying function (i.e., for any t > 0, lim_{x→∞} l(tx)/l(x) = 1) and let c ≥ 0 and ρ ≥ 0 be constants. Then the following are equivalent:

1. U(x) ∼ cx^{ρ}l(1/x)/Γ(1 + ρ) as x → 0+;

2. Û(s) ∼ cs^{−ρ}l(s) as s → ∞.

If c = 0, the above result is to be interpreted to mean that U(x) = o(x^{ρ}l(1/x)/Γ(1 + ρ)) as x → 0+ is equivalent to Û(s) = o(s^{−ρ}l(s)) as s → ∞.

We now prove a theorem that illustrates the technique to be used in the proof of our main theorem:

Theorem 1 The following are equivalent:

1. lim_{n→∞} ρ′_{n} exists;

2. lim_{n→∞} ρ′_{n} = 1;

3. lim_{t→∞} p_{t}/p̄_{t} = 0.

In our main theorem we show the result holds with ρ′_{n} replaced by ρ_{n}.

Proof. We are interested in the behavior of

ρ′_{n} = ∑_{t=1}^{∞} np_{t}e^{−np̄_{t}} = nE(e^{−np̄_{X}}) = nϕ(n)

where ϕ(n) is the Laplace-Stieltjes transform of the cumulative distribution function of the random variable p̄_{X}, with X an random variable with distribution {p_{i}}. For lim_{n→∞} ρ′_{n} to exist and be positive, we would like to have

ϕ(n) ∼ l/n

as n → ∞, and with l > 0 as our limit. Now since ϕ is monotone (because it is the moment generating function of p̄_{X}), this is equivalent to ϕ(s) ∼ l/s as s → ∞ continuously. To get an equivalent condition for this, we use our lemma, i.e., Karamata’s Tauberian Theorem with l(x) = l, c = ρ = 1, and U(x) = Fp̄_{X}, where Fp̄_{X} is the cumulative distribution function of p̄_{X}. This gives us the following condition in terms of the original distribution function near zero:

Fp̄_{X} (y) ∼ ly

as y → 0^{+}. So we are interested in how

f(y) = Fp̄_{X} (y)/y = P (p̄_{X} ≤ y)/y

varies as y → 0. Let y approach 0 along the sequence {p̄_{t}}. Clearly, P (p̄_{X} ≤ p̄_{t}) = P (X ≥ t) = p̄_{t}. So f(y) = 1 along this sequence. Thus, if a positive limit were to exist it would have to be 1. Note that this calculation also eliminates the case of the limit being 0, since if we took c = 0, we could use our theorem to tell us that ϕ(s) = o(1/n) as n → ∞ is equivalent to f(y) = o(1) as y → 0^{+}, which cannot happen since f(y) = 1 along the sequence {p̄_{t}}.

Now suppose the limit existed, and thus was 1. Look at y ∈ [p̄_{t}, p̄_{t−1}). Then P (p̄_{X} ≤ y) = p̄_{t}. So

1 ≥ f(y) ≥ p̄_{t}/p̄_{t−1}

and

lim_{y→p̄_{t−1}^{−}} f(y) = p̄_{t}/p̄_{t−1}.

Thus for f(y) → 1 as y → 0, p̄_{t}/p̄_{t−1} must tend to 1. Now, p̄_{t}/p̄_{t−1} = 1−p_{t−1}/p̄_{t−1}. So we must have p_{t−1}/p̄_{t−1} → 0. We finish by noting that if p_{t−1}/p̄_{t−1} → 0, f(y) is squeezed and must go to 1. □

Theorem 2 Theorem 1 holds when we replace ρ′_{n} with ρ_{n}.

Proof. To note that the result holds for ρ_{n}, we proceed in a similar vein. First we write:

ρ_{n} = ∑_{t=1}^{∞} np_{t}(1 − p̄_{t})^{n−1} = ∑_{t=1}^{∞} np_{t}e^{(n−1) ln(1−p̄_{t})} = nψ(n − 1),

with ψ(n) representing the Laplace-Stieltjes transform of the cumulative distribution function of the random variable − ln(1 − p̄_{X}). So for ρ_{n} we would like, as above with ρ′_{n} and ϕ(n),

ψ(n) ∼ l/n

as n → ∞. As with ϕ(n), ψ(n) is a moment generating function and thus monotone, so going to ∞ discretely is the same as going continuously.So we can again use the Tauberian theorem, to give us that this is equivalent to:

F (y) ∼ ly

as y → 0^{+} with F the cumulative distribution function of − ln(1 − p̄_{X}). Now let us inspect F. We have

F (y) = P (− ln(1 − p̄_{X}) ≤ y) = P (1 − p̄_{X} ≥ e^{−y})
= P (1 − e^{−y} ≥ p̄_{X}) = Fp̄_{X} (1 − e^{−y}).

Now, as y → 0^{+}, the variable x = 1−e^{−y} has x ∼ y. But we know about the behavior of Fp̄_{X} (x) as x → 0^{+}, in particular that its limit is 1 if it exists at all, and that it exists iff p_{t}/p̄_{t} → 0. So our conditions are the same for ρ_{n} as for ρ′_{n}. □

2. The Number Theory Connection

How does this problem connect to number theory? Li’s original paper [2] considered the following problem: Let a and n be integers with (2a, n) = 1. Denote the order of a (mod n) by e_{n}(a). Denote by λ(n) the Carmichael-λ function, which is the maximal order of any element of the multiplicative group mod n. We would like to know when λ(n)/e_{n}(a) is odd.

To do this, we first classify the prime divisors of n into the classes p = 2^{j} +1 (mod 2^{j+1}) as j runs through positive integers. This gives us the highest power of 2 dividing φ(p) = λ(p) = p−1. It is known that the proportion of all primes in the jth class is asymptotically 2^{−j}. Now, the following can be proved easily:

Lemma 2 For λ(n)/e_{n}(a) to be odd, a must be a quadratic non-residue modulo at least one of the prime factors of n which has maximal j.

So as n has more prime factors in the highest class, the more likely it is that λ(n)/e_{n}(a) is odd. Asymptotic uniqueness would mean a small probability that λ(n)/e_{n}(a) is odd. So to investigate the likelihood of \frac{λ(n)}{e_{n}(a)} being odd, we model a “balls in boxes” problem as above, with the balls being the prime factors of n, the boxes being the j-classes, and p_{j} = 2^{−j}. In this paper, we have adopted the more general approach with general p_{j} and shown that lim ρ_{j} exists if and only if lim_{j→∞} \frac{p_{j}}{∑_{i≥j} p_{i}} = 0, in which case, the limit is 1. So we can see that our condition is not satisfied in the special case under consideration by Li. It was shown by Li [2] that ρ_{j} oscillates, and while our result does not give this precision, it is a nice application of Tauberian theorems, and provides a general condition under which this limit does (not) exist.

Note that most “standard” distributions on the integers such as the geometric, Poisson etc. lead to the non-existence of the limit; a normalized zeta-function distribution would lead to the limit existing. Our calculations for the geometric (p_{j} = 2^{−j}), show oscillations in the fourth decimal place; other calculations have been done by Li [2].

Acknowledgements

We would like to thank the National Science Foundation and Michigan Tech University for supporting this research through award DMS-9619889. We would like to thank our colleagues Ashwani Sastry, Ben Wieland, and Donald Ying for useful discussions. We would like to thank Krishna B. Athreya for valuable discussions on the Poisson modification and Tauberian theorems. We would like to thank Carl Pomerance and Robert Vaughan for discussions on the number theory connection. Finally, we would like to thank our REU director, Anant Godbole, not only for discussions but also for the opportunity to participate in the Michigan Tech program.

Acknowledgement of Priority (added: 4/25/01)

It has recently been brought to our attention that the results we obtained had been obtained some years ago by Eisenberg et. al. in a series of papers from the mid-1990’s (Stat and Prob. Letters 23 (1995), 203-209; Annals of Applied Probability 1993, Vol. 3, No. 3, 731-745; J. Math. Anal. and Applications, 198, 458-472 (1996), article 0092.). Even the proofs appear to be quite similar. However, neither we, nor our advisor A. Godbole, had knowledge of this previous work, and thus our work was completely independent. We also believe that the connection to number theory was not explored in the previous papers.

We would like to thank Bennet Eisenberg for bringing this matter to our attention recently.

References

[1] N.H. Bingham, C.M. Goldie, J.L. Teugels, Regular Variation, Encyclopedia of Mathematics and its Applications, Cambridge University Press, 1987.

[2] S. Li, On Artin’s Conjecture for Composite Moduli, Ph.D. Thesis, University of Georgia, 1998.

[3] S. Ross, A First Course in Stochastic Processes, MacMillan, 1998.