5
$\begingroup$

Assume last year I commuted to work in a taxi, and suppose if there are $n$ taxis in the fleet I used. If I took one of these taxis every trip at random and with replacement, then what is the number of trips I need to make in order to use every taxi in the fleet?

$\endgroup$
6
$\begingroup$

This is the coupon collector's problem.

The expected number is $$n \sum_{i=1}^n \frac{1}{i}$$ which is about $n(\log_e(n)+ \gamma) +\tfrac12$ where $\gamma \approx 0.577\ldots$ is the Euler–Mascheroni constant. But there is a wide dispersion and you will never be absolutely sure.

Then there is the issue of what "at random" means: some taxis may usually work when you are not commuting or in other parts of the city.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.