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

If you sample $n$ vectors each with $m$ entries, with each entry chosen from the set $\{-1, 1\}$, how can you calculate the expected maximum absolute value of the inner product between all pairs of vectors? That is let us call the vectors $v_i$ and let $X_{n,m} = \max_{i \ne j} |\langle v_i,v_j \rangle|$. I would like $\mathbb{E}(X_{n,m})$.

We can assume both $n$ and $m$ are large. We can also assume that $n^c \leq m \leq n^{d}$ for constant $c,d > 0$.

share|improve this question

1 Answer 1

up vote 9 down vote accepted

Depending on how sharp an answer you want, concentration inequalities might suffice.

For one pair of (random) vectors, the inner product $X$ is distributed the same way as the sum of $m$ independent $\pm 1$-valued random variables. The simplest Chernoff inequality tells us that $$ \mathbb P(|X| > a) < 2e^{-a^2/2m}. $$ So $|X|$ is exponentially unlikely to take values greater than anything just a tiny bit larger than $\sqrt m$. Since $m$ and $n$ are related polynomially, summing over the $n^2$ pairs of vectors doesn't make the failure probabilty substantially greater, so with very high probability $|X_{m,n}|$ will be less than $m^{1/2+o(1)}$.

share|improve this answer
    
Thank you. Is there a matching lower bound which tells me that it is exponentially unlikely to take values smaller than anything just a tiny bit smaller than $\sqrt{m}$ too? –  Anush Jan 28 at 11:01
1  
The binomial distribution is fairly flat in a strip of width $\sqrt m$ near its mean, so I certainly expect to see values of size $\sqrt m$. Lower bounds for the probability of large deviations are not as common as upper bounds, and I don't know any nice statements offhand, but something precise is said in the appendix of Alon and Spencer, for example. Often the guiding principle is that the binomial distribution is well approximated by a normal distribution in the centre. –  Ben Barber Jan 28 at 11:17

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.