Expected distance of a random point to the convex hull of N other points

Question

Let $X_1, \cdots, X_N$ be i.i.d. $d$-dimensional random vectors, the exact distribution of $X$ is not very important in my application (as long as it continuous) so pick the one that works best, but ideally multivariate normal. Then let $Y$ be another $d$-dimensional random vector from a distribution that share the same central moments as the first distribution (i.e. the first distribution with shifted mean). Could one then find:

$$E\left(\min_{\alpha_1,\cdots,\alpha_N}\left\|Y-\sum_{i=1}^N\alpha_i X_i\right\|\right)\quad s.t. \sum_{i=1}^N \alpha_i = 1 \wedge \alpha_i\geq 0$$

or maybe bounds on it? Or maybe the probability $P\left(\min_{\alpha_1,\cdots,\alpha_N}\left\|Y-\sum_{i=1}^N\alpha_i X_i\right\|=0\right)$?

EDIT:

Actually what's really of interest is the relation between $E\left(\min_{a\in C}\|Y-a\|\right)$ and $E\left(\min_{a\in C}\|X_0-a\|\right)$ where $C=Conv(X_1, \cdots, X_N)$ and $X_0$ is distributed as $X_i$. Ideally I would like to prove that the first is weakly bigger than the second (my intuition tells me it should be true when the central moments are the same).

Right now I'm thinking along these lines. Let $\mu_X$ denote the mean of $X_i$, then let $S=\{x:\|x-\mu_X\|\leq r\}$ be a ball around $\mu_X$ with radius $r$ where we set $r=max_i\|X_i-\mu_X\|$. It then follows that for any point $x$ we have $x\in C\Rightarrow x\in S$, from which we have, for all $x$:

$$E\left(\min_{a\in C}\|x-a\|\right)\geq E\left(\min_{a\in S}\|x-a\|\right),$$

where $E\left(\min_{a\in S}\|x-a\|\right)=E(\max(\|x-\mu_X\|-r, 0))$.

Concerning $r$, if all elements in $X_i-\mu_X$ are independent and standard normal, $\|X_i-\mu_X\|$ will be chi distributed with $d$ degrees of freedom. But what about $max_i\|X_i-\mu_X\|$?

Even if not rigorous I'll would be happy just to compare the lower bounds of the expected distances of $Y$ and $X_0$. I guess a better way would be to construct a upper bound for $X_0$ (e.g. with a ball $S'$ s.t. $x\in S'\Rightarrow x\in C$) and then compare it with the lower bound for $Y$.

Answer 1

There is a trick in statistical physics that might work for your problem. The idea is that you want to minimize some function $H(X)$, which can be seen as an energy function. Therefore, you must compute the partition function $$Z(\beta) = \int dX e^{-\beta X}$$ Then, the expectation you want will be close to $-\beta^{-1}\partial_\beta \mathbb{E}[\ln(Z)]$ when $\beta \to 0$. The problem is to compute $\mathbb{E}[\ln(Z)]$ as a function of $\beta$, and there exists several tricks in statistical mechanics to do this (replica trick, cavity method, etc.) depending on the specific problem.

Good luck !

Answer 2

This answers the question about comparing the expected value of the distance from $X_0$ to the convex hull of the $X_i$ (for $i>1$) and the expected value of the distance from $Y$ to the convex hull.

Suppose the distribution of $X_1,\dots,X_n$ is rotationally symmetric about some origin $O$, and so is that of $X_0$. (I don't need $X_0$ to be distributed according to the same distribution as the $X_i$ with $i\geq 1$.) If we consider the function $F(X_1,\dots,X_n;X_0)$ which is the shortest vector from $X_0$ into the convex hull of the $X_i$'s, then $F$ will be rotationally symmetric too.

Pick $X_1,\dots,X_n$ according to their distribution. Let $P$ be their convex hull.

Now condition the choice of $X_0$ on the length of $F$ equalling $r$; so $F(X_1,\dots,X_n;X_0)$ is uniformly distributed on a sphere of radius $r$. Suppose first that $X_0$ is not in $P$, so $r$ is strictly positive. By symmetry, and after changing co-ordinates, we can put $X_0$ at $(0,\dots,0)$ and the closest point in $P$ at $re_1=(r,0,\dots,0)$. $P$ lies outside the sphere of radius $r$, so it lies in the half-plane $x_1\geq r$.

Let $m$ be the difference between the mean of $Y$ and $O$, the mean of $X_0$. Define $Y=X_0+m$.

We now want to consider what happens when $X_0$ is replaced by $Y$. In the co-ordinate system we are using, $Y$ is moved a uniformly distributed random direction from $X_0$, and the distance is the length of the vector $m$.

Let $v$ be such a randomly chosen vector. Suppose that the first co-ordinate of $v$ is non-negative. We note that the distance from $X_0+v$ to $P$ is decreased by at most the first coordinate of $v$, while the distance from $X_0-v$ to $P$ is increased by at least the first coordinate. Thus, the average over all possible $v$ will not decrease the distance (since $v$ and $-v$ were equally likely amounts by which to perturb $X_0$ to obtain $Y$).

Now consider the case that $X_0$ is in $P$ (i.e. r=0). In this case, it is obviously impossible for the average distance from $Y$ to $P$ to be smaller than that of $X_0$ to $P$, since the latter is 0. So we are done in this case also.