0
$\begingroup$

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!

$\endgroup$

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.