# Batched Urn/coupon problem

The problem setting is as follows. We have an initial collection (urn?) of $$N$$ different coloured balls - say $$C$$ distinct colours. The distribution of different colors is non-uniform and unknown. In successive rounds (batches, indexed by $$i$$), we pick out a set of $$k_i$$ balls, and we get to see which colours were present in the the batch (but we don't see actual counts). The size of each batch is approximately the same, but the number of different colours observed in each batch will be different. In this setting, in batch 2, we'll see some colours that we've seen before, and some new ones. We can assume that the actual number of balls is large enough that sample with and without replacement will give equivalent results.

A standard question would be how many batches do we need to observe before we have seen all $$c$$ colours. However, both $$c$$ and $$n$$ are unknown (although we have an upper bound on $$c$$ if that helps in any way).

Therefore, what I'd like to be able to do is make an estimate of how quickly the number new colours seen in each batch will diminish as we collect batches, given that we've observed a certain number of colours in the first 3 batches.

E.g. Batch 1: I observe 971 different colours Batch 2: I observe 1003 different colours, of which 551 are new, giving 1522 colours seen Batch 3: I observe 1030 different colours, of which 442 are new, giving 1964 colours seen How many batches until I only expect to see 50 new colours in the next batch? Or 10?

• Are you looking for the expected value of the number of new colors observed in the $i$-th draw? Also, are the $k_i$ given and constant over $i$? Nov 30, 2021 at 9:15
• Yes the expected value of the number of new colors observed in the 𝑖-th draw would suffice. $k$ is neither given nor constant, however we can make a simplifying assumption that they are constant over $i$. The ratio $\frac{k}{N}$ is given (e.g. 1/100).
– tdc
Nov 30, 2021 at 16:38