Вероятность выпадения нечетного количества шаров
У нас есть $n$ шары такие, что $k \ge 1$из них черные, а остальные белые. Рассмотрим следующую процедуру:
Сначала складываем все шарики в ведро $B_0$. Затем мы выбираем каждый из них с вероятностью$1/2$ и поместите выбранные в $B_1$. Далее мы выбираем каждый мяч в$B_1$ с вероятностью $1/2$ и поместите выбранные в $B_2$. Мы продолжаем делать это для$\Theta(\log{n})$ итераций.
Какова вероятность того, что хотя бы одно из этих ведерок содержит нечетное количество черных шаров?
Ну если $k$ нечетно, то легко видеть, что вероятность равна $1$, но как это проанализировать, когда $k$ даже?
Ответы
Я буду использовать термин раунд $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)}$