Sample $m$ times from unknown probability distribution $p=(p\_1,p\_2,\cdots,p\_n)$, we can construct a probability distribution $q=(q\_1.q\_2,\cdots,q\_n)$.


How large $m$ should be to achieve that the probability of $||p-q||\_2<\epsilon$ is at least $1-\delta$? We are particularly interested in the case of $\delta=1/n^2$.



Reconstructing probability distribution with high probability
$\newcommand\ep{\epsilon}$
$\newcommand\ch{\operatorname{ch}}$
This answer is based on [Theorem 3 and formula (2)](https://epubs.siam.org/doi/10.1137/1130013), which yield 
$$P(|S\_m|\ge x) 
\le2\exp\Big(-tx+\sum\_{i=1}^m E(e^{t|X\_i|}-t|X\_i|-1)\Big), \tag{0}
$$
where $x$ and $t$ are any nonnegative real numbers, $S\_m:=X\_1+\dots+X\_m$, and $X\_1,\dots,X\_m$ are any independent zero-mean random vectors in any separable Hilbert space $H$ with norm $|\cdot|$. Inequality (0) is also a special case of [Theorem 3.1](https://projecteuclid.org/euclid.aop/1176988477) for martingales in $(2,D)$-smooth separable Banach spaces; note that a Hilbert space is $(2,1)$-smooth. 


In our case, let $H=\mathbb R^n$ with $|\cdot|:=\|\cdot\|\_2$ and let 
$$X\_i:=(1\_{Y\_i=1}-p\_1,\dots,1\_{Y\_i=n}-p\_n),$$
where $Y\_1,\dots,Y\_m$ are iid random variables (r.v.'s) such that $P(Y\_i=j)=p\_j$ for $j\in[n]:=\{1,\dots,n\}$ and $p\_1+\dots+p\_n=1$. Then we can write  

$$S\_m=m(q-p),$$
where $p$ and $q$ are as in the OP. 
So, for all $\ep\in(0,1/2]$ and all real $t\ge0$, 
$$P(|q-p|\ge\ep)=P(|S\_m|\ge m\ep) \\ 
\le2\exp\Big(-tm\ep+\sum\_{i=1}^m E(e^{t|X\_i|}-t|X\_i|-1)\Big). \tag{1}
$$
Next, almost surely (a.s.)
$$|X\_i|^2=\sum\_{j=1}^n1\_{Y\_i=j}-2\sum\_{j=1}^np\_j1\_{Y\_i=j}+\sum\_{j=1}^np\_j^2
\le1-2\times0+\sum\_{j=1}^np\_j^2\le2 $$
and 
$$E|X\_i|^2=1-\sum\_{j=1}^np\_j^2\le1.$$
Also, $r(u):=\frac{e^u-u-1}{u^2}$ is increasing in real $u$ (with $r(0):=1/2$), whence 
$$r(u)\le r(\sqrt 2/2)=:c=0.64\ldots$$
for $u\le\sqrt 2/2$. Letting now $t\_\*:=\frac\ep{2c}<\ep\le1/2$, we have $t\_\*|X\_i|\le\sqrt2/2$ a.s. So, a.s. for all $i\in[m]$  

$$e^{t\_\*|X\_i|}-t\_\*|X\_i|-1=r(t\_\*|X\_i|)t\_\*^2|X\_i|^2\le c t\_\*^2|X\_i|^2. 
$$
Hence, by (1), 
$$P(|q-p|\ge\ep)\le2\exp\Big(-t\_\*m\ep+\sum\_{i=1}^m c t\_\*^2E|X\_i|^2\Big) \\ 
\le2\exp(-t\_\*m\ep+mct\_\*^2)
=2\exp\Big(-\frac{m\ep^2}{4c}\Big). 
$$
So, for any $\delta>0$, 
$$P(|q-p|<\ep)\ge1-\delta
$$
if 
$$m\ge\frac{4c}{\ep^2}\,\ln\frac2\delta $$
and $\ep\in(0,1/2]$. (Replacing $1/2$ in the condition $\ep\in(0,1/2]$ by a small enough positive real number, we can replace $c$ by a constant factor however close to $1/2$.) 


