Supongamos que tengo un conjunto $P$ con $||P|| = N$ elementos únicos. También tengo $S$ multisets, $(m_1, ..., m_S)$ de cardinalidad $L$ que se compone de elementos en $P$ elegido con probabilidad uniforme. Llamamos a un conjunto múltiple, $m_i$ , "distinguible" si contiene al menos $k$ elementos, aunque no necesariamente distintos, que no existen en ningún otro multiconjunto.
¿Cuál es la probabilidad de que todos los $M$ ¿los conjuntos múltiples son "distinguibles" según esta definición?
Editar - ¡Me interesaría mucho conocer las soluciones aproximadas a esta cuestión! Al igual que en mi "pregunta sobre la relación limitada de dos tipos de bolas", aquí $N$ es al menos un orden de magnitud mayor que $S$ , $S > 10^3$ y $L$ es relativamente pequeño (alrededor de $10^1$ a $10^2$ más o menos).
Mientras que el muestreo $S$ veces con la sustitución del conjunto $P$ podemos afirmar que la probabilidad de no elegir nunca el mismo elemento dos veces es
Prob( $S$ selecciones únicas de $P$ ) = $\prod \frac{(N - i)}{N}$ para $i = 0$ a $(S - 1)$
O, de forma equivalente, podemos calcular la probabilidad de que el subconjunto de $S$ elementos muestreados contiene todos los elementos únicos como:
Prob( $S$ selecciones únicas de $P$ ) = $\prod ((1-(\frac{1}{N - i}))^{(S - 1 - i)})$ para $i = 0$ a $(S - 1)$
Quizás podamos simplificar este problema restringiendo $k$ para incluir sólo elementos distintos, es decir, elementos que existen sólo una vez en todos los $(m_1, ..., m_S)$ ¿conjuntos múltiples?
Esto es lo que estoy pensando...
Primero calculamos la probabilidad de que uno de los $(S*L)$ elementos en conjuntos múltiples $(m_1, ..., m_S)$ , seleccionada entre $P$ por muestreo con reemplazo, se selecciona sólo una vez. Esto debería ser equivalente a lanzar $(S*L)$ bolas en $||P|| = N$ y hallar la probabilidad de que una bola determinada se encuentre por sí misma en un recipiente.
De la página 95 de "Probabilidad y computación": Randomized algorithms and probabilistic analysis" de Michael Mitzenmacher y Eli Upfal, cuando lanzamos $(S*L)$ bolas en $N$ la probabilidad de que un recipiente específico tenga exactamente $r$ bolas, P[ $r$ ], se da como:
P[ $r$ ] = ${S*L \choose r}$ $(\frac{1}{N})^r(1-\frac{1}{N})^{(S*L-r)}$
Por linealidad de la expectativa, ahora podemos escribir una expresión para el número esperado de bolas que existen en un recipiente de $r$ bolas como: E[X] = $N*r*{S*L \choose r}$ $(\frac{1}{N})^r(1-\frac{1}{N})^{(S*L-r)}$ . Como las bolas corresponden aquí a los elementos en la primera descripción del problema, esto implica que podemos escribir P[el elemento es único] como:
P[el elemento es único] = $\frac{N*(1)*{S*L \choose 1}(\frac{1}{N})^1(1-\frac{1}{N})^{(S*L-1)}}{S*L}$
Volviendo al problema original, tenemos $S$ multisets que llenamos con $L$ elementos, y queremos calcular la probabilidad de que al menos $k$ de los elementos de cada multiconjunto son únicos (es decir, en todos los multiconjuntos no aparecen en ninguna otra parte). Como ahora conocemos la probabilidad de que un elemento concreto sea único, podemos utilizar la fórmula binomial para hallar la probabilidad de que un subconjunto concreto contenga al menos $k$ elementos únicos:
P[al menos 'k' elementos en un determinado multiconjunto, $m_i$ son únicos] = 1 - $\sum^{k-1}_{i=0}[ {L \choose i}$ * P[elemento es único] $^i$ * (1 - P[elemento es único]) $^{L-i}$ ]
Por la linealidad de la expectativa: $S$ * P[al menos 'k' elementos en un determinado multiconjunto, $m_i$ son únicos] ~ # de conjuntos múltiples con al menos $k$ elementos únicos.
Para calcular la probabilidad de que todos los conjuntos múltiples contengan al menos $k$ elementos únicos, deberíamos poder escribir la probabilidad como P[al menos 'k' elementos en un multiset particular, $m_i$ son únicos] $^S$
Estos cálculos parecen acercarse a los datos simulados, pero siguen estando fuera y me imagino que esto será un accidente. Agradecería cualquier ayuda para encontrar lo que probablemente son fallos obvios. ¿Hay problemas de independencia, etc.?
