Kemungkinan mendapatkan jumlah bola ganjil

Question

Kita punya $n$ bola seperti itu $k \ge 1$di antaranya berwarna hitam dan sisanya berwarna putih. Pertimbangkan prosedur berikut ini:

Kami pertama-tama memasukkan semua bola ke dalam ember $B_0$. Kemudian, kami memilih masing-masing dengan probabilitas$1/2$ dan masukkan yang dipilih $B_1$. Selanjutnya, kami memilih setiap bola masuk$B_1$ dengan probabilitas $1/2$ dan masukkan yang dipilih $B_2$. Kami terus melakukan itu untuk$\Theta(\log{n})$ iterasi.

Berapa probabilitas bahwa setidaknya salah satu ember ini berisi bola hitam dalam jumlah ganjil?

Nah, jika $k$ ganjil maka mudah untuk melihat bahwa probabilitasnya adalah $1$, tapi bagaimana kita bisa menganalisis ini kapan $k$ apakah genap?

Answer 1

Saya akan menggunakan istilah putaran $i$ untuk menggambarkan perpindahan ke keranjang $B_i$. Perhatikan bahwa probabilitas untuk memindahkan bola hitam dalam jumlah genap selama putaran apa pun adalah$\frac{1}{2}$ karena Anda bisa bergerak lebih dulu $x-1$bola secara acak dan kemudian pilih yang terakhir untuk memperbaiki paritas. Juga, perhatikan bahwa jika Anda memiliki jumlah bola genap di semua$B_{k}$ hingga $i$ dan Anda memindahkan bilangan genap dari $B_{i}$ untuk $B_{i+1}$kamu baik-baik saja Itu terjadi dengan probabilitas$\frac{1}{2}^i$.

Jadi, jawaban akhirnya adalah $1 - \frac{1}{2}^{\Theta (\text{log}n)}$