Approximating distributions from samples One claim I find in many papers about identity testing, and closeness testing is that any distribution over $[n]$ can be approximated to within $\ell_1$ distance $\epsilon$ in $O\left(\frac{n}{\epsilon^2}\right)$ samples. 

I do not seem to be able to find a proof of this anywhere. On trying to prove it, I seem to be able to prove it if I assume that there exists $\delta&gt;0$, such that, $\min_{i \in [n]} P_i &gt; \delta$, where $P$ is the true distribution. However, I do not seem to be able to prove it in the general case.

My attempt at a proof is the following:

Let $P$ be any distribution over $[n]$. Let $X_1,X_2,\cdots,X_{\frac{n}{\epsilon^2}}$ be iid samples of $P$. Let $m=c\frac{n}{\epsilon^2}$. Define $C_i$, $1 \leq i \leq n$, as

$$C_i= \sum_{j=1}^{m} 1(X_j=i).$$

We note that $\mathbb{E}[C_i]= mP_i$.

Further from Chernoff bounding, we get that,

$$P[C_i &gt; (1+\epsilon)mP_i] \leq \exp(-\epsilon^2 \frac{mP_i}{3})= \exp(-\frac{cnP_i}{3}).$$

Similarly,
$$P[C_i &lt; (1-\epsilon)mP_i] \leq \exp(-\frac{cnP_i}{2}).$$

Thus defining $\hat{P}_i= \frac{C_i}{m}$, and $\hat{P}=(\hat{P}_1,\cdots,\hat{P}_n)$, by union bounding, we get that with probability at least $1-\sum_{i=1}^n 2\exp(- \frac{cnP_i}{3})$, we have that $||\hat{P}-P||_1 \leq \epsilon$. This gives a proof of the claim as long as there exists $\delta&gt;0$, such that, $\min_{i \in [n]} P_i &gt; \delta$ (as the probability can be made arbitrarily close to 1 by increasing the constant).

However, I do not know how I can generalise this result to the general case. I'd appreciate any help with respect to this.
I think it's a simple application of Hoeffding's inequality. Using your notation, let $Q_i = \frac1m C_i$, i.e. $Q$ is the empirical distribution that approximates $P$. The total variation distance between $P$ and $Q$, i.e. half the $\ell_1$ distance, is
$$
\max_{S \subseteq [n]} \left| \sum_{i \in S}{P_i} - \sum_{i \in S}{Q_i}\right|.
$$

Let $P(S):= \sum_{i \in S}{P_i}$ and define $Q(S)$ analogously. The expectation of $Q(S)$ is $P(S)$ and by Hoeffding, 
$$
\mathbb{P}(|Q(S) - P(S)| &gt; \epsilon) \leq 2e^{-\epsilon^2 m}
$$

If we take $m$ a large enough multiple of $n/\epsilon^2$, we have that $\mathbb{P}(|Q(S) - P(S)| &gt; \epsilon) &lt; 2^{-n}/3$ and by a union bound 

$$
\mathbb{P}(\max_S |Q(S) - P(S)| &gt; \epsilon) &lt; 1/3.
$$
So with probability at least 2/3, the total variation distance is at most $\epsilon$.