Differential privacy what does "where the probability is taken over the randomness used by the algorithm" mean?

Question

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?

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}$$