5
$\begingroup$

Imagine we are in the coupon collector setting: every time step we get independently one coupon out of $n$ coupons uniformly at random. However, unlike the coupon collector problem, we stop the at the time step when the number of distinct coupons seen so far equals half the total number of coupons drawn.

Put differently, imagine we have two counters $N$ and $O$ both initialized to zero; if we see a new coupon then we increment $N$ (for new) and if we see a coupon that we have seen before, we increment $O$ (for old), and we stop the day $O$ equals $N$. Question: what is the expected value of $N$ at the end of this process?

I have a back-of-the-envelope argument that shows this is $\Omega(n)$ (it also gives a good guess of what the coefficient of $n$ should be which turns out to be an irrational number close to $0.8$). However, the argument is not elegant, and the question seemed natural enough that it may have been studied before.

And indeed, I am more interested in the non-uniform distribution where coupons are generated from a distribution $(p_1 \geq p_2 \geq \cdots \geq p_n)$; the expected value of $N$ should be some function of this vector, but my argument doesn't quite lead to an answer in this setting.

Any pointers to literature/solutions would be appreciated. Thanks!

$\endgroup$
0

2 Answers 2

1
$\begingroup$

Here's a not quite complete argument:

Let $t$ be the number of (not necessarily distinct) coupons you've seen so far. For a given coupon, the probability you have not seen it so far is $(1-p_i)^t$. So the expected number of distinct coupons you've seen is $$\sum_{i=1}^n 1- (1-p_i)^t$$

In the regime where all of the $p_i$ are much much smaller than $1$ this is approximately $$\sum_{i=1}^n 1-e^{-tp_i}$$ If $t$ is large it follows from Azuma's (Mcdiarmid's) inequality that with probability $1-o(\frac{1}{n})$ the number of seen coupons is equal to $$\sum_{i=1}^n 1-e^{-tp_i} + O(\sqrt{t} \log n)$$ So, up to the error term, you're looking for when $$n-\sum_{i=1}^n e^{-tp_i} = t/2$$

If we're in the uniform case (where all of the $p_i$ are equal to $\frac{1}{n}$) and $t=cn$, this becomes $$1-e^{-c} = c/2,$$ which has solution approximately $c=1.59$ (matching the value you gave).


What's missing in the above is an analysis of the possibility that the process ends very early on, when the $\sqrt{t} \log n$ error term actually dwarfs the number of coupons seen (the later steps can be handled by the union bound, since the probability of error in an individual step is much smaller than $\frac{1}{n}$).

This is also where things break down when there are a few $p$ values that are not small. Say, for example, $p_1=\frac{1}{3}$ but the remaining values are all very close to $0$. Then there's a positive probability that the process stops after $2$ steps (because we drew the first coupon twice in a row). But there's also a positive probability that the process continues for a long time.

$\endgroup$
0
$\begingroup$

Here is a partial answer. Let $s(n,t)$ denote the number of sequences of coupons that stop at time step $2t$. So for example, $s(n,1)=n$ because to stop at time $2$ you would have to draw the first coupon again at time $2$. The sequence stops after at most $2n$ steps. If you imagine continuing to draw coupons even after you are supposed to stop, then there are $n^{2n}$ equally likely sequences of length $2n$, so your desired expected value is $${1\over n^{2n}} \sum_{t=1}^n t\cdot s(n,t)\cdot n^{2n-2t}.$$ So it remains to compute $s(n,t)$. Empirically, $s(n,n)/n!$ is A107668 in the OEIS, and $$s(n,t) = \biggl({n\over n-t-1}\biggr) s(n-1,t).$$ If one could prove this then the formulas in the OEIS might let you compute your desired asymptotics.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.