Probabilidad de sacar un número impar de bolas
Tenemos$n$pelotas tales que$k \ge 1$de ellos son negros y el resto son blancos. Considere el siguiente procedimiento:
Primero ponemos todas las bolas en el balde$B_0$. Luego, seleccionamos cada uno de ellos con probabilidad$1/2$y poner los seleccionados en$B_1$. A continuación, seleccionamos cada bola en$B_1$con probabilidad$1/2$y poner los seleccionados en$B_2$. Seguimos haciendo eso por$\Theta(\log{n})$iteraciones
¿Cuál es la probabilidad de que al menos una de estas cubetas contenga un número impar de bolas negras?
Bueno, si$k$es impar entonces es fácil ver que la probabilidad es$1$, pero ¿cómo podemos analizar esto cuando$k$¿incluso?
Respuestas
Usaré el término ronda$i$para describir el movimiento al cubo$B_i$. Tenga en cuenta que la probabilidad de mover un número par de bolas negras durante cualquier ronda es$\frac{1}{2}$ya que puedes mover el primero$x-1$bolas al azar y luego elige la última para fijar la paridad. Además, tenga en cuenta que si tiene un número par de bolas en todos$B_{k}$hasta$i$y mueves un número par de$B_{i}$a$B_{i+1}$estás bien. Eso pasa con probabilidad$\frac{1}{2}^i$.
Entonces, la respuesta final es$1 - \frac{1}{2}^{\Theta (\text{log}n)}$