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.