# Weighted circular balls into bins

I would like to ask you for a help about modified balls into bins problem. Consider $$n$$ weighted balls such that each ball has a weight $$w_i$$ that is at most $$W$$. Furthermore, each of $$m$$ bins has a maximum capacity $$W$$. We place $$n$$ balls into $$m$$ bins uniformly at random. That is, there are $$m^n$$ different assignments of balls to bins and all of them are equally likely.

If a ball $$i$$ with the weight $$w_i$$ lands into a random bin $$j$$ that already contains balls of total weight $$w'_j$$, then two cases are possible:

1. $$W \ge w'_j + w_i$$: we put the ball into the bin and set $$w'_j:= w'_j + w_i$$
2. $$W < w'_j + w_i$$ : we split the ball $$i$$ putting $$W-w'_j$$ of its weight to $$j$$-th bin and proceed to insert the $$i$$-th ball with the new weight $$w_i:=w_i-W+w'_j$$ to the bin $$j + 1 \mod{m}$$.

If this helps its a modified linear probing algorithm, when we insert super keys into a hash table, where each super key consists of at most $$W$$ keys.

Now assume that we already have $$n$$ balls with weights $$w_1, \dots, w_x$$ in $$m$$ bins. The total weight of the balls is $$\mathcal{W}$$ and $$\mathcal{W}$$ is a multiple of $$W$$. Let $$E[T]$$ is the average number of bins visited during the insertion of a new ball with the weight $$W$$. I want to show that $$E[T]$$ is maximized when we insert $$x = \mathcal{W}/W$$ balls with the weight $$W$$ each.

Example: we have $$\mathcal{W} = 8$$, $$W = 2$$ and $$m=16$$. We can insert $$x=5$$ balls: $$\{1, 1, 2, 2, 2\}$$ or $$x=4$$ balls: $$\{2, 2, 2, 2\}$$ and so on. The only condition is that the total weight of the balls is $$8$$ and the maximum weight of each ball is $$2$$. I want to show that $$E[T]$$ is maximized when we insert $$x=4$$ balls with maximum weight $$2$$.

Could you please advise me some approaches or papers to tackle this problem. Thank you very much.

• Fixed it. Will copy it here as well. We place $n$ balls into $m$ bins uniformly at random. That is, there are $m^n$ different assignments of balls to bins and all of them are equally likely. – rbtrht Dec 21 '19 at 21:22
• So you fix $n$ balls with weights $w_1, \ldots, w_n$, then perform the following random experiment: insert each of the $n$ balls randomly as described in the post, then insert one more ball of weight $W$, and let r.v.$~T$ be the number of bins visited during the insertion of that last ball. You want to show that, for any integer $k\ge 0$, over all choices of $n$ and $w_1,\ldots, w_n$ such that $\sum_i w_i = kW$ (and $0\le w_i\le W$ for all $i$), the choice $n=k$ and $W, W, \ldots, W$ ($k$ times) maximizes $E[T]$? – Neal Young Dec 21 '19 at 23:10
• Yes, you are correct! – rbtrht Dec 22 '19 at 8:51