Вероятность выпадения нечетного количества шаров

Aug 18 2020

У нас есть $n$ шары такие, что $k \ge 1$из них черные, а остальные белые. Рассмотрим следующую процедуру:

Сначала складываем все шарики в ведро $B_0$. Затем мы выбираем каждый из них с вероятностью$1/2$ и поместите выбранные в $B_1$. Далее мы выбираем каждый мяч в$B_1$ с вероятностью $1/2$ и поместите выбранные в $B_2$. Мы продолжаем делать это для$\Theta(\log{n})$ итераций.

Какова вероятность того, что хотя бы одно из этих ведерок содержит нечетное количество черных шаров?

Ну если $k$ нечетно, то легко видеть, что вероятность равна $1$, но как это проанализировать, когда $k$ даже?

Ответы

2 cgss Aug 18 2020 at 19:12

Я буду использовать термин раунд $i$ описать переход в ведро $B_i$. Обратите внимание, что вероятность перемещения четного числа черных шаров во время любого раунда равна$\frac{1}{2}$ так как вы можете переместить первый $x-1$шары в случайном порядке, а затем выберите последний, чтобы зафиксировать четность. Также обратите внимание, что если у вас четное количество шаров$B_{k}$ вплоть до $i$ и вы перемещаете четное число из $B_{i}$ к $B_{i+1}$ты в порядке. Это случается с вероятностью$\frac{1}{2}^i$.

Итак, окончательный ответ $1 - \frac{1}{2}^{\Theta (\text{log}n)}$