Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

up vote 7 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|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

Your Answer

 
discard

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.