従属確率変数の合計の分散の限界
しましょう $x_1, \ldots, x_n$それぞれが値を取る従属確率変数である可能性があります$x_i \in \{0, 1, 2\}$。さらに、すべての結果で、2に等しい確率変数の数が正確に1であると仮定します。$i \in \{1, \ldots, n\}$ 定義する $$ f_i = \begin{cases} \Pr[x_i = 2 \mid x_i \geq 1] & \text{if } x_i \geq 1\\ 0 & \text{if } x_i =0 \end{cases}, $$ そしてしましょう $ f = \sum_i f_i. $
私の質問は、 $f$でしょうか?私の推測は、私たちはそれを束縛することができるはずだということです$O(1)$ しかし、これを証明する方法がわかりません。
注:それが役立つ場合は、それを証明するのは簡単です $E[f] = 1$: $$ E[f] = \sum_i E[f_i] = \sum_i \Pr[x_i \geq 1] \times \Pr[x_i = 2 \mid x_i \geq 1] = \sum_i \Pr[x_i = 2] = 1, $$ ここで、最後の平等は、すべての結果において、 $x_i$は2に等しい。
回答
$Var\,f$ のオーダーにすることができます $n$ (ただし、それ以上ではありません)。
確かに、 $U$ そして $N$ 次のような独立確率変数である $P(U=1)=:p=1-P(U=0)=:q$ そして $P(N=i)=1/n$ すべてのために $i\in[n]:=\{1,\dots,n\}$。しましょう$$x_i:=1(U=1,N\ne i)+2\times1(N=i). $$ その後、 $p=1/n$ $$Var\,f\sim n/4\tag{1}$$ (なので $n\to\infty$)。
一方、 $$Var\,f\le Ef^2=\sum_{i,j\in[n]}Ef_if_j\le\sum_{i,j\in[n]}Ef_i =n\sum_{i\in[n]}Ef_i=n.$$
(1)の詳細: $$Ef^2=\sum_{i,j\in[n]}Ef_if_j \\ =\sum_{i,j\in[n]}P(x_i=2|x_i\ge1)P(x_j=2|x_j\ge1) P(x_i\ge1,x_j\ge1),\tag{2}$$ $$P(x_i\ge1)=1-P(x_i=0)=1-P(U=0)P(N\ne i)=1-q(1-1/n)=p+q/n,$$ $$P(x_i=2)=P(N=i)=1/n,$$ $$P(x_i=2|x_i\ge1)=\frac{P(x_i=2)}{P(x_i\ge1)}=\frac{1/n}{p+q/n},$$ そして $$P(x_i\ge1,x_j\ge1)=1-P(x_i=0\text{ or }x_j=0)=1-P(x_i=0)-P(x_j=0)+P(x_i=0,x_j=0) =1-2q(1-1/n)+q(1-2/n)=1-q=p$$ にとって $i\ne j$。今すぐ選択$p=1/n$、 我々は持っています
$$Ef^2\sim n/4.$$ 以来 $Ef=1$、(1)が続きます。
(2)を振り返ると、建設の背後にある考え方が透明になるはずです。 $P(x_i\ge1,x_j\ge1)$ にとって $i\ne j$ はるかに大きい $P(x_i\ge1)P(x_j\ge1)$ 同時に作らない $P(x_i\ge1,x_j\ge1)$小さすぎる。選択肢$p=1/n$ この点でほぼ最適です。