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!


1 Answer 1


As you should have suspected, there is only a thin line between what you have tried and what is rigorous.

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).$$


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.