# Using Chebyshev to derive an upper bound for Coupon Collecter's Problem

I'm TA'ing a course and have trouble solving an exercise.

Let $$X$$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $$n$$). Then $$E[X] = nH_n = n \ln(n) + O(n)$$ and $$\sigma^2_X = n^2 \sum_{i=1}^n \frac{1}{i^2} - nH_n$$ with $$\lim_{n \to \infty} \frac{\sigma^2_X}{n^2} = \frac{\pi^2}{6}$$. The exercise asks how Chebyshev's inequality can be used to upper bound the probability that $$X > \beta n \ln(n)$$ for some $$\beta > 1$$.

I tried this: \begin{align*} Pr[X>\beta n \ln(n)] &\leq Pr[|X-\mu_X| \geq (\beta - 1)n \ln n] \\ &\leq Pr\left[|X-\mu_X| \geq (\beta - 1) \left( \frac{\sqrt 6}{\pi} \sigma_X \right) \ln n\right] (1) \\ &\leq \frac{\pi}{6(\beta -1)^2 \ln^2 n} = O\left(\frac{1}{\ln^2n}\right) \end{align*}

where (1) follows because $$n > \frac{\sigma_X \sqrt 6}{\pi}$$. However I believe the first inequality is incorrect because I'm discarding the $$- O(n)$$ from $$\mu_X$$ in deriving an upper bound.

I also tried something else: \begin{align*} Pr[X>\beta n \ln(n)] &\leq Pr[|X-\mu_X| \geq \beta n \ln n - nH_n] \\ &\leq Pr[|X-\mu_X| \geq (\beta -1)nH_n] \\ &= Pr\left[|X-\mu_X| \geq \frac{6(\beta - 1)H_n}{\pi^2n} \left(n^2 \sum_{i=1}^\infty \frac{1}{i^2} - n H_n \right)\right] \end{align*}

but I'm not sure where to go from here. Thanks for any help!

Here it is the rigorous version of your attempt. Since $$\beta n\ln n\gt \mu_X$$ when $$n$$ is large enough, the first inequality holds for $$n$$ large enough. \begin{align*} Pr[X>\beta n \ln(n)] &\leq Pr[|X-\mu_X| \geq \beta n \ln n - \mu_X] \\ &\le \frac{\sigma_X^2}{(\beta n \ln n - \mu_X)^2}.\\ \end{align*} Now
\begin{aligned} \lim_{n\to\infty}\frac{\frac{\sigma_X^2}{(\beta n \ln n - \mu_X)^2}}{\frac1{\ln^2 n}} &=\lim_{n\to\infty}{\frac{\sigma_X^2}{n^2}}\lim_{n\to\infty}\frac{(n\ln n)^2}{(\beta n \ln n - \mu_X)^2}\\ &=\frac{\pi^2}{6}\lim_{n\to\infty}\frac{1}{(\beta - \frac{\mu_X}{n\ln n})^2}\\ &=\frac{\pi^2}{6(\beta - 1)^2}, \end{aligned} which implies $$\frac{\sigma_X^2}{(\beta n \ln n - \mu_X)^2} = O\left(\frac{1}{\ln^2n}\right).$$