# Product of estimates of mean values - Concentration of measure inequality

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

• Are you looking for the worst case scenario (supremum over all possible $\mu_j$ and joint distributions) or for something else? Nov 23 '17 at 7:14
• I am interested in all possible $\mu_j$ and joint distributions if it is easier for a specific case like exponential distributions I would like to see that solution as well. Nov 24 '17 at 21:07

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$).
• If you go that high up with $n$, you can trivially have $P\le 2e^{-\frac 12\varepsilon^2d^{-2}n}$. On the other hand, I'm not sure myself whether $n\ll d^2/\varepsilon^2$ can give you anything interesting here. Dec 11 '17 at 4:34