Confusing notation in the definition of differential privacy

Question

I've started looking into differential privacy from scratch following "The Algorithmic Foundations of Differential Privacy" by Dwork and Roth (freely available online). The mathematical notation is however somewhat confusing. On page 16, they define Probability simplex and Randomized algorithm as:

Is it correct that $\Delta(B)$ is a simple categorical probability distribution over $B$? Or is is something else?

Here's my reasoning:

• $B$ is a categorical random variable of cardinality $|B|$ (so having $|B|$ categories) so $\Delta(B)$ is a probability mass function, PMF (which is a discrete probability distribution function) over $B$. Why? It assigns each category from the random variable B a probability value > 0 such that the sum of all values is one.

But the second definition looks somehow under-defined:

A randomized algorithm $\mathcal{M}$ with domain $A$ and discrete range $B$ is associated with a mapping $M : A \rightarrow \Delta(B)$

• What exactly is $A$ here? It is the domain of the algorithm, but is it discrete, continuous, single-dimensional, multi-dimensional, or what? Or it doesn't matter?

On input $a \in A$, the algorithm $\mathcal{M}$ outputs $\mathcal{M}(a) = b$ with probability $(M (a))_b$ for each $b \in B$.

This notation is confusing: $(M (a))_b$ - why they index with lower-cased $b$ and what does it mean?

The probability space is over the coin flips of the algorithm $\mathcal{M}$.

Flipping a coin sounds funny in a formal definition (why not simply say "a Bernoulli distribution with $\theta = 0.5$"?). Nevertheless, the last sentence doesn't make much sense to me: what is "the probability space"?

I've looked up several other sources but they use different notation and don't even bother with these "first principles". So any explanation is much welcome.

Answer 1

I had the same problem when I was understanding this because it's not so intuitive. I will answer here in case future people had the same trouble.

1. Agree with you $\Delta B$ assigns a probability to every element of the set $B$.

2. $A$ It can be anything I assume from continuos to discrete objects.

3. $(M(a))_b$ is the probability that the mechanism outputs $b$ when the input is $a$.

4. The probability space is over the coin flips of the algorithm $\mathcal{M}$. This means you will not know before you apply the mechanism which will be the result. For example, if you toss a coin, you will know what will be the answer? No. What this space is inducing the most important, the randomness. You will see on some papers " The probability space is over the randomness of the algorithm $\mathcal{M}$", which makes more sense.

I made an example to stabilize these definitions:

• Let's consider an mechanism $\mathcal{M}$ that will find a $a$ in a list $A=\{(x_0,x_1,x_2,x_3,...,x_n): x_i=\{a,b\},n\geq 2\}$ where the half are a's and the other half are b's. With output $B=1$ if it finds an a and $B=0$ if it doesnt . This is $B=\{0,1\}$. Then the algorithm/mechanism $\mathcal{M}(x_i)=b$ with probability $(M(x_i))_b)$ which is defined by $\{(p_1,p_2)\in \mathbf{R}^2: p_1+p_2 = 1;p_1,p_2 \geq 0\}$ (Probability Simplex) . It means give a value of $p_1$ that $B=1$ happens and $p_2$ that $B=0$ happens . Who define this probabilities ?. The space of randomness, which we will never know for sure will be the result of the mecanism, because in that case wil be deterministic.