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](https://arxiv.org/pdf/1507.06871.pdf), 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$. 



Product of estimates of mean values - Concentration of measure inequality
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$).


