Product of estimates of mean values - Concentration of measure inequality

Question

Let $X_{1},...,X_{d} \in \{-1,1\}^d$ be random variables, with $E[X_j]=\mu_j$. Having $n$ i.i.d. samples $x^{(i)}_1,x^{(i)}_2,....,x^{(i)}_d$, $i=1,...,n $, let $\hat{\mu}_{j}=\frac{1}{n}\sum^{n}_{i=1}x^{(i)}_j$ Then we would like to find an upper bound for $\text{Pr}[|\prod^{d}_{i=1}\hat{\mu}_{j}-\prod^{d}_{i=1}\mu_{j}|\geq \epsilon]$ where $\epsilon>0$.

We have $\prod^{d}_{j=1}\hat{\mu}_{j}=\prod^{d}_{j=1}(\frac{1}{n}\sum^{n}_{i=1}x^{(i)}_j)=\frac{1}{n^d}\prod^{d}_{j=1}\sum^{n}_{i_j=1}x^{(i_j)}_j=\frac{1}{n^d}\sum^{n}_{i_1,...,i_d=1}\prod^{d}_{j=1}x^{(i_j)}_j$. The random variables $\prod^{d}_{j=1}x^{(i_j)}_j$ are not independent since $X_{1},...,X_{d}$ are not independent, as a consequence we can not apply Hoeffding's inequality for the $\prod^{d}_{j=1}x^{(i_j)}_j$. There are concentration of measure inequalities for weakly dependent variables and boolean random variables $\{0,1\}$: Hoeffding’s inequality for sums of weakly dependent random variables, is there an extension of those or a different method that can be used to upper bound the $\text{Pr}[|\prod^{d}_{i=1}\hat{\mu}_{j}-\prod^{d}_{i=1}\mu_{j}|\geq \epsilon]$ where $\epsilon>0$.

Answer 1

The simplest idea is to estimate the variance. One has $$ \left(\prod^{d}_{j=1}\hat{\mu}_{j} \right)^2=\frac{1}{n^{2d}}\sum^{n}_{i_1,...,i_{2d}=1}\prod^{d}_{j=1}x^{(i_j)}_j x^{(i_{j+d})}_j $$ When $i_1,\dots,i_{2d}$ are all distinct the inner term has expectation $\left(\prod^{d}_{j=1}\mu_{j} \right)^2$, and there are at most $2d^2n^{2d-1}$ tuples whose entries are not all distinct. Thus $$ \mathbb{E} \left[ \left(\prod^{d}_{j=1}\hat{\mu}_{j} \right)^2 \right] \leq \left(\prod^{d}_{j=1}\mu_{j} \right)^2 + \frac{2d^2}{n}. $$ One does the same with $\prod^{d}_{j=1}\hat{\mu}_{j}$, and one gets $$ \mathbb{E} \left[ \prod^{d}_{j=1}\hat{\mu}_{j} \right] = \prod^{d}_{j=1}\mu_{j} + \theta\frac{d^2}{n}, $$ for some $|\theta| \leq 1$. Thus we have the estimate $$ \mathbb{E} \left[ \left(\prod^{d}_{j=1}\hat{\mu}_{j} - \prod^{d}_{j=1}\mu_{j}\right)^2 \right] \leq \frac{4d^2}{n}. $$ This produces non trivial estimates for $\text{Pr}[|\prod^{d}_{i=1}\hat{\mu}_{j}-\prod^{d}_{i=1}\mu_{j}|\geq \epsilon]$ as long as $n > 4 \varepsilon^{-2} d^2$.

Considering higher moments estimates should NOT lead to better bounds (without further assumptions on the joint distribution of $X _1\dots,X_d$).