Re: [math-fun] Expected time to get any of several hits

On Friday 25 January 2008, Bernie Cosell wrote:

I've been fiddling with the recursion for the expected number of probes [without replacement] to find any of M specific values among N objects. ... But for general M it seems a lot harder. The recursion I have is:

Em(N) = m/N + (N-m)/N * (1 + Em(N-1))

... = m/N + (N-m)/N + (N-m)/N . Em(N-1) = 1 + (N-m)/N . Em(N-1) It's pretty straightforward to unwind this in the case m=2 (you get a sum of products where most of the terms cancel, and then the sum is very easy), which leads to the conjecture Em(N) = (N+1)/(m+1) which, once made, is easy to verify by induction: base case N=m is trivial, and the induction step is simple algebra. -- g