Erwarteter Mindestabstand von einem Punkt mit unterschiedlicher Dichte

Ich sehe mir an, wie sich der erwartete minimale euklidische Abstand zwischen zufällig einheitlichen Punkten und dem Ursprung ändert, wenn wir die Dichte zufälliger Punkte ( Punkte pro Quadrateinheit ) um den Ursprung erhöhen . Ich habe es geschafft, eine Beziehung zwischen den beiden als solche zu finden:

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

Ich kam darauf, indem ich einige Monte-Carlo-Simulationen in R ausführte und eine Kurve manuell anpasste (Code unten).

Meine Frage ist : Hätte ich dieses Ergebnis eher theoretisch als experimentell ableiten können?

#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
  )

Betrachten Sie den Abstand zum Ursprung von unabhängig verteilten Zufallsvariablen , die gleichmäßige Verteilungen auf dem Quadrat( X i , Y i ) [ - 1 , 1 ] 2$n$$(X_i,Y_i)$$[-1,1]^2.$

Wenn für den quadratischen Abstand , zeigt uns die euklidische Geometrie, dass$R_i^2 = X_i^2+Y_i^2$

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

während (mit etwas mehr Arbeit)

$$\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).$$

Zusammen bestimmen diese die Verteilungsfunktion , die allenR i$F$$R_i.$

Da die Punkte unabhängig sind, sind auch die Abstände unabhängig, woher die Überlebensfunktion von stammtR i , min ( R i$n$$R_i,$$\min(R_i)$

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

impliziert die mittlere kürzeste Entfernung ist

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

Für fast die gesamte Fläche in diesem Integral nahe bei daher können wir sie als annähern$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.$$

Der Fehler ist nicht größer als der Teil des Integrals, der weggelassen wurde, was wiederum nicht größer als ist

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

was offensichtlich exponentiell mit abnimmt$n.$

Wir können uns wiederum dem Integranden als annähern

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

Bis zu einer Normalisierungskonstante ist dies die Dichtefunktion einer Normalverteilung mit Mittelwert und Varianz Die fehlende Normalisierungskonstante ist$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}.$$

Erweitern des Integrals von auf (wodurch ein Fehler proportional zu ),$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}}.$$

Bei der Erlangung dieser Näherung wurden drei Fehler gemacht. Zusammen sind sie höchstens in der Größenordnung dem Fehler, der bei der Approximation von durch den Gaußschen auftritt.$n^{-1},$$S_n(r)$

Diese Figur zeigt das fache der Differenz zwischen dem fachen und dem -fachen der mittleren kürzesten Entfernung, die in separaten simulierten Datensätzen für jedes Da sie mit zunehmendem abnehmen , ist dies ein Beweis dafür, dass der Fehler$n$$1$$\sqrt{n}$$10^5$$n.$$n$$o(n^{-1}/\sqrt{n}) = o(n^{-3/2}).$

Schließlich ergibt sich der Faktor in der Frage aus der Größe des Quadrats:$1/2$ Die Dichte ist die Anzahl der Punkte pro Flächeneinheit, und das Quadrat hat die Fläche , woher$n,$$[-1,1]^2$$4$

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

---

Dies ist der RCode für die Simulation:

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")