The definition of differential privacy is as follows:

A randomized mechanism $\mathcal{M}$ is $(\epsilon, \delta)$-differentially private, where $\epsilon \leq 0$ and $\delta \leq 0$, if for any database $D \in \mathcal{X}$ and $D' \in \mathcal{X}$, differing on at most one record, and for any possible output $S \subseteq Range(\mathcal{M})$, the following in-equation holds \begin{align} \Pr[\mathcal{M}(D) \in S] \leq e^{\epsilon} \cdot \Pr[\mathcal{M}(D') \in S] + \delta \end{align} where the probability is taken over the randomness used by $\mathcal{M}$.

What does the part "where the probability is taken over the randomness used by $\mathcal{M}$" mean?


1 Answer 1


So here $\mathcal{M}$ is, as you wrote, a "randomized mechanism", so it means that for one entry $D$ it can output different values. For example, you can imagine that on entry $D = 1$, $\mathcal{M}$ outputs $0$ with probability $1/4$ and $1$ with probability $3/4$. To make it more concrete, you can imagine that in order to choose which output $\mathcal{M}$ will output, $\mathcal{M}$ can have access to a coin that it can toss (or, equivalently, to a random string $r \in \{0,1\}^n$ of sufficiently large size that can represent the result of a bunch of coin tosses that was tossed before). That way, in this example, $\mathcal{M}$ can toss the coin 2 times, and chose to output $0$ iff both coins are head (or, equivalently, it can output $0$ if the first two bits of the random string $r$ are equal to $0$, and it outputs $1$ otherwise).

When we write "where the probability is taken over the randomness used by $\mathcal{M}$", it is exactly this idea that we fix $D$, $S$, and $D'$, and check what is the probability for that $\mathcal{M}$ to output an element of $S$ when given $D$ as output.

In our example, if we take $S = \{1\}$ and $D = 1$, then: $$\Pr[\mathcal{M}(D) \in S] = \Pr[\mathcal{M}(D) = 1] = \frac{3}{4}$$


Your Answer

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

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