Probabilidade de obter um número ímpar de bolas

Aug 18 2020

Nós temos$n$bolas tais que$k \ge 1$deles são negros e os demais são brancos. Considere o seguinte procedimento:

Primeiro colocamos todas as bolas no balde$B_0$. Então, selecionamos cada um deles com probabilidade$1/2$e colocar os selecionados em$B_1$. Em seguida, selecionamos cada bola em$B_1$com probabilidade$1/2$e colocar os selecionados em$B_2$. Continuamos fazendo isso por$\Theta(\log{n})$iterações.

Qual é a probabilidade de que pelo menos um desses baldes contenha um número ímpar de bolas pretas?

Bem, se$k$é ímpar, então é fácil ver que a probabilidade é$1$, mas como podemos analisar isso quando$k$é mesmo?

Respostas

2 cgss Aug 18 2020 at 19:12

vou usar o termo rodada$i$para descrever a mudança para o balde$B_i$. Observe que a probabilidade de mover um número par de bolas pretas durante qualquer rodada é$\frac{1}{2}$já que você pode mover o primeiro$x-1$bolas aleatoriamente e, em seguida, escolha a última para fixar a paridade. Além disso, observe que se você tiver um número par de bolas em todos$B_{k}$até$i$e você move o número par de$B_{i}$para$B_{i+1}$você está bem. Isso acontece com probabilidade$\frac{1}{2}^i$.

Então, a resposta final é$1 - \frac{1}{2}^{\Theta (\text{log}n)}$