Day: August 24, 2024

Just came across this probability puzzle and try it on GPT, it uses MLE to solve it and gives a very poor estimate. The question goes like this

A bus company with bus route number starting from . Say we came across one bus with the number 60. What is a good estimate of the number of bus routes .

If we use maximum likelihood estimation, we can consider maximizing

assuming that the distribution is uniform

Since the observation is 60, has to be at least 60. Maximizing gives us 60.

This of course is a very bad estimate, intuitively, the chance of coming across the bus with the largest bus number is rather unlikely. And considering the uniform distribution, it is reasonable to assume that we come across the average instead. Consequently, since there are 59 numbers below 60, we expect .

A similar trick can be used in a more complex case. Assume that instead of observing one bus, we observe 5 buses and the largest number among all is 60. What will be a good estimate of now?

Since , we can consider the five numbers are uniformly spread to 12, 24, 36, 48, and 60. And thus should be . This is a quick estimate but is actually quite good. When , the average of the largest among 5 buses is actually 59.66, which can be estimated by the Lea code below

import lea

bus=lea.vals(*range(1,72))

bus1=bus.new()
bus2=bus.new()
bus3=bus.new()
bus4=bus.new()
bus5=bus.new()

lea.max_of(bus1,bus2,bus3,bus4,bus5).mean()

For arbitrary number of buses, we can compute the average with the function below

def average_max(N,d):
    T=0;
    for n in range(1,N+1):
        T+=n*(n**d-(n-1)**d)
    return T/(N**d)

where the code is quite easy to verify noting that the prob of getting max equal to for buses is .