Distancia media más corta entre algunos puntos aleatorios de una caja

Question

Supongamos que existe una caja cuadrada de lado $m$ (medido en píxeles). Que haya $n$ puntos en esta caja, distribuidos uniformemente dentro de la caja (con coordenadas enteras, alineadas con una cuadrícula de píxeles). Si tomamos de cada punto la distancia euclidiana a su vecino más cercano, ¿cuál sería el valor esperado de esta distancia promediada sobre todos los puntos?

Mi problema actual es sobre una cuadrícula de píxeles discretos, un $m\times m$ imagen de mapa de bits, pero si eso es más fácil me conformaría con una solución continua. Una solución más general, por ejemplo, para un rectángulo en lugar de una caja cuadrada, es bienvenida, pero en este momento no es necesaria. He encontrado preguntas similares sobre el caso continuo, pero sin respuestas. Para mí no sería fácil generalizar el caso para dos puntos solamente.

Answer 1

Empíricamente está entre $\dfrac{0.5}{\sqrt{n-1}}$ y $\dfrac{0.56}{\sqrt{n-1}}$ tendiendo hacia el límite inferior a medida que $n$ aumenta. Esto no es muy diferente a poner $n-1$ puntos aleatorios en un círculo o cuadrado con área $1$ y encontrar la distancia mínima esperada al centro.

En el extremo inferior con $n=2$ la cuestión se convierte en la distancia euclidiana esperada entre dos puntos aleatorios en un cuadrado, que una respuesta anterior da como $\frac{1}{15}(2+\sqrt{2}+5\log(1+\sqrt{2})) \approx 0.5214$

Los resultados de la simulación son los siguientes, tanto directamente como multiplicando por $\sqrt{n-1}$

con valores de

n    expected dist nn     sqrt(n-1) times expected dist nn
2           0.521                   0.521
3           0.389                   0.550
4           0.322                   0.557
5           0.279                   0.558
6           0.250                   0.558
7           0.227                   0.557
8           0.210                   0.555
9           0.196                   0.553
10          0.184                   0.552
20          0.124                   0.540
50          0.075                   0.527
100         0.052                   0.519
200         0.036                   0.514
500         0.023                   0.509
1000        0.016                   0.507

---

(Ver comentarios) El código de simulación fue

set.seed(1)          # to reproduce
maxn <- 1024         # top number for n-1 neighbours 
cases <- 10^6        # simulations 
x0 <- runif(cases)   # base points  
y0 <- runif(cases)
mindistsq <- rep(Inf, cases)
emindist <- numeric(maxn)
for (i in 1:maxn){
  x <- runif(cases)  # possible neighbour
  y <- runif(cases)
  distsq <- (x0-x)^2 + (y0-y)^2
  mindistsq <- ifelse(distsq < mindistsq, distsq, mindistsq)
  emindist[i] <- mean(sqrt(mindistsq))
  }
emindistsqrtn1 <- emindist * sqrt(1:maxn)   # multiplying by sqrt(n-1)
par(mfrow=c(2,1))
plot(2:(maxn+1), emindist, xlab="number of points in square", 
                     main="Expected distance of nearest neighbour in square",
                     ylab="Expected dist nearest neighbour",
               ylim = c(0,0.6))
plot(2:(maxn+1), emindistsqrtn1 , xlab="number of points in square", 
               ylab="sqrt(n-1) times expct dist nn",
               main="sqrt(n-1) times Expected distance of nearest neighbour",
               ylim = c(0.5,0.56))
par(mfrow=c(1,1))
exn1 <- c(1:9, 19, 49, 99, 199, 499, 999)
tab <- cbind(round(emindist[exn1],3), round(emindistsqrtn1[exn1],3))  
colnames(tab) <- c("expected min","sqrt(n-1) times exp min")
rownames(tab) <- (exn1+1) 
tab

Answer 2

Para la versión continua, suponga que elige $n$ puntos al azar de $[0, 1]^2$ . Usted está tratando de encontrar $$E\left[ \frac{1}{n}\sum_{k=1}^n \min_{i, 1 \le i \le n, i \not=k}||X_k-X_i|| \right] \tag 1$$

donde cada uno de $X_i$ se eligen de forma aleatoria y uniforme entre $[0, 1]^2$ .

Como el valor esperado de una suma de variables aleatorias es igual a la suma de los valores esperados, esto se simplifica a $$ \frac{1}{n}\sum_{k=1}^n E\left[\min_{i, 1 \le i \le n, i \not=k}||X_k-X_i|| \right] \tag 2$$

Por simetría, esto es $$E\left[\min_{i, 1 \le i \le n-1}||X_n-X_i|| \right] \tag 3$$ Dejemos que $F_n(x) = P\left(\min_{i, 1 \le i \le n-1}||X_n-X_i|| > x\right)$ , que sería $1$ para $x < 0$ y $0$ para $x > \sqrt{2}$ . Entonces $(3)$ es $\int_0^{\sqrt{2}}F_n(x) dx$ . $F_n(x)$ es igual a $$P\left(||X_n-X_1|| > x\right)^{n-1} \tag 4$$

La probabilidad $P\left(||X_n-X_1|| > x\right)$ se da mediante la fórmula $(6)$ de este documento como $\int_x^{\sqrt{2}}g(t)dt$ donde $$g(x) = \begin{cases} 2x^{3}-8x^{2}+2\pi x & 0 \leq x < 1 \\ -2x^{3}-\left(2\pi+4\right)x+8x\operatorname{arccsc}\left(x\right)+8x\sqrt{x^{2}-1} & 1\leq x < \sqrt{2} \end{cases} \tag 5$$

Por lo tanto, $P\left(||X_n-X_1|| > x\right)$ viene dada por $$\begin{cases} -\frac{x^{4}}{2}+\frac{8x^{3}}{3}-\pi x^{2}+1 & 0 \leq x < 1 \\ \frac{2}{3}-\frac{4}{3}\left(2x^{2}+1\right)\sqrt{x^{2}-1}+\frac{1}{2}x^{4}+\left(2+\pi\right)x^{2}-4x^{2}\operatorname{arccsc}\left(x\right) & 1 \leq x < \sqrt{2} \end{cases} \tag 6$$

La integral $\int_0^{\sqrt{2}}P\left(||X_n-X_1|| > x\right)^{n-1}dx$ es poco probable que tenga una forma cerrada (o si la tiene, probablemente sería muy complicada). En su lugar, para una aproximación, divídela como $$\int_0^{1}P\left(||X_n-X_1|| > x\right)^{n-1}dx + \int_1^{\sqrt{2}}P\left(||X_n-X_1|| > x\right)^{n-1}dx$$

La segunda integral tiene un límite superior de $\left(\frac{19}{6}-\pi\right)^{n-1}\left(\sqrt{2}-1\right)$ que se obtiene porque cada valor de ese intervalo tiene un límite superior de $P\left(||X_n-X_1|| > 1\right)^{n-1} = \left(\frac{19}{6}-\pi\right)^{n-1}$ . La primera integral viene dada por $$\sum_{k=0}^{n-1}\sum_{m=0}^{n-k-1}\sum_{r=0}^{n-k-1}\frac{\binom{n-1}{k, m, r}}{\left(1+2k+3m+4r\right)}\left(-\pi\right)^{k}\left(\frac{8}{3}\right)^{m}\left(-\frac{1}{2}\right)^{r}$$

Numéricamente, esto se aproxima a $\frac{1}{2\sqrt{n-1}}$ pero tengo problemas para probarlo.