Balls in Bins

When I was learning combinatorics for the first time (I was probably 16) there was this problem about distributing m balls in n bins (or urns) that I came across. We had to count the total number of  such distributions, given certain constraints on the maximum capacities of bins. For example, assuming that each bin must have at least one ball and that there is no upper limit on their capacity, we showed that there are {m - 1 \choose n - 1} ways of distributing m identical balls in n distinct bins. Clearly, this is equal to the number of solutions of x_1 + \cdots + x_n = m, where each x_i must be a positive integer. Not so clearly, this is also equal to the coefficient of t^{m-n} in (1-t)^{-n}.

A few days back, this problem appeared again. This time, in the context of some research problems that I am working on. I will explain what the context is in some later posts. For now, let’s stick to elementary combinatorics.

We are given n bins A_1, \ldots, A_n, where for every i, the bin A_i has maximum capacity a_i. We are going to distribute m balls in these n bins such that each bin gets at least one ball. But instead of counting the total number of ways of doing this, we are interested in finding distributions that minimize the product x_1 \cdots x_n, where x_i is the number of balls in the bin A_i. Since the product doesn’t depend on the order, we will assume that a_1 \geq a_2 \cdots \geq a_n. We will denote the minimum value of the product by \mathfrak{m}(a_1, \ldots, a_n; m).

Let us start with a small example. Say we have 5 balls that we want to distribute in two bins A and B of capacities 4 and 3, respectively. Then, these are the all possible distributions: (4, 1), (3, 2), (2, 3). The minimum product is attained at  (4, 1), and hence \mathfrak{m}(4, 3; 5) = 4.  Before reading further, you might want to play around with some more examples to see if a pattern emerges …

So, here’s how a solution goes [1]. Define a greedy distribution to be the one where you first place a single ball in each of the n bins, and then the remaining m-n balls are placed from left to right, moving from the bin A_i to the bin A_{i+1} only after you have already placed a_i (the maximum capacity of A_i) balls in A_i. We will now prove that this greedy distribution minimises the product by showing that from any given distribution x = (x_1, \ldots, x_n), we can reach the greedy distribution by performing certain moves, such that after each such move the product remains the same or reduces.  The moves that we’ll perform are of the following two types:

  1. Bin Swap: If there are bins A_i and A_j, with i < j, such that x_i < x_j, then swap the balls in these two bins.
  2. Unbalancing Move: If there are bins A_i and A_j, with i < j, such that a_i > x_i \geq x_j > 1, then move a ball from the bin A_j to the A_i.

In the first move, the product doesn’t change. While in the second move, the product reduces, as the ratio of the new product to the old product is equal to \frac{(x_i + 1)(x_j - 1)}{x_ix_j} = \frac{x_ix_j + x_j - x_i - 1}{x_ix_j}, which is less than 1 because x_j \leq x_i.

After some thought, it should be clear that by first performing Bin Swaps, and then doing the Unbalancing Moves on any starting distribution x, we can reach the greedy distribution.This shows that the greedy distribution must minimize the product. Of course, it might be that it is not the unique distribution that minimises the product.

We can now deduce the following facts about the function \mathfrak{m}(a_1, \ldots, a_n; m) that will be useful later.

  1. \mathfrak{m}(2, \ldots, 2; 2n - k) = 2^{n-k}.
  2. \mathfrak{m}(a, \ldots, a; m) = (r+1)a^k, where r is the remainder when you divide m-n by a - 1, and k is the quotient.

[1] http://arxiv.org/abs/1404.7793

Advertisements

About Anurag Bishnoi

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Combinatorics, Polynomial Method and tagged . Bookmark the permalink.

2 Responses to Balls in Bins

  1. Pingback: Alon-Furedi, Schwartz-Zippel, DeMillo-Lipton and their common generalization | Anurag's Math Blog

  2. Pingback: Applications of Alon-Furedi to finite geometry | Anurag's Math Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s