Erwarteter Mindestabstand von einem Punkt mit unterschiedlicher Dichte

8

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:

Expected Min Distance=12Density

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

Geben Sie hier die Bildbeschreibung ein

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

Ein Diagramm der Dichtewerte gegen das erwartete Minimum, sowohl monte carlo als auch theoretisch

Michael Bird
quelle
Die (asymptotische) direkte Abhängigkeit von der inversen Dichte der Dichte ergibt sich leicht und unmittelbar aus Überlegungen zu den Maßeinheiten. Die einzige Frage betrifft also, warum das Vielfache1/2.
whuber
@whuber Ja, ich hatte bemerkt, dass die Einheiten gut aufgereiht waren und ja, die Frage lautet: Woher kamen die beiden?
Michael Bird
1
Die ist die Breite Ihres Quadrats. 2
whuber

Antworten:

8

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(Xi,Yi)[1,1]2.

Wenn für den quadratischen Abstand , zeigt uns die euklidische Geometrie, dassRi2=Xi2+Yi2

Pr(Rir1)=14πr2

während (mit etwas mehr Arbeit)

Pr(1Rir2)=14(πr2+4r214r2ArcTan(r21)).

Abbildung 1: Darstellung der Verteilungsfunktion

Zusammen bestimmen diese die Verteilungsfunktion , die allenR i .FRi.

Da die Punkte unabhängig sind, sind auch die Abstände unabhängig, woher die Überlebensfunktion von stammtR i , min ( R i )nRi,min(Ri)

Sn(r)=(1F(r))n,

impliziert die mittlere kürzeste Entfernung ist

μ(n)=02Sn(r)dr.

Für fast die gesamte Fläche in diesem Integral nahe bei daher können wir sie als annähernn1,0,

μapprox(n)=01Sn(r)dr=01(1π4r2)ndr.

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

(21)(1F(1))n=(21)(1π/4)n,

was offensichtlich exponentiell mit abnimmtn.

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

(1π4r2)nexp(12r22/(nπ)).

Bis zu einer Normalisierungskonstante ist dies die Dichtefunktion einer Normalverteilung mit Mittelwert und Varianz Die fehlende Normalisierungskonstante ist0σ2=2/(nπ).

C(n)=12πσ2=12π 2/(nπ)=n2.

Erweitern des Integrals von auf (wodurch ein Fehler proportional zu ),1en

μapprox(n)0et2/(2σ2)dt=1C(n)12=1n.

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.n1,Sn(r)

! [Abbildung 2: Darstellung der Simulationsfehler

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 Fehlern1n105n.no(n1/n)=o(n3/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 , wohern,[1,1]24

2Density=2n/4=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")
whuber
quelle
2
Beeindruckend! Was für eine Antwort! Vielen Dank, das ist großartig. Vielen Dank!
Michael Bird
Hallo @whuber, ich habe versucht, Ihr zu reproduzieren, und ich habe festgestellt, dass Ihre Gleichung für nicht zurückgibt, wie Ihre Grafiken zeigen. Als ich berechnet habe, habe ich die die von Ihnen angegebene Kurve angibt. Hast du einen Tippfehler gemacht? F(r)1Pr(1RirF(2)1π/4-r(rArcCos(1/r)-Pr(1Rir2)π/4r(rArcCos(1/r)11/r2)
Michael Bird
1
@ Michael Danke, es gibt einen Tippfehler - aber es ist nicht der, den Sie vorschlagen: Eines meiner " " hätte " " sein sollen . Ich habe das behoben. 4r4
whuber