Average number of days to see all possible cards

Question

My father and I go to the restaurant everyday, and each one of us needs to grab a card, which has a number from 1 to 600. I thought about registering every new card we see in a list, and a question arose: "How many days, on average, would we need to see every possible card?"

• Each card has an equal probability of being chosen
• The two cards my father and I get are different

So far, I reasoned that the minimum number is 300, if it were the case that everyday we got different cards. In addition, it gets ever more harder to reach the final number of cards. When the list of seen cards is almost complete, it is more likely that we are going to draw a card that has already been seen before, and not a new one.

I coded 1000 simulations in python and this is the graph of the number of days expected to reach $n$ cards on average:

which is compatible with my reasoning, and results in an average of 2088 days for us to see each one of the 600 cards. But I would like to see a non-brute force way to derive such value.

Answer 1

Let $E_k$ be the expected number of days needed to see all cards when $k$ cards are unseen, and $N$ be the total card count. Then $E_{-1}=E_0=0$ and $$E_k=1+\left(\binom{N-k}2E_k+k(N-k)E_{k-1}+\binom k2E_{k-2}\right)\Big/\binom N2$$ $E_N$ may be easily computed using this recurrence. For $N=600$ this works out to

8811680562792459942398946258747101711876096393133977154769476674327738047674364897328983432691011862688405751916731357166104734388331528355089282222739184014648126943968991084493699738362309278580044419512610098361119484129038113839696652596911039150120983887537144163875349874748255808223097625902743818172423335386062006583188763439060477540352487897399170791765802797781451481218366968559229380559865123297655357640689131813797606942310981351167391816229887003702468658214065550812178233069632038668626978661/4214102157325039618584833864326203795997776444177870231182813656392729795772789605802732077307165602541014302980322730432077482215058464516793042569634244594830162890533802603313182085689051070210521045596971279589537297216582507288609368821092057740008461735909598505487560158947404502130949413085628364157149213652932303703915433272481718831240417233576842751450658118984157039823591959867158637197417212761707815524914107310227771047305213850150648656068313470561815204614063875022693603836462568954334528

which is equal to $2090.998327\dots$

Answer 2

If you draw with replacement instead, then this is the coupon collector's problem, which has a simple solution and is still a good approximation of your situation (since drawing the same card twice on a given day is unlikely).

The expected number of draws to get all coupons from a set of $n$ is $n\sum_{k=1}^n\frac1k\approx n \log n + \gamma n + \frac12$, where $\gamma$ is Euler's constant. For $n=600$, this is about $4185$ draws, or $2092.5$ days at two draws/day.

We can adjust this to simulate drawing without replacement on each day. Drawing two cards without replacement is equivalent to drawing with replacement until we've seen two different cards. If we do this, each draw after the first one has an $\frac{n-1}n$ chance of being different from the first, so the expected number of draws per day is $1+\frac n{n-1}=2+\frac1{n-1}$. At this rate, it takes about $4185/(2+\frac1{599})\approx2090.75$ days to see all the cards.