3
$\begingroup$

Let $v_1, ..., v_n$ be distinct points in $\{0,1\}^d$ with the same norm $\|v_i\|_2=k$ (i.e each $v_i$ has $k$ ones). Let $A=\frac{1}{n}\sum_{i=1}^n v_i$ be their average, and let $C$ be the center of their minimum enclosing ball. Assume $n \gg d > k$.

What is a good upper bound for $\|A-C\|_2$ in terms of $d,k,n$?

Since $A$ is in the minimum enclosing ball, $\|A-C\|$ is at most the radius of that ball, which has diameter at most $\sqrt{2k}$. So by Jung's theorem, the radius of that ball and $\|A-C\|$ are both at most $\sqrt{2k}\sqrt{\frac{d}{2(d+1)}}=\sqrt{\frac{kd}{d+1}}$.

Can we get a better bound using $n$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ @Matt F. Thanks for the edit, the question is much clearer. $\endgroup$
    – AspiringMat
    Commented Nov 8, 2022 at 4:42
  • $\begingroup$ Consider $f:[0,1]\to\{0,1\}^c$ by $(f(x))_i=1_{i\le cx}$. This induces a map from $[0,1]^d$ to $\{0,1\}^{cd}$, and I suspect that using the induced map to transfer examples and bounds will make the problem equivalent to a continuous version. $\endgroup$
    – user44143
    Commented Nov 8, 2022 at 18:42

1 Answer 1

Reset to default
1
$\begingroup$

Assume $d=2\cdot k$. If $d$ is large, then the vertices of the cube such that $\|v\|=k$ lie very densely in $(d-1)$-dimensional sphere.

If $n$ is large, but not that large, then you may choose $n-1$ points near one pole of $\mathbb{S}^{d-1}$ and 1 point near the opposite pole. In this case the $\|A-C\|$ is very close to the worst case.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. The point here is that $n \gg d$. For example, something of the order $\gg d^d$, so I'm wondering if the average gets it closer to its "right" position. At least in 2D, 3D (the only thing I can visualize), it gets really close on almost all examples I tried. $\endgroup$
    – AspiringMat
    Commented Nov 9, 2022 at 18:03
  • $\begingroup$ @AspiringMat, wait, $n\leqslant \binom dk\leqslant 2^d$, so order $d^d$ makes no sense. $\endgroup$
    – Anton Petrunin
    Commented Nov 9, 2022 at 18:24
  • $\begingroup$ @AspiringMat if $n$ is of order $\binom dk$, then, by the concentration of measure phenomenon, $\|A-C\|$ is very small. My argument shows that this is not so if $n$ is much smaller than $\binom dk$, it still can be much larger that $d$. $\endgroup$
    – Anton Petrunin
    Commented Nov 9, 2022 at 18:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .