7
$\begingroup$

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

$\endgroup$

1 Answer 1

9
$\begingroup$

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

$\endgroup$
2
  • $\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$
    – Simd
    Jan 28, 2014 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, 2014 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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