The question I'm referring to comes from Stack Overflow: https://stackoverflow.com/questions/8723652/estimating-number-of-results-in-google-app-engine-query

In short: With $N$ ordered samples of a uniform distribution, how to better estimated $N$ with $k$th sample info?

  1. How to compute the probability that the $k$th fall in a specify interval? For example, Is there a c.d.f for the order statistics?

  2. Is there a better way to estimate the $N$? For example, use three samples 1000th, 2000th, 3000th together?


@whuber: I have read the link you provide, but I still have some question about how to use it correctly.

The probability U(k) falling in the interval [u,u+du] is equaled to enter image description here

(from http://en.wikipedia.org/wiki/Order_statistic#The_order_statistics_of_the_uniform_distribution)

  1. Is this function a p.d.f or a c.d.f? If it is a p.d.f, could I integrate it to get a c.d.f?
  2. While N is big (for example 60000), is there any approximation I can use?
  3. Try to explain this issue more clearly:

We did N(unknown number) random samples for an uniform distribution [0,1]. These samples are collected and sorted (but we still don't know the exactly total number of them). How to guess the N based on the known kth value? For example, if the 10th sample is 0.1, we may guess the N is 10. If the 10th samples is 0.01, we may guess N is 100. But how accurate this guess will be? If I can have more info such as the 10th sample is 0.1 and 20th sample is 0.2, will that help to get better results?

  • 3
    $\begingroup$ The answer to (1) is well known and easy to find. As for the rest of the question, even after reading the SO version I cannot understand what is being asked here. Perhaps you could present a small example? $\endgroup$
    – whuber
    Commented Jan 5, 2012 at 20:29
  • 3
    $\begingroup$ I think the question is about a discrete uniform distribution. German tank problem ? $\endgroup$
    – Elvis
    Commented Jan 5, 2012 at 20:37
  • 3
    $\begingroup$ Great edit, thanks. (1) The Wikipedia expression is a pdf. Yes, you can integrate it to a cdf. (2) The distributions are Beta distributions. Provided neither $k/N$ nor $1-k/N$ is too small, use a Normal approximation. (3) The explanation helps clarify what you're doing. $\endgroup$
    – whuber
    Commented Jan 5, 2012 at 23:37