You are looking for a taxi in a town where all taxis are individually numbered 1,2,3,...

probability/taxis New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

You are looking for a taxi in a town where all taxis are individually
numbered 1,2,3,... No numbers in between are missing.  How can you make
an estimation of the number of taxis from the numbers you can see on
the taxis that are passing by?

Example: If you see just one taxi, numbered 1403, then a good guess
would be 2806.  But how do you change your estimation when the second
taxi is numbered 1500?

-- Lars Lindberg <lli@sypro.cap.se>

Show solution

Assume that, if there are N taxis in the city, they are numbered 1, ...,
N, and that each taxi you see is independently randomly chosen from the
set of taxis.  Then if we use a Bayesian approach, our estimate will
depend only on the maximum taxi number we see, M say, and the number of
taxis we've seen, say k.  If we take the a priori probability of j taxis
to be proportional to 1/j^Q, then our estimated mean number of taxis
will be

(M/M^(Q+k) + (M+1)/(M+1)^(Q+k) + ...)/(1/M^(Q+k) + 1/(M+1)^(Q+k) + ...),

which will be about (1+1/(Q+k-2))M.

By proper choice of Q, we can make this estimate equal whatever we
want!  Low values of Q, close to 1, put more weight on hypothetical very
large taxi numbers, inflating the estimate, and big values of Q put very
little weight on these possibilities, deflating it.  (Values of Q less
than or equal to 1 don't make sense.)  But whatever our value of Q, as k
gets large, our estimated number of taxis will converge to M, the
maximum taxi number we've seen.

-- David Moews <dmoews@xraysgi.ims.uconn.edu>

Mark van Hoeij <hoeij@sci.kun.nl> writes:

> This problem is known in statistics. The best estimator is
> (N+1)/N * MAX_SEEN_SO_FAR.  so that would be 3/2 * 1500 = 2250.

When I tried to simulate this I found (N+2)/(N+1)*MAX_SEEN_SO_FAR to be
a better solution.

-- Lars Lindberg <lli@sypro.cap.se>