Problema combinatorio: bolas negras y blancas divididas en k grupos con límites, y luego seleccionando una secuencia de solo bolas negras.

Question

Problema combinatorio: bolas negras y blancas divididas en k grupos con límites, y luego seleccionando una secuencia de solo bolas negras.

Matemáticas
probabilidad
combinatoria
Matemáticas discretas
coeficientes binomiales
distribuciones de probabilidad

SugerBoy

Tengo el siguiente problema combinatorio: Supongamos que tenemos $N$ pelotas: $W$ blanco y $B$ bolas negras ( $N = B + W$ ).

Paso 1: Lo primero que hacemos es dividir aleatoriamente estos $N$ bolas en $K$ contenedores, cada contenedor tiene $n = \frac{N}{K}$ pelotas. Por supuesto, la división de las bolas en los contenedores se realiza sin reemplazo.

Paso 2: ahora, una vez que las bolas se dividen entre los contenedores, seleccionamos al azar una bola de cada contenedor (es decir, sacamos $k$ bolas, una de cada caja, al azar).

Ahora, la pregunta es : ¿cuál es la probabilidad de que todas las bolas extraídas sean negras? Llamemos a este evento $E$ .

Traté de buscar en el foro algunas sugerencias, pero no encontré este tipo de pregunta. Encontré ese: pregunta combinatoria restringida: 2 tipos de bolas divididas en k grupos con límites , que me dio algunas pistas pero aún no era lo que estaba buscando.

Este es mi pensamiento:

Calculé todas las formas posibles de dividir las bolas como:
$(\binom{norte}{norte}) \cdot (\binom{norte - norte}{norte}) \cdot (\binom{norte - 2 norte}{norte}) \cdot \dots \cdot (\binom{norte - (k - 1) norte}{norte}) = \frac{norte!}{2 norte!}$ ${N \choose n }\cdot {N-n \choose n} \cdot {N-2n \choose n}\cdot \ldots \cdot {N-(K-1)n \choose n} = \frac{N!}{2n!}$ me salteo la papelera $K$ ya que en mi opinión solo hay una forma de poner $n$ bolas allí - y estas son las $n$ bolas restantes. Sin embargo, mi preocupación aquí es que la variable $K$ se canceló en esta ecuación, y me pregunto si eso está bien.
Ahora, el Paso 2 puede ocurrir con una probabilidad distinta de cero solo si al menos $1$ la bola negra está en cada contenedor. La distribución hipergeométrica me permite "formular la probabilidad de $s$ éxitos (es decir, sorteos aleatorios, para los cuales el objeto extraído tiene una característica específica) en $m$ extrae, sin reemplazo, de una población de tamaño $M$ que contiene exactamente $S$ objetos con esa característica, donde cada sorteo es un éxito o un fracaso". Así que pensé que podía usar esto en el Paso 1 cuando estoy asignando bolas aleatoriamente a los contenedores. El éxito sería poner una bola negra en un contenedor. Así que usando la notación de mis bolas blancas y negras, dicha probabilidad se define como
$PAG r (X = X) = \frac{(\binom{B}{X}) (\binom{norte - X}{norte - X})}{(\binom{norte}{norte})} .$ $Pr(X = x) = \frac{{B \choose x}{N - x \choose n -x}}{N \choose n}.$ Y pensé que entonces la probabilidad de que un contenedor contenga al menos 1 bola negra se expresaría como la suma $PAG r (al menos 1 bola negra en la papelera) = \sum_{X = 1}^{norte} \frac{(\binom{B}{X}) (\binom{norte - X}{norte - X})}{(\binom{norte}{norte})} .$ $Pr(\text{at least 1 black ball in the bin}) = \sum_{x=1}^{n} \frac{{B \choose x}{N - x \choose n -x}}{N \choose n}.$ Y ya que tenemos $K$ bins tendria que llevarlo a la potencia de $K$ . Entonces, la probabilidad de que cada contenedor contenga al menos 1 bola negra sería: ${(\sum_{X = 1}^{norte} \frac{(\binom{B}{X}) (\binom{norte - X}{norte - X})}{(\binom{norte}{norte})})}^{k}$ $\left(\sum_{x=1}^{n} \frac{{B \choose x}{N - x \choose n -x}}{N \choose n} \right)^K$

Y una vez que se hace la división de esa manera, lo único que queda es: la probabilidad de que saque una bola negra de cada contenedor y esta no sé cómo definirla.

Entonces, en general, mi pensamiento es que la probabilidad de un evento $E$ se definiría como:

PAG r [mi] = \frac{número de combinaciones que elijo todos negros con la condición de que cada contenedor tenga al menos 1 negro}{número de todas las posibles divisiones y caminos que puedo elegir}

$Pr[E] = \frac{\text{number of combinations that I pick all blacks under the condition that each bin has at least 1 black one}}{\text{number of all possible splits and paths I can pick}}$

Estaría muy agradecido si alguien me puede ayudar un poco ya que siento que estoy nadando alrededor de la solución pero no puedo llegar allí. ¿Mi consideración general es correcta, me estoy perdiendo algo? ¡Cualquier ayuda es bienvenida! ¡Muchas gracias de antemano!

T_M

Todavía no tengo una solución, pero su enfoque parece difícil. La probabilidad de sacar una bola negra de cada contenedor dependerá de la división exacta que tenga, por lo que no puede simplemente calcular la probabilidad de que tenga una división con al menos una bola negra en cada contenedor y luego calcular el siguiente paso . por separado.

T_M

Habiendo dicho eso, es fácil contar el número de divisiones 'válidas', es decir, aquellas con al menos una bola negra. la fórmula es

(\binom{B - 1}{K - 1})

$\binom{B-1}{K-1}$ ; ver aquí: en.wikipedia.org/wiki/…

Respuestas (1)

Problema combinatorio: bolas negras y blancas divididas en k grupos con límites, y luego seleccionando una secuencia de solo bolas negras.

Todavía no tengo una solución, pero su enfoque parece difícil. La probabilidad de sacar una bola negra de cada contenedor dependerá de la división exacta que tenga, por lo que no puede simplemente calcular la probabilidad de que tenga una división con al menos una bola negra en cada contenedor y luego calcular el siguiente paso . por separado.
Habiendo dicho eso, es fácil contar el número de divisiones 'válidas', es decir, aquellas con al menos una bola negra. la fórmula es $\binom{B-1}{K-1}$ ; ver aquí: en.wikipedia.org/wiki/…

T_M · Answer 1

Comenzaré tratando de formalizar un poco su enfoque general y veré si va a alguna parte... Vamos $B_i$ denote el número de bolas negras en el $i^{th}$ bin y considerar particiones $\mathcal{P}$ del $N$ bolas en el $K$ bins, cada uno dado por $B_1 = b_1, \dots, B_K = b_k$ con $b_i \geq 0$ y $b_1 + \dots b_K = B$ . Por la ley de probabilidad total: Entonces

\begin{array}{rcl} PAG (todas las bolas escogidas son negras) \\ = \sum_{\begin{matrix} b_{1} + \dots b_{k} = B \\ b_{i} \geq 1 \forall i \end{matrix}} PAG (todas las bolas escogidas son negras | B_{1} = b_{1}, \dots, B_{k} = b_{k}) \times PAG (B_{1} = b_{1}, \dots, B_{k} = b_{k}) \end{array}

$\begin{eqnarray} & \mathbb{P}\bigl(\text{all picked balls are black}\bigr) \\ & = \sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\mathbb{P}\bigl(\text{all picked balls are black}\ \big|\ B_1 = b_1,\dots,B_K = b_K\bigr) \times \mathbb{P}(B_1 = b_1,\dots,B_K = b_K) \end{eqnarray}$ Como usted señaló, no incluimos en la suma ninguna partición con

b_{i} = 0

$b_i = 0$ para algunos

i

$i$ porque la probabilidad de recuperar todo dada una de esas particiones es automáticamente cero.

Para el primer término, comience con la observación de que

PAG (todas las bolas escogidas son negras | PAG) = PAG (⋂_{i = 1}^{k} {se extrae la bola negra de i^{t h} papelera | PAG})) .

$\mathbb{P}\bigl(\text{all picked balls are black}\ \big|\ \mathcal{P}\bigr) = \mathbb{P}\bigl(\bigcap_{i=1}^K\{\text{black ball is picked from}\ i^{th}\ \text{bin}\ |\ \mathcal{P}\}\bigr)).$ Y estos eventos en el lado derecho son independientes, entonces

PAG (⋂_{i = 1}^{k} {se extrae la bola negra de i^{t h} papelera | PAG})) = \prod_{i = 1}^{k} \frac{b_{i}}{norte} .

$\mathbb{P}\bigl(\bigcap_{i=1}^K\{\text{black ball is picked from}\ i^{th}\ \text{bin}\ |\ \mathcal{P}\}\bigr)) = \prod_{i=1}^K \frac{b_i}{n}.$ Tres posibles interpretaciones:

Si tratamos de ir a lo seguro y etiquetamos los contenedores y las bolas negras, terminamos calculando
$\begin{aligned} PAG (B_{1} = b_{1}, \dots, B_{k} = b_{k}) \\ = \frac{Número de formas de colocar B objetos distintos en K contenedores con b_{i} objetos en el i^{t h} papelera}{Número de formas de colocar B objetos distintos en K contenedores} \\ = \frac{(\binom{B}{b_{1}, \dots, b_{k}})}{k^{B}} . \end{aligned}$ $\begin{align} &\mathbb{P}(B_1 = b_1,\dots,B_K = b_k) \\ & = \frac{\text{Number of ways of placing B distinct objects into K bins with}\ b_i\ \text{objects in the}\ i^{th}\ \text{bin}}{\text{Number of ways of placing B distinct objects into K bins}} \\ & = \frac{\binom{B}{b_1,\dots,b_K}}{K^B}. \end{align}$
Si etiquetamos contenedores pero no bolas, entonces estamos interesados en tuplas $(b_1,\dots,b_K)$ de enteros no negativos que suman $B$ en cuyo caso, cada partición posible es solo 1 multinomio de todos ellos, elegido (¿uniformemente supongo?) Al azar, es decir
$\begin{aligned} PAG (B_{1} = b_{1}, \dots, B_{k} = b_{k}) \\ = \frac{Número de k tuplas de exactamente la forma (b_{1}, \dots, b_{k})}{Número de k tuplas de enteros no negativos que suman B} \\ = \frac{1}{(\binom{B + k - 1}{B})} = \frac{B! (k - 1)!}{(B + k - 1)!} . \end{aligned}$ $\begin{align} &\mathbb{P}(B_1 = b_1,\dots,B_K = b_k) \\ & = \frac{\text{Number of}\ K\ \text{tuples of exactly the form}\ (b_1,\dots,b_K)}{\text{Number of}\ K\ \text{tuples of non-negative integers that sum to}\ B} \\ & = \frac{1}{\binom{B+K-1}{B}} = \frac{B!(K-1)!}{(B+K-1)!}. \end{align}$
Si ni las bolas ni los contenedores están etiquetados, se ingresa en particiones de $B$ con como mucho $K$ partes. No hay buenas fórmulas, demasiado difícil. Suponiendo que todo se haga de manera uniforme, no creo que importe lo que hagas. Usando la segunda de las tres interpretaciones anteriores, que parece natural, estás viendo:
$\begin{aligned} PAG (todas las bolas escogidas son negras) = \sum_{\begin{matrix} b_{1} + \dots b_{k} = B \\ b_{i} \geq 1 \forall i \end{matrix}} (\prod_{i = 1}^{k} \frac{b_{i}}{norte}) \frac{B! (k - 1)!}{(B + k - 1)!} . \end{aligned}$ $\begin{align} & \mathbb{P}\bigl(\text{all picked balls are black}\bigr) = \sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\Bigl(\prod_{i=1}^K \frac{b_i}{n}\Bigr)\frac{B!(K-1)!}{(B+K-1)!}. \\ \end{align}$ Pero no sé qué puedes hacer con esta expresión.

Usando la primera interpretación, obtienes una expresión potencialmente más complicada pero parece ser resumible al final; tienes:

\begin{aligned} PAG (todas las bolas escogidas son negras) & = \sum_{\begin{matrix} b_{1} + \dots b_{k} = B \\ b_{i} \geq 1 \forall i \end{matrix}} (\prod_{i = 1}^{k} \frac{b_{i}}{norte}) \frac{(\binom{B}{b_{1}, \dots, b_{k}})}{k^{B}} \\ = \frac{1}{{norte}^{k} k^{B}} \sum_{\begin{matrix} b_{1} + \dots b_{k} = B \\ b_{i} \geq 1 \forall i \end{matrix}} \frac{B!}{(b_{1} - 1)! \dots (b_{k} - 1)!} \\ = \frac{B!}{{norte}^{k} k^{B} (B - k)!} \sum_{\begin{matrix} b_{1} + \dots b_{k} = B \\ b_{i} \geq 1 \forall i \end{matrix}} \frac{(B - k)!}{(b_{1} - 1)! \dots (b_{k} - 1)!} \\ = \frac{B!}{{norte}^{k} k^{B} (B - k)!} \sum_{\begin{matrix} C_{1} + \dots C_{k} = B - k \\ C_{i} \geq 0 \forall i \end{matrix}} \frac{(B - k)!}{C_{1}! \dots C_{k}!} \\ = \frac{B!}{{norte}^{k} k^{B} (B - k)!} k^{B - k} \\ = \frac{B!}{{norte}^{k} k^{k} (B - k)!} . \end{aligned}

$\begin{align} \mathbb{P}\bigl(\text{all picked balls are black}\bigr) & = \sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\Bigl(\prod_{i=1}^K \frac{b_i}{n}\Bigr)\frac{\binom{B}{b_1,\dots,b_K}}{K^B} \\ &= \frac{1}{n^KK^B}\sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\frac{B!}{(b_1-1)! \dots (b_K-1)!} \\ &= \frac{B!}{n^KK^B(B-K)!}\sum_{\substack{b_1 + \dots b_K = B \\ b_i \geq 1\ \forall i}}\frac{(B-K)!}{(b_1-1)! \dots (b_K-1)!} \\ &= \frac{B!}{n^KK^B(B-K)!}\sum_{\substack{c_1 + \dots c_K = B-K \\ c_i \geq 0\ \forall i}}\frac{(B-K)!}{c_1! \dots c_K!} \\ &= \frac{B!}{n^KK^B(B-K)!}K^{B-K} \\ &= \frac{B!}{n^KK^K(B-K)!}. \end{align}$ Con

B = W = K = 2

$B = W = K = 2$ (en ese caso

n = 2

$n = 2$ ), esta fórmula da:

\frac{2!}{2^{2} 2^{2} 0!} = \frac{2}{dieciséis} = \frac{1}{8},

$\frac{2!}{2^22^2 0!} = \frac{2}{16} = \frac{1}{8},$ que es lo que también traté de explicar en los comentarios. Bien, parece que esto produce algún tipo de fórmula.

Para $B=W=K=2$ esa expresión final es $\frac13$ ; si he entendido el problema correctamente, la enumeración real de las posibilidades lo hace $\frac23$ . Sin embargo, no pasé por la derivación.
Existe cierta ambigüedad en la pregunta de qué división "aleatoria" $N$ bolas en $K$ bins significa, pero ahora que lo pienso, normalmente interpretaría esto como que los contenedores están etiquetados, por lo que las posibles particiones serían BB|WW, BW|BW, WW|BB. La partición BW|BW ocurre con probabilidad 1/2, las otras cada una con probabilidad 1/4. Para obtener todo negro al final, necesita BW|BW. Luego, también debe elegir la bola negra del contenedor 1 con una probabilidad de 1/2 y la bola negra del contenedor 2 con una probabilidad de 1/2. Entonces obtienes 1/8!?
Pensé que mi conteo del número de particiones contaría BB|WW y WW|BB como lo mismo ( $2 = 2 + 0$ ) y luego decir que tiene la misma posibilidad de ocurrir como BW|BW (2 = 1 + 1). Entonces obtendrías la misma respuesta, pero aparentemente me estoy perdiendo algo más
@T_M ¡Muchas gracias por tu ayuda! De hecho, su enfoque es muy sencillo: pasé un tiempo pensando en ello, ¡y tiene mucho sentido! Tuve la única dificultad de entender cómo llegaste $K^{B-K}$ de la última suma, ¡pero supongo que hay una buena fórmula que ayuda a hacerlo! También escribí un pequeño simulador de Python para estimar la probabilidad promedio y da prácticamente los mismos resultados que calcular la probabilidad directamente de su fórmula. ¡Una vez mas, Gracias!

Problema combinatorio: bolas negras y blancas divididas en k grupos con límites, y luego seleccionando una secuencia de solo bolas negras.

SugerBoy

T_M

T_M

Respuestas (1)

T_M

Brian M Scott

T_M

T_M

SugerBoy

Probabilidad de que dos elementos particulares se agrupen en una partición aleatoria con tamaños fijos

¿Trayectorias de coeficientes binomiales?

Una pregunta sobre un caso especial del principio de inclusión-exclusión

Probabilidad de sacar 5 cartas del mazo barajado

Prueba combinatoria (y algebraica) de una identidad que involucra números Lah

Cálculo de puntos mínimos para pasar como equipo en una liga deportiva

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

Número de palabras de 5 letras con al menos una letra doble

Probabilidad de obtener full house en el póquer de cinco cartas cuando faltan cartas en la suite

Demostrar una identidad combinatoria que involucre la suma del producto de coeficientes binomiales