2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @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$? $\endgroup$
    – Alejandro
    Dec 10, 2011 at 17:34

1 Answer 1

2
$\begingroup$

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 :).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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