Tek sayıda top alma olasılığı

Question

Sahibiz $n$ toplar öyle ki $k \ge 1$siyah, geri kalanı beyaz. Aşağıdaki prosedürü düşünün:

Önce tüm topları kovaya koyarız $B_0$. Ardından, her birini olasılıkla seçiyoruz$1/2$ ve seçilenleri koy $B_1$. Sonra, her bir topu seçiyoruz$B_1$ olasılıkla $1/2$ ve seçilenleri koy $B_2$. Bunu yapmaya devam ediyoruz$\Theta(\log{n})$ yinelemeler.

Bu kovalardan en az birinin tek sayıda siyah top içermesi olasılığı nedir?

Peki, eğer $k$ tuhafsa, olasılığın şöyle olduğunu görmek kolaydır $1$ama bunu ne zaman analiz edebiliriz $k$ eşit mi?

Answer 1

Yuvarlak terimini kullanacağım $i$ kovaya geçişi tanımlamak için $B_i$. Herhangi bir raunt sırasında çift sayıda siyah topun hareket etme olasılığının,$\frac{1}{2}$ ilkini hareket ettirebildiğinden beri $x-1$rastgele toplar ve ardından pariteyi sabitlemek için sonuncuyu seçin. Ayrıca, toplamda çift sayıda topunuz varsa$B_{k}$ kadar $i$ ve çift sayıyı $B_{i}$ -e $B_{i+1}$iyisin. Olasılıkla olur$\frac{1}{2}^i$.

Yani, son cevap $1 - \frac{1}{2}^{\Theta (\text{log}n)}$