# Estimating population size

Let's suppose there are $n$ real numbers $a_0 < ... < a_n$ uniformly selected from interval [0, 1). If one knows $k$ numbers on consecutive positions $a_i < ... < a_{i+k-1}$ how good is $(k - 1) / (a_{i+k-1} - a_i)$ an estimator for $n$? What other estimators are possible/better?

NOTE: $n >> k$.

-
What if there are no consecutive numbers? – PEV Jan 17 '11 at 18:19
@Trevor: Edited for clarity. Does it answer your question? – Alexandru Jan 17 '11 at 18:24
How about the error margin for 95% confidence? – Alexandru Jan 17 '11 at 19:09
if we increase $n$, how does $k$ increase? – mpiktas Jan 17 '11 at 20:29
n & k are not correlated. – Alexandru Jan 17 '11 at 21:07

As in the book A First Course in Order Statistics (see, in particular, Section 2.5), let us denote by $W_{i,j:n}$ the spacing $W_{i,j:n} = U_{j:n} - U_{i:n}$, $1 \leq i < j \leq n$, where $U_{1:n} < \cdots < U_{n:n}$ are $n$ order statistics from a ${\rm uniform}(0,1)$ distribution. By equation (2.5.21) of that book, the density function of $W_{i,j:n}$ is given by $$f_{W_{i,j:n} } (w) = \frac{{n!}}{{(j - i - 1)!(n - j + i)!}}w^{j - i - 1} (1 - w)^{n - j + i} ,\;\; 0 < w < 1,$$ so that $W_{i,j:n}$ has a ${\rm Beta}(j - i,n - j + i + 1)$ distribution (which depends only on $j-i$ and not on $i$ and $j$ individually). Having the distribution of $W_{i,j:n}$, you can check how good is $\frac{{j - i}}{{U_{j:n} - U_{i:n} }}$ an estimator for $n$, which is what you asked (in different notation).

EDIT: Using the density function of $W_{i,j:n}$, one can easily calculate the bias (cf. Trevor's answer). My calculation shows that $${\rm E}\bigg[\frac{{j - i}}{{U_{j:n} - U_{i:n} }}\bigg] = \frac{{j - i}}{{j - i - 1}}n,$$ hence the estimator gets better and better as $j-i$ grows. (The expectation is infinite when $j-i=1$; cf. Dinesh's answer.)

-
+1 for the link to the book. – mpiktas Jan 17 '11 at 21:24
Thanks mpiktas. – Shai Covo Jan 17 '11 at 21:31

Are you constrained to use the estimator that you have indicated? If not, another choice for an estimator would be to form the joint pdf of $f(a_i,\dots,a_{i+k-1} \mid n)$ and use the value of $n$ that maximizes this joint pdf as your population estimator.

The joint pdf of the $k$ consecutive values is

$\begin{eqnarray} f(a_i,\dots,a_{i+k-1}) = k!{n \choose k} {{n-k} \choose {i-1}} a_i^{(i-1)} (1-a_{i+k-1})^{(n-i+1)-k} \end{eqnarray}$

This can be seen as follows - Let us say we have $n$ unordered random variables. We choose $k$ of them with order (in $k! {n \choose k}$ ways). Of the remaining $(n-k)$ variables, we choose $(i-1)$ (in ${{n-k} \choose {i-1}}$ ways) and designate them to be the first $(i-1)$ ordered variables in some order. They all are less than $a_i$ and the probability of this happening is $a_i^{i-1}$. The remaining variables we designate to be larger than the $(i+k-1)$th variable which happens with probability $(1-a_{i+k-1})^{(n-i+1-k)}$. It only remains to compute the probability that the $j$th variable takes the value $a_j$ for $i \leq j \leq i+k-1$. But this is just $F(a_j)d(a_j) = d(a_j)$ since the variables are uniformly selected from $[0,1)$.

Maximizing this as a function of $n$ is a potentially messy business. To get an idea of how good this approach is, I used Stirling's approximation for the factorials and further assumed that $n$ is much larger than $i,k$. Then, the maximizing value is approximately

$$\begin{eqnarray} \tilde{n} = \frac{i+k-1}{\log \frac{1}{1-a_{i+k-1}}} \end{eqnarray}$$

Simulations seem to suggest that this estimator is better for some parameter ranges (i.e., when $n$ is much larger than $i,k$ for ex.) while in other regimes, the estimator in the question is better (when $k,i$ can't be ignored in comparison with $n$). Even in the latter regime, it might be possible to optimize the $n$ value that maximizes the joint pdf above more carefully (without using asymptotic stuff like Stirling's) to get a better estimator. Edit: I checked in simulation that numerically maximizing the joint pdf without resorting to Stirling's approximation does give a uniformly better estimator.

Another thing I noted from the simulation is that if $k=2$, the estimator $\frac{1}{a_{i+1}-a_i}$ performs poorly. To see this, note that the distribution of $D = a_{i+1}-a_i$ is independent of $i$ and is equal to $f_D(d) = n_t(1-d)^{n_t-1}$ where $n_t$ denotes the true value of $N$. This makes the population estimator $\tilde{N}$ have the density function

$$$f_{\tilde{N}}(\tilde{n}) = \frac{n_t}{\tilde{n}^2} \left(1-\frac{1}{\tilde{n}}\right)^{n_t-1}$$$

This estimator has an unbounded expectation and thus an unbounded bias. But this is a moot point if for some reason you are constrained to use the estimator you had indicated in the question.

-
You are right. I'm not constrained to use the suggested estimator. However, I didn't understand why the estimation of n depends on i. – Alexandru Jan 17 '11 at 21:06
@Dinesh, in your joint pdf only first and the last elements are present. Is this a mistake, or is it a fact? In the latter case can you point out how did you derive it? – mpiktas Jan 17 '11 at 21:08
@Dinesh, according to the link to the book Shai gave, the joint pdf of $(a_i,a_{i+k-1})$ is governed by formula 2.3.13, so you are missing the term $(a_{i+k-1}-a_i)^k$. – mpiktas Jan 17 '11 at 21:20
@Dinesh +1, though your answer does not exactly answer OP question, you present viable way to get alternative estimate of $n$. – mpiktas Jan 17 '11 at 21:27
@mpiktas: Thanks for the +1. I missed a factor of k! in the joint pdf expression above. This is a different joint pdf from the one in 2.3.13 of the book. That expression is for the joint pdf of the 2 variables $a_i$ and $a_{i+k-1}$ alone - not for all the $k$ variables. I will edit the answer to better show how I derived it. – Dinesh Jan 17 '11 at 22:52

Let $\hat{n} = \frac{k-1}{a_{i+k-1}-a_i}$. I think you have to find $\mathbb{E}(n)- \mathbb{E}(\hat{n}) = n- \mathbb{E}(\hat{n})$ (i.e. the bias). I think the margin of error at $95 \%$ conidence would be of the following form: $$\mathbb{E}(\hat{n}) \pm \underbrace{l_{0.95}\sqrt{\text{Var}(\hat{n})}}_{\text{margin of error}}$$.

-
you use normal approximation, which comes from CLT, but $\hat{n}$ is not the sum of independent random variables. – mpiktas Jan 17 '11 at 20:19