Probabilità di ottenere un numero dispari di palline

Aug 18 2020

abbiamo$n$palle così che$k \ge 1$di loro sono neri e il resto sono bianchi. Considera la seguente procedura:

Per prima cosa mettiamo tutte le palline nel secchio$B_0$. Quindi, selezioniamo ciascuno di essi con probabilità$1/2$e inserire quelli selezionati$B_1$. Successivamente, selezioniamo ogni pallina$B_1$con probabilità$1/2$e inserire quelli selezionati$B_2$. Continuiamo a farlo per$\Theta(\log{n})$iterazioni.

Qual è la probabilità che almeno uno di questi secchi contenga un numero dispari di palline nere?

Bene se$k$è dispari allora è facile vedere che la probabilità è$1$, ma come possiamo analizzare questo quando$k$è anche?

Risposte

2 cgss Aug 18 2020 at 19:12

Userò il termine round$i$per descrivere il passaggio al secchio$B_i$. Nota che la probabilità di muovere un numero pari di palline nere durante ogni round è$\frac{1}{2}$poiché puoi spostare il primo$x-1$palle a caso e poi scegli l'ultima per fissare la parità. Inoltre, tieni presente che se hai un numero pari di palline in tutto$B_{k}$fino a$i$e sposti il ​​numero pari da$B_{i}$a$B_{i+1}$stai bene. Ciò accade con probabilità$\frac{1}{2}^i$.

Quindi, la risposta finale è$1 - \frac{1}{2}^{\Theta (\text{log}n)}$