Reconstructing probability distribution with high probability 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$.
 A: $\newcommand\ep{\epsilon}$
$\newcommand\ch{\operatorname{ch}}$
This answer is based on Theorem 3 and formula (2), 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 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$.) 
A: Based on this cstheory post's argument from Clément Canonne[1], for $\delta = O(1)$ it suffices to draw $m = O(1/\epsilon^2)$ samples. This can be extended to show that
  $$ m = O\left(\frac{\log(1/\delta)}{\epsilon^2}\right) $$
samples suffices.
Slightly more details, which are worked out thanks to Clément / folklore in Theorem D.2 of my paper[2]: We can use the cstheory argument to show if $m \geq \frac{4}{\epsilon^2}$, then $\mathbb{E}\|p-q\|_2^2 \leq \frac{\epsilon^2}{4}$. Jensen’s gives $\mathbb{E}\|p-q\|_2 \leq \frac{\epsilon}{2}$. We can use McDiarmid's concentration inequality to show that if $m \geq \frac{4\ln(1/\delta)}{\epsilon^2}$, then $\|p-q\|_2$ is within $\frac{\epsilon}{2}$ of its expectation w.p. $1-\delta$. This combines to show $\|p-q\|_2$ is at most $\epsilon$ w.p. $1-\delta$.
It’s surprising at first that this doesn’t depend on the support size n (unlike L1 learning), which was the motivation for [2].
[1] https://cstheory.stackexchange.com/a/18498/8243
[2] https://arxiv.org/abs/1412.2314
A: I am assuming you are using the empirical distribution as in the comment by @MattF. 
This is a very broad question, and the answer changes quite a bit according to what properties the true distribution $p$ has. Note that if $\min_{i} p_i=\epsilon,$ which is very small, then you need a very large number of samples before you actually obtain the value $i,$ by sampling. If there are a few large probabilities, they will dominate the samples.
A good place to start is Valiant and Valiant's paper Instance Optimal Learning of Discrete Distributions available here. Also have a look at the references there. Most people focus on the distance $\mid\mid p-q\mid\mid_1$ which is directly related to the maximal query probability of distinguishing $p$ from $q.$ Related work includes estimating entropy and other properties of distributions.
Historically, the Good-Turing method is where all this stuff originates.
Edit: The paper by Indyk et al here seems to provide an answer which is to a question very close to your question. The techniques there should help. Basically they state that, for $\ell_2$ distance $\leq \varepsilon$ between $p$ and $q$ one needs $\widetilde{O}((n/\varepsilon)^2 \log n)$ samples and similar running time. The definition of successful approximation there is the standard one in complexity theory, of probability of error being $\leq 1/3.$ 
