홀수 공을 얻을 확률
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)}$