Sacar todas las bolas de uno o varios colores de una urna que contiene bolas multicolores

Question

Digamos que tienes una urna llena de bolas. Cada bola tiene uno o más colores. Estoy intentando averiguar, dado que sacas E bolas de una urna sin reemplazo, ¿cuál es la probabilidad de que saques todas las bolas de uno o más colores? Creo que lo tengo resuelto para 2 colores, pero más allá de eso, el doble conteo se vuelve problemático, y estoy un poco perdido en cuanto a la forma adecuada de incorporarlo.

He empezado pensando en este problema con dos colores, rojo y verde, y sin bolas de colores mixtos. ¿Cuál es la probabilidad de sacar todas las bolas rojas, R, dadas E extracciones? Bien, podemos obtenerlo a partir de la función de densidad de la función hipergeométrica. Para abreviar, dh(a,b,c,d) es la probabilidad de sacar una bola de un color con b bolas de ese color en la urna, c bolas que no son de ese color, y d extracciones.

La probabilidad de sacar todas las bolas rojas es dh(R, R, G, E). La probabilidad de sacar todas las bolas verdes es dh(G,G,R,E). La probabilidad de sacar todas las rojas O las verdes (ya que no podemos hacer ambas cosas con 2 colores) es dh(R, R, G, E)+dh(G,G,R,E).

Genial. Esto nos lleva a una expresión general fácil para las bolas de un solo color. Sumemos todos los colores, siendo i el número de bolas de color i. T es el número total de bolas.

p(eliminando todos los de 1 o más) = sum(dh(i, i, T-i, E))

Ahora digamos que hay M bolas mezcladas, tanto rojas como verdes. Volvamos a la probabilidad de sacar todas las bolas con rojo.

Aquí tenemos dh(R+M, R+M, G, E). Y podemos dar la vuelta a los Rs y Gs para obtener la misma expresión para G.

¿Podemos sumar estas dos para obtener la respuesta a la probabilidad de sacar todas las bolas con rojo o verde? ¿Tenemos que preocuparnos por la doble contabilidad? Normalmente no en el caso de dos colores solamente. Sólo se pueden sacar todas las bolas rojas o todas las verdes, a menos que se saquen todas las bolas. En ese caso, el doble conteo se convierte en un problema.

¿Cómo puedo derivar un término general que corrija la doble contabilidad con un número C de colores, mezclas que tengan cualquier número de colores en ellas a partir de 2...C, y sorteos E? Supongo que el caso de 1 color por bola es un caso especial. No veo el término de corrección. ¿Qué opinas? Sólo punteros en la dirección correcta sería apreciado.

Answer 1

Suponga que tiene $B$ bolas en $C$ colores, con $b_j$ bolas de color $j$ y dibujar $E$ bolas. Para cualquier subconjunto $S$ de $\{1,2,\ldots, C\}$ , dejemos que $b_S = \sum_{j \in S} b_j$ . La probabilidad $P(S)$ que se obtienen todas las bolas de todos los colores en $S$ es $0$ si $E < b_S$ y ${{B-b_S} \choose {E-b_S}}/{B \choose E}$ si $E \ge b_S$ . Por el principio de inclusión-exclusión, la probabilidad de obtener todas las bolas de al menos un color es $ \sum_S (-1)^{|S|-1} P(S)$ donde la suma es sobre todos los subconjuntos no vacíos $S$ de $\{1,2,\ldots, C\}$ con $b_S \le E$ .

Answer 2

Gracias por las pistas. Tengo una respuesta, pero no estoy satisfecho con ella desde una perspectiva computacional. Primero, la respuesta, luego el dilema en curso. Supongamos que tienes B bolas en una urna. Hay C colores posibles. Para cualquier subconjunto de colores, hay un conjunto de bolas que contiene esos colores -tanto de un solo color como mixtos-. Digamos que cualquier subconjunto de algunos j colores, $S \subset \{1\ldots C\}, j=\left | S \right |$ se puede llamar $S_i|j$ . Para cualquier valor de j, hay t= $\binom{C}{j}$ combinaciones. Entonces, usando esa información y el principio de inclusión/exclusión...

$\sum_{j=1}^{C}-1^{(j-1)}\sum_{S_0 |j}^{S_t|j}dh(|S|, |S|, B-|S|, E) $

Esto es genial. Pero, aquí está el problema. Computacionalmente, es un oso, ya que incluso para un número moderadamente grande de colores, se vuelve lento de calcular. De hecho, uno es a menudo mejor para iterar a través de todas las combinaciones de bolas.

Compara el siguiente código R que funciona con matrices donde las columnas son colores y las filas son bolas

anyGone<-function(amat, E){
 totals<-colSums(amat) 
 #combn doesn't play well with E=1
 if(E==1) return( mean(colSums(apply(amat, 1, function(x) x==totals))>0) )    
 mean(combn(1:nrow(amat), E, function(rows) sum(totals==colSums(amat[rows,])))>0)

}

a esta función, que toma la misma matriz.

anyGone3<-function(amat, E){  
  eachColor<-colSums(amat)
  ret<-sum(dhyper(eachColor, eachColor, nrow(amat)-eachColor, E))

  if(E>1){for (j in 2:ncol(amat)){
    values<-combn(1:ncol(amat), j, function(x) sum(rowSums(amat[,x])>0))
    ret<- ret+(-1)^(j-1)*sum(dhyper(values, values, nrow(amat)-values, E))
  }}

  ret
}

Para una matriz sencilla con 15 colores, 15 bolas y 8 extracciones, la diferencia de rendimiento es notable.

Así que ......Supongo que la siguiente pregunta es más algorítmica. Sabiendo el número de tipos de bolas mezcladas, el número de colores y el número total de bolas, ¿hay alguna manera de reducir una gran cantidad de tiempo de este cálculo?