Let $X_1,\ldots,X_n$ be independent random variables in $\mathbb{R}^d$ with $EX_i=0$ and $||X_i||_{2}\leq 1$. What is the best known exponential upper bound for $$P(||X_1+\cdots+X_n||_{2}>x)?$$

In particular, is it true, that the one dimensional case (Hoeffding's inequality) is the best? That is, is the latter probability at most $C_d\exp(-\frac{x^2}{2n})$? (the conctand $C=C_d$ is needed to account for the effects of the norm for $x$ small, that is, for $x<\sqrt{d}$ we can take all variables taking values $e_i$ and $-e_i$ with probability $1/2$, where $e_i$ stand for the usual basis of $\mathbb{R}^d$.

  • 1
    $\begingroup$ You need additional assumptions, even in the one-dimensional case, for Hoeffding's inequality to hold. $\endgroup$ – Mark Meckes Nov 12 '14 at 3:42
  • $\begingroup$ In 1 dimension this is exaclty hoeffding's inequality, unless I missed something obvious (we have boundedness, zero mean and independence). $\endgroup$ – TOM Nov 13 '14 at 20:18
  • $\begingroup$ Yes, in 1 dimension this is Hoeffding's inequality if you have boundedness, but that was never mentioned. $\endgroup$ – Mark Meckes Nov 14 '14 at 1:25
  • $\begingroup$ Ah, or by $\|X_i\|_2 \le 1$ did you mean that the Euclidean norm of $X_i$ is almost surely at most 1? I thought you were referring to the $L^2$ norm of a random variable. In that case, you can e.g. use a vector-valued version of Talagrand's inequality to get the same type of result as the one dimensional case. $\endgroup$ – Mark Meckes Nov 14 '14 at 3:23
  • $\begingroup$ I indeed meant that the Euclidean distance. $\endgroup$ – TOM Apr 20 '17 at 18:52

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.