How many gaussians to estimate the true mean? 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.
 A: 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.
