I am stuck on a problem about basic probability. Suppose the day is divided into $M=24$ time slots and a person needs a taxi in one of these slots, with uniform probability. Suppose also that $N$ taxis are around for exactly one time slot, each with uniform probability and independent with respect to each other. How many taxis do I need to guarantee that the probability of a match is higher than $80\%$?
My approach up to now has been the following. $80\%$ means that I need $K = 20$ time slots occupied. How many times do I need to pick time slots until at least $K$ are covered, if $M$ are available? For example, with $N = 2$ drivers I occupy 2 slots only if they do not overlap, i.e. the probability is actually $\frac{23}{24}$ (not $1$).
I'm looking for a general formula to understand how much is $N$ if the requirement is to cover at least $K$ different slots among the available $M$. Thank you in advance for any help.
This is an instance of the Coupon collector's problem: “If each box of a brand of cereals contains a coupon, and there are $M$ different types of coupons, what is the probability that by buying $N$ boxes you can collect at least $K$ different coupons?”
Let $E(N,K)$ the event that the first $N$ taxis occupy at least $K$ different slots, and $W(N)$ be the event that the $N$-th taxi arrives at a unoccupied slot. Then $$E(N,K)=E(N-1,K)\sqcup\Big(W(N)\cap E(N-1,K-1)\setminus E(N-1,K)\Bigr),$$ which means that, for $N$ taxis to occupy at least $K$ different slots, either the first $N-1$ taxis already occupy at least $K$ different slots, or the first $N-1$ taxis occupy altogether $K-1$ different slots and the $N$-th taxi arrives at a new slot. Setting $P(N,K):=\mathbb P(E(N,K))$ and passing to probabilities, we get $$P(N,K)=P(N-1,K)+\frac{M-(K-1)}M(P(N-1,K-1)-P(N-1,K)).$$ Given that $P(N,K)=0$ for $N<K\le M$ and $P(1,0)=P(1,1)=1$, this gives you a way to compute any $P(N,K)$. With $M=24$ slots and some quick programming I found $P(46,20)\approx79\%$ and $P(47,20)\approx82\%$.