Given $n,d\in\mathbb{N}, n\gg d$, I'm looking for a bound on the maximum (or minimum) expected value of the following game:
- Draw a vector $\epsilon\in\{\pm 1\}^{\binom{n}{2}}$, uniformly at random. Each of these is assigned to a pair of entries $i,j\in[n], i\neq j$ in some pre-determined way (e.g., placed in a strictly triangular matrix).
- Given this $\epsilon$, choose any sequence of $n$ points $\{v_i\}_{i=1}^n$ (duplicates allowed) on the unit hypersphere $\mathcal{S}^{d-1}$.
- The value of the game is equal to the sum of the products of each $\epsilon_{i,j}$ with the corresponding inner product $v_i^\top v_j$.
You can think of this as choosing a set of $n$ points and then assigning a weight of $\pm 1$ to each pair's inner product, except that we get to see all the $\pm 1$ values before choosing the points. For example, suppose $d=2,n=3$ and $\epsilon = (+1, +1, +1)$, then choosing $v_1 = v_2 = v_3$ will have value 3, since each inner product is 1. However, if $\epsilon = (-1, -1, -1)$, it's less clear (I imagine spacing them out evenly giving a value of $-3cos(\frac{2\pi}{3})$).
Since $\epsilon$ is drawn uniformly, the minimum expected value of this game is the negation of the maximum, so either will do. I've been trying to bound it for specific patterns of $\epsilon$ even, without regard to the distribution, but have had no luck so far. I've also tried writing it as an optimization problem but it is difficult to work with except for very benign $\epsilon$ (such as those that make it convex/concave).
A trivial upper bound is $O(n^2)$, but in general I would expect this to grow slower than that, and I have little intuition for how it should grow with $d$. Honestly, even something slightly smaller such as $O(n^{(2-\epsilon)}\cdot\text{poly}(d))$ would be a useful result for my purposes (overloading $\epsilon$ here to mean a very small positive value).