Giới hạn phương sai của tổng các biến ngẫu nhiên phụ thuộc

Aug 16 2020

Để cho $x_1, \ldots, x_n$thể là các biến ngẫu nhiên phụ thuộc , mỗi biến nhận giá trị$x_i \in \{0, 1, 2\}$. Giả sử thêm rằng trong mọi kết quả, số biến ngẫu nhiên bằng 2 chính xác là 1. Bây giờ cho mỗi$i \in \{1, \ldots, n\}$ định nghĩa $$ 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}, $$ và để $ f = \sum_i f_i. $

Câu hỏi của tôi là phương sai của $f$là? Phỏng đoán của tôi là chúng ta có thể ràng buộc nó bằng$O(1)$ nhưng không biết làm thế nào để chứng minh điều này.


Lưu ý: Trong trường hợp nó hữu ích, dễ dàng chứng minh rằng $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, $$ nơi mà sự bình đẳng cuối cùng xuất phát từ giả định ban đầu của chúng tôi rằng trong tất cả các kết quả, chính xác một trong các $x_i$của bằng 2.

Trả lời

4 IosifPinelis Aug 16 2020 at 22:11

$Var\,f$ có thể theo thứ tự $n$ (nhưng không nhiều hơn thế).

Thật vậy, hãy $U$$N$ là các biến ngẫu nhiên độc lập sao cho $P(U=1)=:p=1-P(U=0)=:q$$P(N=i)=1/n$ cho tất cả $i\in[n]:=\{1,\dots,n\}$. Để cho$$x_i:=1(U=1,N\ne i)+2\times1(N=i). $$ Sau đó với $p=1/n$ $$Var\,f\sim n/4\tag{1}$$ (như $n\to\infty$).

Mặt khác, $$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.$$


Chi tiết về (1): Chúng tôi có $$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$$ cho $i\ne j$. Chọn ngay bây giờ$p=1/n$, chúng ta có
$$Ef^2\sim n/4.$$ Từ $Ef=1$, (1) bây giờ theo sau.


Nhìn lại (2), bây giờ ý tưởng đằng sau việc xây dựng nên trở nên minh bạch: Chúng tôi muốn $P(x_i\ge1,x_j\ge1)$ cho $i\ne j$ lớn hơn nhiều $P(x_i\ge1)P(x_j\ge1)$ đồng thời không làm cho $P(x_i\ge1,x_j\ge1)$quá nhỏ. Sự lựa chọn$p=1/n$ là gần như tối ưu về mặt này.