# Differential privacy definition: subset of range of values vs. equals a value in the range

Consider only $$\epsilon$$-differential privacy. The textbook definition 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.

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.