Skip to main content
MathOverflow

Return to Question

added 51 characters in body
Source Link
white
white
  • 23
  • 3

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., with probability $1-\delta$$\mathbb{P}\{\sum_{x_i\in\mathbb{X}}|\hat{P}(X=x_i)-P(X=x_i)| \leq t\} \geq 1-\delta$, whatwhere $\delta$ is a small value, and the bounds ofquestion is what is $\sum_{x_i\in\mathbb{X}}|\hat{P}(X=x_i)-P(X=x_i)|$$t$ ?

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, i.e., with probability $1-\delta$, what is the bounds of $\sum_{x_i\in\mathbb{X}}|\hat{P}(X=x_i)-P(X=x_i)|$?

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

added 8 characters in body
Source Link
white
white
  • 23
  • 3

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 there are$x_i$ occurs $N_i$ times to takeout of $x_i$$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, i.e., with probability $1-\delta$, what is the bounds of $\sum_{x_i\in\mathbb{X}}|\hat{P}(X=x_i)-P(X=x_i)|$?

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 there are $N_i$ times to take $x_i$. 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, i.e., with probability $1-\delta$, what is the bounds of $\sum_{x_i\in\mathbb{X}}|\hat{P}(X=x_i)-P(X=x_i)|$?

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, i.e., with probability $1-\delta$, what is the bounds of $\sum_{x_i\in\mathbb{X}}|\hat{P}(X=x_i)-P(X=x_i)|$?

Source Link
white
white
  • 23
  • 3

$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 there are $N_i$ times to take $x_i$. 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, i.e., with probability $1-\delta$, what is the bounds of $\sum_{x_i\in\mathbb{X}}|\hat{P}(X=x_i)-P(X=x_i)|$?