In the book The Algorithmic Foundations of Differential Privacy by Cynthia Dwork, Aaron Roth on page 16 (actually page 20 in the pdf viewer) it says at the very bottom of the page:

Definition 2.2 (Randomized Algorithm). A randomized algorithm ℳ with domain A and discrete range B is associated with a mapping M : A → ∆(B). On input aA, the algorithm ℳ outputs ℳ(a) = b with probability (M(a))b for each bB. The probability space is over the coin flips of the algorithm ℳ.

What does the final sentence mean?

Someone said the authors might mean that once you've performed the recipe described in that paragraph, you perform the plausible-deniability double-coin-flip trick described under 2.3 on page 15. Is that what is meant?

  • @neil-smithline thanks for the edit! The paragraph in question uses "M" in two ways and you've just changed it to the wrong one :-) would you mind terribly restoring the pseudo-LaTeX please?
    – cheater
    Jun 27, 2016 at 15:15
  • 1
    Done. Only meant to make it clearer. Sorry if I didn't. You can edit the question as well Jun 27, 2016 at 15:18
  • @NeilSmithline thank you! Didn't want to start an edit scuffle :-) It looks much more clever now than it did at first :-)
    – cheater
    Jun 27, 2016 at 15:23
  • @Anders is a probabilistic algorithm not a concept from statistics? That's why I added the tag. If you agree would you mind re-inserting it?
    – cheater
    Jun 27, 2016 at 15:44
  • 1
    It sure is. But I don't think the tag is supposed to mean mathematical statistics, but more gathering statistics about security incidents and things like that. After all, this is not a site about statistics in the mathematical sense of the word. But since there is no tag wiki, I guess it is open to interpretation.
    – Anders
    Jun 27, 2016 at 15:48

1 Answer 1


I have contacted the authors and they were very helpful. The original quote says it all:

The book is about randomized algorithms that act on data sets. You can always view these as deterministic algorithms, which take two inputs -- the data set, and also a string of random bits.

The definition of differential privacy has a probability operator, and what that remark means is that the probability is taken over the randomness of the random bit string (i.e. the internal randomness of the algorithm), holding the data set fixed.

The key to this is that the definition says: "the algorithm ℳ outputs ... with probability ...". This is a random choice, and the source of randomness is defined by the sentence "The probability space is over the coin flips of the algorithm ℳ".

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .