In Exercise 10.139, you determined the number of trials that, on average, are necessary to get…
In Exercise 10.139, you determined the number of trials that, on average, are necessary to get all 20 answers. But how likely are we to succeed with a certain number of trials?
In expectation, how many trials would we need before we found all 20 answers? (Use the result on coupon collecting from
1. Suppose we perform 200 trials. What is the probability that a particular answer (for example, “ask again later”) was never revealed in any of those 200 trials?
2. Use the Union Bound (Exercise 10.37) and the previous exercise to argue that the probability that we need more than 200 trials to see all 20 answers is less than 0.1%.