# Hoeffding's inequality for dependent random variables

suppose that I have $n$ independent sub-Gaussian random variables, $x_1,\ldots,x_n$. Let real-valued function $g(\cdot,\cdot)\in[-1,1]$ and $\mathbb{E}[g(\cdot,\cdot)]=0$. Set

$S=\frac{2}{n(n-1)}\sum_{1\leq i< j\leq n}g(x_i,x_j)$

How can I bound the term $S$ with high probability? Hoeffding's inequality does not hold here since $g(\cdot,\cdot)$ are not independent. Nevertheless, can I get a similar bound as the Hoeffding's inequality? More specifically, I want a bound in the form of $\mathbb{P}(S>t)\leq e^{-ct^2}$ for any $t>0$.

• @ByronSchmuland Thank you. $e^{-nt^2}$ would also help. But does it require $x_1,\ldots,x_n$ to be independent? – sopin Sep 23 '16 at 18:55
• @ByronSchmuland Oh, sorry, I missed the weight. I meant to bound the average. – sopin Sep 23 '16 at 19:14
• @ByronSchmuland The bound only needs to hold with high probability. Since $\mathbb{E}[g(\cdot,\cdot)]=0$, you can't have $g\equiv 1$. – sopin Sep 24 '16 at 0:01
• Since $P(S>0)<1$ and $P(S>1)=0$ a bound of the type $P(S>t)\leq e^{-ct^2}$ is trivially possible. It has nothing to do with dependence or independence, the sub-Gaussian character of the $x_i$s, or any properties of the function $g$. – user940 Sep 24 '16 at 21:34
• @ByronSchmuland Could you please write down why it is trivial? I am still confused about it. – sopin Sep 25 '16 at 19:25