Probabilité d'obtenir un nombre impair de balles

Question

Nous avons$n$balles telles que$k \ge 1$d'entre eux sont noirs et les autres sont blancs. Considérez la procédure suivante :

Nous avons d'abord mis toutes les balles dans le seau$B_0$. Ensuite, nous sélectionnons chacun d'eux avec probabilité$1/2$et mettre les sélectionnés dans$B_1$. Ensuite, nous sélectionnons chaque balle dans$B_1$avec probabilité$1/2$et mettre les sélectionnés dans$B_2$. Nous continuons à le faire pendant$\Theta(\log{n})$itérations.

Quelle est la probabilité qu'au moins un de ces seaux contienne un nombre impair de boules noires ?

Eh bien si$k$est impair alors il est facile de voir que la probabilité est$1$, mais comment analyser cela quand$k$est même?

Answer 1

J'utiliserai le terme tour$i$pour décrire le passage au bucket$B_i$. Notez que la probabilité de déplacer un nombre pair de boules noires au cours d'un tour est$\frac{1}{2}$puisque vous pouvez déplacer le premier$x-1$boules au hasard puis choisissez la dernière pour fixer la parité. Notez également que si vous avez un nombre pair de boules en tout$B_{k}$jusqu'à$i$et vous déplacez le nombre pair de$B_{i}$à$B_{i+1}$tu vas bien. Cela arrive avec probabilité$\frac{1}{2}^i$.

Donc, la réponse finale est$1 - \frac{1}{2}^{\Theta (\text{log}n)}$