1
$\begingroup$

The problem I have is this: There are N colors. A list of size $i$ is created by choosing $i$ distinct colors randomly from the total $N$ possible colors. A second list of size $j$ is created in a similar manner, choosing $j$ distinct colors out of the $N$ possible colors. What are the expected number of common colors between the two lists?

If there are repetitions allowed within a list, it would be $\frac{ij}{N}$, but here since repetitions are not allowed, I fear that the expression for expectation appears too complicated.

(Note: To get $\frac{ij}{N}$ in the first case, we can create $ij$ pairings of the type $(x,y)$ where $x \in list_1,y \in list_2$. With a probability of $\frac{1}{N}$, $(x,y)$ will be a collision. Each of these pairings are independently, randomly distributed, so the expected number of collisions is $\frac{ij}{N}$. Is that correct? )

$\endgroup$
2
$\begingroup$

The complication here can be extremely reduced by using the basic properties of the expectation, symmetry, and independence.

The number, $C$, of collisions can be written as $$ C=\sum_{k=1}^{N}C_k,\qquad C_k=1_{\{\text{color $k$ is present in both lists}\}}. $$ So, by linearity of expectation, $$ \mathbb{E}[C]=\sum_{k=1}^{N}\mathbb{E}[C_k]=\sum_{k=1}^{N}P(\text{color $k$ is present in both lists})=N\cdot P(\text{color $1$ is present in both lists}), $$ by symmetry. (If you aren't comfortable with the symmetry argument, you can of course just also compute this for arbitrary $k$.)

So, all you need to compute is this last probability. By assumption, the two lists are chosen independently; so, $$ P(\text{color $1$ is present in both lists})=P(\text{color $1$ is in first list})\cdot P(\text{color $1$ is in second list}). $$ I'll let you finish it out from here.

$\endgroup$
2
$\begingroup$

Each colour has probability $\frac iN$ to appear in the first list and independently probability $\frac jN$ to appear in the second list. Thus it has probability $\frac{ij}{N^2}$ to appear in both lists, and by linearity of expectation the expected number of collisions is $\frac{ij}N$, the result that you expected in the case with repetitions. In the case with repetitions, this is not the expected number of common colours but the expected number of pairs with common colours. (Without repetitions, that's the same thing.) The expected number of common colours in that case is, following the above approach:

$$ N\left(1-\left(1-\frac1N\right)^i\right)\left(1-\left(1-\frac1N\right)^j\right)\;. $$

The main point to remember here is that in your statement "Each of these pairings are independently, randomly distributed, so the expected number of collisions is $\frac{ij}N$", the premise "independently" was unnecessary, because linearity of expectation is independent of independence. That's why you can apply it in the case without repetitions just like you were applying it to the case with repetitions, since the dependence engendered by the exclusion of repetitions doesn't matter.

$\endgroup$
  • 1
    $\begingroup$ Ah, now I see the mistake in my argument for the case with repetition. This makes it much clearer, thanks a lot :) $\endgroup$ – Chameleon Mar 23 '16 at 18:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.