1
$\begingroup$

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$ ?

$\endgroup$
4
  • $\begingroup$ do you mean $x_i$ occurs $N_i$ times out of $N$ samples of $X$? $\endgroup$
    – kodlu
    Commented May 16, 2023 at 13:47
  • $\begingroup$ Exactly. @kodlu $\endgroup$
    – white
    Commented May 16, 2023 at 13:51
  • $\begingroup$ The latter sum is a random variable. What kind of bound on it, and in what specific sense, do you want? $\endgroup$ Commented May 16, 2023 at 13:59
  • $\begingroup$ @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$ ? $\endgroup$
    – white
    Commented May 16, 2023 at 14:10

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.