No es agradable la fórmula, pero hay un buen algoritmo. La multiplicación de polinomio funciones de generación de espejos de la secuencial del proceso de dibujo. Como tal, la informática, con la generación de funciones esencialmente realiza una enumeración exhaustiva de las posibilidades. Sin embargo, las propiedades algebraicas pueden ser explotadas para simplificar los resultados intermedios (productos parciales), que conduce a una simplificado considerablemente el cálculo. Estas propiedades algebraicas (formalmente: un ideal de polinomios) codificar los dos hechos que (a) no estamos preocupados con cuántos de cada bola es dibujado, sólo que las bolas se dibujan; y (b) basta para centrarse en los casos en que no se de que todas las pelotas son dibujados.
Esta respuesta muestra cómo estas ideas puede ser utilizado de manera eficiente para calcular una respuesta a la pregunta, así como a sus evidentes generalizaciones a más bolas y diferentes números de los sorteos. Es seguido por el análisis, incluyendo una simulación, lo que demuestra la exactitud de la respuesta. Una última sección discute más temas que pueden ser de interés, tales como la aplicación de este enfoque a la más simple (no ponderado) de los casos.
Para dibujar $k$ bolas (con la ponderación de las probabilidades) de una urna con $n$ bolas que dibujar la primera (pero no reemplazar), luego la segunda (sin reemplazo), y así sucesivamente. Después de haber observado el resultado, se reemplazan todas las pelotas. Por lo tanto la oportunidad de ver una secuencia de bolas con probabilidades de $p_1, p_2, \ldots, p_k$ es igual a
$$\Pr(p_1, p_2, \ldots, p_k) = p_1\frac{p_2}{1-p_1}\cdots\frac{p_k}{1-(p_1+p_2+\cdots+p_{k-1})}$$
and the chance of seeing a combination (unordered sequence) of balls with those probabilities is the sum over all permutations,
$$\Pr(\{p_1, p_2, \ldots, p_k\}) = \sum_{\sigma\in\mathcal{S}_k} \Pr(p_{\sigma(1)}, p_{\sigma(2)}, \ldots, p_{\sigma(k)}).$$
A simple and elegant way to handle these $\binom{n}{k}$ numbers is with a generating polynomial,
$$m_k(x_1, x_2, \ldots, x_n) = \sum_{i_1\lt i_2\lt \cdots \lt i_k}\Pr(\{p_{i_1}, p_{i_2}, \ldots, p_{i_k}\})x_{i_1}x_{i_2}\cdots x_{i_k}.$$
For instance, with probabilities $(4/10, 3/10, 1/10, 1/10, 1/10),$ we may compute
$$m_1(x_1, x_2, x_3, x_4, x_5) = \frac{4 x_1}{10}+\frac{3 x_2}{10}+\frac{x_3}{10}+\frac{x_4}{10}+\frac{x_5}{10},$$
$$m_2(x_1, x_2, x_3, x_4, x_5) = \frac{13 x_1 x_2}{35}+\frac{8 x_3 x_2}{105}+\frac{8 x_4 x_2}{105}+\cdots+\frac{x_3 x_5}{45}+\frac{x_4 x_5}{45},$$
and
$$m_3(x_1, x_2, x_3, x_4, x_5) =\frac{76}{315} x_1 x_2 x_3+\frac{76}{315} x_1 x_2 x_4\cdots+\frac{17}{504} x_2 x_4 x_5+\frac{1}{120} x_3 x_4 x_5.$$
Writing $x = (x_1, x_2, \ldots, x_n),$ the generating polynomial for the total outcome of a sequence of independent draws of sizes $k_1, k_2, \ldots, k_d$ is simply the product $m_{k_1}(x)m_{k_2}(x)\cdots m_{k_d}(x).$ Moreover, all we are interested in is whether all the $x_i$ appear in the outcome, not how many times each does. This allows the computation of the product to be simplified: at each multiplication we may throw away any monomial term that is a multiple of $x_1x_2\cdots x_n$ and replace any power of any $x_i$ by $x_i$ itself (which can be done by equating each $x_i^2$ with $x_i$ itself). The result will encode the chances of not obtaining all $n$ balls among these $d$ draws: the coefficient of each monomial $x_{i_1}x_{i_2}\cdots x_{i_s}$ will be the chance of obtaining exactly the balls $\{i_1, i_2, \ldots, i_s\}$. Setting all the $x_i=1$ te dan la posibilidad de que no todas las pelotas son dibujados.
Los cálculos son más fáciles de realizar con un sistema de álgebra computacional. En Mathematica una solución se parece a esto:
Calcular los coeficientes de la generación de los polinomios de forma recursiva:
prob[{j_, k___}, p_List, x_] := Block[{n = Total@p, q = p},
q[[j]] = 0;
prob[{k}, q, x] p[[j]] Subscript[x, j] / n] ;
prob[{}, _, _] := 1
Suma sobre todas las permutaciones para obtener la generación de polinomios:
m[k_Integer, p_, x_] := m[k, p, x] =
Sum[prob[y, p, x], {y, Permutations[Range[Length[p]], {k}]}]
Especificar el ideal generado por a $x_1x_2\cdots x_n$ e las $x_i^2-x_i$:
ideal[p_, x_] :=
With[{n = Length[p]}, {Product[Subscript[x, i], {i, 1, n}],
Subscript[x, #]^2 - Subscript[x, #] & /@ Range[n]} // Flatten]
Multiplicar la generación de polinomios, la reducción de modulo el ideal en cada paso:
Block[{weights = {4, 3, 1, 1, 1}, draws = {3, 3, 2}, x, i, gf},
i = ideal[weights, x];
gf = Fold[PolynomialMod[#1 m[#2, weights, x], i] &, 1, draws];
Conjunto de todos los $x_i$$1$:
gf /. (Subscript[x, #] -> 1 & /@ Range[Length[weights]])]
La respuesta $0.02$ segundos para calcular y es igual a $\frac{74344589}{111132000}$. Esto significa la posibilidad de obtener todos los cinco bolas es $1 -\frac{74344589}{111132000} = \frac{36787411}{111132000} \approx 0.33102447.$
Discusión
Simulación
Siempre que sea posible, es una buena idea comprobar complicado o difícil cálculos de probabilidad con una simulación. Aquí hay una rápida simulación (para un peso arbitrario y arbitraria de números de sorteos) en R, tal como se aplica al problema original:
weights <- c(4,3,1,1,1)
draws <- c(3,3,2)
n.iter <- 10^4
set.seed(17)
p <- mean(replicate(n.iter, {
length(table(unlist(sapply(draws,
function(d) sample.int(5, d, prob=weights))))) >= length(weights)
}))
cat("Estimate =", p,
"( Z =", (p - 36787411/111132000) / sqrt(p*(1-p)/n.iter), ")")
Estimación = 0.335 ( Z = 0.8422911 )
La salida de los informes de la proporción de iteraciones en el que todas las bolas se observaron, seguido por un Z-estadístico en relación a la anteriormente calculada respuesta. Porque el Z-estadístico es pequeña, esto es evidencia de que la calculada respuesta es correcta (hasta un par de veces el error estándar, que en este ejemplo es $0.005$).
Aplicación a problemas más simples
Uno de los casos en los que no hay una fórmula (de clases) es cuando no hay pesos. El Mathematica código, se aplica a un vector de pesos de {1,1,1,1,1}, salidas de $\frac{9}{20}$, produciendo una respuesta de $1 - \frac{9}{20} = \frac{11}{20} = 0.55.$ Es correcto?
La simetría de este problema, de que todas las pelotas tienen iguales probabilidades--hace independiente del cálculo de la respuesta factible. Después de dibujar las tres primeras bolas, el nombre de ellos $x_1, x_2,$$x_3$, y dejar que el resto de las bolas de ser$x_4$$x_5$. Reemplace todas las bolas y sacar otra de tres. Hay dos eventos relevantes a la pista: si $3$ o $4$ bolas han sido observados. La posibilidad de $3$ es la probabilidad de que el mismo $3$ bolas fueron dibujados en un segundo momento; esto es $1 / \binom{5}{3} = 1/10.$ La oportunidad de observar a $4$ distintas de las bolas es que dos de las nuevas pelotas eran de $\{x_1, x_2, x_3\}$ y el tercero de $\{x_4, x_5\}$: esto es igual a $\frac{\binom{3}{2}\binom{2}{1}}{\binom{5}{3}} = \frac{3\times 2}{10} = \frac{6}{10}.$
En cada uno de estos casos podemos calcular la probabilidad de que el sorteo final de la $2$ bolas no va a completar el conjunto de cinco. Si sólo $3$ bolas se han observado, que la oportunidad es $9/10$. Si $4$ bolas se han observado, la oportunidad es $\frac{\binom{4}{2}}{\binom{5}{2}} = \frac{6}{10}.$ Donde la probabilidad de no completar el conjunto es
$$\frac{1}{10} \frac{9}{10} + \frac{6}{10}\frac{6}{10} = \frac{9+36}{100} = \frac{45}{100} = \frac{9}{20},$$
exactly as reported by the Mathematica code.
Closer examination of the polynomials
How the code works is easy to see in this case, because the polynomials $m_k$ are multiples of the elementary symmetric functions:
$$10 m_2(x) = x_1 x_2+x_3 x_2+x_4 x_2+x_5 x_2+x_1 x_3+x_1 x_4+x_3 x_4+x_1 x_5+x_3 x_5+x_4 x_5$$
$$10 m_3(x) = x_1 x_2 x_3+x_1 x_4 x_3+x_2 x_4 x_3+\cdots+x_1 x_2 x_5+x_1 x_4 x_5+x_2 x_4 x_5.$$
These are constructed by taking a single product, such as $x_1x_2$, and adding to it all monomials attainable by permuting their subscripts (among the set $\{1,2,3,4,5\}$). In effect, each monomial has only one kind of term plus its permuted versions.
Let's compute their products modulo the ideal $\mathcal{I}$ generated by $\{x_1x_2x_3x_4x_5, x_1^2-x_1, x_2^2-x_2, x_3^2-x_3, x_4^2-x_4, x_5^2-x_5\}.$ To do so we only have to look at a limited number of products and then apply all permutations. For instance, in computing $(10 m_3(x))^2$ we find one term like $(x_1x_2x_3)^2 \equiv x_1x_2x_3$ mod $\mathcal{I}$--together with all its permutations--and terms that are congruent to $x_1x_2x_3x_4$ mod $\mathcal{I}$--together with all their permutations. It's straightforward to count that there are $12$ each of the latter, whence
$$(10 m_3(x))^2 \equiv\sum_{\sigma\in \mathcal{S}_5}\left(x_{\sigma(1)}x_{\sigma(2)}x_{\sigma(3)} + 12x_{\sigma(1)}x_{\sigma(2)}x_{\sigma(3)}x_{\sigma(4)}\right)\quad\text{mod }\mathcal{I}.$$
Multiplication by $10m_2(x)$ modulo $\mathcal{I}$ is similarly easy. The result is
$$(10 m_3(x))^2(10 m_2(x)) \equiv \sum_{\sigma\in \mathcal{S}_5}\left(3x_{\sigma(1)}x_{\sigma(2)}x_{\sigma(3)} + 84x_{\sigma(1)}x_{\sigma(2)}x_{\sigma(3)}x_{\sigma(4)}\right)\quad\text{mod }\mathcal{I}.$$
This says there are $\binom{5}{3}\veces 3$ chances in $1000$ of observing exactly three of the balls after independent draws of $3$, $3$, and $2$ balls and $\binom{5}{4}\times 84$ chances in $1000$ of observing exactly four of the balls. Their sum is $10\veces 3 + 5\times 84 = 450$ chances out of $1000$.
El método general utilizado en la ponderación de la probabilidad caso realiza un conjunto similar de los cálculos.
Supuestos alternativos
Para la alternativa de dibujo de procedimientos (ver el hilo de comentarios de la pregunta), simplemente cambiar la definición de la prob, que describe las posibilidades del dibujo de cada secuencia de bolas. El resto del algoritmo se mantiene sin cambios.
