Es probable que una forma cerrada solución para este problema, pero se me había desconcertado por días. Esto se trata de una variante de la clásica paradoja de cumpleaños. En resumen, la paradoja de cumpleaños es donde se da sólo 23 de los estudiantes de la probabilidad de que las dos tengan el mismo cumpleaños es > 0.5.
La variante es esta: Si cada estudiante tiene dos (o K) días especiales, ¿cuál es la probabilidad de que dado N los estudiantes cada estudiante tiene por lo menos un día especial que es única para ellos.
Me topé con este problema, mientras que trabajando en un algoritmo criptográfico.
Otra forma de expresar esto en términos de una lotería: Si un sorteo de la lotería consta de 5 números al azar (con repetición) elaborado a partir de un conjunto de 100 números, después de N dibujos ¿cuál es la probabilidad de que cada dibujo tenido al menos un número único entre 5.
Explícitamente, dado que estas variables:
$C = $ el tamaño del conjunto de opciones (por ejemplo, 100 para la lotería o 365 para los días especiales)
$K = $ # de elecciones aleatorias para cada evento (por ejemplo, 5 de la lotería, 2 para los días especiales)
$N = $ # de eventos que han tenido lugar (por ejemplo, los sorteos de lotería, o el número de estudiantes)
Aquí es lo que estoy tratando de resolver para:
$P(C, K, N) = $ la probabilidad de que después de N eventos, donde cada uno de los sorteos de K elementos aleatorios a partir de un conjunto de C elementos, cada evento tiene al menos un elemento que no fue elegido en cualquier otro caso.
Tenga en cuenta que $P(C, 1, N)$ proporciona la solución a la clásica paradoja de cumpleaños.
Para ser claros, la repetición es permitido. Es decir, un estudiante podría tener en el mismo día dos veces, o el sorteo de la lotería podría ser (5, 5, 78, 10, 5). En ese caso, si al menos uno de esos números nunca antes vistos, que cuenta como único.
El mejor que he encontrado es este:
Dada una función, $Q(C, K, N)$ que calcula la probabilidad de que el $N^{th}$ evento tiene al menos un valor único:
Se obtendrían los siguientes valores en el estudiante escenario:
$$ Q(2, 365, 0) = 1 - \frac{0}{365}\frac{0}{365} = 1.00000 $$ $$ Q(2, 365, 1) = 1 - \frac{2}{365}\frac{2}{365} = 0.99996 $$ $$ Q(2, 365, 2) = 1 - \frac{4}{365}\frac{4}{365} = 0.99987 $$
Y lo mismo para el sorteo de la lotería:
$$ Q(5, 100, 0) = 1 - \frac{0}{100}\frac{0}{100} = 1.00000 $$ $$ Q(5, 100, 1) = 1 - \frac{5}{100}\frac{5}{100} = 0.99999 $$ $$ Q(5, 100, 2) = 1 - \frac{10}{100}\frac{10}{100} = 0.99999 $$
Esto se generaliza a:
$$ Q(C, K, N) = 1 - (\frac{N * K}{C})^K $$
Si $Q$ calcula la probabilidad de que cualquier alumno / a con al menos un día único que la probabilidad de que N todos los eventos que tengan al menos un día único es simplemente multiplicar todas las probabilidades juntos:
$$P(C, K, N) = \prod_{n=0}^N 1 - (\frac{n * K}{C})^{K}$$
Esto se ve prometedor, porque para el caso en que $K = 1$, esto se simplifica a:
$$\prod_{n=0}^N \frac{C - n}{C}$$
cual es la fórmula para el tradicional paradoja de cumpleaños.
El problema es que esta fórmula propuesta, más allá de $K=1$, no es realmente correcto, comprobado mediante una simulación monte-carlo he estado corriendo para compararla.
Me parece que no puede envolver mi cabeza alrededor de lo que el problema es, sin embargo. He probado con una docena de maneras diferentes de abordar el problema. Parece que no puede haber solución de forma cerrada, por desgracia.
