\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\one}{\mathbf{1}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\PP}{\mathbb{P}}
	
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
	\vskip 1cm{\LARGE\bf 
		A Short Note on the Average Maximal \\
		\vskip .1in
		Number of Balls in a Bin
	}
	\vskip 1cm
	\large
	Marcus Michelen \\
	University of Illinois at Chicago \\
	Department of Mathematics, Statistics and Computer Science \\
	Chicago, IL 60607-7045 \\
	USA \\
	\href{mailto:michelen.math@gmail.com}{\tt michelen.math@gmail.com}
\end{center}

\vskip .2 in

\begin{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 $\pi$.  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
\pi^{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.
\end{abstract}


\section{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 ${n \choose 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) = \E 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 \cite{BFZ} of Behrouzi-Far and Zeilberger asks for an explicit expression for $C_{n,r}$ in terms of $n,r$ and $\pi$; 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 \cite{BFZ} 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 \cite{BFZ}, we use a multivariate central limit theorem to prove the following:  

\begin{theorem}\label{th:main} Let $C_{n,r} = \lim_{T \to \infty} \frac{A(n,r;T)}{\sqrt{T}}$.  Then
	$$C_{n,r} = \sqrt{\frac{r(n-r)}{n(n-1)}} \E\left( \max_{1 \leq j \leq n} Z_j \right)$$
	where $Z_j$ are i.i.d.\ standard Gaussians.  
\end{theorem}

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 \ref{lem:brep}, Corollary \ref{cor:convindist}, Lemma \ref{lem:form}).  Manipulating this Gaussian vector then relates this maximum to maximums of i.i.d.\ standard Gaussians (Lemma \ref{lem:compY}).

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 \pi^{3/2}} \arccos(-23/27)$.  A short table of computed values is included in Section \ref{sec:numbers}. 

From here, we extract asymptotics for $n \to \infty$, uniformly in $r$: \begin{corollary}
	As $n \to \infty$, we have 
	$$C_{n,r} \sim \sqrt{\frac{2r(n-r)\log(n)}{n^2}} $$
	uniformly in $r$.
\end{corollary}
\begin{proof}
	Using the standard fact  \cite[Exercise 3.2.3]{durrett} that $\E(\max_{1 \leq j \leq n} Z_j  ) \sim \sqrt{ 2 \log(n) }$ completes the proof (see \cite[Section 10.5]{david2004order} for higher order information about $\max_{1 \leq j \leq n} Z_j$).
\end{proof}

The exact form in Theorem \ref{th:main} also picks up a nice combinatorial property: \begin{corollary}
	For each $n$, the sequence $(C_{n,r})_{r=1}^{n-1}$ is log-concave. 
\end{corollary}
\begin{proof}
	Log-concavity follows from the inequality $$(r-1)(n-r+1)(r+1)(n-r-1) = (r^2 - 1)((n-r)^2 - 1)\leq r^2 (n-r)^2.$$	
\end{proof}

To prove Theorem \ref{th:main}, 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 \ref{cor:convindist}), show that we can exchange the limit and expectation (Lemma \ref{lem:form}), and then relate this expectation to the expected maximum of i.i.d.\ standard normals (Lemma \ref{lem:compY}). 

\section{Proving Theorem~\ref{th:main}}

We first must define the quantities of interest.

\begin{definition}
	Set $b(n,r;T)$ to be the random vector in $\{0,1,\ldots,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 \in \{0,1\}^n$ with $\| v \|_{L^1} = r$.  Let $\Gamma$ be the covariance matrix of $X$.
\end{definition}
 
This immediately gives a representation for $b(n,r; T)$, since $b(n,r;T) \overset{d}{=} \sum_{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 $\Gamma$ of $X$.

\begin{lemma}\label{lem:brep}
	The matrix $\Gamma$ is given by $$\Gamma_{i,j} = \begin{cases}
	\frac{r(n-r)}{n^2}, &\text{ for }i = j; \\
	-\frac{r(n-r)}{n^2(n-1)}, &\text{ otherwise.}
	\end{cases}$$
\end{lemma}
\begin{proof}
	The coordinates of $X$ are Bernoulli random variables with success parameter $r/n$ and covariance $\E[X^{(i)} X^{(j)}] = \frac{  {{n-2} \choose {r-2}}  }{ {{n} \choose {r}} }$ for $i \neq j$. 
	The covariance matrix $\Gamma$ may then be calculated easily: $$\Gamma_{j,j} = \frac{r}{n}\left(1 - \frac{r}{n}\right) = \frac{r(n-r)}{n^2}.$$
For $\Gamma_{i,j}$ with $i \neq j$, we compute $$\Gamma_{i,j} = \frac{  {{n-2} \choose {r-2}}  }{ {{n} \choose {r}} } - \frac{r^2}{n^2} = -\frac{r(n-r)}{n^2(n-1)}.$$
\end{proof}


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

\begin{corollary}\label{cor:convindist} We have
$$\frac{U(n,r;T) - \frac{r}{n} T }{\sqrt{T}} \xrightarrow{d} \max\{Y_1,\ldots, Y_n \}$$
where $(Y_1,\ldots,Y_n)$ is a mean-zero multivariate Gaussian with covariance matrix $\Gamma$, and the convergence is in distribution.
\end{corollary}
\begin{proof}
	The multivariate central limit theorem \cite[Thm.\ 3.9.6]{durrett} implies that $$\frac{b(n,r;T) - \E b(n,r;T)}{\sqrt{T}} \to \mathcal{N}(0,\Gamma).$$
	The identity $\E b(n,r;T) = (\frac{r}{n},\ldots,\frac{r}{n})$ together with an application of the continuous mapping theorem to the maximum function implies the Corollary.	
\end{proof}

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.

\begin{lemma}\label{lem:form}
	$$C_{n,r} := \lim_{T \to \infty}\frac{ A(n,r ; T)}{\sqrt{T}} = \E \max\{Y_1,\ldots,Y_n\}  $$
	where $(Y_1,\ldots,Y_n)$ are jointly Gaussian with mean $0$ and covariance matrix given by $\Gamma$ as defined in Lemma \ref{lem:brep}.
\end{lemma}
\begin{proof}
	Our strategy is to show uniform integrability of $\widehat{U}(T) := (U(n,r;T) - \frac{r}{n} T)/\sqrt{T}$; for $j \in \{1,2,\ldots,n\}$, let $b^{(j)}$ denote the number of balls in bin $j$.  Then by a union bound, we have \begin{equation}
	\PP\left( \left|U(n,r;T) - \frac{r}{n}T \right| \geq \lambda \sqrt{T} \right) \leq n \PP\left( \left|b^{(1)} - \frac{r}{n}T\right| \geq \lambda \sqrt{T} \right).
	\end{equation}
Since $b^{(1)}$ is a sum of independent Bernoulli random variables, we may apply Hoeffding's inequality (e.g., \cite[Thm.\ 7.2.1]{pm}) to bound $$\PP\left( \left|b^{(1)} - \frac{r}{n}T\right| \geq \lambda \sqrt{T} \right) \leq 2 \exp\left(-2 \lambda^2  \right).$$
Thus, for each $T$ and $K > 0$ we have $$\E\left( |\widehat{U}(T)|\cdot \one_{|\widehat{U}(T)| \geq K  } \right) \leq 2n \int_{K}^\infty e^{-2 \lambda^2}\,d\lambda.  $$
	
	This goes to zero uniformly in $T$ as $K \to \infty$, thereby showing that the family $(\widehat{U}(T))_{T \geq 0}$ is uniformly integrable.  Since uniform integrability together with convergence in distribution implies convergence of means, Corollary \ref{cor:convindist} completes the proof.
\end{proof}

All that remains now is to relate $\E \max \{Y_1,\ldots,Y_n  \}$ to the right-hand-side of Theorem \ref{th:main}.

\begin{lemma}\label{lem:compY}
	Let $(Y_1,\ldots,Y_n)$ be jointly Gaussian with mean $0$ and covariance matrix $\Gamma$.  Then $$\E( \max \{ Y_1,\ldots,Y_n\}0 = \sqrt{\frac{r(n-r)}{n(n-1)}} \E\left(\max_{1 \leq j \leq n}Z_j \right)$$
	where the variables $Z_j$ are i.i.d.\ standard Gaussians.
\end{lemma}
\begin{proof}
	Consider a multivariate Gaussian $(W_1,\ldots,W_n)$ with mean $0$ and covariance matrix given by $$\widetilde{\Gamma}_{i,j} = \begin{cases}
	\frac{n}{n-1}, &\text{ for }i = j;\\
	-\frac{n}{(n-1)^2}, &\text{ for }i \neq j.
	\end{cases}$$
Since $\Gamma = \frac{r(n-r)(n-1)}{n^3} \widetilde{\Gamma}$, we have 
\begin{equation}\label{eq:YnWn}
	(Y_1,\ldots,Y_n) \stackrel{d}{=} \sqrt{\frac{r(n-r)(n-1)}{n^3}} (W_1,\ldots,W_n).
	\end{equation} The vector $(W_1,\ldots,W_n)$ can in fact be realized by setting $W_j = Z_j - \frac{\sum_{i \neq 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 = \sum_{i = 1}^n Z_i$, we note $$W_j = -\frac{S_n}{n-1} + \frac{n}{n-1} Z_j$$
thereby implying $$\max_{1 \leq j \leq n} \{W_j\} = -\frac{S_n}{n-1} + \left(\frac{n}{n-1} \right) \max_{1 \leq j \leq n} \{Z_j\}.$$
Taking expectations and utilizing \eqref{eq:YnWn} completes the proof. 
\end{proof}

\begin{remark}
	The final piece of the proof of Lemma \ref{lem:compY}---relating the expected maximum of the process $(Z_j - \frac{\sum_{i \neq 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 \cite{pinelis}.  Further, the vector $(W_1,\ldots,W_n)$ is in fact equal in distribution to the vector $(Z_1,\ldots,Z_n)$ conditioned to sum to $0$.
\end{remark}
Theorem \ref{th:main} now follows from combining Lemmas \ref{lem:form} and \ref{lem:compY}. 

\section{Comparison with numerical values}  \label{sec:numbers}

Theorem \ref{th:main} proves an equality for $C_{n,r}$, although for large $n$, the expectation on the right-hand-side of Theorem \ref{th:main} appears to have no known closed form.  Calculating these values for small $n$ is tricky and tedious; we reproduce a few values of $\E(\max_{1 \leq j \leq n} Z_j)$ which can be computed precisely, as calculated by Selby \cite{table-of-values}:

\begin{table}[h]
\begin{center}
\begin{tabular}{ r | l  }

	$n$ & $\E(\max_{1 \leq j \leq n} Z_j)$ \\ \hline
	2 & $\pi^{-1/2}$ \\ \hline
	3 & $(3/2) \pi^{-1/2}$ \\ \hline
	4 & $3 \pi^{-3/2} \arccos(-1/3)$ \\ \hline
	5 & $(5/2) \pi^{-3/2} \arccos(-23/27)$ \\
	
\end{tabular}
\caption{List of expected values of maximum of Gaussians.} 
\end{center}
\end{table}

We can then use these to obtain exact values for the values of $C_{n,r}$ predicted in Behrouzi-Far and Zeilberger \cite{BFZ}, and note that their predictions are quite close:
\begin{table}[H]
\begin{center}
	\begin{tabular}{ c | c | c | c  }
		
		 & Exact value & Numerical approximation & Predicted value \cite{BFZ}  \\ \hline 
		$C_{2,1}$ & $\frac{1}{\sqrt{2\pi}}$  & $0.39894\ldots$ & $0.3989\ldots$\\ \hline
		$C_{3,1}$ & $\frac{\sqrt{3}}{2 \sqrt{\pi}}$  & $0.48860\ldots$ & $0.489\ldots$\\ \hline
		$C_{4,1}$ & $\frac{3}{2 \pi^{3/2}} \arccos(-1/3)$ & $0.51469\ldots$ & $0.516\ldots$ \\ \hline
		$C_{4,2}$ & $\frac{\sqrt{3}}{\pi^{3/2}}\arccos(-1/3)$ & $0.59431\ldots$ & $0.59430\ldots$
		
	\end{tabular}
\caption{Comparison of exact values of $C_{n,r}$ with predictions from Behrouzi-Far and Zeilberger \cite{BFZ}.}
\end{center}
\end{table}

\begin{thebibliography}{9}
	
	\bibitem{pm}
	N.~Alon and J.~H. Spencer.
	\newblock {\em The Probabilistic Method}.
	\newblock John Wiley \& Sons, Inc., 3rd edition, 2008.
		
	\bibitem{BFZ}
	A.~Behrouzi-Far and D.~Zeilberger.
	\newblock On the average maximal number of balls in a bin resulting from
	throwing $r$ balls into $n$ bins $t$ times.
	\newblock Preprint, 2019, \url{https://arxiv.org/abs/1905.07827}.
	
	\bibitem{david2004order}
	H.~A. David and H.~N. Nagaraja.
	\newblock {\em Order Statistics}.
	\newblock Wiley Online Library, 2004.
	
	\bibitem{durrett}
	R.~Durrett.
	\newblock {\em Probability: Theory and Examples}.
	\newblock Cambridge University Press, 4th edition, 2010.
	
	\bibitem{pinelis}
	I.~Pinelis.
	\newblock Expectation of maximum of multivariate Gaussian.
	\newblock MathOverflow posting.
	\newblock Available at \url{https://mathoverflow.net/q/332113}.
	
	\bibitem{table-of-values}
	A.~Selby.
	\newblock Expected value for maximum of a normal random variable.
	\newblock Mathematics Stack Exchange posting.
	\newblock Available at \url{https://math.stackexchange.com/q/510580}.
	
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A16.

\noindent \emph{Keywords: } 
balls in bins, central limit theorem, multivariate Gaussian.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 19 2019;
revised versions received October 17 2019; October 23 2019.
Published in {\it Journal of Integer Sequences}, December 30 2019.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}