Colisiones en una muestra de distribución uniforme

Question

Preguntado en una entrevista de Microsoft: Suponga que tiene una distribución uniforme (puede ser discreta o continua) de tamaño X y que selecciona al azar una muestra de tamaño Y. 1) ¿Cuál es la probabilidad en términos de X e Y de una colisión? 2) ¿Cuál es el número esperado de colisiones en términos de X e Y?

Answer 1

Para la posibilidad de colisión, véase esta pregunta . La respuesta de Derek Jennings allí con su anotación dice:

$$\mathbb{P}(\mbox{collision})=1 - \left( 1- \frac{1}{X} \right)\left( 1- \frac{2}{X} \right)\cdots \left( 1- \frac{Y-1}{X} \right),$$

---

Para responder a la segunda pregunta, debemos decidir qué se considera una colisión. Por ejemplo, si la muestra es $1,2,1,1,3$ entonces se podría decir que sólo hay una colisión, ya que sólo se repite un valor. Por otro lado, dos veces en el transcurso del muestreo podríamos decir "Oye, ya he visto ese valor". Según esta segunda interpretación, hubo dos colisiones.

Interpretación 1:

Para encontrar el número esperado de colisiones, es útil introducir las variables aleatorias indicadoras idénticamente distribuidas $Z(i)$ para $1\leq i\leq X$ donde $Z(i)=1$ si el artículo $i$ aparece más de una vez, y $Z(i)=0$ de lo contrario.

El número $N(i)$ de veces que ese artículo $i$ aparece es un binomio $(Y,1/X)$ variable aleatoria por lo que $$\mathbb{P}(Z(i)=0)=\mathbb{P}(N(i)\leq 1)=\left({X-1\over X}\right)^{Y}+Y\left({X-1\over X}\right)^{Y-1}\left({1\over X}\right),$$ y
$$\mathbb{E}(\mbox{number of collisions})=\sum_{i=1}^X \mathbb{E}(Z(i)) =X\mathbb{P}(Z(1)=1) =X-X\left({X-1\over X}\right)^Y -Y \left({X-1\over X}\right)^{Y-1}.$$

Interpretación 2:

Con argumentos similares, se puede calcular $$\mathbb{E}(\mbox{number of collisions})=Y+X\left({X-1\over X}\right)^Y -X.$$

Answer 2

Para la versión continua, la probabilidad de colisión será $0$ . Es decir, si la variable aleatoria $W$ tiene una distribución uniforme en el intervalo $[a, b]$ y tomamos una muestra de tamaño $n$ la probabilidad de colisión es $0$ . De hecho, esto es cierto para cualquier distribución continua.

Para la versión discreta, la respuesta es obviamente diferente. Se trata de un problema estándar del primer curso de probabilidad. Puede encontrar la información completa buscando en "Problema de cumpleaños".