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


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

  • $\begingroup$ 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? $\endgroup$ – Anush Jan 28 '14 at 11:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Ben Barber Jan 28 '14 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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