# Minimum distance to a sampled point with given pdf

Let $f(x)>0$ be a probability density function defined on the unit square $[0,1]^2$ in $\mathbb{R}^2$. Suppose that we take $N$ independent samples, $X_1,\dots,X_N$, of $f$. Now, sample a point $Y$, UNIFORMLY, on the unit square. What's the expected distance from $Y$ to its nearest neighbor? It would seem to me that it should be something like $\frac{1}{\sqrt{N}}\int_{[0,1]^2} 1/\sqrt{f(x) }dA$. I

-
@Jennifer: the expression "$N$ independent samples $X_1,\ldots X_N$ of $f$" is not completely clear for me. Does it mean you take $N$ independent points on $[0,1]^2$ with probability $f dA$? – Alejandro Dec 10 '11 at 17:34

The heuristics behind that answer is the following. Consider the probability $P(r)$ that this distance is at least $r$. If equals $\int_Q (1-U(x,r))^N\\,dx$ where $U(x,r)=\int_{B(x,r)}f(x)\\,dx$. Now, $U(x,r)\approx \pi f(x)r^2$, and $(1-U)^N\approx e^{-NU}$, so the expectation in question is $$\int_Q \int_0^\infty (1-U(x,r))^N\\,dr\\,dx\approx\int_Q \int_0^\infty e^{-\pi Nf(x)r^2}\\,dr\\,dx= \frac 1{2\sqrt N} \int_Q f(x)^{-1/2}\\,dx$$ To make this all a rigorous large $N$ asymptotics, we need some conditions on $f$. Of course, if $f^{-1/2}$ is not integrable, the result is meaningless. However, if $f^{-1/2}\in L^1$, then $f^{-1/4}\in L^2$, so $g=M(f^{-1/4})\in L^2$ ($M$ stands for the Hardy-Littlewood maximal function) whence, by Holder, $U(x,r)\ge \pi g(x)^{-4} r^2$ and, finally $(1-U(x,r))\le e^{-\pi g(x)^{-4} r^2}$ giving us the integrable majorant. I'm cheating a bit because we should be a little bit more careful with $x$ near the boundary of the square and with large $r$, of course, but it all works out fine and I leave those details to you to figure out :).