# Best possible concentration inequality in high dimensions

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

• You need additional assumptions, even in the one-dimensional case, for Hoeffding's inequality to hold. – Mark Meckes Nov 12 '14 at 3:42
• In 1 dimension this is exaclty hoeffding's inequality, unless I missed something obvious (we have boundedness, zero mean and independence). – TOM Nov 13 '14 at 20:18
• Yes, in 1 dimension this is Hoeffding's inequality if you have boundedness, but that was never mentioned. – Mark Meckes Nov 14 '14 at 1:25
• 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. – Mark Meckes Nov 14 '14 at 3:23
• I indeed meant that the Euclidean distance. – TOM Apr 20 '17 at 18:52