3
$\begingroup$

Let given a ball of radius $\alpha$ centered in point $u$ in $d$-dimensional space. Let given a sample of $n$ uniformly distributed vectors $x_i$ ($i = 1,\dots,n$) inside the ball. For each vector $x_i$ we connect points $u$ and $x_i$ by a segment and build a hyperplane $P_i$ through the middle of the segment and orthogonal to it. In the general case, the constructed hyperplanes bound a polyhedron in $\mathbb{R}^d$. I need to estimate from above the probability that uniformly distributed vector $q$ fall into this polyhedron.

In some cases the constructed polyhedron can be unbounded. More precisely, as far as I know it can be if and only if $u$ is not contained in the convex hull of $x_i$. This probability can be estimated, see for example here. Then I can write down

$\mathbb{P}( q$ in polyhedron $) \le \mathbb{P}(u$ in convex hull$) \mathbb{P}(q$ in polyhedron$|u$ in convex hull$) + \mathbb{P}(u$ not in convex hull$) \mathbb{P}(q$ in polyhedron$|u$ not in convex hull$) \le \mathbb{P}(q$ in polyhedron$|u$ in convex hull$) + \mathbb{P}(u$ not in convex hull$)$.

In such a way the problem of an unbounded polyhedron is overcome and we only need to estimate $\mathbb{P}(q$ in polyhedron$|u$ in convex hull$)$.

One more idea is that w.l.o.g. we can assume that $x_i$ is uniformly distributed on the sphere. Then we know the radius of sphere inscribed in our polyhedron, which is exactly equal to $\alpha / 2$.

There is another interpretation of this problem, maybe it can help. It is easy to see that our polyhedron is exactly the Voronoi cell of point $u$, so we need to estimate the volume of Voronoi cell.

It is obvious that when $n$ tends to infinity, then polyhedron volume tends to zero, so there has to be some rate of converges, but I do not know how to estimate it.

Thank you very much for any ideas, proofs, estimates, papers and so on!

$\endgroup$
  • 1
    $\begingroup$ Are you still interested in this problem? For a recent paper I've studied this problem, where $n=\exp \Theta(d)$ and I wanted to know the size of the enclosed region. Short answer: denoting $\alpha=n^{1/d}$, the enclosed polyhedron $P$ has volume relative to the unit ball $B$ given by $$\mathrm{vol}(P)=\left(\frac{\alpha^2}{4\alpha^2-4}\right)^{d/2+o(d)}\mathrm{vol}(B).$$ This assumes $\alpha \leq \sqrt{2}$; for larger $\alpha$ we essentially have $\mathrm{vol}(P) = \mathrm{vol}(B) / n$ up to order terms. This directly gives you the probability that a uniformly random point in $B$ is in $P$. $\endgroup$ – TMM Jun 2 at 1:00
2
$\begingroup$

A partial answer. Let us remove some syntactic sugar: we may clearly assume $\alpha=1$ and $u=0$.
Given our $n$ random points $x_i$, in the general case they define a polyhedron enclosing the origin whose volume is lower-bounded by $V(1) \left(\frac{1}{2}\min\|x_i\|\right)^d $, with $V(1)=\frac{\pi^{d/2}}{\Gamma(1+d/2)}$ being the volume of the $d$-dimensional unit ball. On the other hand the distribution of $\min\|x_i\|$ is fairly simple to compute. The PDF of $\|x_i\|$ is supported on $(0,1)$ and given by $f(x)= \frac{1}{d} x^{d-1}$, hence the PDF of $\min\|x_i\|$ is supported on $(0,1)$ and given by $g(x)=ndx^{d-1}(1-x^d)^{n-1}$. It follows that on average $\min\|x_i\|$ equals $\frac{\Gamma(n+1)\Gamma(1/d)}{d\,\Gamma(n+1+1/d)}$, while the expected value of $\left(\min\|x_1\|\right)^d$ simply equals $\frac{1}{1+n}$.

A reasonable upper bound is of the form $\frac{1}{n+1}\left(1+\frac{C_d}{\sqrt{n}}\right)$ (approximately $2^d$ times the lower bound), since our $n$ points, together with the origin, divide the hypersphere in $n+1$ Voronoi cells, which are expected to be roughly of the same volume (with their volumes being approximately normally distributed). Numerical simulations should find the $C_d$ constant with a reasonable accuracy.

$\endgroup$
  • $\begingroup$ Thank you, good solution! But I am mostly interested in upper-bound estimation. $\endgroup$ – Stanislav Morozov Jul 30 '18 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.