Vrftjkry

I have the following problem:

Let us denote a ball with center $C$ and radius $R$ in $mathbb{R}^d$ as $B(C, R)$. Given a unit ball $B(0, 1)$ and vector $u$ has a uniform distribution inside the ball: $u sim U(B(0, 1))$. Then we sample $M$ points $v_1, dots, v_M$ that are uniformly distributed in the ball $B(0, 1)$ and the distance between $u$ and $v_i$ is not greater than $r$, that is $v_i$ are i.i.d. in $B(0, 1) cap B(u, r)$. How to estimate the volume of the Voronoi cell of $u$ inside the ball $B(0, 1)$? I need an upper bound here.

I can obtain only very rough estimates which do not depend on the dimension of the space $d$ and radius $r$. It is clear that the desired values are growing monotonically as $r$ growing and if we put $r ge 2$, then $v_1, dots, v_M$ are uniformly distributed inside the ball $B(0, 1)$. So, $u, v_1, dots, v_M$ are i.i.d. and uniformly distributed in $B(0, 1)$. The rigorous definition of the value that I need to estimate (up to a scaling factor of the volume of unit ball):
$$ mathbb{E}_{u, v_1, dots, v_M} (mathbb{P}{ q~text{belongs to the Voronoi cell of}~u | q sim U(B(0,1))}) $$
It is clear that $mathbb{P}{ q~text{belongs to the Voronoi cell of}~u | q sim U(B(0,1))}$ = $mathbb{P}{ q~text{belongs to the Voronoi cell of}~v_i | q sim U(B(0,1))}$, so the expectations of all volumes are equal and the sum of all volumes is equal to $1$. Hence
$$ mathbb{E}_{u, v_1, dots, v_M} (mathbb{P}{ q~text{belongs to the Voronoi cell of}~u | q sim U(B(0,1))}) = frac{1}{M+1}$$
It remains only to multiply it by the volume of unit ball.

But as $r$ becomes less than $2$ the volume decreases, so would like to obtain estimates which take it into account. Moreover, I performed numerical experiments which shows that the estimation also should depends on the dimension of the space $d$. Here is normal and log scale plots ($M = 10$):

In the more general case when $r < 2$ we still have that $mathbb{P}{ q~text{belongs to the Voronoi cell of}~v_j | q sim U(B(0,1))}$ = $mathbb{P}{ q~text{belongs to the Voronoi cell of}~v_k | q sim U(B(0,1))}$ and the sum of such probabilities for $u$ and $v_1, dots, v_M$ is equal to $1$, so we have:
$$ mathbb{E}_{u, v_1, dots, v_M} (mathbb{P}{ q~text{belongs to the Voronoi cell of}~u | q sim U(B(0,1))}) + M mathbb{E}_{u, v_1, dots, v_M} (mathbb{P}{ q~text{belongs to the Voronoi cell of}~v_1 | q sim U(B(0,1))}) = 1$$

If we were able to find another equation or estimation on the ratio of volumes, then the problem would be solved.

I would very appreciate any your help, ideas, papers, books and so on. Thank you for your help!

UPD: Also it is possible to directly write down the required value as an integral. It is easy to see that the probability $mathbb{P}(rho(q, u) < rho(q, v_i))$ correspond to the volume of spherical cap, it only remains to find the height of this spherical cap. My calculations showed that if $|u| le |v|$ then
$$ h = 1 - dfrac{|v|^2 - |u|^2}{2|v-u|} $$
$$ mathbb{P} = 1 - frac{1}{2} I_{2h - h^2}(frac{d+1}{2}, frac{1}{2}) $$

and if $|u| ge |v|$ then
$$ h = 1 - dfrac{|u|^2 - |v|^2}{2|v-u|} $$
$$ mathbb{P} = frac{1}{2} I_{2h - h^2}(frac{d+1}{2}, frac{1}{2}) $$

where $I_x(a, b)$ is incomplete regularized beta function.

One more observation is:

$$mathbb{P}{ q~text{belongs to the Voronoi cell of}~u} = mathbb{P}(rho(q, u) < rho(q, v_i), i=1,dots,M) = prodlimits_{i=1}^{M}mathbb{P}(rho(q, u) < rho(q, v_i)) = (mathbb{P}(rho(q, u) < rho(q, v)))^M$$

since $v_1,dots,v_M$ are i.i.d.

So now we can integrate for $u$ and $v$ and obtain the desired value:

$$ frac{1}{Vol(B(0,1))} intlimits_{u in B(0,1)} Big( intlimits_{v in B(0,1) cap B(u, r), |v| le |u|} (frac{1}{2}I_{2h-h^2}(frac{d+1}{2},frac{1}{2}))^M frac{1}{Vol(B(0,1) cap B(u,r))}dv + intlimits_{v in B(0,1) cap B(u, r), |v| ge |u|} (1 - frac{1}{2}I_{2h-h^2}(frac{d+1}{2},frac{1}{2}))^M frac{1}{Vol(B(0,1) cap B(u,r))}dv Big) du,$$

where $h = 1 - frac{| |v|^2 - |u|^2 |}{2|v-u|}$

The first summand here is about $frac{1}{2^M}$ since regularized incomplete beta function is bounded by $1$, so it remains only to estimate the second summand.

If I was able to estimate the asymptotics of this integral, it would solve my problem!

Not a full solution but too long for a comment:

For $r ll 1$, volume of $B(u,r) ll$ volume of $B(0,1)$ (esp. if $d$ is high), so an approximation might be available:

(1) $P(B(u,r) subset B(0,1)) approx 1$, which enables us to simplify $B(0,1)cap B(u,r) = B(u,r)$, preserving the symmetry of the distribution of $v_i$.

(2) $P(q in B(0,1) - B(u,r)) approx 1$.

Now, $q in Voronoi(u)$ iff $forall i: dist(q,u) < dist(q,v_i)$. Assuming (1) & (2), we can say:

(3) $P(dist(q,u) < dist(q,v_i)) approx 1/2$, since about half of $B(0,1)cap B(u,r) = B(u,r)$ is closer to $q$ than $u$ is. [Consider the hyperplane through $u$ which is $perp$ to the line segment $L$ from $u$ to $q$. The hyperplane bisects $B(u,r)$ into two half-balls. Any $v_i$ in the half-ball away from $q$ satisfies $dist(q,v_i) > dist(q,u)$. In fact even in the half-ball on the same side of $q$ there are some $v_i$ satisfying $dist(q,v_i) > dist(q,u)$, but if $r ll 1$ then with high prob $r ll |L|$ i.e. $q$ is "far away" from $u$ so the approximation should be good.]

(4) $P(q in Voronoi(u)) approx 1/2^M$, since the $v_i$ are independent.

This approximation should be pretty good for $r ll 1$ and esp. at high $d$, because the ratio of volumes goes as $r^d$. E.g. you seem to have simulated the case of $r=0.1, d = 5$ and I wonder if it's accurate there. (I couldn't check the graph myself since you didn't mention what $M$ you used.)

BTW, this approximation totally ignores the part of $Voronoi(u)$ that is actually inside $B(u,r)$. Effectively we're saying any such part of the Voronoi cell will be too small to matter, and instead the expected volume is almost entirely made of the rare cases when a large portion of $B(0,1)$ is available as $Voronoi(u)$ because all the $v_i$ happen to be picked from "the other side". However, this kind of approximation may break down when $M$ is very large, as the $1/2^M$ term becomes tiny and the part of $Voronoi(u)$ inside $B(u,r)$ might become the dominant (but still very small) term.

For intermediate values of $r, d, M$, the problem seems very difficult to solve exactly, but the intuition probably still kinda holds. The key factor is probably the volume ratio $r^d$, although now that $B(u,r) cap B(0,1)$ is not a ball it significantly complicates matters. But at least this may give an idea why for higher $d$ the probability is closer to the low value ($1/2^M$) but for lower $d$ the probability is closer to the $1/(M+1)$ value.

BTW are you seriously interested in all possible $r,d,M$? If in your application you have certain ranges that are of more interest there might be better solutions / approximations available. (E.g. the case of $M=1$ might be exactly solvable...)