The unreasonable effectiveness of conditional probabilities
I find this a quite terrible explanation of a fairly simple concept, but perhaps I haven't had enough coffee. Here's an alternative try:<p>First, for the computer scientists out there, this is the Coupon Collector's problem - so you probably know already it's Θ(N log N). That doesn't give us a precise answer but it should guide our intuition - it should take <i>somewhere</i> like 4 * log(4) ~= 8 draws to get what we want. [1]<p>Being exact:<p>When you have already have 3 of the 4 toys, what's the chance you get the 4th? It's 1 in 4. The expected number of draws to get an item with P=1/4 is 4.<p>Generalizing, the expected number of tries to get an item with probability p is 1/p. When you have 2 toys, you have a 1/2 probability of getting one of the two you haven't seen already, etc. When you have no toys, you always get something you don't have.<p>So the only slightly tricky case is when you have 1 toy, where you have a 3 in 4 chance of getting something new. 1/(3/4) = 1 1/3.<p>So the answer is very simply 4 + 2 + 1 1/3 + 1 = 8.3333.<p>More on the Coupon Collector's Problem: <a href="https://en.wikipedia.org/wiki/Coupon_collector%27s_problem" rel="nofollow">https://en.wikipedia.org/wiki/Coupon_collector%27s_problem</a><p>[1] The actual bounds use ln, not log2, but from a "getting intuition" perspective log2 gets us into the right range.