There are $n$ bins each with different capacities, $c_1, c_2, .., c_n$.
There are $m$ balls, where $m = p \sum_i c_i$, for $0<p<1$.
Suppose the capacities and number of balls are large so this problem emulates one of a continuous nature.
Balls are sequentially and randomly assigned to bins with uniform probability amongst those that have remaining capacity.
Suppose the number balls allocated to bin $i$ is defined by random variable $B_i$.
Is there a closed form function (of parameters $n, p, c_1, .., c_n$) for $E[B_i]$?
Some numeric analysis
I have implemented the following Monte Carlo Analysis in python:
def bin_expectation(c, p, samples=1000): """ Calculate the expectation of bin allocation based on the uneven capacities of each bin. Ball distribution is performed sequentially and uniformly over all (unfilled) bins. Args: c (array): array of bin capacities p (float): proportion of total capacity to be distributed, i.e. sum(c)*p = total number of balls. samples (int): the number of monte carlo trials to generate statistics from Returns: Array: the mean of number of allocated balls in each bin. Method: i) In each iteration divide the remaining ball allocation into n equal piles. ii) Generate a uniform RV for each pile which describes the pile proportion allocated to the bin. iii) If the bin becomes over allocated reset to its max capacity. iV) repeat until all balls allocated. """ t_balls = c.sum()*p # total number of balls n = len(c) # number of bins c_arr = np.tile(c, (samples, 1)) # create repeated c arr for each MC sample a = np.zeros(shape=(samples, n)) # allocation array for each sample for i in range(40): # 20-30 iterations is generally enough, 40 is conservative rv = stats.uniform.rvs(size=n*samples, loc=0, scale=1/n) rv = np.reshape(rv, newshape=(samples, n)) # generate RVs for allocation r_balls = t_balls - a.sum(axis=1) # the remaining number of balls for each sample a += np.einsum('ij,i->ij', rv, r_balls) # adjust the allocation a = np.where(a > c_arr, c_arr, a) # correct for over allocated bins return a.mean(axis=0)
If I run the above function on the parameters:
c = np.array([100, 200, 300, 400, 500]) p = 0.5 Exp_a = bin_expectation(c, p, samples=2000)
Then the chart below plots the expected allocation of each bin for different $p$. The graphs look like there might be some nice analytical formula but then it also might be quite horribly algebraically cumbersome?