Una extensión del problema del cumpleaños

Question

Th cumpleaños problema (o paradoja) que se ha hecho en muchos sentidos, con alrededor de una docena de hilo sólo en las matemáticas.stackexchange. La forma en que se expresa normalmente es la siguiente:

"Tomemos $n$ de las personas de manera "independiente" (no gemelos, etc.). ¿Cuál es la probabilidad de que no hay dos personas que comparten el mismo cumpleaños?"

Es extraída de la siguiente manera:

"Vamos a $X_1$, $\cdots$, $X_n$ ser $n$ i.yo.d. variables aleatorias tomadas de manera uniforme en $[[1, 365]]$. ¿Cuál es la probabilidad de que todos los $X_i$'s son distintos?"

Hay muchas generalizaciones, por ejemplo:

"Vamos a $n$, $d$ ser de dos enteros positivos, $n \leq d$. Vamos $X_1$, $\cdots$, $X_n$ ser $n$ i.yo.d. variables aleatorias tomadas de manera uniforme en $[[1, d]]$. ¿Cuál es la probabilidad de $p(n,d)$ que todas las $X_i$'s son distintos?"

Uno puede mostrar que en el régimen de $1 \ll n \ll d$, la probabilidad de $p(n,d)$ es de forma logarítmica equivalente a algo como $e^{-\frac{n^2}{2d}}$ (Wikipedia) o $e^{-\frac{n^2}{d}}$ (mis cálculos)*. Este problema puede ser reducido a simple combinatoria, y la fórmula de Stirling (por ejemplo) da la solución.

Sin embargo, en el mundo real, los cumpleaños no se distribuyen de esa manera. Uno podría también desea estimar la probabilidad de que dos pueblos nacen el mismo medio día, a la misma hora, etc. La siguiente generalización parece natural:

"Vamos a $\mu$ ser una medida de probabilidad en $[0,1]$ absolutamente continua con respecto a la medida de Lebesgue. Vamos $n$, $d$ ser de dos enteros positivos. Para $k \in [[0,d-1]]$, vamos a $a_k := [k/d, (k+1)/d]$. Vamos $X_1$, $\cdots$, $X_n$ ser $n$ i.yo.d. variables aleatorias en $[0,1]$$\mu$. ¿Cuál es la probabilidad de $p(n,d)$ que todas las $X_i$'s de la mentira en los diferentes elementos de la partición?"

Yo esperaría que la solución sea algo como $e^{-C(\mu) \frac{n^2}{d}}$, tal vez con cierta expresión explícita de $C(\mu)$. Pero la combinatoria soluciones no funcionan tan bien en este entorno, y todo lo que puedo conseguir son muy crudo límites cuando la densidad de $\mu$ está acotada. Además, yo esperaría $C(\mu)$ a ser mínima cuando se $\mu$ es la medida de Lebesgue, pero no sé cómo demostrarlo. Uno podría preguntarse ¿qué sucede cuando $\mu$ ya no es absolutamente continua, pero esto podría ser un poco demasiado amplio de una generalización.

Estoy seguro de que este problema ha sido hecho para la muerte, pero no tengo acceso a la literatura del momento, y la búsqueda rápida de no producir nada (las generalizaciones del problema del cumpleaños que he encontrado son bastante diferentes). Ningún resultado/prueba/referencia relacionados con los problemas anteriormente sería agradable.

.* Por cierto, cualquier rigurosa prueba de cualquiera de los dos hechos (o de cualquier sonido similar resultado) es apreciado. No sé que puedo confiar más, entre mis cálculos y la Wikipedia.

Answer 1

No tengo idea de tu pregunta principal, pero sé cómo se obtuvo, para la distribución uniforme caso, una fórmula distinta de la de la Wikipedia, porque yo hice el mismo error, en el día de hoy.

Seleccione $n$ valores de un espacio de tamaño $d$, cada selección que se está uniformemente al azar. Suponemos que $n \ll d$ (pero no necesariamente que $n^2 \ll d$, que es el punto crucial). La probabilidad de que no hay colisión es:

$$ p(n,d) = \frac{d!}{d^n(d-n)!} $$

(hay $\frac{d!}{(d-n)!}$ posibles selecciones sin colisiones, de $d^n$ si permitimos que las colisiones).

Utilizando la fórmula de Stirling ($k! \approx \sqrt{2\pi k}(\frac{k}{e})^k)$, obtenemos:

$$ p(n, d) \approx d^{-n} \sqrt{\frac{d}{d-n}} \left(\frac{d}{e}\right)^d\left(\frac{d-n}{e}\right)^{n-d} $$

Desde $n \ll d$, la parte con la raíz cuadrada está muy cerca de a $1$, por lo que ignoramos. La expresión se convierte entonces en:

$$ p(n, d) \approx e^{-n} \left(1-\frac{n}{d}\right)^{n-d} = e^{-n + (n-d)\ln (1-\frac{n}{d})}$$

No vamos a reemplazar el registro con su aproximación de Taylor, y, ese es el difícil punto, usted tiene que utilizar de grado 2. Esto significa que:

\begin{eqnarray} -n + (n-d)\ln (1-\frac{n}{d}) &=& -n + (n-d)\left(-\frac{n}{d} - \frac{n^2}{2d^2} + O\left(\frac{n^3}{d^3}\right)\right) \\ &=& -\frac{n^2}{d} - \frac{n^3}{2d^2} + \frac{n^2}{2d} + O\left(\frac{n^3}{d^2}\right) \\ &=& -\frac{n^2}{2d} + O\left(\frac{n^3}{d^2}\right) \end{eqnarray}

Por lo tanto el resultado:

$$ p(n,d) \approx e^{-\frac{n^2}{2d}} $$

que es la fórmula que figura en la página de la Wikipedia sobre el cumpleaños de "paradoja". En la expresión anterior, cuando vamos a reemplazar el registro con su aproximación, el grado 1 términos cancelar, que es por qué tenemos que ir a grado 2. Parada en grado 1 que fue mi error y me imagino que el tuyo también.

Answer 2

Vamos a reformular el problema:

Hay $m$ papeleras, y $n$ elementos se colocan de forma independiente en una estantería aleatoria con probabilidad de $p_k$ de ir a bin $k\in\{1,\ldots,m\}$. ¿Cuál es la probabilidad de que no a artículos van en la misma bandeja?

Vamos a empezar con una solución aproximada que es bueno para dar cierta intuición sobre el problema y funciona bien siempre y cuando $n\ll m$.

Para cualquiera de los elementos, la probabilidad de que les va en la misma bandeja es $q=\sum_{k=1}^m p_k^2$. Por lo tanto, la probabilidad de que no van en la misma bandeja es $1-q$. Desde allí se $n(n-1)/2$ diferentes pares de elemento, si queremos hacer la aproximación de que cualquiera de los dos pares de elementos independientes (true si los pares no tienen elementos en común y casi true si los dos pares que tienen un elemento en común), encontramos que la probabilidad de que ningún par ir en la misma bandeja a ser $\approx(1-q)^{n(n-1)/2}\approx e^{qn(n-1)/2}$.

Ahora, vamos a hacer esto un poco más formalmente. Si definimos el polinomio $$F(x)=\prod_{k=1}^m (1+p_kx)=\sum_{j=0}^m \frac{f_j x^j}{j!},$$ el coeficiente de $f_n$ es la probabilidad de que ese $n$ artículos van en $n$ distintos contenedores: las sumas de todas las diferentes maneras de recoger $n$ papeleras y la probabilidad de que el $n$ elementos se colocan en estos recipientes en cualquier orden (el factor de $n!$).

Ahora podemos hacer una aproximación: $$ \begin{split} F(x) =&\prod_{k=1}^m (1+p_kx) = \exp\left\{\sum_{j=1}^m\ln(1+p_jx)\right\}\\ =&\exp\left\{\sum_{j=1}^m p_jx-\frac{p_j^2x^2}{2}+\frac{p_j^3x^3}{3}-\cdots\right\}\\ =&\exp\left\{x+\sum_{j=1}^m\left(-\frac{q_2x^2}{2}+\frac{q_3x^3}{3}-\cdots\right)\right\}\\ =&e^x\cdot e^{-q_2x^2/2}\cdot e^{q_3x^3/3}\cdot e^{-q_4x^4/4}\cdots\\ \end{split} $$ donde $q_r=\sum_{k=1}^m p_k^r$ (por lo que la anterior $q=q_2$ mientras $q_1=1$). Podemos mostrar que $q_k\le q_2^{k-1}$ (por ejemplo, de$q_r^2\ge q_{r-1}q_{r+1}$), lo que nos dice $q_2$ es la dominante de ajuste.

Si hacemos la expansión $$ \begin{split} \exp\left\{\sum_{j=1}^m\left(-\frac{q_2x^2}{2}+\frac{q_3x^3}{3}-\cdots\right)\right\} =&\sum_{k=0}^\infty\frac{1}{k!} \left(-\frac{q_2x^2}{2}+\frac{q_3x^3}{3}-\cdots\right)^k\\ =&1-a_2x^2+a_3x^3-a_4x^3+\cdots\\ \end{split} $$ tenemos $a_2=q_2/2$, $a_3=q_3/3$, $a_4=q_4/4-q_2^2/8$, etc. La introducción de estos en la expansión de la energía para $F(x)$, obtenemos $$ \begin{split} F(x)=&e^x\cdot\left(1-a_2x^2+a_3x^3-a_4x^3+\cdots\right)\\ =&\sum_{n=0}^\infty\left(\frac{1}{n!} -\frac{a_2}{(n-2)!}-\frac{a_3}{(n-3)!}-\cdots\right)\cdot x^n\\ =&\sum_{n=1}^\infty\big(1-a_2n(n-1)+a_3n(n-1)(n-2)-\cdots\big)\cdot\frac{x^n}{n!}\\ \end{split} $$ así que el efecto de $a_rx^r$ es un ajuste $a_rn(n-1)\cdots(n-r+1)$ $r\ll n$ tiene la misma magnitud como $a_rn^2$.

Si ignoramos $q_r$ $r>2$ y tome el efecto de la $a_{2r}x^{2r}$ $\approx a_{2r}[n(n-1)]^r$ (lo cual es cierto para $r=1$, pero sólo aproximado de las $r>1$, obtenemos la aproximación original: $e^{-q_2n(n-1)/2}$.