奇数のボールを獲得する確率

Question

我々は持っています $n$ そのようなボール $k \ge 1$そのうちの黒と残りは白です。次の手順を検討してください。

まず、すべてのボールをバケツに入れます $B_0$。次に、確率でそれぞれを選択します$1/2$ 選択したものを入れます $B_1$。次に、各ボールを選択します$B_1$ 確率で $1/2$ 選択したものを入れます $B_2$。私たちはそれを続けます$\Theta(\log{n})$ 反復。

これらのバケットの少なくとも1つに奇数の黒いボールが含まれている確率はどれくらいですか？

まあ、もし $k$ 奇数の場合、確率は次のようになります。 $1$、しかし、これをどのように分析できますか？ $k$ でも？

Answer 1

ラウンドという用語を使用します $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)}$