Distancia mínima esperada desde un punto con densidad variable

Estoy viendo cómo la distancia euclidiana mínima esperada entre puntos aleatorios uniformes y el origen cambia a medida que aumentamos la densidad de puntos aleatorios ( puntos por unidad de cuadrado ) alrededor del origen. He logrado llegar a una relación entre los dos descritos como tales:

$$\text{Expected Min Distance} =\frac{1}{2\sqrt{\text{Density}}}$$

Se me ocurrió esto ejecutando algunas simulaciones de Monte Carlo en R y ajustando una curva manualmente (código a continuación).

Mi pregunta es : ¿podría haber derivado este resultado teóricamente en lugar de a través de la experimentación?

#Stack Overflow example
library(magrittr)
library(ggplot2)


#---------
#FUNCTIONS
#---------
#gen random points within a given radius and given density
gen_circle_points <- function(radius, density) {
  #round radius up then generate points in square with side length = 2*radius
  c_radius <- ceiling(radius)
  coords <- data.frame(
    x = runif((2 * c_radius) ^ 2 * density, -c_radius, c_radius),
    y = runif((2 * c_radius) ^ 2 * density, -c_radius, c_radius)
  )
  return(coords[sqrt(coords$x ^ 2 + coords$y ^ 2) <= radius, ])#filter in circle
}

#Example plot
plot(gen_circle_points(radius = 1,density = 200)) #200 points around origin
points(0,0, col="red",pch=19) #colour origin

#return euclidean distances of points generated by gen_circle_points()
calculate_distances <- function(circle_points) {
  return(sqrt(circle_points$x ^ 2 + circle_points$y ^ 2))
}

#find the smallest distance from output of calculate_distances()
calculate_min_value <- function(distances) {
  return(min(distances))
}


#Try a range of values
density_values <- c(1:100)

expected_min_from_density <- sapply(density_values, function(density) {
  #simulate each density value 1000 times and take an average as estimate for
  #expected minimum distance
  sapply(1:1000, function(i) {
    gen_circle_points(radius=1, density=density) %>%
      calculate_distances() %>%
      calculate_min_value()
  }) %>% mean()
})

results <- data.frame(density_values, expected_min_from_density)

#fit based off exploration
theoretical_fit <- data.frame(density = density_values, 
                              fit = 1 / (sqrt(density_values) * 2))

#plot monte carlo (black) and fit (red dashed)
ggplot(results, aes(x = density_values, y = expected_min_from_density)) +
  geom_line() + 
  geom_line(
    data = theoretical_fit,
    aes(x = density, y = fit),
    color = "red",
    linetype = 2
  )

Considere la distancia al origen de $n$ variables aleatorias distribuidas independientemente $(X_i,Y_i)$ que tienen distribuciones uniformes en el cuadrado $[-1,1]^2.$

Escritura $R_i^2 = X_i^2+Y_i^2$ para la distancia al cuadrado, la geometría euclidiana nos muestra que

$$\Pr(R_i \le r \le 1) = \frac{1}{4} \pi\, r^2$$

mientras (con un poco más de trabajo)

$$\Pr(1 \le R_i \le r \le \sqrt{2}) = \frac{1}{4}\left(\pi\, r^2 + 4\sqrt{r^2-1} - 4 r^2 \operatorname{ArcTan}\left(\sqrt{r^2-1}\right)\right).$$

Juntos, estos determinan la función de distribución común a todos los$F$$R_i.$

Debido a que los puntos son independientes, también lo son las distancias donde la función de supervivencia de es$n$$R_i,$$\min(R_i)$

$$S_n(r) = (1 - F(r))^n,$$

lo que implica que la distancia más corta media es

$$\mu(n) = \int_0^\sqrt{2} S_n(r)\, dr.$$

Para casi toda el área de esta integral está cerca de por lo que podemos aproximarla como$n\gg 1,$$0,$

$$\mu_\text{approx}(n) = \int_0^1S_n(r)\, dr = \int_0^1\left(1 - \frac{\pi}{4}r^2\right)^n\,dr.$$

El error no es mayor que la parte de la integral que se omitió, que a su vez no es mayor que

$$(\sqrt{2}-1)(1-F(1))^n = (\sqrt{2}-1)(1 - \pi/4)^n,$$

que obviamente disminuye exponencialmente con$n.$

A su vez, podemos aproximar el integrando como

$$\left(1 - \frac{\pi}{4}r^2\right)^n \approx \exp\left(-\frac{1}{2} \frac{r^2}{2/(n\pi)}\right).$$

Hasta una constante de normalización, esta es la función de densidad de una distribución Normal con media y varianza La constante de normalización que falta es$0$$\sigma^2=2/(n\pi).$

$$C(n) = \frac{1}{\sqrt{2\pi \sigma^2}} = \frac{1}{\sqrt{2\pi\ 2 / (n\pi)}} = \frac{\sqrt{n}}{2}.$$

Por lo tanto, extendiendo la integral de a (que agrega un error proporcional a ),$1$$\infty$$e^{-n}$

$$\mu_\text{approx}(n) \approx \int_0^\infty e^{-t^2/(2\sigma^2)}\,dt = \frac{1}{C(n)} \frac{1}{2} = \frac{1}{\sqrt{n}}.$$

En el proceso de obtención de esta aproximación se cometieron tres errores. Colectivamente, son como máximo del orden el error incurrido al aproximar por el gaussiano.$n^{-1},$$S_n(r)$

Esta figura representa veces la diferencia entre y veces la distancia más corta media observada en conjuntos de datos simulados separados para cada Debido a que disminuyen a medida que crece, esto es evidencia de que el error es$n$$1$$\sqrt{n}$$10^5$$n.$$n$$o(n^{-1}/\sqrt{n}) = o(n^{-3/2}).$

Finalmente, el factor en la pregunta deriva del tamaño del cuadrado:$1/2$ la densidad es el número de puntos por unidad de área y el cuadrado tiene área , de donde$n,$$[-1,1]^2$$4$

$$2\sqrt{\text{Density}} = 2\sqrt{n/4} = \sqrt{n}.$$

---

Este es el Rcódigo para la simulación:

n.sim <- 1e5  # Size of each simulation
d <- 2        # Dimension
n <- 2^(1:11) # Numbers of points in each simulation
#
# Estimate mean distance to the origin for each `n`.
#
y <- sapply(n, function(n.points) {
  x <- array(runif(d*n.points*n.sim, -1, 1), c(d, n.points, n.sim))
  mean(sqrt(apply(colSums(x^2), 2, min)))
})
#
# Plot the errors (normalized) against `n`.
#
library(ggplot2)
ggplot(data.frame(Log2.n = 1:length(n), Error=sqrt(n)* (1 - y * n^(1/d))),
       aes(Log2.n, Error)) + geom_point() + geom_smooth() 
  ylab("Error * n") + ggtitle("Simulation Means")