Take two sets of bins;
Set $A$ contains $M$ bins, each of unequal capacities $a_i$, $i \in \{1,..,M\}$.
Set $B$ contains $N$ bins, each of unequal capacities $b_j$, $j \in \{1,..,N\}$.
Constrain equal total capacities of both sets: $\sum A = \sum a_i = \sum b_j = \sum B = 1$, normalizing with unity, WLOG.

From each set choose a subset of bins, $\hat{A}, \hat{B}$. The probability of choosing any bin from each set is uniformly equal to $p$.
Now take the minimum capacity of either subset, $X = \min ( \sum \hat{A}, \sum \hat{B} )$.

What is the expectation of $X$ as a function of $p, N, M$? That is, what is function $f$ in $E[X]=f(p, N, M, [a_i, b_j])$?

I believe this problem also depends upon the distribution of the unequal capacities, so I would also appreciate an answer to the simpler version where $a_i=\frac{1}{M}$ and $b_j = \frac{1}{N}$.

Also any approximation techniques or suggestions in the case there is no analytical solution are very welcome!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.