<p>They use variation distance (page 8 in the linked paper), which is essentially <span class="math-container">$L_1$</span>. For two discrete distributions <span class="math-container">$\|A - B\| = \frac12\sum_{\omega \in \Omega} |A(\omega) - B(\omega)|$</span>.</p>

CC BY-SA 4.0
2024-08-20T09:55:44.450Z
2024-08-20T09:55:44.450Z
Vladimir Lysikov
<p><a href="https://arxiv.org/abs/1009.5104" rel="nofollow noreferrer">This paper</a> defines the class of sampling problems <strong>SampP</strong> (see Definition 11). It requires that the probability of the generated samples <span class="math-container">$C_x$</span> is close to the target probability <span class="math-container">$D_x$</span> within an error <span class="math-container">$\epsilon$</span>. The definition of this admissible error is:
<span class="math-container">$$ \lVert C_s - D_x \rVert \le \epsilon $$</span>
Now, what I do not clearly understand is what this norm is: <span class="math-container">$L_1$</span>, <span class="math-container">$L_2$</span>, 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?</p>

CC BY-SA 4.0
2024-08-20T09:54:57.713Z
*All* norms satisfy the triangle inequality, by definition. Anyway, the notation is defined on p. 8.
Emil Jeřábek
CC BY-SA 4.0
2024-08-20T10:02:04.517Z
Actually, the symbol is never called "norm" in the paper.
Doriano Brogioli
<cc.complexity-theory><complexity-classes><norms>
Norm in the definition of sampling computational complexity class SampP
Doriano Brogioli
# Norm in the definition of sampling computational complexity class SampP

(Asked by: username_0 on 2024-08-20)

[This paper](https://arxiv.org/abs/1009.5104) 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?

**Tags:** cc.complexity-theory, complexity-classes, norms

> **Comments:**
> **username_1**: *All* norms satisfy the triangle inequality, by definition. Anyway, the notation is defined on p. 8.  
> **username_0**: Actually, the symbol is never called "norm" in the paper.  

---

## 1 answers

### Answer by username_2 on 2024-08-20. Score: 4 | Accepted answer

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)|$.


---

