<p>If you are working with discrete probability distributions, then for any subset <span class="math-container">$S$</span> of the range, you have
<span class="math-container">$$
\Pr[\mathcal{M}(x)\in S]
= \sum_{s\in S} \Pr[\mathcal{M}(x)=s]
\leq \sum_{s\in S} e^\varepsilon  \Pr[\mathcal{M}(x')=s]
= e^\varepsilon \Pr[\mathcal{M}(x')\in S]
$$</span>
and so the second definition implies the first (and thus they are equivalent).</p>
<p>You will have some issues with <span class="math-container">$(\varepsilon,\delta)$</span>-differential privacy though, as the <span class="math-container">$\delta$</span>'s will add up.</p>
<hr />
<p><em>Technically, I guess that for both definitions you would need to write &quot;measurable&quot; wherever needed, as not all subsets/singletons may be measurable.</em></p>

CC BY-SA 4.0
2021-12-06T02:24:36.107Z
2021-12-06T03:52:31.387Z
2021-12-06T03:52:31.387Z
Clement C.
<p>Consider only <span class="math-container">$\epsilon$</span>-differential privacy. The <a href="https://www.cis.upenn.edu/%7Eaaroth/Papers/privacybook.pdf" rel="nofollow noreferrer">textbook definition</a> for this is:</p>
<p><em>Definition 1:</em> &quot;A randomized algorithm <span class="math-container">$\mathcal{M}$</span> with domain <span class="math-container">$\mathbb{N}^{|\chi|}$</span> is <span class="math-container">$\epsilon$</span>-differentially private if for all <span class="math-container">$S \subseteq Range(\mathcal{M})$</span> and for all <span class="math-container">$x, y \in \mathcal{N}^{|\chi|}$</span> such that <span class="math-container">$||x − y||_1 ≤ 1$</span>:</p>
<p><span class="math-container">$Pr[\mathcal{M}(x) \in S] ≤ \exp(\epsilon) Pr[\mathcal{M}(y) \in S]$</span>.&quot;</p>
<p>However, in some papers, the definition is (incorrectly) written as:</p>
<p><em>Definition 2:</em> &quot;A randomized...is <span class="math-container">$\epsilon$</span>-differentially private...if for all <span class="math-container">$S \in Range(\mathcal{M})$</span>...:</p>
<p><span class="math-container">$Pr[\mathcal{M}(x) = S] \leq \exp(\epsilon) Pr[\mathcal{M}(y) = S]$</span>.&quot;</p>
<p>Obviously, the second definition is meaningless given continuous probability distributions. But suppose for now that we are working with discrete distributions so that the second definition has some meaning.</p>
<p><strong>Question:</strong> In the case when we are working with discrete probability distributions, is there a problem with Definition 2? If so, what is the problem with it?</p>
<p>I seem to remember that there is still an issue with Definition 2 in the discrete case, but I've forgotten what the issue is. Please comment if any part of this question is unclear.</p>

<pr.probability><st.statistics><privacy>
Differential privacy definition: subset of range of values vs. equals a value in the range
user1246462
# Differential privacy definition: subset of range of values vs. equals a value in the range

(Asked by: username_0 on 2021-12-05)

Consider only $\epsilon$-differential privacy. The [textbook definition](https://www.cis.upenn.edu/%7Eaaroth/Papers/privacybook.pdf) for this is:

*Definition 1:* "A randomized algorithm $\mathcal{M}$ with domain $\mathbb{N}^{|\chi|}$ is $\epsilon$-differentially private if for all $S \subseteq Range(\mathcal{M})$ and for all $x, y \in \mathcal{N}^{|\chi|}$ such that $||x − y||\_1 ≤ 1$:

$Pr[\mathcal{M}(x) \in S] ≤ \exp(\epsilon) Pr[\mathcal{M}(y) \in S]$."

However, in some papers, the definition is (incorrectly) written as:

*Definition 2:* "A randomized...is $\epsilon$-differentially private...if for all $S \in Range(\mathcal{M})$...:

$Pr[\mathcal{M}(x) = S] \leq \exp(\epsilon) Pr[\mathcal{M}(y) = S]$."

Obviously, the second definition is meaningless given continuous probability distributions. But suppose for now that we are working with discrete distributions so that the second definition has some meaning.

**Question:** In the case when we are working with discrete probability distributions, is there a problem with Definition 2? If so, what is the problem with it?

I seem to remember that there is still an issue with Definition 2 in the discrete case, but I've forgotten what the issue is. Please comment if any part of this question is unclear.

**Tags:** pr.probability, st.statistics, privacy

---

## 1 answers

### Answer by username_1 on 2021-12-06. Score: 1 | Accepted answer

If you are working with discrete probability distributions, then for any subset $S$ of the range, you have
$$
\Pr[\mathcal{M}(x)\in S]
= \sum\_{s\in S} \Pr[\mathcal{M}(x)=s]
\leq \sum\_{s\in S} e^\varepsilon \Pr[\mathcal{M}(x')=s]
= e^\varepsilon \Pr[\mathcal{M}(x')\in S]
$$
and so the second definition implies the first (and thus they are equivalent).

You will have some issues with $(\varepsilon,\delta)$-differential privacy though, as the $\delta$'s will add up.

---

*Technically, I guess that for both definitions you would need to write "measurable" wherever needed, as not all subsets/singletons may be measurable.*


---

