A Short Note on the Average Maximal Number of Balls in a Bin

Marcus Michelen University of Illinois at Chicago

Department of Mathematics, Statistics and Computer Science Chicago, IL 60607-7045 USA

                michelen.math@gmail.com

Abstract

We analyze the asymptotic behavior of the average maximal number of balls in a bin obtained by throwing uniformly at random r balls without replacement into n bins, T times. Writing the expected maximum as

\frac{r}{n}T + C_{n,r}\sqrt{T} + o(\sqrt{T}),

a recent preprint of Behrouzi-Far and Zeilberger asks for an explicit expression for C_{n,r} in terms of n, r and π. In this short note, we find an expression for C_{n,r} in terms of n, r and the expected maximum of n independent standard Gaussians. This provides asymptotics for large n as well as closed forms for small n—e.g., C_{4,2} = \frac{3}{2π^{3/2}} arccos(−1/3)—and shows that computing a closed form for C_{n,r} is precisely as hard as the difficult question of finding the expected maximum of n independent standard Gaussians.

1 Introduction

Suppose that you have n bins, and in each round, you throw r balls such that each ball lands in a different bin, with each of the \binom{n}{r} possibilities equally likely. After T rounds, set U(n, r; T) to be the maximum occupancy among the n bins. Set A(n, r; T) = 𝔼U(n, r; T) − \frac{r}{n}T; utilizing a central limit theorem, one can show that A(n, r; T) = C_{n,r}\sqrt{T} + o(\sqrt{T}). A recent preprint [2] of Behrouzi-Far and Zeilberger asks for an explicit expression for C_{n,r} in terms of n, r and π; they also calculate estimates for C_{2,1}, C_{3,1}, C_{4,1}, C_{4,2} using recurrence relations derived with computer aid. As a motivation, Behrouzi-Far and Zeilberger [2] note that this problem arises in computer systems since load distribution across servers can be modeled with balls and bins.

Rather than utilizing exact computation in the vein of Behrouzi-Far and Zeilberger [2], we use a multivariate central limit theorem to prove the following:

Theorem 1. Let C_{n,r} = lim_{T →∞} \frac{A(n,r;T)}{\sqrt{T}}. Then

C_{n,r} = \sqrt{\frac{r(n − r)}{n(n − 1)}}𝔼 ( max_{1≤j≤n} Z_{j})

where Z_{j} are i.i.d. standard Gaussians.

The multivariate central limit theorem together with the continuous mapping theorem will give that C_{n,r} is a maximum over some Gaussian vector (Lemma 5, Corollary 6, Lemma 7). Manipulating this Gaussian vector then relates this maximum to maximums of i.i.d. standard Gaussians (Lemma 8).

The expected maximum of n i.i.d. standard Gaussians appears to have no known closed form for general n and in fact the known forms for small n can be quite nasty; for instance, when n = 5, the expected value is \frac{5}{2π^{3/2}} arccos(−23/27). A short table of computed values is included in Section 3.

From here, we extract asymptotics for n → ∞, uniformly in r:

Corollary 2. As n → ∞, we have

C_{n,r} ∼ \sqrt{\frac{2r(n − r) log(n)}{n^{2}}}

uniformly in r.

Proof. Using the standard fact [4, Exercise 3.2.3] that 𝔼(max_{1≤j≤n} Z_{j}) ∼ \sqrt{2 log(n)} completes the proof (see [3, Section 10.5] for higher order information about max_{1≤j≤n} Z_{j}).

The exact form in Theorem 1 also picks up a nice combinatorial property:

Corollary 3. For each n, the sequence (C_{n,r})_{r=1}^{n−1} is log-concave.

Proof. Log-concavity follows from the inequality

(r − 1)(n − r + 1)(r + 1)(n − r − 1) = (r^{2} − 1)((n − r)^{2} − 1) ≤ r^{2}(n − r)^{2}.

To prove Theorem 1, we use a multivariate central limit theorem to prove a limit theorem for \frac{U(n,r;T)− \frac{r}{n} T}{\sqrt{T}} (Corollary 6), show that we can exchange the limit and expectation (Lemma 7), and then relate this expectation to the expected maximum of i.i.d. standard normals (Lemma 8).

2 Proving Theorem 1

We first must define the quantities of interest.

Definition 4. Set b(n, r; T) to be the random vector in {0, 1, …, T }^{n} denoting the occupancies of the bins at time T. Define X to be the random variable in {0, 1}^{n} chosen uniformly among vectors v ∈ {0, 1}^{n} with ∥v∥_{L^{1}} = r. Let Γ be the covariance matrix of X.

This immediately gives a representation for b(n, r; T), since b(n, r; T) =^{d} ∑_{j=1}^{T} X_{j} where X_{j} are i.i.d. copies of X. Aiming to use a multivariate central limit theorem, we must calculate the covariance matrix Γ of X.

Lemma 5. The matrix Γ is given by

Γ_{i,j} = \begin{cases}\frac{r(n−r)}{n^{2}}, & for i = j; \\ −\frac{r(n−r)}{n^{2}(n−1)}, & otherwise. \end{cases}

Proof. The coordinates of X are Bernoulli random variables with success parameter r/n and

covariance 𝔼[X^{(i)}X^{(j)}] = \begin{matrix}( & {n−2 \atop r−2} & ) \\ ( & {n \atop r} & ) \end{matrix} for i ≠ j. The covariance matrix Γ may then be calculated

easily:

Γ_{j,j} = \frac{r}{n} (1 − \frac{r}{n}) = \frac{r(n − r)}{n^{2}}.

For Γ_{i,j} with i ≠ j, we compute

Γ_{i,j} = \begin{matrix}( & {n−2 \atop r−2} & ) \\ ( & {n \atop r} & ) \end{matrix} − \frac{r^{2}}{n^{2}} = −\frac{r(n − r)}{n^{2}(n − 1)}.

From here, the multivariate central limit theorem shows convergence in distribution.

Corollary 6. We have

\frac{U(n, r; T) − \frac{r}{n}T}{\sqrt{T}} ⟶^{d} max\{Y_{1}, …, Y_{n}\}

where (Y_{1}, …, Y_{n}) is a mean-zero multivariate Gaussian with covariance matrix Γ, and the convergence is in distribution.

Proof. The multivariate central limit theorem [4, Thm. 3.9.6] implies that

\frac{b(n, r; T) − 𝔼b(n, r; T)}{\sqrt{T}} → N (0, Γ).

The identity 𝔼b(n, r; T) = (\frac{r}{n}, …, \frac{r}{n}) together with an application of the continuous mapping theorem to the maximum function implies the Corollary.

To gain information about A(n, r; T), we need to show that not only do we have convergence in distribution, but that we can switch the order of taking limits and expectation.

Lemma 7.

C_{n,r} := lim_{T →∞} \frac{A(n, r; T)}{\sqrt{T}} = 𝔼 max\{Y_{1}, …, Y_{n}\}

where (Y_{1}, …, Y_{n}) are jointly Gaussian with mean 0 and covariance matrix given by Γ as defined in Lemma 5.

Proof. Our strategy is to show uniform integrability of Û(T) := (U(n, r; T) − \frac{r}{n}T)/\sqrt{T}; for j ∈ {1, 2, …, n}, let b^{(j)} denote the number of balls in bin j. Then by a union bound, we have

ℙ (|U(n, r; T) − \frac{r}{n}T | ≥ λ\sqrt{T} ) ≤ nℙ (|b^{(1)} − \frac{r}{n}T | ≥ λ\sqrt{T} ) .  (1)

Since b^{(1)} is a sum of independent Bernoulli random variables, we may apply Hoeffding’s inequality (e.g., [1, Thm. 7.2.1]) to bound

ℙ (|b^{(1)} − \frac{r}{n}T | ≥ λ\sqrt{T} ) ≤ 2 exp (−2λ^{2}) .

Thus, for each T and K > 0 we have

𝔼 (|Û(T)| · 1_{|Û(T)|≥K}) ≤ 2n ∫_{K}^{∞} e^{−2λ^{2}} dλ.

This goes to zero uniformly in T as K → ∞, thereby showing that the family (Û(T))_{T ≥0} is uniformly integrable. Since uniform integrability together with convergence in distribution implies convergence of means, Corollary 6 completes the proof.

All that remains now is to relate 𝔼 max{Y_{1}, …, Y_{n}} to the right-hand-side of Theorem 1.

Lemma 8. Let (Y_{1}, …, Y_{n}) be jointly Gaussian with mean 0 and covariance matrix Γ. Then

𝔼(max\{Y_{1}, …, Y_{n}\}0 = \sqrt{\frac{r(n − r)}{n(n − 1)}}𝔼 ( max_{1≤j≤n} Z_{j})

where the variables Z_{j} are i.i.d. standard Gaussians.

Proof. Consider a multivariate Gaussian (W_{1}, …, W_{n}) with mean 0 and covariance matrix given by

Γ̃_{i,j} = \begin{cases}\frac{n}{n−1}, & for i = j; \\ −\frac{n}{(n−1)^{2}} , & for i ≠ j. \end{cases}

Since Γ = \frac{r(n−r)(n−1)}{n^{3}} Γ̃, we have

(Y_{1}, …, Y_{n}) =^{d} \sqrt{\frac{r(n − r)(n − 1)}{n^{3}}}(W_{1}, …, W_{n}).  (2)

The vector (W_{1}, …, W_{n}) can in fact be realized by setting W_{j} = Z_{j} − ^{\frac{∑_{i≠j} Z_{i}}{n−1}} with Z_{i} i.i.d. standard Gaussians. This is because the two vectors are both mean-zero multivariate Gaussians and have the same covariance matrix. Setting S_{n} = ∑_{i=1}^{n} Z_{i}, we note

W_{j} = −\frac{S_{n}}{n − 1} + \frac{n}{n − 1}Z_{j}

thereby implying

max_{1≤j≤n}\{W_{j}\} = −\frac{S_{n}}{n − 1} + (\frac{n}{n − 1}) max_{1≤j≤n}\{Z_{j}\}.

Taking expectations and utilizing (2) completes the proof.

Remark 9. The final piece of the proof of Lemma 8—relating the expected maximum of the process (Z_{j} − ^{\frac{∑_{i≠j} Z_{i}}{n−1}} )_{j=1}^{n} to that of (Z_{j})_{j=1}^{n}—is due to a Math Overflow answer of Iosef Pinelis [5]. Further, the vector (W_{1}, …, W_{n}) is in fact equal in distribution to the vector (Z_{1}, …, Z_{n}) conditioned to sum to 0.

Theorem 1 now follows from combining Lemmas 7 and 8.

3 Comparison with numerical values

Theorem 1 proves an equality for C_{n,r}, although for large n, the expectation on the righthand-side of Theorem 1 appears to have no known closed form. Calculating these values for small n is tricky and tedious; we reproduce a few values of 𝔼(max_{1≤j≤n} Z_{j}) which can be computed precisely, as calculated by Selby [6]:

n 𝔼(max_{1≤j≤n} Z_{j})
2 π^{−1/2}
3 (3/2)π^{−1/2}
4 3π^{−3/2} arccos(−1/3)
5 (5/2)π^{−3/2} arccos(−23/27)

Table 1: List of expected values of maximum of Gaussians.

We can then use these to obtain exact values for the values of C_{n,r} predicted in Behrouzi-Far and Zeilberger [2], and note that their predictions are quite close:

Exact value  Numerical approximation Predicted value [2]
C_{2,1}  \frac{1}{\sqrt{2π}}  0.39894 …  0.3989 …
C_{3,1}  \frac{\sqrt{3}}{2\sqrt{π}}  0.48860 …  0.489 …
C_{4,1} \frac{3}{2π^{3/2}} arccos(−1/3)  0.51469 …  0.516 …
C_{4,2} \frac{\sqrt{3}}{π^{3/2}} arccos(−1/3)  0.59431 …  0.59430 …

Table 2: Comparison of exact values of C_{n,r} with predictions from Behrouzi-Far and Zeilberger [2].

References

[1] N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley & Sons, Inc., 3rd edition, 2008.

[2] A. Behrouzi-Far and D. Zeilberger. On the average maximal number of balls in a bin resulting from throwing r balls into n bins t times. Preprint, 2019, https://arxiv.org/

   abs/1905.07827.

[3] H. A. David and H. N. Nagaraja. Order Statistics. Wiley Online Library, 2004.

[4] R. Durrett. Probability: Theory and Examples. Cambridge University Press, 4th edition, 2010.

[5] I. Pinelis. Expectation of maximum of multivariate Gaussian. MathOverflow posting.

   Available at https://mathoverflow.net/q/332113.

[6] A. Selby. Expected value for maximum of a normal random variable. Mathematics Stack

   Exchange posting. Available at https://math.stackexchange.com/q/510580.

2010 Mathematics Subject Classification: Primary 05A16. Keywords: balls in bins, central limit theorem, multivariate Gaussian.

Received August 19 2019; revised versions received October 17 2019; October 23 2019. Published in Journal of Integer Sequences, December 30 2019.

Return to Journal of Integer Sequences home page.