Probabilità di ottenere un numero dispari di palline
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
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)}$