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

  • $\begingroup$ Are you looking for the worst case scenario (supremum over all possible $\mu_j$ and joint distributions) or for something else? $\endgroup$ – fedja Nov 23 '17 at 7:14
  • $\begingroup$ 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. $\endgroup$ – user_Lee 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$).

  • $\begingroup$ 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. $\endgroup$ – fedja Dec 11 '17 at 4:34

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.