Estou vendo como a distância euclidiana mínima esperada entre pontos aleatoriamente uniformes e a origem muda à medida que aumentamos a densidade de pontos aleatórios ( pontos por unidade quadrada ) ao redor da origem. Eu consegui chegar a um relacionamento entre os dois descritos como tal:
Eu vim com isso executando algumas simulações de Monte Carlo em R e ajustando uma curva manualmente (código abaixo).
Minha pergunta é : eu poderia ter derivado esse resultado teoricamente, e não através de experimentação?
#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
fonte
fonte
Respostas:
Considere a distância até a origem de variáveis aleatórias distribuídas independentemente que possuem distribuições uniformes no quadrado( X i , Y i ) [ - 1 , 1 ] 2 .n ( XEu, YEu) [ - 1 , 1 ]2.
Escrevendo para a distância ao quadrado, a geometria euclidiana nos mostra queR2Eu= X2Eu+ Y2Eu
enquanto (com um pouco mais de trabalho)
Juntos, estes determinam a função de distribuição comum a todos osF REu.
Como os pontos são independentes, assim como as distâncias onde a função de sobrevivência de én min ( R i )REu, min ( REu)
implicando a menor distância média é
Para quase toda a área nesta integral é próxima de portanto podemos aproximar isso comon » 1 , 0 ,
O erro não é maior que a parte da integral omitida, que por sua vez não é maior que
o que obviamente diminui exponencialmente comn.
Por sua vez, podemos aproximar o integrando como
Até uma constante de normalização, esta é a função de densidade de uma distribuição Normal com média e variância A constante de normalização ausente é0 σ2=2/(nπ).
Portanto, estendendo a integral de para (que adiciona um erro proporcional a ),1 ∞ e−n
No processo de obtenção dessa aproximação, três erros foram cometidos. Coletivamente, eles estão no máximo na ordem o erro incorrido ao se aproximar de pelo gaussiano.n−1, Sn(r)
Esta figura plota vezes a diferença entre e vezes a menor distância média observada em conjuntos de dados simulados separados para cada Como eles diminuem à medida que cresce, isso é evidência de que o erro én 1 n−−√ 105 n. n o(n−1/n−−√)=o(n−3/2).
Finalmente, o fator da questão deriva do tamanho do quadrado:1/2 a densidade é o número de pontos por unidade de área e o quadrado tem a área , de onden, [−1,1]2 4
Este é o
R
código para a simulação:fonte