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

<p>If a ball <span class="math-container">$i$</span> with the weight <span class="math-container">$w_i$</span> lands into a random bin <span class="math-container">$j$</span> that already contains balls of total weight <span class="math-container">$w'_j$</span>, then two cases are possible:</p>

<ol>
<li><span class="math-container">$W \ge w'_j + w_i$</span>: we put the ball into the bin and set <span class="math-container">$w'_j:= w'_j + w_i$</span> </li>
<li><span class="math-container">$W &lt; w'_j + w_i$</span>  : we split the ball <span class="math-container">$i$</span> putting <span class="math-container">$W-w'_j$</span> of its weight to <span class="math-container">$j$</span>-th bin and proceed to insert the <span class="math-container">$i$</span>-th ball with the new weight <span class="math-container">$w_i:=w_i-W+w'_j$</span> to the bin <span class="math-container">$j + 1 \mod{m}$</span>.</li>
</ol>

<p>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 <span class="math-container">$W$</span> keys.</p>

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

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

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

CC BY-SA 4.0
2019-12-21T21:22:20.210Z
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
CC BY-SA 4.0
2019-12-21T23:10:33.650Z
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
CC BY-SA 4.0
2019-12-22T08:51:36.213Z
Yes, you are correct!
rbtrht
<reference-request><pr.probability>
Weighted circular balls into bins
rbtrht
# Weighted circular balls into bins

(Asked by: username_0 on 2019-12-21)

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.

**Tags:** reference-request, pr.probability

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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]$?  
> **username_0**: Yes, you are correct!  

---

## 0 answers

