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

  • $\begingroup$ @ByronSchmuland Thank you. $e^{-nt^2}$ would also help. But does it require $x_1,\ldots,x_n$ to be independent? $\endgroup$ – sopin Sep 23 '16 at 18:55
  • $\begingroup$ @ByronSchmuland Oh, sorry, I missed the weight. I meant to bound the average. $\endgroup$ – sopin Sep 23 '16 at 19:14
  • $\begingroup$ @ByronSchmuland The bound only needs to hold with high probability. Since $\mathbb{E}[g(\cdot,\cdot)]=0$, you can't have $g\equiv 1$. $\endgroup$ – sopin Sep 24 '16 at 0:01
  • $\begingroup$ 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$. $\endgroup$ – user940 Sep 24 '16 at 21:34
  • $\begingroup$ @ByronSchmuland Could you please write down why it is trivial? I am still confused about it. $\endgroup$ – sopin Sep 25 '16 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.