¿Cómo se distribuye la distancia de dos puntos aleatorios en un hipercubo unitario?

Question

Dejemos que $p_1, p_2 \sim U([0, 1]^n)$ con $n \in \mathbb{N}$ sean dos puntos en el $n$ -hipercubo unitario de dimensiones uniformes muestreadas de forma independiente y aleatoria.

¿Cómo es la distancia $d(p_1, p_2) = \sqrt{\sum_{i=1}^n { \left (p_1^{(i)} - p_2^{(i)} \right )}^2}$ ¿Distribuido?

Preguntas similares

Hay preguntas en math.SE que cubren la pregunta de distancia media para $n=1$ y $n =2$ (el de $n=2$ también explica cómo )

• Una dimensión : $\frac{1}{3}$
• Dos dimensiones : sobre $0.521...$ (esto me hace suponer que la distribución no es "estándar", porque entonces la pregunta sobre la distancia media debería ser fácil de responder. ¿Se puede hacer una afirmación como "la distribución de la distancia de dos puntos es 'casi'..."?)

Answer 1

Como señaló Parcly Taxel, MathWorld tiene una página sobre Recogida de líneas en el hipercubo con muchas referencias.

Mathworld ofrece una tabla con la distancia media de los hipercubos hasta $n=8$ dimensiones. Por razones que explicaré más adelante, para grandes $n$ una buena aproximación a la media es $\sqrt{\dfrac{n}{6}-\dfrac{7}{120}}$ y no está mal para los pequeños $n$ o bien

n   Mathworld mean  sqrt(n/6-1/16)  sqrt(n/6-7/120) sqrt(n/6-1/18)
1   0.333333333       0.3227          0.3291          0.3333
2   0.521405433       0.5204          0.5244          0.5270
3   0.661707182       0.6614          0.6646          0.6667
4   0.777665654       0.7773          0.7800          0.7817
5   0.878530915       0.8780          0.8803          0.8819
6   0.968942083       0.9682          0.9704          0.9718
7   1.051583873       1.0508          1.0528          1.0541
8   1.128165340       1.1273          1.1292          1.1304

Para $n=1$ se tiene una distribución triangular para la distancia con densidad $f_{d_1}(x)=2-2d_1$ para $0 \lt x \le 1$ , dando una media de $\frac13$ , una varianza de $\frac1{18}$ y un segundo momento de $\frac1{6}$ . El cuadrado de la distancia tiene densidad $f_{d_1^2}(x)=\frac{1}{\sqrt{x}}-1$ para $0 \lt x\le 1$ , dando una media de $\frac16$ , una varianza de $\frac7{180}$ y un segundo momento de $\frac1{15}$ .

La cosa se complica para dimensiones superiores, pero (como dice Ivan Neretin) el Teorema Central del Límite nos dice que el cuadrado de la distancia es casi normalmente distribuido para grandes $n$ con la media $\frac{n}{6}$ y la varianza $\frac{7n}{180}$ . Así que podemos decir $$\dfrac{D_n^2 - \frac{n}{6}}{\sqrt{\frac{7n}{180}}} \ \xrightarrow{d}\ N(0,1)$$

De forma menos evidente, la propia distancia también es casi normalmente distribuido para grandes $n$ . En general podemos decir que si $X_1, \ldots, X_n$ son variables aleatorias i.i.d. con media finita no nula $\mu$ y la varianza $\sigma^2$ y $\displaystyle Y=\sum_{i=1}^n X_i$ y $Z=\sqrt{|Y|}$ entonces $\displaystyle \dfrac{Z - \sqrt{n |\mu|-\tfrac{\sigma^2}{4|\mu|}}}{\sqrt{\tfrac{\sigma^2}{4|\mu|}}}\ \xrightarrow{d}\ N(0,1)$ como $n$ aumenta. En este caso particular $\mu=\frac{1}{6}$ y $\sigma^2 = \frac7{180}$ como estadísticas del $1$ -cuadrado de la distancia, por lo que podemos decir $$\dfrac{D_n - \sqrt{\frac{n}{6}-\frac7{120}}}{\sqrt{\frac{7}{120}}} \ \xrightarrow{d}\ N(0,1)$$ sugiriendo una media aproximada para la distancia de $\sqrt{\frac{n}{6}-\frac7{120}}$ y la varianza aproximada de $\frac7{120}$ cuando $n$ es grande.

Las densidades reales no son sencillas analíticamente, pero el siguiente gráfico utiliza la convolución e integración numérica para ilustrar las densidades para la distancia cuando $n=1$ a $16$ y también muestra en rojo la aproximación normal cuando $n=16$ .

Para los grandes $n$ la varianza de la distancia se mantiene cerca de $\frac{7}{120}$ haciendo que la desviación estándar sea de aproximadamente $0.24$ . Por ejemplo, con un $n=2500$ hipercubo unitario dimensional, la distancia puede ser desde $0$ a $50$ pero en la gran mayoría de los casos estará entre $20$ y $21$ y en todos los casos, salvo en una ínfima proporción, estará entre $19$ y $22$ . En el análisis de datos, este maldición de la dimensionalidad significa que puede haber relativamente poca diferencia en las distancias entre diferentes pares de muestras aleatorias.