Probabilidad de duplicar la muestra libre de la muestra aleatoria discreta iid

Question

Dejemos que $\{X_1,\ldots,X_n\}$ sean variables aleatorias discretas independientes e idénticamente distribuidas. Me interesa calcular la probabilidad del evento de que la muestra esté libre de duplicados: $$ \mathbb{P}\left( \bigcap_{i<j} \{ X_i \not= X_j\}\right) $$ en términos de $p_2 = \mathbb{P}\left(X_1 = X_2\right)$ , $p_3=\mathbb{P}\left(X_1 = X_2 = X_3\right)$ , ..., $p_n = \mathbb{P}\left(X_1 = X_2 = X_3=\ldots=X_n\right)$ .

Caso especial
Si $X_k$ se distribuyen uniformemente, siendo el tamaño del espacio muestral $d$ Este es un clásico problema de cumpleaños con la respuesta: $$ \mathbb{P}\left( \bigcap_{i<j} \{ X_i \not= X_j\}\right) = \frac{n!}{d^n} \binom{d}{n} = \sum_{k=1}^n \frac{s(n,k)}{d^{n-k}} $$ donde $s(n,k)$ denota el número de Stirling del primer tipo.

Motivación
Considere Número de punto flotante IEEE con mantisa $m$ codificado como $d$ -tupla de significativo dígitos binarios (es decir, el primer bit es siempre 1), y exponente binario entero $e$ . Para un real aleatorio $0<x<1$ los bits son variables aleatorias iid Bernoulli(1/2), y $-e$ es una variable aleatoria Geométrica(1/2). Me interesa calcular la probabilidad del tamaño $n$ muestra que tiene un duplicado.

Mi enfoque
Aplicando el principio de inclusión-exclusión, la probabilidad complementaria es $$ \sum_{i<j} \mathbb{P}\left(X_i = X_j\right) - \sum_{i<j,i<p<q} \mathbb{P}\left(X_i = X_j, X_p=X_q\right)+\ldots = \\ \binom{n}{2} p_2 - 3 \binom{n}{4} p_2^2 - 2 \binom{n}{3} p_3 + \ldots $$

Soluciones, ideas y referencias son bienvenidas.

Answer 1

La referencia que resuelve el problema de los cumpleaños para una distribución arbitraria de los mismos es

Shigeru Mase, " Aproximaciones al problema del cumpleaños con probabilidades de ocurrencia desiguales y su aplicación al problema de los apellidos en Japón ," Ann. Inst. Statist. Math., vol. 44, no. 3, pp. 379-499 (1992).

Utiliza un argumento bastante ingenioso que implica funciones generadoras. En primer lugar, hay que tener en cuenta que $$ r_n := \mathbb{P}\left(\bigcap_{1\leqslant i<j \leqslant n} \{X_i \not= X_j\}\right) = n! \sum_{1 \leqslant i_1 < i_2 < \ldots < i_{n-1} < i_n \leqslant n} \pi_{i_1} \pi_{i_2} \cdots \pi_{i_{n}} = n! [t^n] \prod_{k \geqslant 1} \left(1 + \pi_k t\right) $$ donde $\pi_k = \mathbb{P}(X=k)$ . Por lo tanto, $$ 1 + \sum_{n=1}^\infty \frac{r_n}{n!} t^n = \prod_{k \geqslant 1} \left(1 + \pi_k t\right) = \exp\left( \sum_{k \geqslant 1} \log\left(1+\pi_k t\right)\right) = \exp\left( \sum_{s=1}^\infty \frac{(-1)^{s-1}}{s} t^s \sum_{k \geqslant 1} \pi_k^s\right) = \exp\left( 1 + \sum_{s=2}^\infty \frac{(-1)^{s-1}}{s} t^s p_s\right) $$ Esto da la expresión para $r_n$ como el polinomio de Bell completo : $$ r_n = B_n\left(1, -p_2, \ldots, (-1)^{n-1} (n-1)! p_n\right) \tag{1} $$ En particular, suponiendo que $r_0 =1$ el resultado anterior implica la ecuación de recurrencia para las probabilidades de no ocurrencia $r_n$ : $$ r_n = \sum_{k=1}^n (-1)^{k-1} \frac{(n-1)!}{(n-k)!} p_k r_{n-k} \tag{2} $$

Grande $n$ asintótica (con $n \cdot \max\limits_{k \geqslant 1} \pi_k$ que es pequeño) también se trabaja en el artículo: $$ r_n \approx \exp\left(-\binom{n}{2} p_2 - \binom{n}{3}\left( 3 p_2^2 - 2 p_3 \right) + \cdots \right) $$