In a famous book whose authors do not want the solutions of the exercises published on the web, one can find the following exercise.

Let $(X^i)_{i \in \{1,\cdots,n\}}$ be i.i.d gaussian vectors of law $\mathcal{N}(0,I_d)$, that is, each $X^i$ is a vector in $\mathbb{R}^d$, and each of its coordinates is a gaussian variable of zero mean and variance one.

Let $\mu_S := \frac{1}{n}\sum^n_{i=1} X^i$. The question is, roughly speaking: how far, in $\Vert \cdot \Vert_\infty$-norm, is $\mu_S$ away from the origin?

My attempt is the following: each coordinate of $\mu_S$ is a gaussian variable of zero mean and variance $\frac{1}{n}$ and the coordinates of $\mu_S$ are independent.

Therefore, for all $\epsilon >0$, $\mathbb{P}[\Vert \mu_S \Vert_\infty \leq \epsilon] = \mathbb{P}[\max_{k \in \{1,\cdots,k\}} \vert \frac{1}{n}\sum^n_{i=1} X^i_k \vert \leq \epsilon] = \left(\mathcal{N}(0,\frac{1}{n}) \left([-\epsilon,\epsilon]\right)\right)^d$.

We therefore get, by Chebyshev's inequality, $\mathbb{P}[\Vert \mu_S \Vert_\infty \leq \epsilon] \geq \left(1 - \frac{1}{n\epsilon^2}\right)^d$.

The authors write:

show that $O(\frac{\log d}{\epsilon^2})$ samples suffice to estimate the true mean up to error $\epsilon$ with probability $0.99$

but according to my estimate, $n$ should be of order $\frac{d}{\epsilon^2}$ to do so. Should I have used another inequality, instead of Chebyshev's?

PS: I do not know very well the tags used on this SE site, sorry about that.


1 Answer 1


Chebyshev's inequality gives bounds under the assumption that a random variable has a second moment. Intuitively, the reason why it does not give the best possible answer in your case is that Guassian random variables have much stronger restrictions on their moments than simple existence of second moment. In particular, the density of the Gaussian is of the order of $\exp\left(-\frac{x^2}2\right)$, which implies that the probability of extreme observations dies off extremely fast.

As a result, the proper inequality to use here is Hoeffding's inequality for sub-Gaussian random variables. From this, you will get that for some constant $c$, $\mathrm{Pr}[|\frac1n\sum_{i=1}^n X_k^i| >\varepsilon] \leq 2\exp\left(-c\varepsilon^2/n\right)$. Combining with the union bound, we get that $$\begin{aligned}\mathrm{Pr}\left[||\frac1n\sum_{i=1}^n X^i||_\infty >\varepsilon\right] &= \mathrm{Pr}\left[\bigcup_k |\frac1n\sum_{i=1}^n X^i_k| > \varepsilon\right]\leq \sum_{k=1}^d \mathrm{Pr}\left[|\frac1n\sum_{i=1}^n X^i_k| >\varepsilon\right] \\&\leq 2d\exp\left(-cn\varepsilon^2\right)\end{aligned}$$ This shows that to get the quantity on the LHS to be $\leq 0.01$, it suffices to solve for $n$ such that $2d\exp(-cn\varepsilon^2) \leq 0.01$, i.e. to have $-cn\varepsilon^2 + \log (2d) \leq \log(0.01)$, i.e. that $n\geq -\log(0.01) + \frac{\log(2d)}{c \varepsilon^2} = O(\log(d) /\varepsilon^2)$, as desired.

  • $\begingroup$ Neat! I actually didn't know the existence of a version of Hoeffding's inequality for such unbounded variables! Thank you very much! Let me just say that I think that your first inequality (inside the probability bracket) should be the other way. $\endgroup$
    – Plop
    Nov 2, 2022 at 8:40
  • $\begingroup$ Oh yeah, fixed now $\endgroup$ Nov 2, 2022 at 16:09

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.