MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@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 :).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.