Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $A$ be an $n\times n$ gaussian matrix whose entries are i.i.d. copies of a gaussian variable, and $\left\{ a_{j}\right\} _{j=1}^{n}$ be the column vectors of $A$. How to show that the probability $\mathbb{P}\left(d\geq t\right)\leq Ce^{-ct}$ for some $c,C>0$ and every $t>0$, where $d$ is the distance between $a_{1}$ and the $n-1$-dimensional subspace spanned by $a_{2},\cdots,a_{n}$.

Thanks a lot!

share|improve this question
    
Is this Gaussian variable assumed to have mean 0? –  Harald Hanche-Olsen Mar 13 '10 at 13:23
    
Yes, we assume it is in stardard normal distribution. –  user4606 Mar 14 '10 at 3:46
add comment

1 Answer

symmetry shows that you can suppose that $$\text{span}(a_2, \ldots, a_n) = ( x \in \mathbb{R}^n: x_1=0 ) = H.$$ Hence you just want to show that $d(a_1, H) = |A_{1,1}|$ is exponentially small - there is a closed-form expression for that: $$ P(d>t) = P(|\mathcal{N}(0,1)|>t) = \sqrt{\frac{2}{\pi}} \int_t^{\infty} e^{-\frac{x^2}{2}} dx.$$

share|improve this answer
    
I don't see how to use symmetry to get $$\text{span}(a_2, \ldots, a_n) = ( x \in \mathbb{R}^n: x_1=0 ) = H$$. Could you please explain a little more on that? –  user4606 Mar 14 '10 at 3:25
1  
You can see it using the concepts of conditional probability. For each possible $H$ (using Alekk's notation) there is a probability distribution of $d$ conditional on that $H$, and the total (unconditional) distribution of $d$ is obtained from that by integrating over $H$. Now the conditional distribution of $d$ given $H$ is independent of $H$, because the joint probability distribution of all the $a$'s is invariant under rotation. So integrating over $H$ is unnecessary – just use one fixed $H$. –  Harald Hanche-Olsen Mar 14 '10 at 4:40
1  
If you want $\ell_1$ distance, I think the formula (if one can be found) will be rather complex, and its derivation horrendously so. You might experiment with a computer algebra system and see how it works out for small values of $n$. –  Harald Hanche-Olsen Mar 14 '10 at 21:53
add comment

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.