Choose items from different sets such that no two items come from the same set but all items are equally likely to be chosen.

37 Views Asked by At

I have a number of sets.

Each set contains $n_i$ items. I would like to choose 2 items from the sets so that overall each item has equal chance of being drawn.

I could choose a set with probability $p_i$, then choose an item from that set and then choose a different set, now with probability $\frac{p_j}{1-p_i}$ and then choose an item from that set.

In order for the overall probability to be equal over all we would need.

$$\frac{2}N = \frac{p_i}{n_i} + \sum_{i\neq j} \frac{p_jp_i}{(1-p_j)n_i}$$

Where $$N=\sum_i n_i$$

This looks awful. I suspect there is an easier way to do this. Though obviously it is impossible in the case where $$\frac{n_i}N>\frac12$$