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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.