# Random Points Have Constant Density. Estimate It From $n$ of Them Chosen By Proximity?

N.B. I am specifically interested in the 2D case, but I'll present the 1D case for simplicity.

I have an infinite number of points on the real line, spaced at some constant density $\rho$ (on average). The points are uniformly and independently random1. Now suppose I generate a new point $x$ (also randomly). Now, I find the $n$ closest points $y_1,y_2,\cdots,y_n$ to $x$.

The question: How can I use these $n$ points (only them, along with x) to estimate $\rho$?

One simple method is to say:$$\hat{\rho} := n / (max\{y_i\} - min\{y_i\})$$Unfortunately, while this is consistent, it is biased (the region is too small, resulting in an overestimate). Try it, for example, on evenly spaced points with $n=2$.

I am specifically looking for something better than this.

1If you don't like this, here's a more formal way. Generate any number of points uniformly at random within an interval. For a sufficiently small (related to $\rho$) subset of this region, the property is satisfied.

• Unbiased estimate of average spacing is definitely $\hat{\frac 1 \rho}=\frac R {n-3/2+(1/2)^{n-2}}$ for $n\ge 3$ and simply $R$ for $n=2$ where $R$ is range of your sample.
– A.S.
Commented Nov 17, 2015 at 11:28
• Re: your question in bold - can we use $x$ (and $n$ distances to it)? If you can, then $\hat s_b=\frac {2\max\{d(x,y_i)\}}{n}$ is a good (possibly best) unbiased estimator of average spacing $s=\frac 1 \rho$ (and it works for $n=1$ as well). If we can't, a simple $\hat \rho=\frac {n-1}R$ should take most of the bias out of the method mentioned in your question (holds exact for equally spaced points and reminds a common addition/deletion of $1-2$ "ghost" data points). Do you necessarily need an unbiased estimator (and that of $\rho$ rather than $s$)?
– A.S.
Commented Nov 17, 2015 at 17:07
• @A.S. I have clarified the question. I haven't been able to find references to any of these formulas. If you can explain your formulas (esp. $\hat{s}_b$ in your last comment in relation to mine), that sounds like an answer. Commented Nov 17, 2015 at 23:10
• I wrote the answer - the result is standard for homogeneous Poisson process. The problem becomes more interesting if $x$ is "forgotten". There might be intensity estimators but I can't come up with one.
– A.S.
Commented Nov 18, 2015 at 0:32

Let $P_t$ be the number of points in the ball of radius $t$ around $x$. Then $P_t$ is a Poisson process with intensity $2\rho$. Expected time of $n$th count is $\frac n{2\rho}$, i.e $E(y_n-x)=ns/2$ and $$\hat s_1=\frac{2\max d_i}{n}$$ is an unbiased estimator of $s$. Similarly in a $2-D$ case,
$$\hat s_2=\frac {\pi\max d_i^2}{n}$$ is an unbiased estimator of inverse intensity $\frac 1 {\rho_2}$. Notice simularity in formulas: $2\max d_i$ and describes the size of the ball centered at $x$ and passing through $y_n$ while $\pi\max d_i^2$ is area of the corresponsing circle. You can easily generalize it to $k$ dimensions: $$\hat s_n=\frac {B_k(\max d_i)}n$$ where $B_k(r)=B_k(1)r^k$ is volume of the $k$-dimensional ball of radius $r$.
There is also an unbiased estimator of intensity: $$\hat \rho_1=\frac{n-1}{2\max d_i}$$ and similarly for $k-D$: $$\hat\rho_k=\frac{n-1}{B_k(1)(\max d_i)^k}$$ but only for $n\ge 2$.
• Thanks for the answer and clear explanation. May I ask, why aren't the estimators for $\hat{\rho}_i$ and $\hat{s}_i$ pure reciprocals of each other? Commented Nov 18, 2015 at 19:35
• @imall Because the function $1/X$ is not linear. By Jensen's inequality $E(1/X)\ge 1/E(X)$ with a strict inequality for non-constant $X$. Similarly, unbiased estimator of $\rho^2$ is not simply $\hat\rho^2$. It is very common to see a "correction factor" of $\frac {n-1}n$ or similar when going from estimating a quantity to estimating its reciprocal (that's why I suggested such a correction to your initial estimator that was using $R$ without any details). As $n\to \infty$ and $\hat s$ becomes more centered around its average value, the correction factor $\to 0$.