# Estimate the nearest of N random points in a box in E^d?

I have N uniform-random points $p_j$ in a box in $E^d$, $a_i \le x_i \le b_i$, and want to estimate the expected distance of the point nearest the origin in $L_q$:

$\quad$ nearest( points $p_j$, box $a_i .. b_i$, $q$ ) $\;\equiv\;$ $\min_{j=1..N}$ $\sum_{i=1..d}$ |$p_{ji}|^q$

The box might straddle 0 in some dimensions, $a_i < 0 < b_i$.
Also I'd like the estimator to work for $0 < q < 1$ too, the "fractional metric".

(16 March) Let's try to do a simpler case: $L_1$, unit cube 0 $\le x_i \le$ 1.
Geometrically, we want (correct me) the diagonal slice of the unit cube with volume $\frac{1}{N+1}$.
(Does anyone have a picture or applet of a 3d cube sliced into equal-volume slices ?)

If d is big enough for a central limit theorem to hold,
$\quad \sum_{i=1..d} uniform_i \ \sim\ \mathcal{N}( \frac{d}{2}, \frac{d}{12} )$;
so $\mathcal{N}^{-1}( \frac{1}{N+1} )$ gives approximately the cut, and the expected nearest distance, that I want.

In Python with scipy.stats, this is

def cutcube( dim, vol ):
""" cut a slice of the unit cube in E^dim with volume vol
normal approximation: cutcube( 3, 1/6 ) = .339 ~ 1/3
vol 1/(N+1) -> E nearest of N random points in the cube ?
"""
return norm.ppf( vol, loc=dim/2, scale=np.sqrt( dim/12 )) / dim

cutcube( dim=2, vol=1/10 ) = 0.24
cutcube( dim=4, vol=1/10 ) = 0.32
cutcube( dim=8, vol=1/10 ) = 0.37
cutcube( dim=16, vol=1/10 ) = 0.41
cutcube( dim=32, vol=1/10 ) = 0.43

-
Do you need the expected distance? Its distribution? The first few moments? –  whuber Mar 14 '11 at 4:46

First, here are some commonly known facts which will be useful. Suppose i.i.d $X_1, \cdots, X_n$ have the cumulative distribution function $F(X) = P[X \leq x]$, then cumulative distribution function of $\min X_i$ is $G(X) = 1-(1-F(X))^n.$ The expected value of a nonnegative random variable in terms of its cdf is $E[X] = \int_0^\infty G(x) dx$. The median is $G^{-1}(1/2)$.

In this problem, the cdf of the distance from the center is

$$F(r) = P[|X| \leq r] = \frac{vol(B_q(r) \cap E^d)}{vol(E^d)}$$

where $B_q(r) = \{x: |x| \leq q\}$ and $vol(S)$ denotes the volume (Lesbesgue measure) of $S$.

The tricky part is evaluating $vol(B_q(r) \cap E^d)$. We will deal with the special case that $a_i \geq 0$ for $1 \leq i \leq d$. The general case follows from subdividing $E^d$ by quadrant.

Since we are working with the $q$-norm, it will be invaluable to do a change of coordinates, letting $y_i = x_i^q$. (Remember that we are assuming that the $x_i$ are nonnegative.) Then we have $\frac{dy_i}{dx_i} = qx_i^{q-1}$, so $$dx_i = q^{-1} x_i^{1-q}dy_i = (1/q) y_i^{(1-q)/q} dy_i.$$

For notational clarity, we illustrate the calculation for $d=2$, and for general $d$ our methods should extend in the obvious way.

Assuming that $|(a_1, a_2)| \leq r$, we have $$vol(B_q(r) \cap E^d) = \int_{a_1}^{\min(b_1, r^q)} \int_{a_2}^{\min(b_2, r^q - y_1)} (1/q) y_2^{(1-q)/q} dy_2 (1/q) y_1^{(1-q)/q} dy_1$$ $$= (1/q)^2 \int_{a_1}^{\min(b_1, r^q)} \int_{a_2}^{\min(b_2, r^q - y_1)} y_2^{(1-q)/q} dy_2 y_1^{(1-q)/q} dy_1$$ $$=(1/q)^2 \int_{a_1}^{\min(b_1, r^q)} q [\min(b_2, r^q - y_1)^{1/q} - a_2^{1/q}]y_1^{(1-q)/q} dy_1$$ $$=(1/q) \int_{a_1}^{\min(b_1, r^q)} [\min(b_2, r^q - y_1)^{1/q} - a_2^{1/q}]y_1^{(1-q)/q} dy_1$$

We will want to split the preceding integral into the cases when $y_1 > r^q - b_2$ and $y_1 \leq r^q - b_2$. The integral in the first case is $$(1/q) \int_{a_1}^{r^q - b_2} [(r^q - y_1)^{1/q} - a_2^{1/q}]y_1^{(1-q)/q} dy_1$$ and the integral in the second case is $$(1/q) \int_{r^q - b_2}^{\min(b_1, r^q)} [b_2^{1/q} - a_2^{1/q}]y_1^{(1-q)/q} dy_1.$$

The reader is strongly advised to find a Computer Algebra System at this point.

-
+1 As you see, it can get really messy in higher dimensions. I think even your computer algebra system will choke once $d$ gets larger than 4 or 5--if it handle this problem in full generality at all. –  whuber Mar 14 '11 at 4:45