"Problema del cumpleaños inverso": inferir los días del año a partir de las colisiones en la muestra

Question

Supongamos que tiene n estudiantes seleccionados al azar de otro planeta cuyos cumpleaños se conocen. x de ellos tienen cumpleaños que coinciden con al menos otro estudiante. ¿Cómo se calcula el número de días de su año?

Como alternativa, tal vez pueda utilizar el hecho de que sabe que estos n estudiantes tienen $x_1$ pares de colisiones de cumpleaños, $x_2$ colisión de cumpleaños trillizos y así sucesivamente. ¿Cómo se podría estimar el número de días de su año a partir de eso?

Editar para el contexto : Estoy construyendo un marco de trabajo en el que los profesores pueden construir pequeños programas para generar preguntas matemáticas de forma procedimental y me gustaría mostrarles una estimación de cuántas preguntas reales están generando. Puedo probar su programa un montón de veces para obtener diferentes preguntas y comprobar si las he visto antes (colisiones de cumpleaños).

Por supuesto que inmediatamente después de abandonar y publicar aquí me doy cuenta de que $x_1$ , $x_2$ etc. mencionado anteriormente me daría una distribución binomial donde si puedo obtener P, creo que el "tamaño de la población" debería ser 1/P. Estoy probando este enfoque en este momento y voy a comprobar la cordura y comparar con wolfram alfa. También por favor, sea amable, soy sólo un programador, no sé realmente lo que estoy haciendo.

Answer 1

¡Buena pregunta!

Tiene mucho en común con el Problema de los tanques alemanes Así que tal vez quieras consultar ese artículo para obtener más ideas.

Denotemos el número de días en el año de los extranjeros por $d$ .

Ciertamente, se podría estimar $d$ del número $X$ de estudiantes implicados en colisiones. No es la mejor manera de hacerlo, pero una ventaja que tiene es que se puede calcular fácilmente el número esperado de esos estudiantes en términos de $d$ y resolver para $d$ .

La probabilidad de que un determinado alumno se vea implicado en una colisión es $1-\left(1-\frac1d\right)^{n-1}$ por lo que el número esperado de estudiantes involucrados en colisiones es

$$ E[X]=n\left(1-\left(1-\frac1d\right)^{n-1}\right)\;. $$

Resolver para $d$ rendimientos:

$$ d=\frac1{1-\sqrt[n-1]{1-E[X]/n}}\;. $$

Como una estimación bastante cruda, se podría introducir el valor $X=x$ que has observado como si fuera el valor esperado, dando lugar a la estimación

$$ d=\frac1{1-\sqrt[n-1]{1-x/n}}\;. $$

Esto no tiene mucho sentido en casos extremos: Si no se observa ninguna colisión, el resultado es infinito, y si todos $n$ estudiantes estuvieron involucrados en colisiones, el resultado es $d=1$ . Más adelante veremos que no hay mucho que hacer en el primer caso, pero el resultado poco útil en el segundo caso se debe al uso subóptimo de $x$ .

La razón por la que el número de estudiantes implicados en colisiones no es la mejor manera de utilizar sus datos es que no es un estadística suficiente . Lo ideal es resumir los datos en una estadística suficiente, es decir, una estadística que contenga toda la información sobre $d$ que contienen sus datos. Este no es el caso del número de estudiantes involucrados en colisiones, ya que $4$ estudiantes todos con el mismo cumpleaños y $4$ los estudiantes con dos pares de cumpleaños contienen información diferente sobre $d$ , pero ambos casos contribuyen $4$ al número de estudiantes implicados en colisiones.

Una estadística suficiente viene dada por el número $K$ de los diferentes cumpleaños entre los estudiantes. Por ejemplo, mientras que un estudiante que cumple años una sola vez y tres estudiantes que cumplen años la misma vez tienen una probabilidad diferente a la de dos pares de estudiantes que comparten cumpleaños, la relación de estas probabilidades no depende de $d$ por lo que los dos casos contienen la misma información sobre $d$ .

Así que vamos a tratar de estimar $d$ dado $K$ (y $n$ que forma parte de la configuración, no de los datos).

De un frecuentista punto de vista, nos gustaría obtener un estimador insesgado; es decir, un estimador tal que si se realiza el mismo experimento muchas veces, el valor esperado del estimador sea el verdadero valor del parámetro $d$ . Sin embargo, tal estimador no existe en este caso, ya que sólo podemos obtener $n$ diferentes valores de $K$ mientras que hay infinitos valores del parámetro $d$ que hay que estimar. (Esta es una diferencia cualitativa con el problema del tanque alemán, que sí permite un estimador insesgado).

Así que vamos a probar un Bayesiano enfoque. Parece razonable asumir una prioridad plana, es decir, asignamos el mismo a priori probabilidad a todos los valores posibles de $d$ . Hasta factores independientes de $d$ la probabilidad de observar $K=k$ diferentes cumpleaños entre $n$ estudiantes es proporcional a

$$ \binom dk\left(\frac kd\right)^n\;, $$

ya que podemos elegir $k$ de $d$ días en $\binom dk$ formas y la $n$ los estudiantes tienen cada uno una probabilidad $\frac kd$ para tener su cumpleaños en uno de estos días. (La probabilidad real implica un cálculo más complicado para asegurarse de que todos los $k$ de hecho, los cumpleaños se producen, pero los factores resultantes son independientes de $d$ .)

Para $k=n$ este valor tiende a $1$ de abajo para $d\to\infty$ por lo que no hay una estimación de máxima verosimilitud finita. Esto corresponde al caso anterior en el que $x=0$ produjo un número infinito de $d$ . Se necesita al menos una colisión para obtener cualquier información sobre $d$ .

Así que veamos el caso $k=n-1$ con una sola colisión. Aquí hay una trama para $n=10$ , $k=9$ . Aquí sí tenemos un máximo en la probabilidad; en el ejemplo del gráfico se produce en $d=42$ . Así que si observas $10$ estudiantes y tienen $9$ diferentes, correspondientes a una colisión que implique a dos de ellos, la estimación de máxima verosimilitud (suponiendo un prior plano) sería $d=42$ . Nuestra estimación anterior, basada en el cálculo del valor esperado del número de estudiantes implicados en colisiones, arroja, con $x=2$ y $n=10$ :

$$ d=\frac1{1-\sqrt[9]{1-2/10}}\approx40.8\;, $$

en buena concordancia (lo cual sospecho que es una ligera coincidencia).

Otra forma de utilizar la probabilidad sería calcular la expectativa de $d$ . Sin embargo, esto no existe en el caso actual de una sola colisión, ya que en este caso la probabilidad sólo decae como $d^{-1}$ , por lo que no podemos sumar hasta el infinito. Incluso con dos colisiones (o una triple colisión), es decir $k=n-2$ aunque la probabilidad decae como $d^{-2}$ y por lo tanto es sumable, sigue sin serlo cuando lo multiplicamos por $d$ para obtener el valor esperado, por lo que de nuevo el valor esperado no existe en este caso. Como en el problema del tanque alemán, necesitamos al menos tres colisiones, es decir $k\le n-3$ para obtener una expectativa finita.

Así que vamos a ver qué pasa por $n=10$ , $k=7$ . La máxima probabilidad está en $d=12$ ( aquí hay una trama ). El valor esperado de $d$ es aproximadamente $30.4$ es decir, mucho mayor, debido a la larga cola. La estimación anterior utilizando $x$ sale diferente según las colisiones. Si tenemos $3$ parejas de estudiantes que comparten cumpleaños, eso hace que $x=6$ y la estimación es

$$ d=\frac1{1-\sqrt[9]{1-6/10}}\approx10.3\;; $$

si tenemos un par y un triplete, eso hace $x=5$ y la estimación es

$$ d=\frac1{1-\sqrt[9]{1-5/10}}\approx13.5\;; $$

y si tenemos un cuatrillizo, eso hace $x=4$ y la estimación es

$$ d=\frac1{1-\sqrt[9]{1-4/10}}\approx18.1\;, $$

todas ellas más acordes con la estimación de máxima verosimilitud que con el valor esperado de $d$ .

Como es habitual, cabe esperar que las diferencias entre los distintos enfoques sean menos pronunciadas a medida que se disponga de más datos. Veamos qué ocurre con $n=100$ , $k=90$ . Aquí hay una trama de la función de probabilidad, que ahora se parece más a una gaussiana que antes. La máxima probabilidad está en $d=461$ . El valor esperado de $d$ se trata de $569.0$ . Así que todavía hay una diferencia considerable, pero el acuerdo es considerablemente mejor. Utilizando el enfoque con el número de alumnos implicados en las colisiones, en este caso se podría obtener una estimación entre

$$ d=\frac1{1-\sqrt[99]{1-20/100}}\approx444.2 $$

para el caso en que $10$ parejas de estudiantes comparten un cumpleaños, lo que lleva a $d=20$ , a

$$ d=\frac1{1-\sqrt[99]{1-11/100}}\approx850.0 $$

para el improbable caso de que $11$ los estudiantes comparten un cumpleaños, lo que lleva a $d=11$ .

El caso más probable, con ocho pares y un triplete, y por tanto $d=19$ , produce

$$ d=\frac1{1-\sqrt[99]{1-19/100}}\approx470.3\;, $$

que se acerca bastante a la estimación de máxima verosimilitud utilizando el número de cumpleaños diferentes. Por lo tanto, es posible que desee utilizar el estimador de máxima verosimilitud, que también es algo más fácil de calcular que el valor esperado de $d$ .

En el otro caso extremo $k\ll n$ tanto la estimación de máxima verosimilitud como el valor esperado de $d$ tienden a $k$ . Por ejemplo, para $n=100$ , $k=10$ la estimación de máxima verosimilitud es $d=10$ y el valor esperado de $d$ se trata de $10.0008$ . Obsérvese que éste es un resultado mucho más significativo que la estimación $d=1$ que tenemos para $x=n$ arriba. Para $k\ll n$ casi todos los estudiantes están involucrados en colisiones, no importa cuántos días tenga el año, por lo que no se puede concluir nada sobre $d$ de $x$ en ese caso, mientras que $k$ en ese caso te da una estimación muy precisa de $d$ .

Answer 2

Deje $N$ el número total de días en un año.

Para el límite inferior, considere el caso de la $x$ extranjeros, todos tienen la misma fecha de nacimiento, así $$n-x+1\le N$$

Para un límite superior, poner el $x$ extranjeros en grupos por el mismo cumpleaños. El menor número de miembros en un grupo es de dos. Por lo tanto, hay en la mayoría de las $\frac{x}2$ distintas cumpleaños: $$N\le n-x+\frac{x}2$$

Para incluir el caso de $x$ ser un número impar, tenemos $$n-x+1\le N\le n-x+\lfloor\frac{x}2\rfloor$$

No sé si los extraterrestres son escogidos al azar. Si es así, entonces el problema es más interesante desde la perspectiva de la probabilidad.

EDITAR:

En este problema, las incógnitas son a $x_1, x_2,\cdots,N$.

Tenga en cuenta que aquí $x_k$ significa que el número de grupos de $k$ extranjeros con el mismo cumpleaños.(así que hay $x_1$ extranjeros con el único cumpleaños)

La probabilidad($p_k$) que hay $x_k$ $k$-permite($x_k$ grupos de $k$ extranjeros con la misma fecha de nacimiento) en $n$ extranjeros es $$p_k=\frac{P^N_{x_k}(N-kx_k)^{n-kx_k}}{N^n}$$

Desde el principio del valor esperado: $$np_k=x_k$$

Supongamos que el máximo de $k$$t$, es decir,$$k\le t$$. Then we have $ t+1$ unknowns. We also have $t+1$ simultaneous equations, which are, for $1\le k\le t$: $$n \frac{P^N_{x_k}(N-kx_k)^{n-kx_k}}{N^n} =x_k$$ y $$\sum^t_{k=1}kx_k=n$$

Es solucionable por mano/analíticamente? Yo no lo creo.