problema de cumpleaños - número esperado de colisiones

Question

Hay muchas descripciones del "problema del cumpleaños" en este sitio - el problema de encontrar la probabilidad de que en un grupo de $n$ personas habrá alguna (= al menos 2) que comparta un cumpleaños.

Me pregunto cómo encontrar en cambio el número esperado de personas que comparten un cumpleaños en un grupo de $n$ personas. Recuerdo que la expectativa significa la suma ponderada de las probabilidades de cada resultado:

$$E[X]=\sum_{i=0}^{n-1}x_ip_i$$

Y aquí $x$ debe significar el número de colisiones que implican $i+1$ personas, que es $n\choose i$ . Todo $n$ personas nacidas en días diferentes significa que no hay colisiones, $i=0$ dos personas nacidas el mismo día significa $n$ colisiones, $i=1$ Todos $n$ personas nacidas el mismo día significa $n$ colisiones, $i=n-1$ .

Dado que las probabilidades de que haya tres o más personas con la misma fecha de nacimiento son muy pequeñas en comparación con las de dos personas con la misma fecha de nacimiento, y disminuyen más rápidamente que $x$ aumenta, ¿es correcto decir que esta expectativa puede ser aproximada por

$$E[X]\approx {n\choose 0}p_{no\ collisions}+{n\choose 1}p_{one\ collision}$$

Esto no me parece bien y agradecería alguna orientación.

---

Lo siento - editado para cambiar ${n\choose 1}$ a ${n\choose 0}$ en la segunda ecuación. Es un descuido por mi parte.

Answer 1

La persona de probabilidades $B$ acciones persona $A$ es el cumpleaños de $1/N$ , donde $N$ es el número de cumpleaños igualmente posibles,

por lo que la probabilidad $B$ no comparte la persona $A$ es el cumpleaños de $1-1/N$ ,

por lo que la probabilidad $n-1$ otras personas no comparten $A$ es el cumpleaños de $(1-1/N)^{n-1}$ ,

por lo que el número esperado de personas que no tienen otras que compartan su cumpleaños es $n(1-1/N)^{n-1}$ ,

por lo que el número esperado de personas que comparten cumpleaños con alguien es $n\left(1-(1-1/N)^{n-1}\right)$ .

Answer 2

Intentaré controlar la interpretación más estándar de nuestra pregunta utilizando (al principio) un lenguaje muy informal. Llamemos a alguien infeliz si una o más personas comparten su "cumpleaños". Queremos encontrar el "número esperado" de personas infelices.

Definir la variable aleatoria $X$ diciendo que $X$ es el número de personas infelices. Queremos encontrar $\text{E}(X)$ . Sea $p_i$ sea la probabilidad de que $X=i$ . Entonces $$\text{E}(X)=\sum_{i=0}^{n} i\,p_i$$ Ese es más o menos el enfoque que usted adoptó. Ese enfoque es correcto, y algo muy razonable para intentar. De hecho han sido entrenado para utilizar este enfoque, ya que es exactamente como resolvió los ejercicios que siguieron a la definición de la expectativa.

Por desgracia, en este problema, encontrar el $p_i$ es muy difícil. Uno podría, como usted, decidir que para una buena aproximación, sólo los primeros $p_i$ realmente importa. Eso es a veces cierto, pero depende bastante de los valores $N$ de "días en el año" y el número $n$ de personas.

Afortunadamente, en este problema, y en muchos otros similares, existe una alternativa muy enfoque eficaz. Implica un poco de teoría, pero la recompensa es considerable.

Alinea a las personas en una fila. Define las variables aleatorias $U_1,U_2,U_3,\dots,U_n$ diciendo que $U_k=1$ si el $k$ -la persona es infeliz, y $U_k=0$ si el $k$ -la persona no es infeliz. La observación crucial es que $$X=U_1+U_2+U_3+\cdots + U_n$$

Una forma de interpretarlo es que tú, el observador, recorres la fila de personas, marcando con una cruz en tu hoja de cálculo si la persona está descontenta, y no marcando nada si la persona no está descontenta. El número de marcas es $X$ el número de personas infelices. También es la suma de los $U_k$ .

A continuación utilizamos el siguiente teorema muy importante: La expectativa de una suma es la suma de las expectativas . Este teorema se cumple "siempre". Las variables aleatorias que se suman no tienen por qué ser independientes . En nuestra situación, el $U_k$ no son independientes, pero, para la expectativa de una suma, eso no importa. Así que tenemos $$\text{E}(X)=\text{E}(U_1) + \text{E}(U_2)+ \text{E}(U_3)+\cdots +\text{E}(U_n)$$

Por último, hay que tener en cuenta que la probabilidad de que $U_k=1$ es, como explica cuidadosamente @Henry, igual a $p$ , donde $$p=1-(1-1/N)^{n-1}$$ De ello se desprende que $\text{E}(U_k)=p$ para cualquier $k$ y por lo tanto $\text{E}(X)=np$ .

Answer 3

La siguiente aproximación puede ser útil.

Si hay $k$ personas y $N$ los posibles cumpleaños (o en el caso de una tabla hash, $k$ los elementos que se han convertido en hash en $N$ cubos), entonces el número esperado de personas/objetos que colisionan con al menos uno de los otros es exactamente (ver la respuesta de Henry o la de André Nicolas) $$\begin{align} & k \left(1 - \left(1-\frac1N\right)^{k-1}\right) \\ & = \frac{k(k-1)}{N} - \frac{k(k-1)(k-2)}{2N^2} + O\left(\frac1{N^3}\right) \\ & \approx \frac{k^2}{N}. \end{align}$$

---

La anterior es una posible definición de "número esperado de colisiones". Si hay $r$ cumpleaños/cubos cada uno con dos personas/artículos en ellos, la expresión anterior da cuenta $2r$ ya que cuenta cada miembro de cada par. Si en cambio se quiere contar el número de cubos/cumpleaños que tienen varias personas en ellos, entonces la respuesta es aproximadamente $$\approx \frac{k^2}{2N}.$$

Este resultado puede derivarse

• del análisis anterior, observando que, en primer orden, el tipo de colisión más común es tener 2 en un cubo (las colisiones a tres bandas y superiores serán estadísticamente raras), por lo que sólo hay que reducir el recuento a la mitad;

• o bien, haciendo un análisis similar centrado en los cumpleaños/cubos: la probabilidad de que $0$ o $1$ de la $k$ la gente tiene ese cumpleaños en particular es $$\left(1 - \frac1N\right)^k + k\frac1N\left(1 - \frac1N\right)^{k-1}$$ Por lo tanto, el número esperado de cubos con múltiples valores en ellos es $$\begin{align} & N \left(1 - \left(1 - \frac1N\right)^k - k\frac1N\left(1 - \frac1N\right)^{k-1}\right) \\ & = \frac{k(k-1)}{2N} - \frac{k(k-1)(k-2)}{3N^2} + O\left(\frac1{N^3}\right) \\ & \approx \frac{k^2}{2N}. \end{align}$$