This paper defines the class of sampling problems SampP (see Definition 11). It requires that the probability of the generated samples $C_x$ is close to the target probability $D_x$ within an error $\epsilon$. The definition of this admissible error is: $$ \lVert C_s - D_x \rVert \le \epsilon $$ Now, what I do not clearly understand is what this norm is: $L_1$, $L_2$, or something else? It is not stated. There are passages relying on the triangular inequality, so I can tell that it must refer to some norm that has a triangle inequality. Do you have any suggestion?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ All norms satisfy the triangle inequality, by definition. Anyway, the notation is defined on p. 8. $\endgroup$– Emil JeřábekCommented Aug 20 at 9:54
-
$\begingroup$ Actually, the symbol is never called "norm" in the paper. $\endgroup$– Doriano BrogioliCommented Aug 20 at 10:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
They use variation distance (page 8 in the linked paper), which is essentially $L_1$. For two discrete distributions $\|A - B\| = \frac12\sum_{\omega \in \Omega} |A(\omega) - B(\omega)|$.
answered Aug 20 at 9:55