Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to estimate the cumulative number of distinct values when sampling with replacement from a changing population of integers over time. Concretely (and forgive my awful notation here), I'm assuming that there is some initial population ($m_0 = \{0,1,2,...n_0\}$) which experiences a constant rate $d$ at which members are removed from the pool and a constant rate $a$ at which members are added. Which members are removed is random, s.t. the size of a set at some time period can be written as:$$|m_t| = |m_{t-1}| * (1 + a - d)$$

I know that for some set time period the estimated number of distinct values I see when drawing $s$ samples from a population of size $p$ is one of the solutions to the Birthday Problem, i.e.: $$p*(1-(1-1/p)^s)$$ At this point, however, I'm a little stuck. I'm tempted to try to go the route of estimating the expected number of set members not seen in a cumulative time period, and I've also been encouraged to try to solve a more incremental version of the above problem as a stepping-stone (e.g. to try and solve the case where after each sample is taken the underlying population increases by one)

At this point I've spent a good couple of hours trying to find any leads on this and haven't had much success, so any and all pointers, help, etc. would be appreciated. Thanks!

share|improve this question
If $\Sigma m_t$ is meant to denote the size of $m_t$, that's rather confusing because it looks like a sum; I'd replace it by $|m_t|$. Also, the equation seems to be wrong; why should the size of the set be $0$ if the rates are the same? –  joriki Dec 6 '12 at 12:14
@joriki: I've updated the notation around the size of $m_t$; sorry for the confusion, and I've updated the equation to correctly represent the growth/death paradigm. –  Venantius Dec 6 '12 at 19:50
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.