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



Expected maximum inner product
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)}$.


