# 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 "where the probability is taken over the randomness used by $$\mathcal{M}$$" mean?

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