Bolsas con bolas - Optimización combinatoria del problema de la probabilidad

Question

Supongamos que hay $n$ bolsas, cada una de las cuales contiene varios números de bolas de diferentes tamaños.

Una bola blanca, de cierto tamaño, distinta de todas las demás bolas de las bolsas, se lanza a una de las bolsas, seleccionada al azar con probabilidad $p_{i}$ ( para que $\sum_{i=1}^{n} p_{i} = 1$ ).

La probabilidad de escoger esta bola blanca, de la bolsa $i$ , condicionado a que la pelota sea lanzada en esa bolsa $i$ es $c_{i} \in [0,1]$ . Las probabilidades $c_{i}$ puede variar de una bolsa a otra, según el tamaño y el número de otras bolas que haya. Nótese que aquí el intervalo cerrado $[0,1]$ se da para $c_{i}$ como puede ser que la bola blanca sea tan pequeña comparada con las otras bolas ya presentes en la bolsa $i$ que las posibilidades de elegirla son esencialmente nulas, mientras que en el otro extremo, la bolsa $i$ podría estar vacío de antemano.

Tengo $k$ intenta sacar una bola blanca de las bolsas. Aquí $k \geq n$ . Puedo coger una bola de cualquiera de las bolsas en cualquier orden, y puedo volver a coger una bola de cualquiera de las bolsas tantas veces como quiera (hasta un máximo de $k$ en total). Me detengo cuando elijo por primera vez una bola blanca. Después de cada intento fallido, vuelvo a colocar la bola en la misma bolsa.

Por ejemplo, si $n=3$ y $k=6$ una posible secuencia de bolsas que elijo, suponiendo que sólo consigo una bola blanca en el último intento (o que no consigo la bola blanca en absoluto) podría ser $3, 1, 3, 2, 2, 3 $ . Otra posibilidad podría ser $1,1,1,1,1,2$ etc.

Mi pregunta es: ¿cómo puedo diseñar una estrategia para el número de intentos de cada bolsa, de manera que la probabilidad de que saque una bola blanca en $k$ intentos o menos se maximiza?

Answer 1

El problema se plantea como una optimización global (maximizar la probabilidad de encontrar la bola en no más de $k$ intentos), pero parece cierto (asumido, no demostrado aquí [*]) que es equivalente a maximizar iterativamente (con avidez) la probabilidad de encontrar la bola en el siguiente intento.

Dejemos que $c_i$ sea la probabilidad de encontrar la bola blanca al intentar una extracción de la bolsa $i$ , condicionado a que la bola blanca esté allí. Esto no cambia.

Dejemos que $X$ sea la posición de la pelota, y que $p_i=P(X=i)$ sea la probabilidad de que la bola blanca esté en la bolsa $i$ . Inicialmente, esto se da a priori. En cada intento (fallido), lo actualizaremos para reflejar la probabilidad a posteriori.

Dejemos que $F_i$ ser el caso de que no consigamos la bola blanca, dado que intentamos la bolsa $i$ .

Para maximizar la probabilidad de éxito en el primer intento, hay que minimizar $F_i$ . Pero $P(F_i) = 1 - d_i$ , donde $d_i = p_i \, c_i$ . Por lo tanto, denotando por $s$ la bolsa seleccionada, tenemos $s= \mathrm{argmax}_i \, d_i$ . Y la probabilidad de éxito es $d_s=\max_i(d_i)$

Dado que fallamos, las probabilidades $p_i$ se actualizan mediante Bayes de este modo:

Para $i=s$ :

$$ \begin{align} p'_s=P(X=s \mid F_s)&=\frac{P(F_s\mid X=s)P(X=s)}{P(F_s\mid X=s)P(X=s)+P(F_s\mid x\ne s)P(X\ne s)}\\ &=\frac{(1-c_s)p_s}{(1-c_s)p_s + (1-p_s)}\\ &=\frac{p_s-d_s}{1-d_s} \tag 1 \end{align}$$

Para $i\ne s$ primero calculamos

$$ \begin{align} P(F_s \mid X \ne i) &= P(F_s \mid X=s, X \ne i ) P(X=s\mid X \ne i) + P(F_s \mid X \ne s, X \ne i)P(X=s\mid X \ne i) \\ &= (1-c_s) \frac{p_s}{1-p_i} + 1\times (1 - \frac{p_s}{1-p_i}) \\ &= \frac{1}{1-p_i}(1- p_i - c_s p_s) \end{align} $$

Y luego

$$ \begin{align} p'_i =P(X=i \mid F_s)&= \frac{P(F_s\mid X=i)P(X=i)}{P(F_s\mid X=i)P(X=i)+P(F_s\mid X\ne i)P(X\ne i)} \\ &= \frac{ 1\times p_i }{1\times p_i + \frac{1}{1-p_i}(1- p_i - c_s p_s) (1-p_i) }\\ &=\frac{p_i}{1 -c_s p_s} = \frac{p_i}{1 - d_s} \tag{2} \end{align}$$

Con $(1)$ y $(2)$ juntos actualizamos las probabilidades $p_i$ y $d_i$ y repite.

Un ejemplo con $n=4$ bolsas y $k=5$

En amarillo, las bolsas seleccionadas en cada intento. En naranja, la probabilidad de haber encontrado la bola blanca en ese momento.

---

Actualización: Para los grandes $k$ podríamos intentar una maximización utilizando (abusando) de los multiplicadores de Lagrange. Me ahorraré los detalles (pregunta si los quieres), pero el resultado es

Dejemos que $k_i$ denota cuántas veces bolsa $i$ fue seleccionado, en $k$ extracciones (por lo tanto $\sum_{i=1}^n k_i=k$ ) Entonces la probabilidad de fracaso es

$$\begin{align} P(F; k_1,k_2 \cdots k_n) &= \sum_{i=1}^n P(X=i) P(F \mid X=i; k_1,k_2 \cdots k_n) \\ &= \sum_{i=1}^n p_i (1 - c_i)^{k_i} = \sum_{i=1}^n p_i e^{ -a_i \,k_i} \end{align}$$

donde $a_i = - \log(1-c_i)$

Queremos minimizar esta función de la variable multivariante $(k_1,k_2 \cdots k_n)$ con la condición de que $C(k_1,k_2 \cdots k_n) = \sum_{i=1}^n k_i-k =0$

Los multiplicadores de Lagrange serían aptos para esto excepto que nuestras variables no son reales sino enteras. De todos modos, abusando del método, igualando la derivada a cero da:

$$ - p_i a_i e^{ -a_i \,k_i} + \lambda = 0 \hskip{1 cm} i=1,2 \dots n$$

que puede escribirse como

$$k_i = \frac{\log(\, p_i a_i) + \beta }{a_i} \tag 3$$

donde y $\beta$ es un número que se obtiene resolviendo (numéricamente, al parecer) la restricción $\sum k_i = k$ junto con $(3)$ .

Por supuesto, $(3)$ da números no enteros, deberíamos esperar que el redondeo a los enteros más cercanos (siempre respetando la restricción de la suma) da al menos una buena aproximación al valor óptimo.

Por ejemplo, con $k=10$ y lo mismo $p_i$ , $c_i$ como en el ejemplo anterior, obtengo $k_i=(4.198, 2.941, 1.538, 1.330)$ mientras que los valores óptimos son $(4, 3, 2 ,1)$ .