Estimar el más cercano de N puntos aleatorios en un cuadro en E ^ d?

Question

Tengo N uniforme-puntos aleatorios $p_j$ en un cuadro en $E^d$, $a_i \le x_i \le b_i$, y queremos estimar la espera de la distancia del punto más cercano al origen en $L_q$:

$\quad$ más cercano( puntos $p_j$, cuadro de $a_i .. b_i$, $q$ ) $\;\equiv\;$ $\min_{j=1..N}$ $\sum_{i=1..d}$ |$p_{ji}|^q$

La caja podría straddle 0 en algunas dimensiones, $a_i < 0 < b_i$.
También me gustaría que el estimador de trabajar para$0 < q < 1$, la "fraccional métrica".

(16 de Marzo) Vamos a tratar de hacer un caso más sencillo: $L_1$, de la unidad de cubo 0 $\le x_i \le$ 1.
Geométricamente, queremos (me corrija) el corte diagonal de la unidad de cubo de volumen,$\frac{1}{N+1}$.
(¿Alguien tiene una foto o un applet de un cubo 3d en rodajas en igualdad de volumen rodajas ?)

Si d es lo suficientemente grande para un teorema del límite central para sostener,
$\quad \sum_{i=1..d} uniform_i \ \sim\ \mathcal{N}( \frac{d}{2}, \frac{d}{12} )$;
así $\mathcal{N}^{-1}( \frac{1}{N+1} )$ da aproximadamente la corte, y se espera que la más cercana a distancia, que yo quiero.

En Python con scipy.estadísticas, este es

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

Answer 1

En primer lugar, aquí están algunos de los más comúnmente conocidos los hechos que va a ser útil. Supongamos que yo.yo.d $X_1, \cdots, X_n$ tienen la función de distribución acumulativa $F(X) = P[X \leq x]$, entonces la función de distribución acumulativa de $\min X_i$ $G(X) = 1-(1-F(X))^n.$ El valor esperado de una variable aleatoria no negativa en términos de su cdf es $E[X] = \int_0^\infty G(x) dx$. La mediana es $G^{-1}(1/2)$.

En este problema, la cdf de la distancia desde el centro de es

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

donde $B_q(r) = \{x: |x| \leq q\}$ $vol(S)$ denota el volumen (Lesbesgue medida) de $S$.

La parte difícil es la evaluación de $vol(B_q(r) \cap E^d)$. Vamos a tratar con el caso especial de que $a_i \geq 0$$1 \leq i \leq d$. El caso general de la siguiente manera a partir de la subdivisión de la $E^d$ por cuadrante.

Dado que estamos trabajando con el $q$-norma, será de gran valor para hacer un cambio de coordenadas, dejando $y_i = x_i^q$. (Recuerde que estamos suponiendo que el $x_i$ son no negativos.) Luego tenemos a $\frac{dy_i}{dx_i} = qx_i^{q-1}$, por lo que $$dx_i = q^{-1} x_i^{1-q}dy_i = (1/q) y_i^{(1-q)/q} dy_i.$$

Para la anotación de la claridad, se ilustra el cálculo de $d=2$, y para general $d$ nuestros métodos deben extenderse de una manera obvia.

Suponiendo que $|(a_1, a_2)| \leq r$, tenemos $$ 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$$

Vamos a dividir la anterior integral en los casos de $y_1 > r^q - b_2$$y_1 \leq r^q - b_2$. La integral en el primer caso es $$(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$$ y la integral en el segundo caso es $$ (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. $$

El lector es muy recomendable para encontrar un Sistema de Álgebra computacional en este punto.