2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ You need additional assumptions, even in the one-dimensional case, for Hoeffding's inequality to hold. $\endgroup$
    – Mark Meckes
    Commented Nov 12, 2014 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
    Commented Nov 13, 2014 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
    Commented Nov 14, 2014 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
    Commented Nov 14, 2014 at 3:23
  • $\begingroup$ I indeed meant that the Euclidean distance. $\endgroup$
    – TOM
    Commented Apr 20, 2017 at 18:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .