Número esperado de colisiones entre dos listas sin repetición

Question

El problema que tengo es el siguiente: Hay N colores. Una lista de tamaño $i$ se crea seleccionando $i$ colores distintos al azar del total $N$ posibles colores. Una segunda lista de tamaño $j$ se crea de forma similar, eligiendo $j$ colores distintos de la $N$ posibles colores. ¿Cuál es el número esperado de colores comunes entre las dos listas?

Si se permiten repeticiones dentro de una lista, sería $\frac{ij}{N}$ pero aquí, como no se permiten las repeticiones, me temo que la expresión para la expectativa parece demasiado complicada.

(Nota: Para obtener $\frac{ij}{N}$ en el primer caso, podemos crear $ij$ emparejamientos del tipo $(x,y)$ donde $x \in list_1,y \in list_2$ . Con una probabilidad de $\frac{1}{N}$ , $(x,y)$ habrá una colisión. Cada uno de estos emparejamientos se distribuye de forma independiente y aleatoria, por lo que el número esperado de colisiones es $\frac{ij}{N}$ . ¿Es correcto? )

Answer 1

La complicación aquí puede reducirse enormemente utilizando las propiedades básicas de la expectativa, la simetría y la independencia.

El número, $C$ de colisiones puede escribirse como $$ C=\sum_{k=1}^{N}C_k,\qquad C_k=1_{\{\text{color $ k $ is present in both lists}\}}. $$ Así que, por linealidad de la expectativa, $$ \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}), $$ por simetría. (Si no se siente cómodo con el argumento de la simetría, por supuesto, también puede calcular esto para arbitraria $k$ .)

Entonces, todo lo que necesitas calcular es esta última probabilidad. Por supuesto, las dos listas se eligen de forma independiente, por lo que, $$ 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}). $$ Dejaré que lo termines desde aquí.

Answer 2

Cada color tiene una probabilidad $\frac iN$ para aparecer en la primera lista e independientemente probabilidad $\frac jN$ para aparecer en la segunda lista. Por tanto, tiene probabilidad $\frac{ij}{N^2}$ para aparecer en ambas listas, y por linealidad de las expectativas el número esperado de colisiones es $\frac{ij}N$ el resultado que esperaba en el caso con repeticiones. En el caso con repeticiones, no es el número esperado de colores comunes, sino el número esperado de pares con colores comunes. (Sin repeticiones, es lo mismo.) El número esperado de colores comunes en ese caso es, siguiendo el planteamiento anterior:

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

El punto principal que hay que recordar aquí es que en su afirmación "Cada uno de estos emparejamientos está distribuido de forma independiente y aleatoria, por lo que el número esperado de colisiones es $\frac{ij}N$ ", la premisa "independientemente" era innecesaria, porque la linealidad de la expectativa es independiente de la independencia. Por eso puedes aplicarlo en el caso sin repeticiones igual que lo aplicabas en el caso con repeticiones, ya que la dependencia engendrada por la exclusión de las repeticiones no importa.