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

Question

El problema que tengo es el siguiente: Hay N colores. Se crea una lista de tamaño $i$ eligiendo $i$ colores distintos al azar de los $N$ colores posibles. Se crea una segunda lista de tamaño $j$ de manera similar, eligiendo $j$ colores distintos de los $N$ colores posibles. ¿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í, dado que no se permiten repeticiones, temo que la expresión para la expectativa parezca demasiado complicada.

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

Answer 1

La complicación aquí se puede reducir considerablemente mediante el uso de las propiedades básicas de la expectativa, simetría e independencia.

El número, $C$, de colisiones se puede escribir como $$ C=\sum_{k=1}^{N}C_k,\qquad C_k=1_{\{\text{el color $k$ está presente en ambas listas}\}}. $$ Entonces, por linealidad de la expectativa, $$ \mathbb{E}[C]=\sum_{k=1}^{N}\mathbb{E}[C_k]=\sum_{k=1}^{N}P(\text{el color $k$ está presente en ambas listas})=N\cdot P(\text{el color $1$ está presente en ambas listas}), $$ por simetría. (Si no te sientes cómodo con el argumento de simetría, por supuesto puedes calcular esto también para un $k$ arbitrario.)

Entonces, todo lo que necesitas calcular es esta última probabilidad. Por suposición, las dos listas se eligen de forma independiente; entonces, $$ P(\text{el color $1$ está presente en ambas listas})=P(\text{el color $1$ está en la primera lista})\cdot P(\text{el color $1$ está en la segunda lista}). $$ Te dejo que termines desde aquí.

Answer 2

Cada color tiene probabilidad $\frac{i}{N}$ de aparecer en la primera lista e independientemente probabilidad $\frac{j}{N}$ de aparecer en la segunda lista. Por lo tanto, tiene probabilidad $\frac{ij}{N^2}$ de aparecer en ambas listas, y por linealidad de la esperanza el número esperado de colisiones es $\frac{ij}{N}$, el resultado que esperabas en el caso con repeticiones. En el caso con repeticiones, este no es el número esperado de colores comunes sino el número esperado de pares con colores comunes. (Sin repeticiones, eso es lo mismo). El número esperado de colores comunes en ese caso es, siguiendo el enfoque anterior:

$$ N\left(1-\left(1-\frac{1}{N}\right)^i\right)\left(1-\left(1-\frac{1}{N}\right)^j\right)\;. $$

El punto principal a recordar aquí es que en tu afirmación "Cada uno de estos emparejamientos se distribuye de forma independiente y aleatoria, así que el número esperado de colisiones es $\frac{ij}{N}$", la premisa "independientemente" era innecesaria, porque la linealidad de la esperanza es independiente de la independencia. Es por eso que puedes aplicarlo en el caso sin repeticiones igual que lo estabas aplicando en el caso con repeticiones, ya que la dependencia engendrada por la exclusión de repeticiones no importa.