# What does "probability space is over coin flips of algorithm M" mean?

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? Jun 27, 2016 at 15:15
• 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 :-) 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? Jun 27, 2016 at 15:44
• 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. Jun 27, 2016 at 15:48