The variance of the average of Bernoulli random variables

51 Views Asked by At

Suppose to have two triangular arrays of Bernoulli random variables, that is, for all $n\in\mathbb{N}$, the collections of random variables $\{A_{j,n}| j=1,...,n\}$ and $\{B_{j,n}| j=1,...,n\}$ are such that $$ A_{j,n}=\begin{cases} 1 & \textrm{ with probability }p_{A,n}\\ 0 & \textrm{ with probability }1-p_{A,n} \end{cases},\quad B_{j,n}=\begin{cases} 1 & \textrm{ with probability }p_{B,n}\\ 0 & \textrm{ with probability }1-p_{B,n} \end{cases}. $$ Assume further that the $A$'s and the $B$'s are all independent from each others, although it is not required that the $A_{j,n}$ is independent from $A_{k,n}$ for $k\neq j$ (and the same for the $B$'s).

My problem is the following. I know that, for $n\rightarrow\infty$ $$ \mathbb{V}\left\{\frac{1}{n}\sum_{j=1}^nA_{j,n}\right\}\rightarrow 0,\quad \mathbb{V}\left\{\frac{1}{n}\sum_{j=1}^nB_{j,n}\right\}\rightarrow 0, $$ where $\mathbb{V}\{\}$ indicates the variance. Can I conclude that $$ \mathbb{V}\left\{\frac{1}{n}\sum_{j=1}^nA_{j,n}\,B_{j,n}\right\}\rightarrow 0\quad ? $$ This is my attempt. Assume $p_{A,n}\leq p_{B,n}$ for all $n$, then \begin{eqnarray} \mathbb{V}\left\{\frac{1}{n}\sum_{j=1}^nA_{j,n}\,B_{j,n}\right\} &=& \mathbb{E}\left\{\frac{1}{n^2}\left(\sum_{j}A_{j,n}\,B_{j,n}+\sum_{i\neq j}A_{i,n}\,A_{j,n}\,B_{i,n}\,B_{j,n}\right)\right\}-(p_{A,n}\,p_{B,n})^2 \\ &\leq &\mathbb{E}\left\{\frac{1}{n^2}\left(\sum_{j}A_{j,n}+\sum_{i\neq j}A_{i,n}\,A_{j,n}\right)\right\}-(p_{A,n})^4\neq \mathbb{V}\left\{\frac{1}{n}\sum_{j=1}^nA_{j,n}\right\} \end{eqnarray} My problem is that I do not get, as an upper bound, the variance of the average of the $A$'s. I tried also with Cauchy-Schwartz and it does not work. It seems intuitively true, but probably I am wrong.

1

There are 1 best solutions below

0
On BEST ANSWER

We can reduce the question to one about covariance matrices. Indeed, let $\Sigma_A^n, \Sigma_B^n$ denote the covariance matrices of the $A$ and $B.$ Just expanding the square and using independence, we get that

\begin{align} \mathbb{E}\left[ \left(\frac1n\sum A_{j,n} B_{j,n}\right)^2\right] &= \frac1{n^2}\sum_{j, k} \mathbb{E}[A_{j,n} A_{k,n} B_{j,n}B_{k,n}] \\ &= \frac{1}{n^2}\sum_{j,k} \mathbb{E}[A_{j,n}A_{k,n}] \mathbb{E}[B_{j,n}B_{k,n}]\\ &= \frac{1}{n^2} \langle \Sigma_A^n + p_A^2 \mathbf{1}\mathbf{1}^\top, \Sigma_B^n + p_B^2 \mathbf{1}\mathbf{1}^\top\rangle\\ &= \frac{1}{n^2} \left(\langle \Sigma_A^n, \Sigma_B^n\rangle + p_A^2 p_B^2 n^2 + \langle p_B^2\Sigma_A^n + p_A^2\Sigma_B^n, \mathbf{1}\mathbf{1}^\top\rangle \right),\end{align} where I'm using the Frobenius inner product $\langle U,V\rangle = \sum_{i,j} U_{ij} V_{ij} = \mathrm{Tr}(U^\top V),$ and $\mathbf{1}$ is the all ones vector.

Since $ \mathbb{E}[ \frac1n \sum A_{j,n} B_{j,n}] = p_Ap_B,$ this gives $$\mathbb{V}\left( \frac1n\sum A_{j,n} B_{j,n}\right) = \frac{1}{n^2}\langle \Sigma_A^n, \Sigma_B^n\rangle + \frac{1}{n^2}\langle p_B^2\Sigma_A^n + p_A^2\Sigma_B^n, \mathbf{1}\mathbf{1}^\top\rangle.$$

Now, since $\mathbb{V}(\frac1n\sum A_{j,n}) \to 0,$ we know that $\langle \Sigma_A^n, \mathbf{1}\mathbf{1}^\top\rangle/n^2 \to 0$, and similarly for $\Sigma_B^n$. The question then amounts to asking whether this implies that $\langle \Sigma_A^n, \Sigma_B^n\rangle /n^2 \to 0$. This does not hold in general, as the counterexample below shows.


Let us say that $i$ is early if $i \le \lceil n/2\rceil,$ and late if $i > \lceil n/2\rceil$. For $0 < |\alpha| \le 1/4,$ take a covariance structure of the form $$ \Sigma_{ij}^n = \begin{cases} 1/4 & i = j\\ + \alpha & i,j \textrm{ are both early or both late} \\ -\alpha & \textrm{one of } i,j\textrm{ is early, the other late} \end{cases}. $$ Set $\Sigma_A^n = \Sigma_B^n = \Sigma^n$. Then $\langle \Sigma^n, \mathbf{1}\mathbf{1}^\top \rangle = O(n)$ due to the cancellation induced by the nearly balanced $+\alpha$ and $-\alpha$ terms, but $\langle \Sigma_A^n, \Sigma_B^n\rangle = \|\Sigma^n\|_F^2 \ge n^2\alpha^2.$

Of course, we need to argue that such a covariance structure can be achieved using bits, but this is not too hard: let $Z_i$ denote iid $\mathrm{Bern}(p)$ random variables. Set $X_1 \sim \mathrm{Bern}(1/2)$ independently of the $Z$s, and for early $i$ set $X_i = X_1 \oplus Z_i,$ while for late $i$ set $X_i = X_1 \oplus 1 \oplus Z_i$. Note that marginally each $X_i$ is a fair bit. We have that if both $i,j$ are early or both late, then $$ \mathbb{E}[X_iX_j] -1/4= \frac{1}{2} p^2 + \frac12 (1-p)^2 - \frac14 = \frac{1 - 4p(1-p)}{4},$$ while if $i$ is early and $j$ late, then $$\mathbb{E}[X_iX_j] - \frac14 = \frac{4p(1-p) - 1}{4} $$


We can also use the characterisation about to derive sufficient conditions for convergence to $0$. For instance, suppose $A,B$s have $k$-decorrelation, i.e., that for every $i$, if $j > k$, then $\mathrm{Cov}(A_i, A_{i + j}) = 0,$ adding modularly (such a structure arises from moving averages of independent random variables, for instance). Then you'd get that $\|\Sigma_A\|_F = O(\sqrt{nk})$ and similarly for $\|\Sigma_B\|_F$, which would yield that their inner product is bounded as $nk,$ establishing convergence so long as $k = o(n).$ Ideally you'd look into a particular application to figure out conditions that make more sense.