2
$\begingroup$

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:

Screenshot from the book

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.

$\endgroup$
2
  • 1
    $\begingroup$ I'm not sure exactly what your question is. It seems your source of confusion is about discrete versus continuous objects. Computer scientists almost exclusively study discrete objects, since computers can only work with discrete objects. Unfortunately, it is common to see a definition that assumes things are discrete without stating so and then, worse, that definition is applied to continuous objects and the reader must figure out how to interpret that. $\endgroup$
    – Thomas
    May 8, 2020 at 3:00
  • $\begingroup$ Thank you, Thomas. I admit there were more than one question and a bit vaguely formulated. But indeed, the confusion was about the $A$ domain of the random function. And it seems that $A$ is in fact considered discrete or even categorical. Another (and much better) introductory chapter link.springer.com/chapter/10.1007/978-3-319-57048-8_7 states explicitly "To avoid introducing continuous probability formalism (and to be able to discuss algorithmic issues), we will assume that X, Q, and Y are discrete." -- here X corresponds to A. $\endgroup$
    – John Doe
    May 9, 2020 at 7:24

1 Answer 1

1
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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