Finite-sample deviation bound of empirical distribution from true distribution 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.
 A: A self-contained proof.


*

*Step 1: $\mathbb{E} \|\hat{P}_n - P\|_2^2 \leq \frac{1}{n}$.

*Step 2: McDiarmid's inequality.


Let $X_i$ be the number of samples of $i \in \{1,\dots,k\}$. Then $X_i \sim \text{Binom}(p_i,n)$.
\begin{align*}
  \mathbb{E} \|\hat{P}_n - P\|_2^2
  &= \frac{1}{n^2} \sum_{i=1}^k \mathbb{E} \left( X_i - \mathbb{E} X_i \right)^2  \\
  &= \frac{1}{n^2} \sum_{i=1}^k \text{Var}(X_i)  \\
  &= \frac{1}{n^2} \sum_{i=1}^k n P(i) (1-P(i)) \\
  &\leq \frac{1}{n^2} \sum_{i=1}^k n P(i) \\
  &= \frac{1}{n} .
\end{align*}
Jensen's inequality now implies $\mathbb{E} \|\hat{P}_n - P\|_2 \leq \sqrt{\frac{1}{n}}$.
Now to apply McDiarmids, let $Y_j \in \{1,\dots,k\}$ be the $j$th sample, for $j=1,\dots,n$. Write $f(\vec{Y}) = \|\hat{P}_n - P\|_2$. Suppose we change $Y_j$ to $Y_j'$, changing $\hat{P}_n$ to $\hat{P}_n'$. Then the vector $v := \hat{P}_n - \hat{P}_n'$ has two nonzero entries, a $\frac{1}{n}$ and a $\frac{-1}{n}$, so $\|v\|_2 = \frac{\sqrt{2}}{n}$. By the triangle inequality,
\begin{align*}
  \left| f(\vec{Y}) - f(\vec{Y}') \right| \leq \|v\|_2 = \frac{\sqrt{2}}{n} .
\end{align*}
So McDiarmid's gives
\begin{align*}
  \Pr\left[ \|\hat{P}_n - P\|_2 \geq \sqrt{\frac{1}{n}} + \epsilon \right] \leq \exp\left(-n\epsilon^2 \right) .
\end{align*}
In particular, assume $\epsilon \geq \sqrt{\frac{1}{n}}$ and let $\alpha = (2\epsilon)^2$:

For $\alpha \geq \frac{4}{n}$,
  \begin{align*}
  \Pr\left[ \|\hat{P}_n - P\|_2^2 \geq \alpha \right] \leq \exp\left( \frac{- n \alpha}{4}\right) .
\end{align*}

I first learned of Step 1 here: https://cstheory.stackexchange.com/a/18498/8243
A: I will answer the question as stated though I am not sure you wanted to square the norm of $P_n-P$. Let $e_1,\ldots,e_k$ be the standard basis of ${\bf R}^k$. Write $\mu:=\sum_{j=1}^k p_j e_j$. Let $d_t$ be independent random variables for $t=1,\ldots,n$ with 
${\bf Pr}[d_t=(e_i-\mu)/\sqrt{n}]=p_i$ for $i=1,\ldots,k$. Then 
${\bf Pr}[\| P_n-P\|_2^2 \ge \epsilon]=  {\bf Pr}[\|\sum_{t=1}^n d_t \| \ge \sqrt{n\epsilon}]  \le 2\exp(-n\epsilon/2)$ by Theorem 3 in [1]. This avoids the dependence on $k$ in the bound.
[1] Pinelis, Iosif. "An approach to inequalities for the distributions of infinite-dimensional martingales." In Probability in Banach Spaces, 8: Proceedings of the Eighth International Conference, pp. 128-134. Birkhäuser, Boston, MA, 1992. See https://link.springer.com/chapter/10.1007/978-1-4612-0367-4_9#page-1
