1
$\begingroup$

Say you buy $m$ coupons out of $n$ possible types, and each is given you randomly with replacement. It's standard that the amount of time you need to wait to get $k$ coupons is approximately in expectation $$ n[\log (n) - \log (n - k)] $$ and inverting this you'd expect that the number of types of coupons you get after buying $m$ of them is about $$ n(1 - e^{-m/n}) $$ My question is, do you get concentration about this quantity? That is, I'm looking for a statement like: with high probability, if you buy $m$ coupons you are unlikely to be very far from having exactly $n(1 - e^{-m/n})$ distinct types of coupons. I'd be ok with a factor difference, but ideally I want to be only lower order terms away from this expectation.

$\endgroup$
  • $\begingroup$ In which $(n,m)$ regime? $\endgroup$ – Did May 19 '17 at 7:21
  • $\begingroup$ @Did I'm interested mostly in the $m \sim n$ regime. In the $m \ll n$ regime it's almost trivial to get multiplicative concentration, since you never expect more than, say, six-fold collisions for the case of $m \sim \sqrt{n}$. However I'm not sure how common collisions are so maybe that would still be interesting --- that is, the fluctuations are probably lower-order. $\endgroup$ – Julien Clancy May 19 '17 at 7:59
1
$\begingroup$

The expected distinct number collected is $$n\left(1- \left(1-\frac1n\right)^m\right)$$ which, as you say, can be close to $n\left(1- e^{-m/n}\right)$

The variance of the distinct number collected is $$n\left(1-\frac1n\right)^m + n^2\left(1-\frac1n\right)\left(1-\frac2n\right)^m - n^2\left(1-\frac1n\right)^{2m}$$ which empirically for large $m=n$ seems to be about $0.0972n$, while for large $m \approx n \log(n)$ seems to be about $1$, and for large $m\approx n H_n$ seems to be about $0.56$. For large $m \approx \sqrt{n}$, the variance seems to be about $0.5$

You could for example use the standard deviation (the square root of the variance) as a measure of spread

$\endgroup$
  • $\begingroup$ Where can I find a reference for this? $\endgroup$ – Julien Clancy May 25 '17 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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