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 '16 at 15:15
  • 1
    Done. Only meant to make it clearer. Sorry if I didn't. You can edit the question as well – Neil Smithline Jun 27 '16 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 '16 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 '16 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 '16 at 15:48

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 ℳ".

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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