Approximating distributions from samples
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$.