J'examine comment la distance euclidienne minimale attendue entre des points uniformément aléatoires et l'origine change à mesure que nous augmentons la densité de points aléatoires ( points par unité de carré ) autour de l'origine. J'ai réussi à trouver une relation entre les deux décrits comme tels:
J'ai trouvé cela en exécutant des simulations de Monte Carlo en R et en ajustant une courbe manuellement (code ci-dessous).
Ma question est : aurais-je pu dériver ce résultat théoriquement plutôt que par l'expérimentation?
#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
)
r
expected-value
monte-carlo
uniform
minimum
Michael Bird
la source
la source
Réponses:
Considérez la distance à l'origine den variables aléatoires distribuées indépendamment (Xje,Ouije) qui ont des distributions uniformes sur le carré [ - 1 , 1]2.
L'écritureR2je=X2je+Oui2je pour la distance au carré, la géométrie euclidienne nous montre que
tout (avec un peu plus de travail)
Ensemble, ceux-ci déterminent la fonction de distribution commune à tous lesF Rje.
Parce que les points sont indépendants, les distances le sont où la fonction de survie de estn Rje, min (Rje)
impliquant la distance la plus courte moyenne est
Pour presque toute l'aire de cette intégrale est proche de nous pouvons donc l'approcher commen ≫ 1 , 0 ,
L'erreur n'est pas supérieure à la partie de l'intégrale qui a été omise, qui n'est à son tour pas supérieure à
ce qui diminue évidemment exponentiellement avecn .
On peut à son tour approximer l'intégrale comme
Jusqu'à une constante de normalisation, il s'agit de la fonction de densité d'une distribution normale avec une moyenne de et une variance La constante de normalisation manquante est0 σ2= 2 / ( n π) .
Par conséquent, l'extension de l'intégrale de1 à (ce qui ajoute une erreur proportionnelle à ),∞ e- n
Dans le processus d'obtention de cette approximation, trois erreurs ont été commises. Collectivement, ils sont au plus d'ordren- 1, l'erreur encourue lors de l'approximation de par le gaussien.Sn( r )
Cette figure représente fois la différence entre et fois la distance moyenne la plus courte observée dans ensembles de données simulés distincts pour chaquen 1 n--√ dix5 n . Parce qu'ils diminuent à mesure que croît, cela prouve que l'erreur estn o (n- 1/n--√) = o (n- trois / deux) .
Enfin, le facteur dans la question découle de la taille du carré:1 / 2 la densité est le nombre de points par unité de surface et le carrén , [ - 1 , 1]2 a la surface , d'où4
Voici le
R
code de la simulation:la source