Down to the last three badges

Question

An app awards one random badge per level, uniformly from 8 badge types, independently. You currently hold 5 different badges. On average, how many more badges must you earn to collect all eight?

Accepted Answer

Only the 3 missing badges count now. Track stages by how many distinct badges you hold, from 5 to 8. With k badges in hand, a new one arrives with probability \frac{8-k}{8}, so the average wait is \frac{8}{8-k} badges per new type. Sum over k = 5,6,7: E = \frac{8}{3} + \frac{8}{2} + \frac{8}{1} = 8\left(	frac13+	frac12+1ight) = 8 	imes \frac{11}{6} = \frac{44}{3} \approx 14.67. The very last badge alone averages 8 tries, more than the other two combined. Takeaway. Extra draws to finish is \sum{j=k}^{n-1}\frac{n}{n-j}; here 5 of 8 leaves an average of \frac{44}{3} badges to go.

Down to the last three badges

Your answer

Discussion

Learn the concepts

Related questions