# Balls and Bins - Simple Concentration Bounds

Ernst Schulte-Geers  Bo Waggoner

###### Abstract

Concentration bounds are given for throwing balls into bins independently
according to a distribution $p$. The probability of a $k$-loaded bin after $m$
balls is shown to be controlled on both sides by
$\rho_{m,k}\coloneqq\frac{m\|p\|_{k}}{k}$. This gives concentration
inequalities for the maximum load as well as for the waiting time until a
$k$-loaded bin.

##  1 Introduction

In a classic problem, balls are thrown randomly into $n$ bins. Each ball
selects a bin independently from a probability distribution $p$, where
$p_{i}\geq 0$ and $\sum_{i=1}^{n}p_{i}=1$. The set of probability
distributions on bins is denoted $\Delta_{n}$. We seek non-asymptotic
probability bounds on the max-loaded bin, in terms of two quantities:

  * •

$B_{m}$, the maximum load after throwing $m$ balls (i.e. the maximum entry of
a multinomial); and

  * •

$T_{k}$, the number of trials until the maximum load is $k$.

Naturally, much research in this vein exists (Section 1.2), particularly for
the uniform distribution. This work contributes by giving nonasymptotic
concentration bounds that aim to be user-friendly; and by showing that these
bounds are controlled by the quantity

$\rho_{m,k}\coloneqq\frac{m\|p\|_{k}}{k}.$ (1)

In particular, we observe a phase change in the likelihood of a $k$-loaded bin
as $\rho_{m,k}$ changes by a small constant factor around $\rho_{m,k}=1$. This
gives concentration results for $B_{m}$ around the quantity $k^{*}$ where
$\rho_{m,k^{*}}=1$; and for $T_{k}$ around $m^{*}$ where $\rho_{m^{*},k}=1$.

###  1.1 Results

Let $\operatorname{Binom}(m,\alpha)$ denote a Binomial random variable with
$m$ trials and $\alpha$ probability of success. We state most results in terms
of $B_{m}$, but a reformulation for $T_{k}$ is immediate by the observation
that $\Pr[T_{k}\leq m]=\Pr[B_{m}\geq k]$.

######  Theorem 1.

Let integers $m\geq 0$, $n\geq 1$, and $k\geq 1$ be given. Let
$p\in\Delta_{n}$ be given and throw balls into $n$ bins indepedently with
distribution $p$. Let $B_{m}$ be the maximum load after $m$ trials. Then

$\Pr[\operatorname{Binom}(m,\|p\|_{k})\geq k]~{}\leq~{}\Pr[B_{m}\geq
k]~{}\leq~{}{m\choose k}\|p\|_{k}^{k}.$

The proofs of the upper and lower bounds appear in Sections 2 and 3
respectively. Section 6 generalizes the result to the case where
$n=\aleph_{0}$ and we are interested in the maximum load of any subset of
bins. Illustrations of the bounds’ tightness in simulations appear in Section
4.

We next leverage Theorem 1 to obtain more specific tail bounds. The proofs of
the following corollaries appear in Section 5. Throughout, recall that
$\Pr[T_{k}\leq m]=\Pr[B_{m}\geq k]$ and recall (1), the definition of
$\rho_{m,k}$.

######  Corollary 1.

Throw $m\geq 1$ balls into $n\geq 2$ bins independently according to
$p\in\Delta_{n}$. For any $k\in[1,\infty)$:

$\displaystyle\Pr{\left[B_{m}\geq k\right]}$
$\displaystyle\leq\exp\left(-k~{}\ln(\tfrac{1}{e\cdot\rho_{m,k}})\right)$ if
$\rho_{m,k}<1/e$; and $\displaystyle\Pr{\left[B_{m}\geq k\right]}$
$\displaystyle\geq
1-\exp\left(-k~{}\left(\rho_{m,k}-\ln(e\cdot\rho_{m,k})\right)\right)$
$\displaystyle\text{if $\rho_{m,k}>1$}.$

######  Corollary 2.

Throw $m\geq 1$ balls into $n\geq 2$ bins independently according to
$p\in\Delta_{n}$. For any $k\in[1,\infty)$ and $\delta\in(0,1)$:

$\displaystyle\Pr{\left[B_{m}\geq k\right]}$ $\displaystyle\leq\delta$ if
$\rho_{m,k}\leq\left(\frac{\delta^{1/k}}{e}\right)$
$\displaystyle\Pr{\left[B_{m}\geq k\right]}$ $\displaystyle\geq 1-\delta$ if
$\rho_{m,k}\geq\max\left\\{e^{2},2\ln(\tfrac{1}{\delta^{1/k}})\right\\}$.

Finally, we derive concentration bounds for $B_{m}$ and $T_{k}$.

######  Corollary 3.

Throw $m\geq 1$ balls into $n\geq 2$ bins independently according to
$p\in\Delta_{n}$. Define $k^{*}\in[1,\infty)$ to be the solution of
$\frac{k^{*}}{\|p\|_{k^{*}}}=m$. For any $\delta\in(0,1)$:

$\displaystyle\Pr{\left[B_{m}\geq\left(\frac{e}{\delta}\right)k^{*}\right]}$
$\displaystyle\leq\delta$ and (2)
$\displaystyle\Pr{\left[B_{m}\geq\frac{1}{\max\left\\{e^{2},2\ln(\tfrac{1}{\delta})\right\\}}k^{*}\right]}$
$\displaystyle\geq 1-\delta.$ (3)

######  Corollary 4.

Throw balls into $n\geq 2$ bins independently according to $p\in\Delta_{n}$
and let $k\in\mathbb{N},k\geq 1$. Define $m^{*}=\frac{k}{\|p\|_{k}}$. Then for
any $\delta\in(0,1)$:

$\displaystyle\Pr{\left[T_{k}\leq\left(\frac{\delta}{e}\right)m^{*}\right]}$
$\displaystyle\leq\delta$ and (4)
$\displaystyle\Pr{\left[T_{k}\leq\max\left\\{e^{2},2\ln(\tfrac{1}{\delta})\right\\}m^{*}\right]}$
$\displaystyle\geq 1-\delta.$ (5)

Finally, we observe that Theorem 1 directly implies simple bounds on
$\operatorname*{\mathbb{E}}T_{k}$. As discussed in Section 5, the upper bound
is the best possible and the lower bound almost so (for completeness, we will
mention a slightly better one).

######  Corollary 5.

Let $n\geq 1$, $p\in\Delta_{n}$, and $k\in\mathbb{N},k\geq 1$. Then

$\left(\frac{1}{e}\right)\left(\frac{k}{k+1}\right)\frac{k}{\|p\|_{k}}\leq\operatorname*{\mathbb{E}}T_{k}\leq\frac{k}{\|p\|_{k}}.$

#### Remarks.

Depending on the application, the concentration bound for $B_{m}$ (Corollary
3) may or may not be satisfactory. For small, e.g. single-digit maximum loads
$k^{*}$, a constant-factor interval may be considered too wide. And even for
large $k^{*}$, true confidence interval around $B_{m}$ could be as small as
width zero in some scenarios, making a constant-factor range comparatively
loose.111We used the naive bound $\|p\|_{k}\geq\|p\|_{k+1}$. If this is far
from tight, then $\rho_{m,k}\gg\rho_{m,k+1}$, implying that a confidence
interval need not contain both $k$ and $k+1$. On the other hand, if it is
close to tight, then $p$ is in a sense far from uniform, and the maximum bin
may exhibit some concentration for this reason. Perhaps future work can
leverage this tradeoff to give tighter bounds.

We expect the confidence interval for $T_{k}$, Corollary 4, to be sufficient
and useful for many scenarios. It gives a closed-form $m^{*}$ for
approximately how many balls must be thrown until some bin receives $k$ balls;
and shows that within a small constant factor around $m^{*}$, the probability
transitions from almost $0$ to almost $1$.

More generally, Corollary 2 suggests a kind of phase transition for
$\Pr{\left[B_{m}\geq k\right]}$ around $\rho_{m,k}=1$. In Section 4, we use
simulation results to illustrate this transition along with the tightness of
Theorem 1.

As $\rho_{m,k}\to\infty$, we observe $\Pr[B_{m}<k]\to 0$ exponentially fast in
$\rho_{m,k}$. However, as $\rho_{m,k}\to 0$, we only obtain $\Pr[B_{m}\geq
k]\to 0$ polynomially in $\tfrac{1}{\rho_{m,k}}$. Given that the upper bound,
$\Pr[B_{m}\geq k]\leq{m\choose k}\|p\|_{k}$, arises from a simple Markov
inequality (we will see), one might expect it to be loose. However, in this
regime the upper and lower bounds match up to a factor only depending on $k$.
Specifically, consider the regime $\rho_{m,k}\leq\tfrac{1}{2}$, i.e.
$m\|p\|_{k}\leq\tfrac{k}{2}$. Suppose for example that
$\|p\|_{k}\leq\tfrac{1}{2}$, then we obtain

$\displaystyle{m\choose k}\|p\|_{k}^{k}$ $\displaystyle\geq\Pr[B_{m}\geq k]$
$\displaystyle\geq\Pr[\operatorname{Binom}(m,\|p\|_{k})=k]$
$\displaystyle\geq(1-\|p\|_{k})^{m}{m\choose k}\|p\|_{k}^{k}$
$\displaystyle\geq\exp\left(-2m\|p\|_{k}\right){m\choose k}\|p\|_{k}^{k}$
$\displaystyle\geq e^{-k}{m\choose k}\|p\|_{k}^{k}.$

If $m\|p\|_{k}\to 0$, then the upper and lower bounds match to a factor $1\pm
o(1)$; this is illustrated for $k=2$ in Figure 3.

#### Applications with the uniform distribution.

For any $p$ and $m$, a rough estimate of the max loaded bin can be obtained
simply by solving $\rho_{m,k}\approx 1$ for $k$ (though this calculation is
not always simple). By Corollary 3, with high probability this estimate will
be within a constant factor of $B_{m}$. Similarly, for any $p$ and $k$, an
estimate of the number of throws until a $k$-loaded bin can be obtained by the
calculation $\rho_{m,k}\approx 1$ (which is simple). In particular when $p$ is
uniform, then $\|p\|_{k}=\frac{n^{1/k}}{n}$ and

$\rho_{m,k}=\frac{mn^{1/k}}{nk}.$

We recover some known results, possibly with more application-friendly tail
bounds than have been previously stated.

  * •

For the classic birthday paradox, set $k=2$, obtaining
$\rho_{m,k}=\frac{m}{2\sqrt{n}}$ and $m^{*}=2\sqrt{n}$. Apply Corollary 4 to
obtain that $\tfrac{2\delta}{e}\sqrt{n}\leq
T_{k}\leq\max\\{2e^{2},4\ln(\tfrac{1}{\delta})\\}\sqrt{n}$ except with
probability $2\delta$. The polynomial dependence on $\delta$ in the lower
bound appears necessary (cf. above remarks and Figure 3).

  * •

In the classic case of $m=n$, the problem $\rho_{m,k}=1$ reduces to solving
$k^{k}=n$, or $k\approx\frac{\ln(n)}{\ln(\ln(n))}$.

  * •

For another example, if $m=n\log(n)$, then for $k=\log(n)$ we have
$\rho_{m,k}=1$ exactly.

  * •

Similarly, consider any $m\geq n\log(n)$. Then $k^{*}\leq e\tfrac{m}{n}$, by
observing that for $k=e\cdot\tfrac{m}{n}$ we have $\rho_{m,k}\leq 1$. As
$k^{*}\leq e\tfrac{m}{n}$, the maximum load is concentrated within a small
constant factor of the average load.

###  1.2 Related work

The waiting time $T_{k}$ for the first $k$-fold repeat is subject of the
classical $k$-birthday problem and has been intensively investigated. The
literature is vast, we just give some pointers. Most of the research focuses
on asymptotic results for the case of uniformly distributed birthdays (bins).
Von Mises (1939) started by proving Poisson limits for the number of $k$-bins,
and Klamkin and Newman (1967) gave an elegant integral representation for
$\mathbb{E}(T_{k})$ and proved asymptotic Weibull distribution of $T_{k}$.
Raab and Steger (1998) gives precise estimates for the max-loaded bin in a
variety of regimes. However, these results focus on the uniform distribution
only and are asymptotic. For the non-uniform case the possible limit
distributions for $T_{k}$ were given by Camarri and Pitman (2000) ($k=2$)
resp. Camarri (1998) ($k>2$).

For obtaining bounds multinomial probabilities must be estimated, and several
common approaches are known. For the upper bound, a common basic approach is
to separately bound the chance that each bin is $k$-loaded and apply a union
bound (Bonferroni correction). For the lower bound, one can utilize _negative
dependence_ (Dubhashi and Ranjan, 1996), based on the inequality of Mallows.
Another general technique is to approximate the process by independent Poisson
variables in each bin. This work differs from such results in that it
emphasizes the role of $\rho_{m,k}$ in controlling the probabilities, and that
it gives nonasymptotic bounds.

For non-uniform $p$, non-asymptotic bounds for the case $n=2$ were studied by
Wiener (2005), and the lower bound of Theorem 1 for the case $k=2$ was already
proved there. Holst (1995) studies the general $k$-birthday problem and shows
that $\Pr[T_{k}\leq m]$ is Schur-convex in $p$. Thus $\Pr[T_{k}\leq m]$ is for
a given $\|p\|_{k}=c$ minimized resp. maximized for the distributions which
are minimal resp. maximal (in the order of majorization) under this side
condition. A possible route to bounds then consists in determining these
minimal/maximal distributions and to proceed from there. This is in essence
Wiener’s approach. The same idea could be followed for $n>2$, but the
arguments become lengthy and tedious. In contrast we derive bounds here by
elementary direct arguments.

##  2 Upper bound

Recall that $B_{m}$ is the maximum load when $m\geq 0$ balls are thrown
independently into $n\geq 1$ bins with distribution $p\in\Delta_{n}$. Let
$k\geq 1$.

######  Proposition 1.

$\Pr[B_{m}\geq k]\leq{m\choose k}\|p\|_{k}^{k}.$

###### Proof.

Let $Z_{k}\subseteq\\{1,\dots,m\\}$ be the set of all subsets of $k$ distinct
balls. For $S\in Z_{k}$, let $\mathbf{1}\left[S\right]$ be the indicator that
all balls in $S$ fall into the same bin; we call the event
$\\{\mathbf{1}\left[S\right]=1\\}$ a _$k$ -way collision_. Define
$C_{k}=\sum_{S\in Z_{k}}\mathbf{1}\left[S\right]$, the number of $k$-way
collisions.

For each $S\in Z_{k}$, we have
$\operatorname*{\mathbb{E}}[\mathbf{1}\left[S\right]]=\sum_{i=1}^{n}p_{i}^{k}=\|p\|_{k}^{k}$.
This follows because the event $\\{\mathbf{1}\left[S\right]=1\\}$ is the
disjoint union of the events that all balls fall into bin $1$ or …or $n$.

Thus, $\operatorname*{\mathbb{E}}[C_{k}]=|Z_{k}|\|p\|_{k}^{k}={m\choose
k}\|p\|_{k}^{k}$. Now,

$\displaystyle\Pr[B_{m}\geq k]$ $\displaystyle=\Pr[C_{k}\geq 1]$
$\displaystyle\leq\operatorname*{\mathbb{E}}\left[C_{k}\right]$ Markov’s
inequality $\displaystyle={m\choose k}\|p\|_{k}^{k}.$

∎

##  3 Lower bound

Recall that $B_{m}$ is the maximum load when $m\geq 0$ balls are thrown
independently into $n\geq 1$ bins with distribution $p\in\Delta_{n}$. Let
$k\geq 1$. Write $[n]=\\{1,\dots,n\\}$. In this section, we prove:

######  Proposition 2.

$\Pr[B_{m}\geq k]\geq\Pr[\operatorname{Binom}(m,\|p\|_{k})\geq k].$

The proof will modify $p$ to some $p^{\prime}$ and consider the maximum load
of only bins $2,\dots,n$. By repeating the argument, we eventually compare to
the maximum load under some $q$ of only the final bin, and we show that
$q_{n}=\|p\|_{k}$.

To execute this argument, we utilize a stand-alone proof of Proposition 2 for
the $n=2$ case, starting with a useful known fact (e.g. Knuth (2019), Vol. 4,
Fascicle 5, Mathematical Preliminaries Redux, Problem 23):

######  Fact 1.

Let $0\leq\alpha\leq 1$ and $0\leq t\leq m-1$. Then
$\Pr[\operatorname{Binom}(m,\alpha)\leq
t]=(1-\alpha)^{m-t}\sum_{j=0}^{t}{m-t-1+j\choose j}\alpha^{j}$.

###### Proof.

Suppose we flip coins independently with success probability $\alpha$ until we
have $m-t$ tails, then halt. The probability that we halt at or before step
$m$ is $\Pr[\operatorname{Binom}(m,\alpha)\leq t]$. Now with a counting
argument: Consider the steps where it is possible to halt, $\ell=m-t,\dots,m$.
We stop at such an $\ell$ if and only if there are $m-t-1$ tails in the first
$\ell-1$ steps and a tail on the $\ell$th. The number of ways this can occur
is ${\ell-1\choose m-t-1}={\ell-1\choose\ell-(m-t)}$. The probability of each
of these ways is $(1-\alpha)^{m-t}\alpha^{\ell-(m-t)}$. Thus the total
probability of stopping is
$\sum_{\ell=m-t}^{m}{\ell-1\choose\ell-(m-t)}(1-\alpha)^{m-t}\alpha^{\ell-(m-t)}$.
A change of variables with $j=\ell-(m-t)$ proves the fact. ∎

######  Lemma 1.

Given $m\geq 0$, $n=2$, $p\in\Delta_{n}$, and $k\geq 1$, let
$p^{\prime}=\left(1-\|p\|_{k},\|p\|_{k}\right)$ and let $B_{m}^{\prime}$ be
the load of bin $2$ when throwing $m$ balls independently according to
$p^{\prime}$. Then $\Pr[B_{m}\geq k]\geq\Pr[B_{m}^{\prime}\geq k]$.

###### Proof.

Let us first consider corner cases. If $m\leq k-1$ then both sides are zero
and the inequality is satisfied. Otherwise, if $p_{1}\in\\{0,1\\}$ or if
$m\geq 2k-1$ then the left side equals one and the inequality is satisfied.

Now assume $0<p_{1}<1$ and $k\leq m\leq 2k-2$. This implies $0\leq m-k\leq
k-2$. Let $X\sim\operatorname{Binom}(m,p_{1})$ and
$Y\sim\operatorname{Binom}(m,p_{2})$.

$\displaystyle\Pr[B_{m}\geq k]$ $\displaystyle=\Pr[X\geq k]+\Pr[X\leq m-k]$
disjoint events $\displaystyle=\Pr[Y\leq m-k]+\Pr[X\leq m-k]$
$\displaystyle=\sum_{j=0}^{m-k}{k-1+j\choose
j}\left(p_{2}^{k}p_{1}^{j}+p_{1}^{k}p_{2}^{j}\right)$ using Fact 1. (6)

Meanwhile, let $X^{\prime}\sim\operatorname{Binom}(m,1-\|p\|_{k})$:

$\displaystyle\Pr[B_{m}^{\prime}\geq k]$ $\displaystyle=\Pr[X^{\prime}\leq
m-k]$ $\displaystyle=\sum_{j=0}^{m-k}{k-1+j\choose
j}\|p\|_{k}^{k}(1-\|p\|_{k})^{j}.$ (7)

By inequality of $k$-norm and $\infty$-norm, we have
$\max\\{p_{1},p_{2}\\}\leq\|p\|_{k}$, so
$1-\|p\|_{k}\leq\min\\{p_{1},p_{2}\\}$. So

$\displaystyle\|p\|_{k}^{k}(1-\|p\|_{k})^{j}$
$\displaystyle=\left(p_{1}^{k}+p_{2}^{k}\right)(1-\|p\|_{k})^{j}$
$\displaystyle\leq p_{1}^{k}p_{2}^{j}+p_{2}^{k}p_{1}^{j}.$

Thus (6) is at least (7), as claimed. ∎

We will use Lemma 1 to iteratively compare the following variables.

######  Definition 1 ($B_{m}^{q,j}$).

When throwing $m$ balls into $n$ bins independently according to
$q\in\Delta_{n}$, for any $j\in[n]$, define $B_{m}^{q,j}$ to be the maximum
load of any bin in $\\{j,\dots,n\\}$. In particular, $B_{m}=B_{m}^{p,1}$.

######  Lemma 2.

Given $m,n\geq 2,k$, any $q\in\Delta_{n}$, and any $j\in\\{1,\dots,n-1\\}$,
define $q^{\prime}$ as follows: $q^{\prime}_{\ell}=q_{\ell}$ for all
$\ell\not\in\\{j,j+1\\}$, and

$\displaystyle q^{\prime}_{j}$
$\displaystyle=q_{j}+q_{j+1}-\|(q_{j},q_{j+1})\|_{k}$ $\displaystyle
q^{\prime}_{j+1}$ $\displaystyle=\|(q_{j},q_{j+1})\|_{k}.$

Then $\Pr[B_{m}^{q,j}<k]\leq\Pr[B_{m}^{q^{\prime},j+1}<k]$.

###### Proof.

We will condition on $t$ balls total landing in bins $\\{j,j+1\\}$. To that
end, let $A_{t}$ be the maximum load when throwing $t$ balls into bins
$\\{j,j+1\\}$ according to the conditional distribution
$(q_{j},q_{j+1})/(q_{j}+q_{j+1})$. Let $A^{\prime}_{t}$ be the load of bin
$j+1$ when throwing $t$ balls into $\\{j,j+1\\}$ according to
$(q^{\prime}_{j},q^{\prime}_{j+1})/(q^{\prime}_{j}+q^{\prime}_{j+1})$. Lemma 1
implies $\Pr[A_{t}<k]\leq\Pr[A^{\prime}_{t}<k]$.

Similarly, let $D_{m-t}$ (respectively, $D^{\prime}_{m-t}$) be the maximum
load of bins $\\{j+2,\dots,n\\}$ when throwing $m-t$ balls according to $q$
(respectively, $q^{\prime}$) conditioned on landing in
$[n]\setminus\\{j,j+1\\}$. (If $j=n-1$, define $D_{m-t}=D^{\prime}_{m-t}=0$.)
We observe that $D_{m-t}$ and $D^{\prime}_{m-t}$ are identically distributed
because $q$ and $q^{\prime}$ are identical outside of $\\{j,j+1\\}$. Let
$f(t)=\Pr[\operatorname{Binom}(m,q_{i}+q_{j})=t]$. Then

$\displaystyle\Pr[B_{m}^{q,j}<k]$
$\displaystyle=\sum_{t=0}^{m}f(t)\Pr[A_{t}<k]\Pr[D_{m-t}<k]$
$\displaystyle=\sum_{t=0}^{m}f(t)\Pr[A_{t}<k]\Pr[D^{\prime}_{m-t}<k]$ observed
above
$\displaystyle\leq\sum_{t=0}^{m}f(t)\Pr[A^{\prime}_{t}<k]\Pr[D^{\prime}_{m-t}<k]$
Lemma 1 $\displaystyle=\Pr[B_{m}^{q^{\prime},j+1}<k].$

∎

###### Proof of Proposition 2.

We show $\Pr[B_{m}<k]\leq\Pr[\operatorname{Binom}(m,\|p\|_{k})<k]$. If $n=1$
the result is immediate.

Apply Lemma 2 to $p$ at $j=1$. We obtain $p^{\prime}$ where
$p^{\prime}_{2}=\|(p_{1},p_{2})\|_{k}=\left(p_{1}^{k}+p_{2}^{k}\right)^{1/k}$
and the guarantee $\Pr[B_{m}<k]\leq\Pr[B_{m}^{p^{\prime},2}<k]$. Next apply
Lemma 2 to $p^{\prime}$ at $j=2$. We obtain $p^{\prime\prime}$ where
$p^{\prime\prime}_{3}=\|(p^{\prime}_{2},p_{3})\|_{k}=\left(p_{1}^{k}+p_{2}^{k}+p_{3}^{k}\right)^{1/k}=\|(p_{1},p_{2},p_{3})\|_{k}$
and the guarantee $\Pr[B_{m}<k]\leq\Pr[B_{m}^{p^{\prime\prime},3}<k]$.

Continuing, by induction, at the final step we obtain some $q$ with
$q_{n}=\|p\|_{k}$ and the guarantee $\Pr[B_{m}<k]\leq\Pr[B_{m}^{q,n}<k]$. Now
we observe that $B_{m}^{q,n}$ is simply the load of the $n$th bin, so it is
distributed $\operatorname{Binom}(m,\|p\|_{k})$. ∎

#### Remark.

The above elementary proof is based on a more concise version that utilizes
generating functions to analyze $T_{k}$. This proof appeared at (esg,
https://mathoverflow.net/users/48831/esg).

##  4 Illustrations

We illustrate Theorem 1 with some simulation results for the uniform
distribution $p$, Figure 1, and a non-uniform distribution $p$ proportional to
$(1,2,\dots,n)$, Figure 2. Each curve plots the empirical probability of a
$k$-loaded bin as we vary the number of balls $m$ thrown. The horizontal axes
are parameterized by $\rho_{m,k}=\frac{m\|p\|_{k}}{k}$.

We have derived upper and lower bounds with no dependence on the number of
bins $n$ or the details of $p$ except through $\|p\|_{k}$. Simulations support
that this is almost exactly true of the exact frequency as well: _(a)_ In both
Figures 1 and 2, the top two plots are almost identical to the bottom two
plots, suggesting that $n$ has almost no impact on $\Pr[B_{m}\geq k]$ once we
control for $\rho_{m,k}$. _(b)_ All plots in Figure 2 are almost identical to
their counterparts in Figure 1, suggesting that the structure of $p$ has
little impact on $\Pr[B_{m}\geq k]$ once we control for $\rho_{m,k}$.

Figure 1: Uniform distribution: Throwing $m$ balls into $n$ bins uniformly.
For each fixed $k$, we vary $m$ and plot the empirical frequency for
$\Pr[B_{m}\geq k]$ across 5000 trials (solid lines) versus
$\rho_{m,k}=\frac{m\|p\|_{k}}{k}$. Dashed lines plot the upper and lower
bounds of Theorem 1. In all settings, but particularly as $k$ grows, we
observe a phase transition where the chance of a $k$-loaded bin quickly
transitions from almost zero to almost one.

0.000.250.500.751.001.251.501.752.00$\displaystyle\rho_{m,k}$0.00.20.40.60.81.0$\displaystyle\Pr[B_{m}\geq
k]$n = 20, uniformk=2k=4Upper boundsLower bounds

0.000.250.500.751.001.251.501.752.00$\displaystyle\rho_{m,k}$0.00.20.40.60.81.0$\displaystyle\Pr[B_{m}\geq
k]$n = 20, uniformk=20k=40Upper boundsLower bounds

0.000.250.500.751.001.251.501.752.00$\displaystyle\rho_{m,k}$0.00.20.40.60.81.0$\displaystyle\Pr[B_{m}\geq
k]$n = 100, uniformk=2k=4Upper boundsLower bounds

0.000.250.500.751.001.251.501.752.00$\displaystyle\rho_{m,k}$0.00.20.40.60.81.0$\displaystyle\Pr[B_{m}\geq
k]$n = 100, uniformk=20k=40Upper boundsLower bounds

Figure 2: Nonuniform: Throwing $m$ balls into $n$ bins according to the
distribution $\tfrac{2}{n(n+1)}\left(1,\dots,n\right)$. Solid lines are
empirical frequencies for $\Pr[B_{m}\geq k]$ from 5000 trials. Dashed lines
plot the upper and lower bounds of Theorem 1.

0.000.250.500.751.001.251.501.752.00$\displaystyle\rho_{m,k}$0.00.20.40.60.81.0$\displaystyle\Pr[B_{m}\geq
k]$n = 20, nonuniformk=2k=4Upper boundsLower bounds

0.000.250.500.751.001.251.501.752.00$\displaystyle\rho_{m,k}$0.00.20.40.60.81.0$\displaystyle\Pr[B_{m}\geq
k]$n = 20, nonuniformk=20k=40Upper boundsLower bounds

0.000.250.500.751.001.251.501.752.00$\displaystyle\rho_{m,k}$0.00.20.40.60.81.0$\displaystyle\Pr[B_{m}\geq
k]$n = 100, nonuniformk=2k=4Upper boundsLower bounds

0.000.250.500.751.001.251.501.752.00$\displaystyle\rho_{m,k}$0.00.20.40.60.81.0$\displaystyle\Pr[B_{m}\geq
k]$n = 100, nonuniformk=20k=40Upper boundsLower bounds

Figure 3: Birthday paradox: Illustration of the the probability of a
$2$-loaded bin when throwing $m$ balls uniformly into $n=5000$ bins. Solid
lines are empirical frequencies for $\Pr[B_{m}\geq 2]$ from 50000 trials.
Dashed lines plot the upper and lower bounds of Theorem 1. The bounds match to
a ratio of $1\pm o(1)$ as $\rho_{2}\to 0$.

0.000.250.500.751.001.251.501.752.00$\displaystyle\rho_{m,2}=\frac{m\|p\|_{2}}{2}$0.00.20.40.60.81.0$\displaystyle\Pr[B_{m}\geq
2]$k = 2, uniformn = 5000Upper boundsLower bounds

0.000.050.100.150.200.250.300.35$\displaystyle\rho_{m,2}=\frac{m\|p\|_{2}}{2}$0.0000.0250.0500.0750.1000.1250.1500.1750.200$\displaystyle\Pr[B_{m}\geq
2]$k = 2, uniformn = 5000Upper boundsLower bounds

##  5 Proofs of Corollaries

It will be useful to observe that $\rho_{m,k}:=\frac{m\|p\|_{k}}{k}$ is
decreasing in $k$.

###### Proof of Corollary 1.

The upper bound follows from the inequality222Proof of inequality: ${m\choose
k}\leq\tfrac{m^{k}}{k!}$, and from
$e^{k}=\sum_{i=0}^{\infty}\tfrac{k^{i}}{i!}\geq\tfrac{k^{k}}{k!}$ we get
$\frac{1}{k!}\leq\tfrac{e^{k}}{k^{k}}$. ${m\choose k}\leq\left(\frac{e\cdot
m}{k}\right)^{k}$, giving for integer $k\geq 1$, $\Pr[B_{m}\geq
k]\leq\delta_{k}:=\exp\left(-k\ln\frac{e}{\rho_{m,k}}\right)$. Because
$\delta_{k}$ is decreasing in $k$, the bound follows for all real $k\geq 1$:
we have $\Pr[B_{m}\geq k]=\Pr[B_{m}\geq\lceil k\rceil]\leq\delta_{\lceil
k\rceil}\leq\delta_{k}$.

For the lower bound: by Hoeffding (1962),

$\Pr[\operatorname{Binom}(m,\|p\|_{k})<k]\leq\exp\left(-mD(\tfrac{k}{m},\|p\|_{k})\right)$

where

$\displaystyle mD(\tfrac{k}{m},\|p\|_{k})$
$\displaystyle=k\ln\left(\frac{k}{m\|p\|_{k}}\right)+(m-k)\ln\left(\frac{1-\tfrac{k}{m}}{1-\|p\|_{k}}\right)$
$\displaystyle=k\ln\left(\frac{1}{\rho_{m,k}}\right)-(m-k)\ln\left(\frac{m-m\|p\|_{k}}{m-k}\right)$
$\displaystyle=k\ln\left(\frac{1}{\rho_{m,k}}\right)-(m-k)\ln\left(1+\frac{k-m\|p\|_{k}}{m-k}\right)$
$\displaystyle\geq
k\ln\left(\frac{1}{\rho_{m,k}}\right)-(m-k)\left(\frac{k-m\|p\|_{k}}{m-k}\right)$
$\displaystyle=k\ln\left(\frac{1}{\rho_{m,k}}\right)-\left(k-m\|p\|_{k}\right)$
$\displaystyle=k\left(\ln\left(\frac{1}{\rho_{m,k}}\right)-1+\rho_{m,k}\right)$
$\displaystyle=k\left(\ln\left(\frac{1}{e\cdot\rho_{m,k}}\right)+\rho_{m,k}\right).$

Therefore,

$\displaystyle\Pr[\operatorname{Binom}(m,\|p\|_{k})<k]$
$\displaystyle\leq\exp\left(-k\left(\rho_{m,k}-1-\ln(\rho_{m,k})\right)\right).$
(8)

We now argue that the bound (8) holds not just for integer $k$ but also any
real $k\geq 1$. Let $\delta_{k}$ denote the right side of (8). Then
$\delta_{k}$ is decreasing in $k$, because $\rho_{m,k}$ is increasing in $k$.
So we have
$\Pr[\operatorname{Binom}(m,\|p\|_{k})<k]=\Pr[\operatorname{Binom}(m,\|p\|_{k})<\lceil
k\rceil]\leq\delta_{\lceil k\rceil}\leq\delta_{k}$, as desired. ∎

###### Proof of Corollary 2.

The upper bound follows directly by plugging
$\rho_{m,k}\leq\left(\frac{\delta^{1/k}}{e}\right)$ into Corollary 1. For the
lower bound, for $\rho_{m,k}\geq e^{2}$, we have
$\rho_{m,k}-\ln(e\cdot\rho_{m,k})\geq\rho_{m,k}/2$. For $\rho_{m,k}\geq
2\ln\left(\tfrac{1}{\delta^{1/k}}\right)$, we have

$\displaystyle\exp\left(-k\left(\frac{\rho_{m,k}}{2}\right)\right)$
$\displaystyle\leq\delta.$

∎

###### Proof of Corollary 3.

Upper bound: let $k=\left(\tfrac{e}{\delta}\right)k^{*}$. Then, using that
$k\geq k^{*}$,

$\displaystyle\rho_{m,k}$ $\displaystyle=\frac{m\|p\|_{k}}{k}$
$\displaystyle\leq\frac{m\|p\|_{k^{*}}}{k}$ $\displaystyle=\frac{\delta\cdot
m\|p\|_{k^{*}}}{e\cdot k^{*}}$ $\displaystyle=\frac{\delta}{e}$
$\displaystyle\leq\frac{\delta^{1/k}}{e},$

and we apply Corollary 2.

Lower bound: let $k=k^{*}/\max\left\\{e^{2},2\ln(\tfrac{1}{\delta})\right\\}$.
Then

$\displaystyle\rho_{m,k}$ $\displaystyle=\frac{m\|p\|_{k}}{k}$
$\displaystyle\geq\frac{m\|p\|_{k^{*}}}{k}$
$\displaystyle=\max\left\\{e^{2},~{}2\ln\left(\frac{1}{\delta}\right)\right\\}$
$\displaystyle\geq\max\left\\{e^{2},~{}2\ln\left(\frac{1}{\delta^{1/k}}\right)\right\\},$

and we again apply Corollary 2. ∎

###### Proof of Corollary 4.

Follows almost immediately from Corollary 2 and $\delta\leq\delta^{1/k}$. ∎

###  5.1 The Expected Waiting Time

We first show that Theorem 1 implies Corollary 5, i.e.
$\frac{k}{k+1}\frac{k}{e\|p\|_{k}}\leq\operatorname*{\mathbb{E}}T_{k}\leq\frac{k}{\|p\|_{k}}$.
We then discuss the tightness of the bounds.

###### Proof of Corollary 5.

Let the random variable $X_{k}$ be the number of independent flips of a coin
with bias $\|p\|_{k}$ until $k$ heads appear. Then $\Pr[X_{k}\leq
m]=\Pr[\operatorname{Binom}(m,\|p\|_{k})\geq k]$. By Theorem 1, $\Pr[X_{k}\leq
m]\leq\Pr[T_{k}\leq m]$. In other words, $X_{k}$ first-order stochastically
dominates $T_{k}$, and it follows that
$\operatorname*{\mathbb{E}}T_{k}\leq\operatorname*{\mathbb{E}}X_{k}=\frac{k}{\|p\|_{k}}$.

For the other direction: let $\alpha=\left(\tfrac{e\cdot\|p\|_{k}}{k}\right)$
and let $M=\frac{1}{\alpha}$. Recall from Theorem 1 and the inequality
${m\choose k}\leq\left(\tfrac{e\cdot m}{k}\right)^{k}$ that we have
$\Pr[T_{k}\leq m]\leq\left(\tfrac{e\cdot
m\cdot\|p\|_{k}}{k}\right)^{k}=m^{k}\alpha^{k}$.

$\displaystyle\operatorname*{\mathbb{E}}T_{k}$
$\displaystyle=\sum_{m=1}^{\infty}m\Pr[T_{k}=m]$
$\displaystyle=\sum_{m=1}^{\infty}\Pr[T_{k}\geq m]$
$\displaystyle=\sum_{m=0}^{\infty}\Pr[T_{k}>m]$
$\displaystyle=\sum_{m=0}^{\infty}1-\Pr[T_{k}\leq m]$
$\displaystyle\geq\sum_{m=0}^{\infty}\max\left\\{0,1-m^{k}\alpha^{k}\right\\}$
$\displaystyle\geq\int_{m=0}^{M}\left(1-m^{k}\alpha^{k}\right)dm$
$\displaystyle=M-\frac{M^{k+1}\alpha^{k}}{k+1}$
$\displaystyle=M-\frac{M}{k+1}$ $\displaystyle=\frac{k}{k+1}M$
$\displaystyle=\left(\frac{k}{e\cdot(k+1)}\right)\frac{k}{\|p\|_{k}}.$

∎

We present Corollary 5 as an exploration of the tightness of Theorem 1, and
show now that the denumerators of the bounds for
$\operatorname*{\mathbb{E}}T_{k}$ are (essentially) best possible. For
$\operatorname*{\mathbb{E}}T_{k}$ a simple integral represention is known
(Flajolet et al. (1992)):

$\operatorname*{\mathbb{E}}T_{k}=\int_{0}^{\infty}\prod_{i=1}^{n}\big{(}q_{k}(p_{i}t)e^{-p_{i}t}\big{)}dt\;\;,$

where $q_{k}(t):=\sum_{i=0}^{k-1}\frac{t^{i}}{i!}$ is the sum of the first $k$
terms of the exponential series. Using this we show:

######  Proposition 3.

Let $k\geq 2$ be fixed. Then
(1) $\|p\|_{k}\operatorname*{\mathbb{E}}T_{k}\geq{c_{k}}$, and
$c_{k}\coloneqq\int_{0}^{\infty}e^{-\frac{t^{k}}{k!}}\,dt=(k!)^{1/k}\Gamma(1+\frac{1}{k})$
is the best possible lower bound.
(2) $\|p\|_{k}\operatorname*{\mathbb{E}}T_{k}\leq{k}$, and $k$ is the best
possible upper bound.

###### Proof.

It is easy to see (using logarithmic differentiation) that $q_{k}(t)e^{-t}\geq
e^{-\frac{t^{k}}{k!}}$ for $t\geq 0$.
(1) Therefore

$\|p\|_{k}\operatorname*{\mathbb{E}}T_{k}\geq\|p\|_{k}\int_{0}^{\infty}\prod_{i=1}^{n}\big{(}e^{-\frac{p_{i}^{k}t^{k}}{k!}}\big{)}dt=\|p\|_{k}\int_{0}^{\infty}e^{-\frac{\|p\|_{k}^{k}t^{k}}{k!}}dt=c_{k}\;\;$

Thus $c_{k}$ is a lower bound. It is best possible since it arises as the
limit of $\|p\|_{k}\operatorname*{\mathbb{E}}T_{k}$ for the uniform
distribution on bins as $n\longrightarrow\infty$ (Klamkin and Newman (1967)) .
(2) We now already know that $k$ is an upper bound. Let $a\in(0,1)$ and let
$p_{1}=a$, $p_{2}=\ldots=p_{n}=\frac{1-a}{n-1}$. Then
$\|p\|_{k}^{k}=a^{k}+\frac{(1-a)^{k}}{(n-1)^{k-1}}$ and

$\operatorname*{\mathbb{E}}T_{k}=\int_{0}^{\infty}\prod_{i=1}^{n}\big{(}q_{k}(p_{i}t)e^{-p_{i}t}\big{)}dt\geq\int_{0}^{\infty}q_{k}(at)e^{-at}e^{\frac{(1-a)^{k}t^{k}}{(n-1)^{k-1}k!}}dt$

For $n\longrightarrow\infty$ then $\|p\|_{k}\longrightarrow a$ and
$\operatorname*{\mathbb{E}}T_{k}\longrightarrow\frac{k}{a}$. Therefore the
bound $k$ can not be lowered. ∎

Thus the upper bound of Corollary 5 is best possible, and since
$c_{k}>\frac{k}{e}$ and

$c_{k}=\frac{k}{e}\Big{(}1+\frac{1}{2}\frac{\log 2\pi
k}{k}-\frac{\gamma}{k}+O\left(\frac{1}{k^{2}}\right)\Big{)},$

also the lower bound of Corollary 5 is essentially the best possible.

##  6 Generalizations

Finally we remark that Theorem 1 can be generalized in two directions.

#### (1) Maximum load in a restricted set of bins.

Suppose that we are only interested in the maximum load (resp. the waiting
time for maximum load $k$) of $r<n$ bins (say, bins $1,\ldots,r$) , where
$p_{1}+\ldots+p_{r}<1$. Denote by $B_{r,m}$ the maximum load in bins
$1,\ldots,r$ at time $m$, and let $\|(p)_{r}\|_{k}$ denote the $k$-norm of
$(p_{1},\ldots,p_{r})$. Then

$\Pr[\operatorname{Binom}(m,\|(p)_{r}\|_{k})\geq k]~{}\leq~{}\Pr[B_{r,m}\geq
k]~{}\leq~{}{m\choose k}\|(p)_{r}\|_{k}^{k}.$

###### Proof.

The proof for the upper bound applies essentially unchanged. For the lower
bound we may assume that there is only one additional bin (numbered $r+1$),
which is chosen with probability $p_{r+1}=1-(p_{1}+\ldots+p_{r})$. Let
$N_{r+1,m}$ denote the random variable “load of bin $r+1$ after $m$ balls”.
Then $N_{r+1,m}$ is binomially distributed with parameters $m$ and $p_{r+1}$,
and conditionally on $N_{r+1,m}=\ell$ the joint distribution of the loads in
bins $1,\ldots,r$ is multinomial with parameters $m-\ell$ and
$q_{1}=\frac{p_{1}}{1-p_{r+1}},\ldots,q_{r}=\frac{p_{r}}{1-p_{r+1}}$.
Conditioning on $N_{r+1,m}$, and using Theorem 1, we get

$\displaystyle\Pr[B_{r,m}\geq k]$
$\displaystyle=\sum_{\ell=0}^{m}\Pr[B_{r,m}\geq k\mid
N_{r+1,m}=\ell]\Pr[N_{r+1,m}=\ell]$
$\displaystyle\geq\sum_{\ell=0}^{m}\Pr[\operatorname{Binom}(m-\ell,\|q\|_{k})\geq
k]\Pr[N_{r+1,m}=\ell]$
$\displaystyle=\sum_{\ell=0}^{m}\sum_{j=k}^{m-\ell}{m\choose\ell}p_{r+1}^{\ell}(1-p_{r+1})^{m-\ell}{m-\ell\choose
j}\|q\|_{k}^{j}(1-\|q\|_{k})^{m-\ell-j}$
$\displaystyle=\sum_{j=k}^{m}\sum_{\ell=0}^{m-j}\frac{m!}{j!\ell!(m-\ell-j)!}p_{r+1}^{\ell}\|(p)_{r}\|_{k}^{j}(1-p_{r+1}-\|(p)_{r}\|_{k})^{m-\ell-j}$
$\displaystyle=\sum_{j=k}^{m}{m\choose
j}\|(p)_{r}\|_{k}^{j}(1-\|(p)_{r}\|_{k})^{m-j}$
$\displaystyle=\Pr[\operatorname{Binom}(m,\|(p)_{r}\|_{k})\geq k]$

∎

#### (2) Maximum load in countably infinite many bins.

Let $p=p_{1},p_{2},...$ a probability distribution with infinite support. Then
Theorem 1 still holds, i.e.

$\Pr[\operatorname{Binom}(m,\|p\|_{k})\geq k]~{}\leq~{}\Pr[B_{m}\geq
k]~{}\leq~{}{m\choose k}\|p\|_{k}^{k}.$

###### Proof.

By the preceding remark we have that for any $r\geq 1$

$\Pr[\operatorname{Binom}(m,\|(p)_{r}\|_{k})\geq k]~{}\leq~{}\Pr[B_{r,m}\geq
k]~{}\leq~{}{m\choose k}\|(p)_{r}\|_{k}^{k}$

Passing to the limit $r\longrightarrow\infty$ proves the claim. ∎

Applying the argument (1) again to the countably-infinite setting gives the
generalization in both directions simultaneously.

## References

  * Camarri [1998] Michael Camarri.  Asymptotics for k-fold repeats in the birthday problem with unequal probabilities.  Technical report, Citeseer, 1998.
  * Camarri and Pitman [2000] Michael Camarri and Jim Pitman.  Limit distributions and random trees derived from the birthday problem with unequal probabilities.  _Electronic Journal of Probability_ , 5:1–18, 2000.
  * Dubhashi and Ranjan [1996] Devdatt P Dubhashi and Desh Ranjan.  Balls and bins: A study in negative dependence.  _BRICS Report Series_ , 3(25), 1996.
  * esg [https://mathoverflow.net/users/48831/esg] esg (https://mathoverflow.net/users/48831/esg).  Bounding the max-loaded bin using${m\choose k}\|a\|_{k}^{k}$.  MathOverflow.  URL https://mathoverflow.net/q/393224.  URL:https://mathoverflow.net/q/393224 (version: 2021-05-23).
  * Flajolet et al. [1992] Philippe Flajolet, Daniele Gardy, and Loÿs Thimonier.  Birthday paradox, coupon collectors, caching algorithms and self-organizing search.  _Discrete Applied Mathematics_ , 39(3):207–229, 1992.
  * Hoeffding [1962] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  _Institute of Statistics Mimeo Series_ , 326, 1962.  URL https://repository.lib.ncsu.edu/handle/1840.4/2170.
  * Holst [1995] Lars Holst.  The general birthday problem.  _Random Structures & Algorithms_, 6(2–3):201–208, mar 1995.  ISSN 1042-9832.  doi: 10.1002/rsa.3240060207.
  * Klamkin and Newman [1967] Murray S Klamkin and Donald J Newman.  Extensions of the birthday surprise.  _Journal of Combinatorial Theory_ , 3(3):279–282, 1967.
  * Knuth [2019] Donald E Knuth.  The art of computer programming, volume 4, fascicle 5: Mathematical preliminaries redux; introduction to backtracking; dancing links, 2019.
  * Raab and Steger [1998] Martin Raab and Angelika Steger.  “Balls into bins” - a simple and tight analysis.  In _Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science_ , RANDOM 1998, pages 159–170. Springer-Verlag, 1998.  ISBN 3-540-65142-X.
  * Von Mises [1939] Richard Von Mises.  _Über Aufteilungs-und Besetzungswahrscheinlichkeiten_.  na, 1939.
  * Wiener [2005] Michael J Wiener.  Bounds on birthday attack times.  _IACR Cryptol. ePrint Arch._ , 2005:318, 2005.  URL https://eprint.iacr.org/2005/318.


Pullbacks of hyperplane sections for Lagrangian fibrations are primitive

Ljudmila Kamenova, Misha Verbitsky111Partially supported by the Russian
Academic Excellence Project ’5-100’.

Dedicated to Professor Claire Voisin

Abstract. Let $p:\;M\rightarrow B$ be a Lagrangian fibration on a hyperkähler
manifold of maximal holonomy (also known as IHS), and $H$ be the generator of
the Picard group of $B$. We prove that $p^{*}(H)$ is a primitive class on $M$.

##  1 Introduction

In this paper we consider a compact hyperkähler manifold of maximal holonomy
admitting a holomorphic fibration $\pi:\;M\rightarrow B$. The fibration
structure is quite restricted due to the work of Matsushita, [Mat1], who first
noticed that the general fiber is a Lagrangian abelian variety of half of the
dimension of the total space. The base has the same rational cohomology as
${\mathbb{C}}P^{n}$ and the Picard group $\operatorname{Pic}(B)$ has rank one.
We prove that the pullback of the fundamental class of a hyperplane section is
primitive, i.e., indivisible as an integral class.

Theorem 1.1: Let $M$ be a hyperkähler manifold admitting a Lagrangian
fibration $\pi:\;M\rightarrow B$ and $H$ be the generator of
$\operatorname{Pic}(B)$. Then the class $\pi^{*}H\in H^{2}(M,{\mathbb{Z}})$ is
primitive.

The proof is based on the observation that if $\pi^{*}H\in
H^{2}(M,{\mathbb{Z}})$ is not primitive, i.e., $\pi^{*}H=mH^{\prime}$, then
$H^{\prime}$ has trivial cohomology by Demailly, Peternell and Schneider’s
theorem. Applying the Hirzebruch-Riemann-Roch formula for an irreducible
hyperkähler manifold, one would obtain a contradiction.

As an application of the primitivity of $\pi^{*}H$ one can see that if $P_{1}$
and $P_{2}$ are non-ample nef line bundles associated with different
Lagrangian fibrations $\pi_{i}:\;M\rightarrow{\mathbb{C}}P^{n}$, then
$P_{1}\otimes P_{2}$ is ample and base point free.

##  2 Basic notions

Definition 2.1: A hyperkähler manifold of maximal holonomy (or irreducible
holomorphic symplectic) manifold $M$ is a compact complex simply connected
Kähler manifold with $H^{2,0}(M)={\mathbb{C}}\sigma$, where $\sigma$ is
everywhere non-degenerate.

For the rest of the paper we consider hyperkähler manifolds of maximal
holonomy. Due to the work of Matsushita we know that the fibration structure
of hyperkähler manifolds is quite restricted.

Theorem 2.2:  (D. Matsushita, [Mat1]) Let $M$ be a hyperkähler manifold and
$f\colon M\rightarrow B$ a proper surjective morphism with a smooth base $B$.
Assume that $f$ has connected fibers and $0<\dim B<\dim M$. Then $f$ is
Lagrangian and $\dim_{{\mathbb{C}}}B=n$, where $\dim_{{\mathbb{C}}}M=2n$.

Definition 2.3: Following 2, we call the morphism $f\colon M\rightarrow B$ a
Lagrangian fibration on the hyperkähler manifold $M$.

Remark 2.4:  In [Mat2], D. Matsushita also proved that the base $B$ of a
Lagrangian fibration has the same (rational) cohomology as
${\mathbb{C}}P^{n}$. In [Hw], J.-M. Hwang proved that when $B$ is smooth, then
it is actually isomorphic to ${\mathbb{C}}P^{n}$.

Definition 2.5: Given a hyperkähler manifold $M$, there is a non-degenerate
primitive form $q$ on $H^{2}(M,{\mathbb{Z}})$, called the Beauville-Bogomolov-
Fujiki form (or “BBF form” for short) of signature $(3,b_{2}-3)$, satisfying
the Fujiki relation

$\int_{M}\alpha^{2n}=c\cdot q(\alpha)^{n}\qquad\text{for }\alpha\in
H^{2}(M,{\mathbb{Z}}),$

with $c>0$ a constant depending on the topological type of $M$. This form
generalizes the intersection pairing on K3 surfaces. A detailed description of
the form can be found in [Be], [Bog] and [F].

Definition 2.6: Let $f:\;M{\>\longrightarrow\>}B$ be a Lagrangian fibration.
As shown in [Mat2],
$H^{*}(B,{\mathbb{Q}})=H^{*}({\mathbb{C}}P^{n},{\mathbb{Q}})$. Let $H$ be a
primitive integral generator of $H^{2}(M,{\mathbb{Q}})$, and ${\cal O}(1)$ be
a holomorphic line bundle on $B$ with first Chern class $H$. When
$B={\mathbb{C}}P^{n}$ (this is the case when $B$ is smooth by Hwang’s result
[Hw]), the bundle ${\cal O}(1)$ coincides with the usual ${\cal O}(1)$. We
call $H$ the fundamental class of a hyperplane section.

Remark 2.7: A semiample bundle is a base point free line bundle which has
positive Kodaira dimension. Let $f:\;M\rightarrow B$ be a Lagrangian
fibration, and $L:=f^{*}({\cal O}(k))$, $k>0$. Clearly, $L$ is a semiample nef
line bundle. By Matsushita’s theorem any semiample nef line bundle is either
ample or obtained this way. The SYZ conjecture (due to Tyurin, Bogomolov,
Hassett, Tschinkel, Huybrechts and Sawon; see [V]) claims that converse is
also true: any nef line bundle on a hyperkähler manifold is either ample or
semiample. This conjecture is a special case of Kawamata’s abundance
conjecture.

Remark 2.8:  The Hirzebruch-Riemann-Roch formula for an irreducible
hyperkähler manifold $M$ states that for a line bundle $L$ on $M$, the Euler
characteristic of $L$ is $\chi(L)=\sum a_{i}q(c_{1}(L))^{i}$, where the
coefficients $a_{i}$ are constants depending on the topology of $M$ (see
[Hu]). In particular, if $q(c_{1}(L))=0$, then $\chi(L)=a_{0}=\chi({\cal
O}_{M})=n+1$, where $2n=\dim M$.

Using the Hirzebruch-Riemann-Roch formula, we can easily obtain our main
result for K3 surfaces. We are grateful to Claire Voisin for this observation.

Lemma 2.9: Let $S$ be a K3 surface with an elliptic fibration
$\pi:\;S\rightarrow{\mathbb{C}}P^{1}$. Then the class $\pi^{*}{\cal O}(1)\in
H^{2}(S,{\mathbb{Z}})$ is primitive.

Indeed, if we assume that $\pi^{*}{\cal O}(1)=mH$ for $m>1$, then $H$ would be
$m$-torsion on all fibers and $h^{0}(H)=0$. By Serre duality, $h^{2}(H)=0$.
Then applying the Hirzebruch-Riemann-Roch formula as in 2, we obtain
$2=\chi(H)=h^{0}(H)-h^{1}(H)+h^{2}(H)=-h^{1}(H)\leqslant 0$ \- a
contradiction.

Remark 2.10: For the standard series of examples this was also known by
Wieneck (Lemma 2.7 in [W]). We thank Klaus Hulek for pointing out this
reference to us.

Here we restate a theorem by Demailly, Peternell and Schneider applied to
compact Kähler manifolds with trivial canonical bundle, which is the set-up we
need. The more general version of this result is Theorem 2.1.1 in [DPS]. This
theorem was obtained under various hypotheses during the 1990s, see [Eno93]
and [Mou99]. It was proved in [Tak97] when $L$ is nef.

Theorem 2.11: ([DPS, Theorem 2.1.1]) Let $(M,I,\omega)$ be a compact Kähler
manifold, $K_{M}$ its canonical bundle, $\dim_{{\mathbb{C}}}M=n$, and $E$ a
non-trivial nef line bundle on $M$. Assume that $E$ admits a Hermitian metric
with semipositive curvature form. The cohomology class $\omega$ is considered
as an element in $H^{1}(\Omega^{1}M).$ Consider the corresponding
multiplication operator $\eta{\>\longrightarrow\>}\omega\wedge\eta$ maping
$H^{p}(\Omega^{q}M\otimes E)$ to $H^{p+1}(\Omega^{q+1}M\otimes E)$. Then
$\eta{\>\longrightarrow\>}\omega^{i}\wedge\eta$ induces a surjective map
$H^{0}(\Omega^{n-i}M\otimes E)\twoheadrightarrow H^{i}(E\otimes K_{M})$.

Further on, we shall also need the following trivial topological observation.

Claim 2.12:  Let $M$ be a hyperkähler manifold of maximal holonomy. Then
$H^{2}(M)$ is torsion-free.

Proof: The universal coefficients formula gives the exact sequence:

$0\to\operatorname{Ext}_{\mathbb{Z}}^{1}(H_{1}(M;{\mathbb{Z}}),{\mathbb{Z}})\to
H^{2}(M;{\mathbb{Z}})\to\operatorname{Hom}_{\mathbb{Z}}(H_{2}(M;{\mathbb{Z}}),{\mathbb{Z}})\to
0$

Since $H_{1}(M,{\mathbb{Z}})=0$ for a maximal holonomy hyperkähler manifold,
this gives an isomorphism
$H^{2}(M;{\mathbb{Z}})=\operatorname{Hom}_{\mathbb{Z}}(H_{2}(M;{\mathbb{Z}}),{\mathbb{Z}})$,
hence the torsion vanishes.

##  3 Main Results

Proposition 3.1:  Let $M$ be a hyperkähler manifold admitting a Lagrangian
fibration $\pi:\;M\rightarrow B$, and $E$ is a line bundle on $M$ which is
trivial on the general fiber and torsion on all irreducible components of all
fibers of $\pi$. Then $E=\pi^{*}E^{\prime}$, where $E^{\prime}$ is a line
bundle on the base.

Proof: The bundle $E$ is torsion on all fibers of $\pi$, hence for some $k$
its tensor power $E^{\otimes k}$ belongs to $\pi^{*}(\operatorname{Pic}(B))$.
Choose a metric $h^{k}$ on $E^{\otimes k}$ which is trivial on the fibers, and
let $h$ be its $k$-th root, which is a metric on $E$. Then the Chern
connection associated with $h$ is flat on the fibers of $\pi$. To finish the
proof it remains to show that its monodromy is trivial on all fibers. However,
since $E$ is trivial on the general fiber, the monodromy of $E$ is trivial on
the general fiber. The special fibers $F_{s}$ of $\pi$ are deformation
retracts of the general fiber $F_{g}$ (see [Mor], [P], [C]). Therefore, the
monodromy representation of $E$ on $F_{s}$ is induced by the monodromy of $E$
on $F_{g}$, which is trivial. We have proven that $E$ is trivial on all fibers
of $\pi$.

Remark 3.2: Using only the properties of the BBF form, Ulrike Rieß informed us
that she was able to prove that in the settings of 3, $E$ is a rational
multiple of $\pi^{*}{\cal O}(1)$, where ${\cal O}(1)$ is the ample generator
of $\operatorname{Pic}(B)$.

Theorem 3.3:  Let $M$ be a hyperkähler manifold admitting a Lagrangian
fibration $\pi:\;M\rightarrow B$, and let $H$ be the generator of
$\operatorname{Pic}(B)$ (this group has rank one, as shown by D. Matsushita;
see 2). Then the class $\pi^{*}H\in H^{2}(M,{\mathbb{Z}})$ is primitive.

Proof:  Suppose that $\pi^{*}H$ is not primitive, and $\pi^{*}H=kH^{\prime}$
in $H^{2}(M,{\mathbb{Z}})$. Denote by $E$ the line bundle with
$c_{1}(E)=H^{\prime}$. By 3, $E=\pi^{*}E^{\prime}$ unless $E$ is a non-trivial
torsion bundle on the general fiber of $\pi$. In the second case, $\pi^{*}H$
is primitive. This implies that $E$ is a non-trivial torsion bundle on the
smooth fibers of $\pi$, and torsion on all irreducible components of non-
smooth fibers.

Apply the Enoki-Mourugane-Takegoshi-Demailly-Peternell-Schneider vanishing
theorem (2) to the manifold $M$ with the torsion nef line bundle $E$ to obtain
the surjective map $H^{0}(\Omega^{2n-i}M\otimes E)\twoheadrightarrow
H^{i}(E)$. The bundle $TM$ restricted to a regular fiber $S$ of
$\pi:\;M{\>\longrightarrow\>}B$ can be expressed as an extension

$0{\>\longrightarrow\>}TS{\>\longrightarrow\>}TM{\left|{}_{{\phantom{|}\\!\\!}_{S}}\right.}{\>\longrightarrow\>}NS{\>\longrightarrow\>}0,$

where $NS$ is the normal bundle, which is trivial because $S$ is a fiber of
the submersion $\pi:\;M{\>\longrightarrow\>}B$, in $s\in B$ which gives
$NS=\pi^{*}T_{s}B$. However, $TS$ is dual to $NS$, because $S$ is Lagrangian,
hence $\Omega^{k}M{\left|{}_{{\phantom{|}\\!\\!}_{S}}\right.}$ is an extension
of trivial bundles. Then
$\Omega^{k}(M){\left|{}_{{\phantom{|}\\!\\!}_{S}}\right.}\otimes E$ has no
sections for all $k$, and 2 implies that $H^{i}(E)=0$ for all $i$.

To finish the proof, we apply the Hirzebruch-Riemann-Roch formula for the
hyperkähler manifold $M$ with the line bundle $E$. Since $q(E)=q(L)=0$ and
$H^{i}(E)=0$, from 2 we obtain $n+1=\chi(E)=\sum(-1)^{i}\dim H^{i}(E)=0$, a
contradiction. Therefore, $\pi^{*}H$ is primitive.

##  4 Applications

In this section we describe some applications of the primitivity result.

Proposition 4.1:  Let $M$ be a hyperkähler manifold admitting a Lagrangian
fibration $f\colon M\rightarrow{\mathbb{C}}P^{n}$. Then the map
$\pi_{2}(M){\>\longrightarrow\>}\pi_{2}({\mathbb{C}}P^{n})$ is surjective.

Proof: From 3 we know that $L=f^{*}{\cal O}(1)$ is primitive, i.e., $c_{1}(L)$
is not divisible. By Poincaré duality there is $\alpha\in
H_{2}(M,{\mathbb{Z}})$ such that the pairing $\langle
c_{1}(L),\alpha\rangle=1$ in $M$. This is the same as the pairing $\langle
r_{*}\alpha,c_{1}({\cal O}(1))\rangle$ in ${\mathbb{C}}P^{n}$, which means
that $r_{*}\alpha$ is the class of a line, therefore
$H_{2}(M,{\mathbb{Z}}){\>\longrightarrow\>}H_{2}({\mathbb{C}}P^{n},{\mathbb{Z}})$
is surjective. Since $M$ and ${\mathbb{C}}P^{n}$ are simply connected, this
induces a surjection on the homotopy groups
$\pi_{2}(M){\>\longrightarrow\>}\pi_{2}({\mathbb{C}}P^{n})$.

Remark 4.2: We conjecture that if the fibration $f\colon
M\rightarrow{\mathbb{C}}P^{n}$ has no multiple fibers, then for a general
curve $C\subset{\mathbb{C}}P^{n}$ there is a continuous section $C\rightarrow
M$. The evidence is that for every curve class $[C]$ there is a class on $M$
surjecting to $[C]$ by 4.

Definition 4.3: A pullback of a very ample bundle is called very semiample.

Corollary 4.4: Let $E$ be a semiample line bundle on a hyperkähler manifold,
which is not ample. Assume that the corresponding Lagrangian fibration has
base ${\mathbb{C}}P^{n}$. Then $E$ is very semiample.

Proof: Indeed, by 3, $E=f^{*}{\cal O}(i)$, where $i>0$ and
$f:\;M{\>\longrightarrow\>}{\mathbb{C}}P^{n}$ is a Lagrangian fibration.

Claim 4.5: Let $P_{1}$ and $P_{2}$ be non-ample nef line bundles associated
with different Lagrangian fibrations with base ${\mathbb{C}}P^{n}$. Then
$P_{1}\otimes P_{2}$ is ample and base point free.

Proof: By the corollary above, the line bundles $P_{i}$ are very semiample,
hence globally generated.

Acknowledgments. We are very grateful to Claire Voisin whose ideas inspired
the proof of the main theorem. The work was completed at the SCGP diring the
second-named author’s visit. We are grateful to the SCGP for their
hospitality. The first named author thanks Michel Brion for their
conversations about an earlier argument of the main theorem and for his
interest. We would like to thank Christian Lehn for his interest and
references. We are grateful to Ulrike Rieß for her invaluable advice, her
interest in this work, and for finding an inconsistency in an earlier draft.

## References

  * [Be] Beauville, A., Varietes Kähleriennes dont la première classe de Chern est nulle. J. Diff. Geom. 18 (1983) 755 - 782.
  * [Bog] Bogomolov, F., Hamiltonian Kähler manifolds, Sov. Math. Dokl. 19 (1978) 1462 - 1465.
  * [C] Clemens, C. H. Degeneration of Kähler manifolds, Duke Math. J. 44 (1977), no. 2, 215 - 290.
  * [DPS] Demailly, J.-P., Peternell, T., Schneider, M., Compact complex manifolds with numerically effective tangent bundles, J. Alg. Geom. 3 (1994) 295 - 345.
  * [Eno93] Enoki, I., Strong-Lefschetz-type theorem for semi-positive line bundles over compact Kähler manifolds, Geometry and global analysis (Sendai, 1993) 211 - 212, Tohoku Univ., Sendai, 1993
  * [F] Fujiki, A., On the de Rham Cohomology Group of a Compact Kähler Symplectic Manifold, Adv. Stud. Pure Math. 10 (1987) 105 - 165.
  * [Hw] Hwang, J.-M., Base manifolds for fibrations of projective irreducible symplectic manifolds, Invent. Math. 174, No. 3 (2008) 625 - 644.
  * [Hu] Huybrechts, D., Compact hyper-Kähler manifolds: basic results, Invent. Math. 135 (1999) 63 - 113.
  * [Mat1] Matsushita, D., On fibre space structures of a projective irreducible symplectic manifold, Topology 38 (1999), No. 1, 79 - 83. Addendum, Topology 40 (2001) No. 2, 431 - 432.
  * [Mat2] Matsushita, D., Higher direct images of Lagrangian fibrations, arXiv:math/0010283, Amer. J. Math. (2005) 127: 243 - 259.
  * [M] Milne, J., Lectures on Etale cohomology, version 2.10 (2008).
  * [Mor] Morrison, D. R., The Clemens-Schmid exact sequence and applications, Topics in transcendental algebraic geometry (Princeton, N.J., 1981/1982), 101-119, Ann. of Math. Stud., 106, Princeton Univ. Press, Princeton, NJ, 1984.
  * [Mou99] Mourougane, Ch., Théorèmes d’annulation génériques pour les fibrés vectoriels semi-négatifs, Bull. Soc. Math. Fr. 127 (1999) 115 - 133.
  * [P] Persson, U., On degenerations of algebraic surfaces, Mem. Amer. Math. Soc. 11 (1977), no. 189.
  * [Tak97] Takegoshi, K., On cohomology groups of nef line bundles tensorized with multiplier ideal sheaves on compact Kähler manifolds, Osaka J. Math. 34 (1997) 783 - 802.
  * [V] Verbitsky, M., Hyperkahler SYZ conjecture and semipositive line bundles, arXiv:0811.0639, GAFA 19, No. 5 (2010) 1481 - 1493.
  * [W] Wieneck, B., Monodromy Invariants and Polarization Types of Generalized Kummer Fibrations, arXiv:1606.09010 [math.AG].

Ljudmila Kamenova
Department of Mathematics, 3-115
Stony Brook University
Stony Brook, NY 11794-3651, USA,
<EMAIL_ADDRESS>

Misha Verbitsky
Université libre de Bruxelles, CP 213,
Bd du Triomphe, 1050 Brussels, Belgium,
also:
Laboratory of Algebraic Geometry,
National Research University HSE,
Faculty of Mathematics, 7 Vavilova Str.,
Moscow, Russian Federation,
<EMAIL_ADDRESS>