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