ขอบเขตความแปรปรวนของผลรวมของตัวแปรสุ่มตาม
ปล่อย $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$ เกือบจะเหมาะสมที่สุดในเรื่องนี้