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

Improve this question
$\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$
    – Iosif Pinelis
    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

Reset to default
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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .