3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Stephan Kolassa Aug 9 '17 at 6:35
  • $\begingroup$ @StephanKolassa $ x_{i} $ counts the number of balls in the bin $ i $. The balls are assigned to bins uniformly and randomly. $\endgroup$ – Jess Smith Aug 10 '17 at 12:50
  • $\begingroup$ 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? $\endgroup$ – Stephan Kolassa Aug 10 '17 at 12:52
  • $\begingroup$ 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. $\endgroup$ – Jess Smith Aug 10 '17 at 14:07
  • $\begingroup$ 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. $\endgroup$ – Stephan Kolassa Aug 11 '17 at 4:32
1
$\begingroup$

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.

n=13

n=15

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.

$\endgroup$
  • 1
    $\begingroup$ +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. $\endgroup$ – whuber Aug 11 '17 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.