Bernie 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. When M=1 the recursion is simple enough: E(N) = 1/N + (N-1)/N * (1+E(N-1))) and it reduces fairly easily to E(N) = (N+1)/2. 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)) And I can't see how to simplify it. Am I missing something obvious, or some trick, or is this just a hard one? Thanks!!

...

<< Just to clarify a bit, my "intuition" for the answer seems straightforward: if there are M items, you'd expect them to be about equally distributed, and so you'd expect to have to go, on average, around 1/(M+1)-th of the way to hit the first on, and on average M/(M+1)-th of the way to get all of them. [and so if you were looking for five items, you'd expect to go have to check about one-sixth of them before you ran into the first one and have to go through five-sixths to find them all]. I was just trying to see if I could derive that explicitly.

...

I'm guessing that the intended question is to find the expected number of binomial trials to the first success. If so, the only relevant number here is the probability of success in each trial, p. So here, p = M/N. By definition, this expectation is E(p) = Sum{k=1..oo} k * (1-p)^(k-1) * p, i.e., = p * Sum{k=1,oo} k * q^(k-1) (where q = 1-p). = p * (d/dq)(Sum{1,oo) q^k) = p * (d/dq)(q/1-q) = p * 1/(1-q)^2 = 1/p. So here the expected number of trials to the first success is N/M. (Since 1/p is such a simple answer, I'd expect there's a much cleverer way to obtain it.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele