Cómo calcular la distancia esperada a un vecino más cercano en una matriz de vectores aleatorios?

Question

Veamos $k$ independiente de vectores aleatorios $x_1, x_2, \dots, x_k$ con una distribución uniforme sobre $ \left[0;1 \right]^n $. La distancia (preferiblemente de Manhattan) entre un vector arbitrario $x_a$ y su vecino más cercano entre estos vectores es una variable aleatoria. ¿Cómo podemos estimar su momenta? Especialmente el valor esperado?

Ya que no tengo idea de cómo empezar comencemos con el caso de dos vectores $a$ $b$ en dos dimensiones:

En este caso, uno es el vecino más cercano a la otra, de manera que su distancia es: $$ d \left(a, b\right) = \left | a_1 - b_1 \right | + \left | a_2 - b_2 \right | $$ Donde $a_1, a_2, b_1, b_2 \sim U \left[0;1 \right]$ y son independientes.

En este caso podemos calcular el valor esperado como una integral doble: $$ I := \iint_{\left[0;1 \right)^2}^{} \left | x - y \right | + \left | x - y \right | dxdy $$

Puesto que el integrando es simétrica a lo largo de $x = y$: $$ I = 2 \iint_{\left[0;1 \right)^2}^{} \left | x - y \right | dxdy = 4 \int_{0}^{1} \left ( \int_{0}^{x} x - y dy \right ) dx = 4 \int_{0}^{1} \frac{x^2}{2} dx = \frac{2}{3} $$

No iba a ser tan duro para extender este resultado a $n$ dimensiones. El verdadero desafío es agregar otros vectores de la imagen.

Si tenemos tres vectores $a,b,c$, $b$ $c$ tienen igual probabilidad de ser el más cercano al individuo a $a$. Podemos entonces calcular la distancia esperada como la suma ponderada de los valores esperados condicionales. $$ \frac{1}{2} E \left [ d \left( a, b \right) | b \text{ es más} \right] + \frac{1}{2} E \left [ d \left( a, c \right) | c \text{ es más} \right] $$ Tanto en $E \left [ d \left( a, b \right) | b \text{ is closer} \right]$ $E \left [ d \left( a, c \right) | c \text{ is closer} \right]$ puede ser calculada como integrales en 6 dimensiones de alguna manera.

Answer 1

Considerar la variable $D=|A-B|$ donde $A$,$B$, y iid uniforme en $[0,1]$ A continuación, $D$ tiene un triangular de densidad de $f_D(d)=2(1-d) \,[0\le d\le1]$ y la función característica

$$\psi_D(t)=\frac{2}{t^2}(1+i\, t -e^{i t})= 2\left(\frac{1}{2!}+\frac{i\,t}{3!}+\frac{(i \, t)^2}{4!}+\frac{(i \, t)^3}{5!}+\cdots \right)$$

De esto podemos obtener los primeros momentos de $D$ : $E(D)=1/3$, $E(D^2)=1/6$ o $\sigma_D^2=1/18$, etc

Luego, en $n$ dimensiones, la Manhattan de la distancia entre dos puntos está dada por la suma de $n$ variables con la densidad. La densidad resultante se obtiene por la $n$-th convolución de $f_D(d)$, y la CF como $\psi_D^n(t)$.

Dado que, se insterested en el mínimo de $k-1$ realizaciones de tales (independiente) variables. Eso es bien conocido problema.

Estos pasos le permiten obtener la densidad del vecino más cercano distancia de $x_1$, y por lo tanto los momentos. Por supuesto, todo esto no es muy straighforward para calcular, pero dudo de que hay un atajo (para obtener los primeros momentos). Tal vez para un gran $n$ y/o $k$ algunos asymptotics se puede encontrar.

Véase también la pregunta relacionada con la

Actualización: Si el número de puntos de $k$ es grande (y la dimensión $n$ no es, por lo que el punto seleccionado es, con alto probabily redondeado a partir de otros puntos, y no cerca de la caja de los bordes; en concreto, si $k > M^n$$M$ , dicen, más de 10 o 30) se puede obtener una aproximación mediante el cálculo del volumen de la "diamante" de la forma que corresponde a un almacén de Manhattan distancia (cruz polytope). Por lo tanto, si $X$ es el Manhattan de distancia del vecino más cercano, que nos iba a llegar

$$P(X \le x) \approx 1 - \left(1 - x^n \frac{2^n}{n!}\right)^{k-1}, \;\; 0\le x\le x_M=\frac{(n!)^{1/n}}{2}$$

Y así, por ejemplo, se podría aproximar $$E(X) = \int_0^\infty (1-F_X(x))\, dx \approx \int_0^{x_M} \left(1 - x^n \frac{2^n}{n!}\right)^{k-1} dx$$