# Sum of k most extreme values

I have $n$ balls, which I put independently and at random into $\ell$ bins or urns. I then look at the $k$ bins with the most balls inside and count the total number $S$ of balls in these bins. What can I say about the distribution of $S$, or at least about bounds for $S$?

Is there an extension of extreme value theory to the bounding the sum of the $k$ most extreme values of the random variable?

One solution may be to create a new random variable that models the sum of a subset of random variables of size $k$, and then apply EVT to that. It seems that this approach may become impractical because of the combinatorial explosion due of the number of subsets.

• If you are interested in bounding the sum $S$, then of course there are the trivial bounds $kx_{(k)}\leq S\leq kx_{(1)}$. And if your data are well-behaved under summation (e.g., normally or Poisson distributed), then things might be easier, too. Can you tell us anything about the underlying distribution of your data? – Stephan Kolassa Aug 9 '17 at 6:35
• @StephanKolassa $x_{i}$ counts the number of balls in the bin $i$. The balls are assigned to bins uniformly and randomly. – Jess Smith Aug 10 '17 at 12:50
• That may be helpful. If you say that "balls are assigned to bins uniformly and randomly", does that mean that you first distribute $n$ balls to $\ell$ bins, and then you are interested in the probability distribution (or bounds for the extreme values) of the $k$ bins with the largest numbers of balls? – Stephan Kolassa Aug 10 '17 at 12:52
• Exactly. I am interested in the probability distribution of those $k$ bins so that I can find how many total balls are contained in those $k$ bins. – Jess Smith Aug 10 '17 at 14:07
• Thanks! One more question: are you only interested in bounding this sum, or do you need its full distribution? Sharp bounds are not overly hard, the distribution looks harder and may not have a closed-form expression. – Stephan Kolassa Aug 11 '17 at 4:32

## 1 Answer

Sharp bounds for your sum $S$ are not too hard.

The upper bound is simple: $S\leq n$, and this bound is sharp. All $n$ balls could end up in $k$ or fewer bins, so the sum of the contents of the $k$ fullest bins would be $n$.

The lower bound is not much more complicated. It is achieved if the original distribution of $n$ balls to $\ell$ bins is "as equal as possible". This in turn will happen if we first put $\lfloor\frac{n}{\ell}\rfloor$ balls in each bin, then put one ball each in $n-\ell\times\lfloor\frac{n}{\ell}\rfloor = n\text{ mod } \ell$ bins. We then need to distinguish whether this number is smaller or larger than $k$. Overall, the lower bound is

$$k\times\lfloor\frac{n}{\ell}\rfloor + \min\{k,n\text{ mod } \ell\}\leq S,$$

and this bound is again sharp, since we just saw how it can be achieved.

I like to test my calculations through simulation, so below I'll give histograms of simulated values of $S$ for $n\in\{13, 15\}$, $\ell=4$ and $k=2$, plus R code below. The vertical red line gives the theoretical lower bound. As we see, the bound seems to make sense in these examples.  nn <- 13    # number of balls
ll <- 4 # number of bins
kk <- 2     # number of fullest bins

n.sims <- 10000
set.seed(1) # for reproducibility

assignments.to.bins <- t(replicate(n=n.sims,expr=sample(x=1:ll,size=nn,replace=TRUE)))
bin.contents <- t(apply(assignments.to.bins,1,function(xx)table(ordered(xx,levels=1:ll))))
contents.of.fullest.bins <- apply(bin.contents,1,function(xx)sum(sort(xx,decreasing=TRUE)[1:kk]))

(theoretical.minimum <- kk*floor(nn/ll) + min(c(kk,nn%%ll)))
hist(contents.of.fullest.bins,col="grey",xlab="Contents of fullest bins",
breaks=seq(min(contents.of.fullest.bins)-.5,max(contents.of.fullest.bins)+.5),
main=paste0("n = ",nn,", l = ",ll,", k = ",kk))
abline(v=theoretical.minimum,lwd=2,col="red")


Now, if you want the actual full distribution of $S=S(n,\ell,k)$, this looks a lot harder. For combinatorial problems like these, you can sometimes derive a recurrence relationship, e.g., to calculate $S(n,\ell,k)$ as a function of $S(1,\ell,k), \dots, S(n-1,\ell,k)$, but I don't see how this would work here.

Alternatively, a brute force bottom-up approach might be possible, which would first look at the joint distribution of the contents of your $\ell$ bins.

I'd assume that something like this might already exist, possibly involving Stirling numbers of the second kind. However, it seems like just getting a handle on the distribution of the bin with maximum load is nontrivial (Raab & Steger), which is of course just the special case of $S(n,\ell,k=1)$. Searching for "balls" in the combinatorics tag at Mathoverflow, but excluding "color" (and purposely not mentioning "bins", because some people prefer "urns") turns up a number of likely helpful threads, e.g.:

However, it may well be that your best best might be simply to simulate the distribution. The code above is not overly long (if a bit terse), although it may run for a long time or even run into memory problems if your parameters get large.

• +1 For larger problems, especially for larger n, consider using rmultinom: it will be orders of magnitude faster. Here's an example using input n, l, k, and n.sim: table(apply(rmultinom(n.sim, size=n, prob=rep(1/l,l)), 2, function(y) sum(sort(y, decreasing=TRUE)[1:k]))) Using for or replicate will take a little longer but allows for much larger values of l and n. E.g., 1000 iterations with $n=10^9$ and $l=10^4$ took just one second. – whuber Aug 11 '17 at 20:52