Differential privacy what does "where the probability is taken over the randomness used by the algorithm" mean? 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 &quot;where the probability is taken over the randomness used by $\mathcal{M}$&quot; mean?
So here $\mathcal{M}$ is, as you wrote, a &quot;randomized mechanism&quot;, 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 &quot;where the probability is taken over the randomness used by $\mathcal{M}$&quot;, 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}$$