I don't believe Dan. Suppose we set n=1, then it's pretty clear that we expect to collect the first element, and there is a 50% (I'm guessing) chance of replacing it with something smaller, and we can continue this argument ad infinitum and we expect to collect on average 2 elements.
So, the probability of adding an additional useful element is x (assuming we populate S with elements between 0 and 1). Unfortunately, I don't know how fast we go through x, so I can't really do the integral. I think you expect to through x at a rate of around x * (S-1)/S. This should allow for a diffeq to be solved or somesuch, but this is all just hacked together thoughts near midnight.
no subject
I don't believe Dan. Suppose we set n=1, then it's pretty clear that we expect to collect the first element, and there is a 50% (I'm guessing) chance of replacing it with something smaller, and we can continue this argument ad infinitum and we expect to collect on average 2 elements.
So, the probability of adding an additional useful element is x (assuming we populate S with elements between 0 and 1). Unfortunately, I don't know how fast we go through x, so I can't really do the integral. I think you expect to through x at a rate of around x * (S-1)/S. This should allow for a diffeq to be solved or somesuch, but this is all just hacked together thoughts near midnight.