Coupon Collection, Poisson Distribution with Repeated Coupons

61 Views Asked by At

This is a variant of the Coupon Collector problem.

Suppose that you draw $X \sim \text{Poi}(n^2)$ coupons. How can we show, with high probability, that the same coupon was not drawn (i.e., repeated) more than $1.1n$ times? (assume that $n$ is very large).

My hunch is that we need to use some kind of bound (Chebyshev Inequality or Chernoff bound) but I'm struggling with how to get to that point.

1

There are 1 best solutions below

0
On BEST ANSWER

Consider the $i^{\text{th}}$ coupon and let $X_i$ denote the (random) number of times the $i^{\text{th}}$ coupon is drawn. Since $X \sim \text{Poi}(n^2)$, $X_i$ is also a Poisson random variable with mean $n^2 \cdot \frac{1}{n} = n$. Using the concentration inequality for Poisson random variables which states that for $Y \sim \text{Poi}(\lambda)$, $\Pr(Y > \lambda + y) \leq \exp\left( -\frac{y^2}{2(\lambda + y)}\right)$, we obtain \begin{align*} \Pr(X_i > 1.1n) \leq \exp\left( -\frac{0.01n^2}{(2 \cdot 1.1n)}\right) = \exp\left(-\frac{n}{220}\right). \end{align*}

If you want to show that this holds for all coupons, note that $X_i$'s are independent and hence union bound gives us $\Pr( \max_{i} X_i > 1.1n) \leq n \exp\left(-\frac{n}{220}\right)$, which is very small for large $n$.