# $L_1$ norm concentration of an empirical distribution

Suppose we have one random variable $$X$$, whose sample space is $$\mathbb{X}=\{x_1,x_2,\dots,x_m\}$$, and the size of the sample space is $$m$$. We have $$N$$ i.i.d. samples from this distribution, and $$x_i$$ occurs $$N_i$$ times out of $$N$$ samples. Then we construct such empirical distribution as $$\hat{P}(X=x_i)=\frac{N_i}{N}$$.

The question is the concentration bounds of $$L_1$$ norm of the distribution estimate error. That is to say, we have a "good event" -- the estimation error is small with a high probability, i.e., $$\mathbb{P}\{\sum_{x_i\in\mathbb{X}}|\hat{P}(X=x_i)-P(X=x_i)| \leq t\} \geq 1-\delta$$, where $$\delta$$ is a small value, and the question is what is $$t$$ ?

• do you mean $x_i$ occurs $N_i$ times out of $N$ samples of $X$? Commented May 16, 2023 at 13:47
• Exactly. @kodlu Commented May 16, 2023 at 13:51
• The latter sum is a random variable. What kind of bound on it, and in what specific sense, do you want? Commented May 16, 2023 at 13:59
• @IosifPinelis I mean concentration bound, for example like Hoeffding inequality for one-dimensional variable. Here, we want $\mathbb{P}\{\sum_{x_i\in\mathbb{X}}|\hat{P}(X=x_i)-P(X=x_i)| \leq t\} \geq 1-\delta$, where $\delta$ is a small value, and the question is what is $t$ ? Commented May 16, 2023 at 14:10

The way this is usually put, the answer is that to achieve $$\Pr[\|\hat{P}-P\|_1 \leq t] \geq 1- \delta$$, one needs a sample size $$N = \Theta\left(\frac{m + \ln(1/\delta)}{t^2}\right)$$.

The answer is the same up to constant factors for $$L_1$$ distance and total variation distance, as the first always equals twice the second.

Find a proof and discussion by Clement Canonne here: https://cstheory.stackexchange.com/a/39030/8243