7
$\begingroup$

For my research I have designed a metric that is based on the average Euclidean distance between $n$ points in the $n$-dimensional hypercube $[-1,1]^n$. However, I have a hard time finding the maximal average Euclidean distance between $n$ points in $[-1,1]^n$.

I need this maximum to normalize my metric between $0$ and $1$ . Please help!

Improve this question
$\endgroup$
4
  • $\begingroup$ I took the liberty to add the word average to the title (and to clarify that the hypercube is continuous and not discrete), as your question is more interesting than it looked from its title. $\endgroup$
    – Benoît Kloeckner
    Aug 23, 2017 at 13:16
  • $\begingroup$ Why do you want your metric to be normalised between 0 and 1 in this particular way? For many applications you can take just plug your distance function into arctan function or into simple cutoff $\min(d(x,y), 1).$ $\endgroup$
    – Vít Tuček
    Aug 23, 2017 at 13:48
  • 2
    $\begingroup$ @BenoîtKloeckner But the maximum can be attained only at vertices, no? $\endgroup$
    – Vít Tuček
    Aug 23, 2017 at 13:51
  • 1
    $\begingroup$ Indeed it's coordinate-wise convex so the maximum is attained at vertices, and only at the vertices actually (because, as a function of one coordinate of one of the $n$ points, it is a nonzero positive linear combination of $x\mapsto |x|$ or $x\mapsto\sqrt{1+x^2}$ (pre-composed by affine maps), for $n\ge 2$. $\endgroup$
    – YCor
    Aug 24, 2017 at 8:12

2 Answers 2

Reset to default
7
$\begingroup$

Here's the first few $n$ with the maximum average distance $m$ over all corner configurations, and a configuration which realizes it. I've changed the interval from $[-1,1]$ to $[0,1]$ to make it easier to read.

\begin{align} n=2, & \ m=\sqrt{2}\simeq 1.414 & (0,0)\\ & & (1,1)\\ n=3, & \ m=\sqrt{2}\simeq 1.414 & (0,0,1)\\ & & (0,1,0)\\ & & (1,0,0)\\ n=4, & \ m=\frac{\sqrt{2}+2\sqrt{3}}{3}\simeq 1.626 & (0,0,0,0)\\ & & (0,0,1,1)\\ & & (1,1,0,1)\\ & & (1,1,1,0)\\ n=5, & \ m=\frac{\sqrt{2}+3\sqrt{3}+\sqrt{4}}{5}\simeq 1.722 & (0,0,0,0,0) \\ & & (0,0,0,1,1)\\ & & (0,1,1,0,0)\\ & & (1,0,1,0,1)\\ & & (1,1,0,1,0)\\ \end{align} This suggests that choosing all coordinates independently and randomly may get an average close to the maximum, and for large $n$ that average is roughly $$\left(1-\frac{1}{8n}\right)\sqrt{\frac{n}{2}}.$$

Improve this answer
$\endgroup$
4
  • $\begingroup$ I do not think that is what he is asking. The way I interpret the question is: Choose n points in the n dimensional unit cube randomly. What is the expected value of the maximum distance between two of these n points? $\endgroup$
    – Michael Renardy
    Aug 23, 2017 at 15:32
  • 3
    $\begingroup$ The question says "maximum average distance", not "average maximum distance". If he means what you say, he should ask that question in a separate post. $\endgroup$
    – user44143
    Aug 23, 2017 at 15:35
  • $\begingroup$ @MichaelRenardy: To clarify: I do NOT mean " Choose n points in the n dimensional unit cube randomly" - What I mean is: What is the the maximum average Euclidean distance between n points in [-1,1]^n, given that you can choose these n points freely. $\endgroup$
    – Simon
    Aug 24, 2017 at 12:35
  • $\begingroup$ @MattF.: Thanks for showing the solution up to n=5, and for suggesting a way forward! However, since this is not really the solution to the problem yet, I will not set my tick... $\endgroup$
    – Simon
    Aug 24, 2017 at 12:53
4
$\begingroup$

Not what you are asking for, but I wanted to point out that the problem is very easy if you work with squared distances. Formulate the problem as the following optimization problem: \begin{align} \max \quad & \sum_{i\neq j} \| x_i- x_j\|_2^2 \\ s.t. \quad & x_i(k) \in \{-1,1\}, \end{align} where $x_i\in \mathbb{R}^n$. If the solution is at the corners, the set of maximizers is non convex (consider permutations).

Observe that $ \| x_i- x_j\|_2^2=\sum_{k=1}^n (x_i(k)-x_j(k))^2= \sum_{k=1}^n x_i(k)^2+x_j(k)^2 -2 x_i(k) x_j(k)$. For the corner points, we have $x_i(k)^2=1$, thus the problem becomes \begin{align} z=\min \quad & \sum_k\sum_{i\neq j} x_i(k) x_j(k) \\ s.t. \quad & x_i(k) \in \{-1,1\}, \end{align} where the optimal objective of the former problem is $n^2(n-1)-2z$. The latter problem decouples over $k$. For each $k$, we solve \begin{align} \min \quad & \sum_{i\neq j} x_i(k) x_j(k) \\ s.t. \quad & x_i(k) \in \{-1,1\}, \end{align} This basically is a max-cut problem for an n-node complete graph. Suppose n is even, the optimal solution is achieved by setting half of $x_i(k)$ to $+1$ other half to $-1$. Corresponding objective value is $2\frac{(n/2) ((n/2)-1)}{2}-(n/2)^2=-n/2$. Thus, $z=-n^2/2$. And the optimal objective of the original problem is $n^3$. Average of these squared distances is $n^2$.

Improve this answer
$\endgroup$

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.