4
$\begingroup$

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:

  1. 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).
  2. Given this $\epsilon$, choose any sequence of $n$ points $\{v_i\}_{i=1}^n$ (duplicates allowed) on the unit hypersphere $\mathcal{S}^{d-1}$.
  3. 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).

$\endgroup$

2 Answers 2

3
$\begingroup$

Let $\lambda$ be the largest eigenvalue of the symmetric matrix $M_{ij}$ with diagonal entries $0$ and off-diagonal entries $\epsilon_{ij}$.

Then

$$\sum_{1\leq i<j\leq n} \epsilon_{ij} v_i v_j^T =\sum_{1\leq i<j\leq n} \epsilon_{ij} \sum_{k=1}^d v_{i,k } v_{j,k} = \sum_{k=1}^d \sum_{1\leq i<j\leq n} \epsilon_{ij} v_{i,k } v_{j,k} \leq \sum_{k=1}^d \frac{\lambda}{2} \sum_{i=1}^n v_{i,k}^2 = \frac{\lambda}{2} \sum_{i=1}^n \sum_{k=1}^d v_{i,k}^2 = \frac{\lambda}{2} \sum_{i=1}^n |v_i|^2 = \frac{n \lambda}{2}. $$

Here the only non-formal calculation is the inequality $w^T M w \leq \lambda |w|^2$ for a symmetric matrix $M$ with largest eigenvalue $\lambda$.

By random matrix theory, the expected value of the largest eigenvalue of such a random matrix is going to be, I think, $O(n^{1/2})$, so your game has expectation at most $O(n^{3/2})$.

$\endgroup$
2
  • $\begingroup$ Thank you! Would you happen to know off the top of your head a reference for the bound on the spectral radius of such a random matrix? Otherwise I will try to find something myself. $\endgroup$
    – Allen94
    Commented May 7, 2022 at 16:36
  • $\begingroup$ @Allen94 I don't know off the top of my head but I believe I could give a proof for $O(n^{1/2} \log n)$. $\endgroup$
    – Will Sawin
    Commented May 7, 2022 at 19:17
3
$\begingroup$

This is correct.

Consider a random symmetric matrix $A=(a_{ij})$, $a_{ij}=a_{ji}=\epsilon_{ij}/2$, $a_{ii}=0$.

Let $u_1,\ldots,u_n$ be your $n$ points on the sphere $\mathcal{S}^{d-1}$. Denote $u_i=(u_{i1},u_{i2},\ldots,u_{id})$, $\sum_s u_{is}^2=1$. Consider $d$ vectors in $\mathbb{R}^n$: $f_s=(u_{1s},\ldots,u_{ns})^t$ for $s=1,\ldots,d$ (an uppercase $t$ denotes the transposition). Then your sum equals $$ \sum_{i,j} a_{ij}\langle u_i,u_j \rangle=\sum_{s=1}^d \sum_{i,j}a_{ij} u_{is}u_{js}=\sum_{s=1}^d \langle Af_s, f_s\rangle \leqslant C\sum_{s=1}^d \|f_s\|^2=Cn, $$ where $C$ is the maximal absolute value of the (random) matrix $A$. So, we want to prove that $C$ is small enough, like $O(n^{1-\delta})$ (sorry, I do not like your $\epsilon$ here, because you previously used $\epsilon$ in other context.)

This may be done, for example, by considering the sum $\Phi$ of fourth powers of eigenvalues: it equals $\sum a_{ij}a_{jk}a_{kl}a_{li}$, and the expectation of each such guy for which all $i,j,k,l$ are distinct equals 0. We are remained with expressions like $a_{ij}^2a_{ki}^2$, thus the expected value of $\Phi$ is, say, at most $n^3$. Therefore the expected value of $C$ is at most $n^{3/4}$, and the probability that $C>n^{3/4+1/100}$ is already small for large $n$.

This may be improved (and a lot is known about eigenvalues of such random matrices), but as I understand for your goals that's enough.

$\endgroup$
1
  • $\begingroup$ Ah! I had exactly the same construction for A, but I did not think to transpose the points and consider $d$ vectors in $\mathbb{R}^n$. $\endgroup$
    – Allen94
    Commented May 7, 2022 at 16:18

Your Answer

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