# Bounds on variance of sum of dependent random variables

Let $$x_1, \ldots, x_n$$ be possibly dependent random variables, each taking values $$x_i \in \{0, 1, 2\}$$. Suppose further that in every outcome the number of random variables that equal 2 is exactly 1. Now for each $$i \in \{1, \ldots, n\}$$ define $$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},$$ and let $$f = \sum_i f_i.$$

My question is how large can the variance of $$f$$ be? My conjecture is that we should be able to bound it by $$O(1)$$ but don't know how to prove this.

Note: In case it helps, it is easy to prove that $$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,$$ where the last equality comes from our initial assumption that in all outcomes exactly one of the $$x_i$$'s equals 2.

$$Var\,f$$ can be on the order of $$n$$ (but not more than that).

Indeed, let $$U$$ and $$N$$ be independent random variables such that $$P(U=1)=:p=1-P(U=0)=:q$$ and $$P(N=i)=1/n$$ for all $$i\in[n]:=\{1,\dots,n\}$$. Let $$x_i:=1(U=1,N\ne i)+2\times1(N=i).$$ Then with $$p=1/n$$ $$Var\,f\sim n/4\tag{1}$$ (as $$n\to\infty$$).

On the other hand, $$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.$$

Details on (1): We have $$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},$$ and $$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$$ for $$i\ne j$$. Choosing now $$p=1/n$$, we have
$$Ef^2\sim n/4.$$ Since $$Ef=1$$, (1) now follows.

Looking back at (2), now the idea behind the construction should become transparent: We want to make $$P(x_i\ge1,x_j\ge1)$$ for $$i\ne j$$ much greater than $$P(x_i\ge1)P(x_j\ge1)$$ and at the same time not to make $$P(x_i\ge1,x_j\ge1)$$ too small. The choice $$p=1/n$$ is nearly optimal in this regard.

• Thank you for the prompt response and the excellent demonstration of the distribution Iosif! Now I understand why I wasn't able to prove my conjecture lol. – Mathman Aug 17 '20 at 1:36
• Btw, I posted a related question (which was the main thing I was trying to prove via bounding the variance of $f$, which you refuted here). It would be great if you take a look at that one too if you have time. mathoverflow.net/questions/369355/… – Mathman Aug 17 '20 at 1:56