Let $P=(p_1,\ldots,p_k) \in \Delta_k$ be distribution supported on set of size $k$ and let $\hat{P}_n$ be an empirical version of $P$ based on an iid sample of size $n$.

# Question

What's a good **non-asymptotic** tail-bound of the form $\text{Proba}(\|\hat{P}_n-P\|_2^2 \le \epsilon) \ge 1 - \delta$ ?

# Take 1

One may write $\hat{P}_n = (X_1/n,\ldots,X_k/n)$, where $X_j$ is the number of times $j$ was observed in the sample. It's clear that $(X_1,\ldots,X_k) \sim \text{Multinomial}(p_1,\ldots,p_k)$.

Now, $\|\hat{P}_n-P\|_2^2 = (1/n^2)\sum_{j=1}^k (X_j-np_j)^2$, and so to have $\|\hat{P}_n-P\|_2 \le \epsilon$, it suffices to have $|X_j-np_j| \le n^2\epsilon^2/k$. Noting that $X_j$ has mean $\mathbb E[X_j] = np_j$ and variance $\operatorname{Var}[X_j] =np_j(1-p_j) \le n/4$, we may apply Hoeffding's inequality to obtain that

$|X_j-np_j| \ge \epsilon$ with probability at most $2\exp(-(n^2\epsilon^2/k)/2(n/4))=2\exp(-n\epsilon^2/k)$.

A direct computation then gives
$$
\begin{split}
\text{Proba}(\|\hat{P}_n-P\|_2^2 \le \epsilon) &= \text{Proba}(\sum_{j=1}^k (X_j-np_j)^2 \le n^2\epsilon^2) \ge \text{
Proba}(|X_j-np_j| \le n^2\epsilon^2/k\;\forall j)\\
&=1-\text{Proba}(\exists j\;|X_j-np_j| \ge n^2\epsilon^2/k)\\
& \overset{(a)}{\ge} 1 - \sum_{j=1}^k\text{Proba}(|X_j-np_j| \ge n^2\epsilon^2/k)
\overset{(b)}{\ge} 1-2k\exp(-n\epsilon^2/k),
\end{split}
$$
where *(a)* is a union bound and *(b)* is Hoeffding bound obtained earlier.

**Disclaimer:** The multiplicative factor $k$ in the above bound is probably suboptimal.