Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X \sim {\cal N}_d(0, \sigma^2I_d)$. I am interested in bounding the tail probability $P[||X||_1 > t]$ from above. A pointer to a known exponential or polynomial tail bound would be appreciated.

One idea to deal with the above probability is to use something like McDiarmid's inequality, but suitable for unbounded random variables.

share|cite|improve this question
up vote 8 down vote accepted

A typical trick is to use Chebyshev's inequality with the function $\exp(\alpha x)$ to obtain $$P(\|X\|_1>t)\leq E(\exp(\alpha\|X\|_1))/\exp(\alpha t).$$ Since the 1-norm is a sum and the coordinates are independent, the right hand side equals $$\exp(-\alpha t)\ E(\exp(\alpha |Z|))^d=\exp(-\alpha t)\left(\exp(\alpha^2/2) (1+\mbox{erf}(\alpha/\sqrt{2})) \right)^d.$$ Here $Z$ is a one dimensional standard normal random variable.

You can now try to optimize over $\alpha$. Substituting the cheap upper bound $\mbox{erf}(\alpha/\sqrt{2})\leq 1$, and then optimizing gives $\alpha=t/d$. Plugging this in we get

$$ P(\|X\|_1>t)\leq 2^d \exp(-t^2/2d).$$

I know you could do better, but maybe it will suffice for your purposes.

share|cite|improve this answer
(+1) Nice and clean. Note that the OP specified the variance as $\sigma^2$, but that's easy to incorporate. – cardinal Apr 20 '11 at 2:45
@cardinal Whoops, quite right I accidentally dropped the $\sigma$. I'll leave it as an exercise. – Byron Schmuland Apr 20 '11 at 2:52
@ByronSchmuland hi, could please help me to address a similar question… – olivia Apr 25 at 4:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.