0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

$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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Mathman Aug 17 '20 at 1:36
  • $\begingroup$ 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/… $\endgroup$ – Mathman Aug 17 '20 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.