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.



Finite-sample deviation bound of empirical distribution from true distribution
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>


