Hoeffding's inequality for dependent random variable
Matthew Martinez 
Let $X_1,X_2\in \{-1,+1\}^2$ be dependent random variables with fixed moments $\mathbb{E}[X_1 X_2],\mathbb{E}[X_1],\mathbb{E}[ X_2]\in [-1,+1]$. Given $n$ iid samples we can estimate $\mathbb{E}[X_1],\mathbb{E}[ X_2]$ by using the following estimates $$\hat{\mathbb{E}}[X_1]=\frac{1}{n}\sum^{n}_{i=1} X^{(i)}_1 $$ and $$\hat{\mathbb{E}}[X_2]=\frac{1}{n}\sum^{n}_{i=1} X^{(i)}_2, $$ to find a rate of convergence we can use Hoefding's inequality. Since $\mathbb{E}[\hat{\mathbb{E}}[X_1]]=\mathbb{E}[X_1]$ and $\mathbb{E}[\hat{\mathbb{E}}[X_2]]=\mathbb{E}[X_2]$ we have an exponential rate of convergence for the above estimates by direct application of Hoefding's inequality.
Now assume that we would like to estimate also the quantity $\mathbb{E}[X_1]\mathbb{E}[X_2]$. A reasonable choice would be $$\hat{\mathbb{E}}[X_1]\hat{\mathbb{E}}[X_2]=\frac{1}{n^2}\sum^{n}_{i=1} X^{(i)}_1\sum^{n}_{i=1} X^{(i)}_2=\frac{1}{n^2}\sum^{n}_{i_1,i_2=1}X^{(i_1)}_1X^{(i_2)}_2.$$ The above estimate converges to $\mathbb{E}[X_1]\mathbb{E}[X_2]$ a.s. and we can use again Hoeffding's inequality, however, we have:$$\mathbb{E}[\hat{\mathbb{E}}[X_1]\hat{\mathbb{E}}[X_2]]=\mathbb{E}[\frac{1}{n^2}\sum^{n}_{i_1,i_2=1}X^{(i_1)}_1X^{(i_2)}_2]=\frac{n(n-1)}{n^2}\mathbb{E}[X_1]\mathbb{E}[X_2]+\frac{n^2-n(n-1)}{n^2}\mathbb{E}[X_1 X_2].$$ As a consequence there is a bias which is equal to $$\text{bias}=\frac{1}{n}(\mathbb{E}[X_1 X_2]-\mathbb{E}[X_1]\mathbb{E}[X_2]).$$ That bias affects the convergence rate and makes it slower than an exponential rate.
My question is the following are there estimates $\hat{a},\hat{b},\hat{c}$ such that all the folowing hold: $$\hat{a}\overset{\text{a.s.}}{\rightarrow} \mathbb{E}[X_1]\mathbb{E}[X_2],\\ \hat{b}\overset{\text{a.s.}}{\rightarrow} \mathbb{E}[X_1],\\ \hat{c}\overset{\text{a.s.}}{\rightarrow} \mathbb{E}[X_2]$$ $$\hat{a}=\hat{b}\times\hat{c}$$ and the rate of convergence for all $\hat{a},\hat{b},\hat{c}$ is exponential? If not is there any way to prove what is the worst case scenario for the sum of all rates over all possible estimators?
$\endgroup$ 1 Reset to default
