Consecutivos cumpleaños probabilidad

Question

Deje $n$ ser un número de personas. Al menos dos de ellos pueden ser nacido en el mismo día del año con una probabilidad de: $$1-\prod_{i=0}^{n-1} \frac{365-i}{365}$$

But what is the probability that at least two of them are born on two consecutive days of the year (considering December 31st and January 1st also consecutive)? It seems a good approximation is: $$1-\prod_{i=0}^{n-1} \frac{365-2 \times i}{365}$$

Sin embargo, la simulación de pseudo-aleatorios enteros con Python, el 99%-de los intervalos de confianza pueden ser ligeramente diferentes. Así que usted tiene cerrada la leche de fórmula?

---

Resultados de la simulación con Python. Aquí hay un 99% de confianza de los intervalos siguientes:

Number of people:  1    Lower bound: 0.0        Upper bound: 0.0
Number of people:  2    Lower bound: 0.00528    Upper bound: 0.00567
Number of people:  3    Lower bound: 0.01591    Upper bound: 0.01657
Number of people:  4    Lower bound: 0.03185    Upper bound: 0.03277
Number of people:  5    Lower bound: 0.0528     Upper bound: 0.05397
Number of people:  6    Lower bound: 0.07819    Upper bound: 0.07959
Number of people:  7    Lower bound: 0.10844    Upper bound: 0.11006
Number of people:  8    Lower bound: 0.14183    Upper bound: 0.14364
Number of people:  9    Lower bound: 0.17887    Upper bound: 0.18086
Number of people: 10    Lower bound: 0.21816    Upper bound: 0.2203
Number of people: 11    Lower bound: 0.25956    Upper bound: 0.26183
Number of people: 12    Lower bound: 0.30306    Upper bound: 0.30544
Number of people: 13    Lower bound: 0.34678    Upper bound: 0.34925
Number of people: 14    Lower bound: 0.39144    Upper bound: 0.39397
Number of people: 15    Lower bound: 0.43633    Upper bound: 0.4389
Number of people: 16    Lower bound: 0.48072    Upper bound: 0.48331
Number of people: 17    Lower bound: 0.52476    Upper bound: 0.52734

---

Doy aquí algunos de los resultados con un ajustado aproximación de la fórmula, el uso de Wolfram Alpha: $$\left( 1 - \frac{n-1}{2 \times 365 + n-1} \right) \times \left( 1-\prod_{i=0}^{n-1} \frac{365-2 \times i}{365} \right)$$

However, this is just a tweak, ans is clearly wrong for $n=33$ desde:

Number of people: 33    My guess: 0.91407
Number of people: 33    Lower bound: 0.94328    Upper bound: 0.94447

---

Gracias a Jacopo Notarstefano, leonbloy, y Morón, aquí está la (correcta) fórmula: $$ 1-\sum_{k=1}^{n}\frac{1}{365^{n-k}k}\left(\prod_{i=1}^{k-1}\frac{365-\left(k+i\right)}{365\times i}\right)\sum_{j=0}^{k-1}\left(-1\right)^{j}C_{k}^{j}\left(k-j\right)^{n} $$

Y aquí están los resultados de los cálculos utilizando esta fórmula con la de Python:

Number of people:  1    Probability: 0.0
Number of people:  2    Probability: 0.005479452
Number of people:  3    Probability: 0.016348283
Number of people:  4    Probability: 0.032428609
Number of people:  5    Probability: 0.053459591
Number of people:  6    Probability: 0.079104502
Number of people:  7    Probability: 0.108959718
Number of people:  8    Probability: 0.14256532
Number of people:  9    Probability: 0.179416899
Number of people: 10    Probability: 0.218978144
Number of people: 11    Probability: 0.260693782
Number of people: 12    Probability: 0.304002428
Number of people: 13    Probability: 0.34834893
Number of people: 14    Probability: 0.393195856
Number of people: 15    Probability: 0.438033789
Number of people: 16    Probability: 0.482390182
Number of people: 17    Probability: 0.525836596
Number of people: 18    Probability: 0.567994209
Number of people: 19    Probability: 0.608537602
Number of people: 20    Probability: 0.647196551
Number of people: 21    Probability: 0.683756966
Number of people: 22    Probability: 0.718059191
Number of people: 23    Probability: 0.749995532
Number of people: 24    Probability: 0.779509664
Number of people: 25    Probability: 0.806569056
Number of people: 26    Probability: 0.831211564
Number of people: 27    Probability: 0.853561895
Number of people: 28    Probability: 0.873571839
Number of people: 29    Probability: 0.892014392
Number of people: 30    Probability: 0.906106867
Number of people: 31    Probability: 0.919063161
Number of people: 32    Probability: 0.928791992
Number of people: 33    Probability: 0.944659069

Answer 1

Creo que podemos dar una fórmula, pero yo no lo llamaría "forma cerrada".

Tenemos $\displaystyle n$ de la gente, y $\displaystyle k$ cumpleaños posibles a elegir (es decir, $\displaystyle k$ días en un año). Deje $\displaystyle M$ es el mínimo de los dos.

Vamos a tratar de contar el número de cumpleaños de asignaciones en las que no hay dos personas que han consecutivos cumpleaños.

Para ello, vamos a tratar de contar las asignaciones que usar exactamente $d$ distintas cumpleaños, para $\displaystyle d=1, 2 \dots, k$, y luego sumarlos.

Ahora supongamos que tenemos un conjunto de $\displaystyle d$ distintas cumpleaños (no te preocupes por los consecutivos parte, todavía). De cuántas maneras podemos asignar estos $\displaystyle d$ cumpleaños a $\displaystyle n$ de la gente, de modo que cada cumpleaños es usado al menos una vez?

Esto es, básicamente, el problema de hallar el número de maneras de partición de un conjunto de tamaño $\displaystyle n$ exactamente $\displaystyle d$ no vacía partes y asignar el $\displaystyle d$ cumpleaños a cada parte en la partición, exactamente uno para cada uno.

El número de formas de partición de un conjunto de tamaño $\displaystyle n$ a $\displaystyle d$ no vacía partes está dada por un Número de Stirling de Segundo Tipo, $S(n,d)$. El número de maneras de asignar $\displaystyle d$ cumpleaños es $\displaystyle d!$.

Por lo tanto el número que estamos buscando es $\displaystyle S(n,d) \times d!$.

Ahora supongamos que hemos conseguido para contar el número de subconjuntos que contienen $\displaystyle d$ elementos (de la $\displaystyle k$ cumpleaños) de tal manera que no hay dos elementos del conjunto son consecutivos, entonces podríamos multiplicar ese número por $\displaystyle S(n,d) \times d!$ a dar el número de cumpleaños tareas que usar exactamente $\displaystyle d$ cumpleaños tales que no haya dos consecutivos.

Por el momento, ignorar el hecho de que el 1 de enero y el 31 de diciembre son consecutivos.

Necesitamos seleccionar $\displaystyle d$ números de $\displaystyle 1,2, \dots, k$ de manera tal que no hay dos consecutivos.

Ahora si $\displaystyle b_1 \lt b_2 \lt \dots \lt b_d$ eran tales números, a continuación, observe que

$\displaystyle 1 \le b_1 \lt b_2 - 1 \lt b_3 - 2 \dots \lt b_d - (d-1) \le k-(d-1)$ nos da una manera de seleccionar los números de $\displaystyle 1, 2, \dots, k-(d-1)$ sin tener que preocuparse de los consecutivos problema.

Esto se puede hacer en $\displaystyle {k-d+1 \choose d}$ maneras.

Ahora, desde el 1 de enero y el 31 de diciembre son consecutivos, tenemos que restar de esto, el número de conjuntos que contienen tanto $\displaystyle 1$$\displaystyle k$.

Este número es igual al número de $\displaystyle d-2$ no consecutivos subconjuntos de a$\displaystyle \{3, \dots, k-2\}$$\displaystyle {k-d-1 \choose d-2}$.

Por tanto, el número de maneras de seleccionar los $\displaystyle d$ no consecutivos cumpleaños (asumiendo $\displaystyle 1$ $\displaystyle k$ son consecutivos) es $\displaystyle {k-d+1 \choose d} - {k-d-1 \choose d-2}$, con el entendimiento de que el término que se resta es $\displaystyle 0$ $\displaystyle d = 1$ y $\displaystyle {a \choose b} = 0$ si $\displaystyle a \lt b$

Así, por $\displaystyle M = \text{min}\{n,k\}$, el número total que estamos buscando es,

$$ \sum_{d=1}^{M} S(n,d)\times d! \times \left({k-d+1 \choose d} - {k-d-1 \choose d-2}\right)$$

Tenga en cuenta que $\displaystyle S(n,d) \ d! = \sum_{j=0}^{d} (-1)^j {d \choose j} (d-j)^n$

Así también se podrían escribir la fórmula como

$$ \sum_{d=1}^{M} \left(\sum_{j=0}^{d} (-1)^j {d \choose j} (d-j)^n\right) \left({k-d+1 \choose d} - {k-d-1 \choose d-2}\right)$$

que es un poco feo.

Por lo tanto la probabilidad que se busca es la

$$1 - \frac{ \sum_{d=1}^{M} S(n,d)\times d! \times \left({k-d+1 \choose d} - {k-d-1 \choose d-2}\right)}{k^n}$$

Answer 2

PD: he trabajado antes en este tipo de problema y con la solución siguiente. La primera respuesta que se publicó, me hizo pensar que tengo algo mal, y dejé de lado mi trabajo. Desde la nueva respuesta por Morón de acuerdo (esencialmente) con mi trabajo anterior, aquí está, un poco diferente de la derivación de la misma fórmula.

Deje $k$ el número de días en un año. Deje $m$ ser el número distinto de cumpleaños entre el $n$ amigos. Supongamos que $k$ es lo suficientemente grande como para tener un no-problema trivial (es decir, $k > n/2$)

Estamos interesados en cadenas binarias con estas tres condiciones:

1. Son de longitud $k$, $m$ queridos y $k-m$ ceros.
2. Hay por lo menos un cero entre los dos.
3. Condición 2 mantiene cuando "envolver" la cadena.

Vamos a contar que su construcción con el siguiente algoritmo:

• Comenzar con una cadena de $m$: $11\dots 1$
• Ahora hay tres distintos casos: hay un cumpleaños en el primer día del año, hay un cumpleaños en el último día del año, hay un cumpleaños en ninguno de los dos.
• En el primer caso tenemos a distribuir $k-m$ ceros en $m$ no vacía los cubos. Son las llamadas composiciones, y uno puede demostrar que no se $\binom{k-m-1}{m-1}$ tales asignaciones.
• El segundo caso es análogo, dando otro $\binom{k-m-1}{m-1}$ cadenas posibles.
• El tercer caso es similar, dando lugar a $\binom{k-m-1}{m}$ cadenas.

Poner esto juntos tenemos: $$2\cdot \binom{k-m-1}{m-1}+\binom{k-m-1}{m}$$

Desde $n$ amigos comparten $m$ cumpleaños tenemos que dar cuenta de que, dando a esta expresión:

$$p(n,k) =\frac{\sum_{m=1}^n{ m! \cdot S(n,m)\cdot \Bigg (2\cdot \binom{k-m-1}{m-1}+\binom{k-m-1}{m}}\Bigg )}{k^n}$$

donde $S(n,m)$ es el número de Stirling del segundo tipo.

@Morón: ¿por Qué tenemos que multiplicar por $m!$ aquí? Ah, claro! Los números de Stirling del segundo tipo, cuente el número de coaliciones, sino que nos preocupamos por su orden, también!

Answer 3

ACTUALIZACIÓN - ESTO ESTÁ MAL, VEA A CONTINUACIÓN LA RESPUESTA CORRECTA --- Vamos a llamar a N1 el número de configuraciones que tienen al menos un día entre cumpleaños (esto excluye no sólo consecutivos de cumpleaños, sino también la coincidencia de cumpleaños).

Puedo obtener (contando débil composiciones) :

$ \displaystyle N_1 = 365 \frac{(365-n-1)!}{(365-2n)!}$

Si desea incluir la coincidencia de fechas de cumpleaños, tenemos

$\displaystyle N_0 = \frac{365!}{(365-n)!}$

Así que la probabilidad de pedido es

$\displaystyle P = \frac{N_0 - N_1}{365^n}$

Actualización: no puede ser es que algunos de error aquí, creo que me estoy fallando a tomar en cuenta las configuraciones que tienen ambos coincidentes y consecutivas de cumpleaños, voy a revisar esta noche. Sospecho que N1 es correcto, y que permite calcular la probabilidad de tener consecutivos O coincidente cumpleaños. Contar consecutivos (exclusivamente) cumpleaños parece más difícil.

---

ACTUALIZACIÓN: Aquí es el correcto (espero) con la respuesta.

La probabilidad de tener al menos un par de consecutivos de cumpleaños para M (=365 días) y n personas es

$\displaystyle P(M,n) = 1 - \sum_{k=1}^n P(M,k) {M \elegir k} \frac{S(n,k) k! }{M^n} = 1 - \frac{1}{M^{n-1}} \sum_{k=1}^n \frac{(M-k-1)!}{(M-2k)!} S(n,k) $

donde $ \displaystyle P(M,k) = \frac{{M -k - 1 \elegir k -1} }{{M -1 \elegir k -1} } $

and $S(n,k)$ are the Stirling numbers of the second kind

Some computed values follow

M=365 n=1 p=0.00000000
M=365 n=2 p=0.00547835
M=365 n=3 p=0.01634745
M=365 n=4 p=0.03242761
M=365 n=5 p=0.05345896
M=365 n=6 p=0.07910314
M=365 n=7 p=0.10895871
M=365 n=8 p=0.14256439
M=365 n=9 p=0.17941667
M=365 n=10 p=0.21897764
M=365 n=11 p=0.26069278
M=365 n=12 p=0.30400167
M=365 n=13 p=0.34834843
M=365 n=14 p=0.39319571
M=365 n=15 p=0.43803357
M=365 n=16 p=0.48239009
M=365 n=17 p=0.52583640

M=365 n=30 p=0.90729104

M=365 n=42 p=0.99074145 

Explanation follows: \begin{gather} 1+5+9 \\ 1+6+8 \\ 2+4+9 \\ 2+5+8 \\ 2+6+7 \\ 3+5+7 \\ 3+4+8 \\ 4+5+6 \end--------------------------

Let $M$ (=365) number of days, and $n$ = number of persons and $k$ = number of distinct birthdays ($k$ is not fixed, it's a random variable in the range $1..n$). Let $P_{M,n}(S)$ be the probability of NOT having consecutive birthdays (S is the event: "all birthdays are separated")

Then $P_{M,n}(S) = \sum_k P_{M,n}(S \; k) = \sum_k P_{M,n}( S | k ) P_{M,n}(k )$

The following steps compute the two factors inside the summation:

STEP 1:

$P_{M,n}( S | k )$ is the probability of having the events separated, given that the number of distinct birthdays is $k$. If we think of birthdays as occupied boxes in a circular list, a little reflection shows that all configurations are equiprobable ($n$ does not matter now) and we can assume without altering the result that the first box of the list is occupied. Now, the total number of possible ocurrences are the number of selection of $k-1$ boxes among $M-1$ (combination).

And the number of "succesfull" arrangements are those that result in non-consecutive occupied boxes. But this is equivalent of specifying a list of $k$ numbers greater than 1 that sum up to M; and this is the same as specifying a list of $k$ numbers greater than 0 than sum up to $M-k$; and this can be counted, by a reasoning similar to this one, as the combination of $k -1$ taken from $M -k - 1$. So,

$\displaystyle P_{M,n}( S | k ) = \frac{{M -k - 1 \elegir k -1} }{{M -1 \elegir k -1} } = P(M,k)$

STEP2:

$P_{M,n}(k)$ : if we place $n$ balls at random in $M$ boxes, what is the probability that exactly $k$ boxes will be non-empty?

The total counting is given by $M^n$. To count the "successful" cases, we multiply:

• all the possible sets of occupied boxes (combinations of $k$ taken from $M$)

• el número total de maneras de poner $n$ bolas en $k$ cajas sin dejar ninguna casilla vacía: que es dada por los números de Stirling del segundo tipo.

• y tenemos que multiplicar por $k!$ (permutaciones de las cajas) porque los números de Stirling considerar nondistinct cajas.

  $\displaystyle P_{M,n}(k ) = {M \choose k} \frac{S(n,k) k! }{M^n}$

Y a partir de ahí sigue la fórmula de arriba.