Ampliación del problema clásico del cumpleaños

Question

Estoy leyendo unos apuntes que ha subido nuestro profesor de Probabilidad, y deja una variación bastante interesante del clásico Problema de cumpleaños como ejercicio para "el probabilista aventurero con demasiado tiempo libre".

Dejamos que $B_k$ sea el número de grupos de $k$ personas que cumplen años el mismo día. Por el enunciado de la primera parte del problema, creo que pretende que el ejercicio permita que los grupos se solapen, es decir, si tenemos 3 personas que cumplen años el 1 de enero y ninguna otra coincide, entonces $B_3 = 1$ , $B_2 = 3$ y $B_k = 0$ para $k > 3$ .

El problema clásico determina un valor para $\mathbb{P} \{B_2>0\}$ y encontrar el menor $n$ tal que la probabilidad de dos personas en una población de tamaño $n$ compartir un cumpleaños es mayor que $\frac{1}{2}$ . A través de un enfoque combinatorio estándar he identificado $n=23$ .

Problème

Ahora se nos pide que determinemos $\mathbb{E}[B_2]$ , $\text{Var}[B_2]$ , $\mathbb{E}[B_3]$ y $\text{Var}[B_3]$ . Creo que aquí es donde se rompe un enfoque combinatorio, aunque no estoy seguro.

También me preguntaba (más allá del ámbito de este ejercicio, pero parece un problema interesante, que me deja totalmente perplejo), cómo encontraríamos el menor $n$ tal que la probabilidad de tres personas en una población de tamaño $n$ compartir un cumpleaños es mayor que $\frac{1}{2}$ . Creo que esto podría abordarse utilizando Desigualdad de Chebyshev aunque aún no he llegado a la conclusión de cómo podría aplicarse con éxito.

El ejercicio del profesor también da lugar de forma natural a la pregunta de cómo podríamos determinar $\mathbb{E}[B_k]$ , $\text{Var}[B_k]$ en general $k$ . Esto parece que podría ser un ejercicio de combinatoria bastante engorroso.

Agradecería mucho a quien pueda ayudarme con este ejercicio. Saludos, MM.

Answer 1

El caso $k=2$ es bastante simple.

Expresar el número de pares $Z=\sum_i Z_i$ donde el índice recorre todos los pares $i=\{i_1,i_2\}$ de índices distintos de $\{1,\dots, n\}$ . Aquí $Z_i$ es la variable aleatoria indicadora del suceso de que las personas $i_1$ y $i_2$ comparten un cumpleaños. Sorprendentemente, si $i\neq j$ entonces $Z_i$ y $Z_j$ no están correlacionadas (aunque no son independientes) si la intersección de $i$ y $j$ está vacío o no.

Así, para $N={n\choose 2}$ y $p=1/365$ la variable aleatoria $Z$ tiene la misma media y varianza que si fuera binomial: $$\mathbb{E}(Z)=Np,\quad \mathbb{V}(Z)=Np(1-p).$$

Lamentablemente, esto ya no funciona cuando $k$ es mayor que $2$ .

---

Actualización: Está claro que tengo demasiado tiempo libre. He aquí el resultado general: $$\mathbb{E}(B_k)={n\choose k}p^{k-1},\quad \mathbb{V}(B_k)={n\choose k}\sum_{j=2}^k{k\choose j}{n-k\choose k-j}\left[p^{2k-j-1}-p^{2(k-1)}\right].$$

Answer 2

Me centraré en la segunda cuestión porque éste era uno de los problemas en los que estaba trabajando con respecto a las funciones inyectivas que no son equilibradas (el número de preimágenes de cualquier elemento de la imagen no son necesariamente iguales).

Hay otras generalizaciones de la paradoja del Cumpleaños desde el punto en que se mira. McKinney tiene un artículo en JSOTR, titulado Problema del cumpleaños generalizado que hace lo mismo. Otro punto de vista de la generalización ha sido contemplado por un artículo de Mathis, titulado Un problema de cumpleaños generalizado .

Si desea buscar funciones que tengan un rango arbitrario (digamos $n$ donde $n$ en el problema clásico de cumpleaños es 365), hay un buen artículo de Suziki et al. que da un límite sobre el número esperado de cálculos que hay que hacer para encontrar un $k$ -colisiones en el camino. Puede consultar el documento aquí . Hubo un documento de Diaconis y Mosteller Método de estudio de las coincidencias que da un teorema muy complicado sin demostración que se reduce al resultado de Suziki et al cuando se mira asintóticamente.

Si tienes problemas con alguno de los documentos anteriores, házmelo saber. Le ayudaré con mi comprensión de estas obras. Estoy seguro de que hay muchos más, pero estos son los que me he tomado la paciencia de leer.

Answer 3

Por las expectativas $E(B_k)$ considere la probabilidad de que el primer $k$ comparten un cumpleaños que es $1/365^{k-1}$ así que $$E(B_k) = {n \choose k}/365^{k-1}. $$

Si no se cuentan los solapamientos, hay que considerar la probabilidad de que el primer $k$ comparten un cumpleaños y el otro $n-k$ no comparten ese cumpleaños que es $364^{n-k}/365^{n-1}$ así que $$E(B_k) = {n \choose k}\frac{364^{n-k}}{365^{n-1}}.$$

Un resultado relacionado es que el número esperado de cumpleaños diferentes es $$365 (1 - (364/365)^n)$$ mientras que la varianza del número esperado de cumpleaños diferentes es $$365(364/365)^n + 364\times 365(363/365)^n - 365^2(364/365)^{2n}.$$

Answer 4

Pista: la expectativa es aditiva. Es decir, $E(A+B)$ = $E(A)+E(B)$ aunque $A$ y $B$ dependen de alguna manera. Esto acaba con todo lo que implica $E(B_k)$ casi al instante.

Casi se puede hacer el mismo truco con la varianza - y de hecho, se puede hacer exactamente el mismo truco para $V(B_2)$ - pero para $V(B_3)$ y superiores, necesitas poner algunos términos de covarianza.

Al sumar un grupo de variables aleatorias, la varianza de la suma es igual a la suma de las varianzas más el doble de la suma de las covarianzas por pares. Véase http://en.wikipedia.org/wiki/Variance#Properties para más información. Puede calcular la covarianza con bastante facilidad para $V(B_3)$ ya que sólo es distinto de cero cuando los grupos de tres comparten dos miembros (es decir, {A,B,C} y {B,C,D}).

Para $V(B_k)$ en general, se convierte en la pesadilla que mencionas, ya que los grupos pueden compartir desde $2$ a $k-1$ miembros. Necesitarás una buena dosis de PIE (principio de inclusión-exclusión), pero es posible (aunque difícil).

Answer 5

Algunas ideas...

Sea n = número de personas y d = número de días del año.

Supongamos que n < d

Intentamos calcular $\mathbb{E}[B_2]$ que es el número esperado de parejas que cumplen años el mismo día. Excluimos los triples (o más) con la misma fecha de nacimiento.

$C_{2,1}$ =número de combinaciones con exactamente 1 pareja con el mismo cumpleaños = $\binom{n}{2}\cdot \frac{d!}{(d-n+1)!}$

$C_{2,2}$ =número de combinaciones con exactamente 2 parejas con el mismo cumpleaños = $\binom{n}{4}\cdot 3 \cdot \frac{d!}{(d-n+2)!}$

$C_{2,3}$ =número de combinaciones con exactamente 3 parejas con el mismo cumpleaños = $\binom{n}{6}\cdot 5 \cdot 3 \cdot \frac{d!}{(d-n+3)!}$

$C_{2,4}$ =número de combinaciones con exactamente 4 parejas con el mismo cumpleaños = $\binom{n}{8}\cdot 7 \cdot 5 \cdot 3 \cdot \frac{d!}{(d-n+4)!}$

$C_{2,k}$ =número de combinaciones con exactamente $k=\left \lfloor \frac{n}{2} \right \rfloor$ parejas con el mismo cumpleaños = $\binom{n}{2k}\cdot \left( 2k-1 \right) \cdot \left( 2k-3 \right) \cdot ... \cdot 3 \cdot \frac{d!}{(d-n+k)!}$

Ahora debemos encontrar una forma de sumar todas estas combinaciones.

$\mathbb{E}[B_2]$ = $ \frac{\sum_{l=1}^{k}{kC_{2,l}}} {d^n}$