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

 A: 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.
