Estrategia en un problema de urna con dos urnas

Question

Consideramos dos urnas cada que contiene bolas de $N$. Una de las urnas tiene bolas blancas solamente. El otro tiene $k$ negro bolas y así $N-k$ blanco bolas. Ambos $N$ $k$ son conocidos y $k>0$.

¿Cuál sería la mejor estrategia de extracción de la bola (sin devolver una bola extraída a cualquiera de las urnas) si uno quiere saber, que es la urna con las bolas negras? Mejor estrategia es entendido en el sentido de reducir el número de bolas extraídas esperado.

Answer 1

Claramente se detiene cuando se encuentra una bola negra. También puede detener cuando se han tenido $N-k+1$ bolas blancas de cualquiera de las urnas. Hay dos evidente estrategias a considerar:

1. Seguir tomando las bolas de una urna hasta que pueda dejar (evitando el costo de la mirada en la otra urna)
2. Tomar una bola de una urna y si no se detiene, a continuación, tomar una de la otra. Si usted todavía no se han detenido, a continuación, repita. Una versión de muchos equivalente versiones sería alternar entre las urnas hasta que se detenga.

Para la estrategia 1, si usted elige el blanco de urna el tiempo de espera para detener la es $N-k+1$, mientras que si eliges la parte-negro urna es $$\sum_{n=1}^{N-k+1} n\frac{k}{N-k+1}\frac{N-k+1 \choose n}{N \choose n}=\frac{N+1}{k+1}$$ so the overall expectation is $$\frac{N-k+1}{2} +\frac{N+1}{2(k+1)}.$$

Para la estrategia 2, es un poco como buscar la parte-negro urna pero el uso de dos selecciones de un tiempo, aunque a veces puede ahorrar una pelota, por lo que es $$(2N-2k+1) \frac{k}{N-k+1}\frac{N-k+1 \choose N-k+1}{N \choose N-k+1} +\sum_{n=1}^{N-k} \left(2n-\frac{1}{2}\right)\frac{k}{N-k+1}\frac{N-k+1 \choose n}{N \choose n}$$ or slightly simplified $$\frac{2(N+1)}{k+1} -\frac{1}{2} \left(1+ \frac{1}{{N \choose k}}\right). $$

Editado siguientes joriki comentario:

La diferencia entre la primera y la segunda de las expectativas es $0$ al $k=N$ (no es de extrañar, ya que sólo tienen que ver el $1$ pelota con cualquier estrategia, y empíricamente es negativo cuando $k \le 2$, $N \le 6$, o $k=N-1$ y positivo en caso contrario. Esto se traduce en una estrategia mixta dependiendo $k$ $N$ vwhich varía con el número de pelotas a la izquierda en cada urna.

Una estrategia mixta es difícil caclulate teóricamente, pero no imposible para los valores reales de a $k$ y el número de bolas en cada urna en cualquier momento (a pesar de que hay muchas oportunidades para los errores). La estrategia óptima se convierte en uno de continuar hasta llegar a una condición de parada. Parece ser:

1. Si tiene igual número de bolas en cada urna, de la que elegir uno de los, en particular, si usted tiene $k$ bolas a la izquierda en cada urna, de la que elegir una bola y dejar de.
2. Si usted tiene $k$ bolas en una urna y más en sacar una bola de la urna con el menor número de bolas y, a continuación, detener; esto significa que si usted comienza con $N=k+1$ la mejor estrategia es el plan para sacar dos bolas de la misma urna, si es necesario
3. Si $k=1$, siempre elegir la estrategia 1, todas las bolas de una sola urna hasta que se detenga
4. Si $k\ge 3$ e hay $k+1$ o más bolas a la izquierda en cada urna, elegir una bola de la urna con bolas
5. Si $k=2$ y no es uno más de la bola de una urna que la otra, o si hay cinco bolas en una urna y tres en la otra, o si hay $k$ bolas en una urna, de la que, a continuación, elegir una bola de la urna con el menor número de bolas; de lo contrario, elegir una bola de la urna con bolas.