# Bins in balls where bin size grows exponentially

I have $k$ bins. The first bin can fit $1$ ball. Each subsequent bin can fit two times more balls than the previous one. In other words, the $i$th bin can fit $2^i$ balls.

We randomly assign $U = 2^{k-d}$ balls to bins ($d \geq 1$), respecting the constraint on the number of balls a bin can fit. In other words, we randomly select $2^{k-d}$ places from all the $2^k - 1$ places of all the bins.

We then sort the bins in ascending order with respect to their size, i.e. how many balls an empty bin can fit. Call the random variable $X$ the number of balls in the first non-empty bin in this order.

Example:

Bins               [-] [--] [----] [--------] ... [--------...----]
With balls         [-] [*-] [-**-] [-------*] ... [-**-***-...--*-] => X = 1
Another example    [-] [--] [-***] [-------*] ... [-**-***-...--*-] => X = 3


What is the expected value of the random variable $X$? How can I compute it?

Is a more general way to compute this random variable for any given bin size distribution known?

-
I think you shoul elaborate a bit more on the distribution used. For each ball, select a not-yet-filled bin uniformly? Or randomly assign all balls uniformly and reject/repeat if one bin should turn out to be overfull? Or randomly select $2^{k-d}$ out of the $2^k-1$ "places" in all bins? – Hagen von Eitzen Feb 7 '13 at 17:42
Actually - I meant randomly select $2^{k-d}$ out of the $2^k - 1$ places in all the bins. – axel22 Feb 7 '13 at 17:44

I suggest thinking of it as finding the total number of balls in bins from the first one upto the first bin that contain at least one ball. Or, in other words $$X =\sum_{i=1}^k \begin{cases} \#\text{balls in bin }i & \text{if all bins to the left of i are empty} \\ 0 & \text{otherwise} \end{cases}$$ Only one of the terms in this sum will be nonzero in each situation, but the ones to the left and the right of the chosen bin are zero for different reasons. The trick: By linearity of expectation, the expectation of each term in the sum can be computed separately!

For generality, let the size of bin $i$ be $m_i$, and $c_i=\sum_{j=i}^k m_j$ be total capacity of all bins from bin $i$ up to the right end of the line. Then the total capacity of all bins is $c_1$. (In your particular case we have $c_i=2^{k+1}-2^{i}$.)

Now, the probability that given bin number $i$ is included in the sum is $$\binom{c_i}{U} \Big/ {\binom{c_1}{U}} = \frac{c_i!\; (c_1-U)!}{c_1!\; (c_i-U)!}$$ Here $\binom{c_i}{U}$ must be considered to be 0 if $c_i<U$ -- there are no ways to choose a set of $U$ positions from only $c_i$ possible ones. To the right of the equals sign we can get the same result by considering the factorial of a negative integer to be "infinitely large", such that $(c_i-U)!$ in the denominator kills the entire fraction when $c_i<U$. (This is not quite as arbitrary as it may sound at first, because $(-n)!$ correspond to poles of the gamma function anyway).

The expected number of balls in bin $i$, given that it is included in the sum, can be computed (again by linearity of expectation, now applied to each position in the bin) as $$m_i \frac{U}{c_i}$$ because once we know that all positions to the left are empty, all ways to distribute $U$ balls among the remaining $c_i$ positions are equally likely.

Putting it all together, $$\langle X\rangle = U\frac{(c_1-U)!}{c_1!} \sum_{i=1}^{k} m_i \frac{(c_i-1)!}{(c_i-U)!} \quad\left(= \frac{U}{c_1{}^{\underline U}} \sum_{i=1}^k m_i (c_i-1)^{\underline{U-1}}\right)$$ which is not nearly as nice looking as my first, wrong, attempt. The parenthesized formula on the right uses falling factorials in a (probably futile) attempt to make it look prettier.

Sanity check (suggested by @Jan Dvorak): When $U=1$, $X$ is always $1$. The formula above reduces to $$\langle X\rangle = \frac{(c_1-1)!}{c_1!} \sum_{i=1}^{k} m_i \frac{(c_i-1)!}{(c_i-1)!} = \frac{1}{c_1} \sum_{i=1}^{k} m_i = \frac{c_1}{c_1} = 1$$ Also when $U=c_1$, $X$ is always $m_1$. In this case all terms of the summation but the first one are killed by the $(c_i-U)!$ in the denominator, and we get $$\langle X\rangle = c_1\frac{0!}{c_1!} \sum_{i=1}^{1} m_i \frac{(c_i-1)!}{0!} = m_1\frac{c_1!}{c_1!} = m_1$$

-
Remember the result should be $1$ when $b=1$ and $m_1$ when $b=s_k$ – Jan Dvorak Feb 7 '13 at 19:46
@JanDvorak: Good sanity checks. It seems to work fine with the current version. – Henning Makholm Feb 7 '13 at 20:31
Looks like a good solution - thanks! I've been numbering the bins starting from $0$, so I think the only notation detail I'd change is $k+1$ to $k$ and $c_1$ to $c_0$. – axel22 Feb 8 '13 at 9:26
And it that case, I should have said that $d \geq 1$. – axel22 Feb 8 '13 at 10:02