How to test for differential privacy on multiple choice data?

Question

I apologize I am new to statistics so I do not know all terms and concepts.

My current algorithm for adding noise to multiple-choice favorite color data is this:

x = rand(1)
if x > .5:
    return original_color
if x < .5:
    y = rand(1)
    if y > .67:
        return "blue"
    else if y > .33:
        return "red"
    else:
        return "green"

From this I get a "private" dataset and will calculate how many people's favorite color is red.

My question is: how can I calculate whether this is differentially private? I know I need to calculate the chance that this algorithm yields any given number of reds, and the chance that a dataset with one changed row would have the same number of reds. I keep getting stuck.

Assume the original dataset has 100 rows: 50 red, 30 blue, 20 green. Then for each row there is a

.5 (chance of red) x .5(chance noise is added) x .66 (chance noise added is not red) probability that a red will be subtracted and a

.5 (chance of not red) x .5(chance noise is added) x .33 (chance noise added is red) probability that a red will be added.

How do I synthesize this information to calculate whether the algorithm is differentially private? Can anyone point me in the right direction? Furthermore, is my algorithm completely naive? Thank you!

Answer 1

You're adding noise to each data point, so you're doing local differential privacy. This means you need to consider, for each data point $i$, each output color $c$ and each pairs of colors $c_1$, $c_2$ what is the maximum ratio of:

$$ \frac{P(\text{noised_color}(i)=c|\text{original_color}(i)=c_1)}{P(\text{noised_color}(i)=c|\text{original_color}(i)=c_2)} $$

In your case, the numerator is maximized when $c=c_1$ (it's $\frac{1}{2}+\frac{1}{2}\times\frac{1}{3}=\frac{2}{3}$ — the probability of returning the true answer directly plus the probability of returning the correct answer at random), and minimal when $c\neq c_1$ (it's $\frac{1}{2}\times\frac{1}{3}=\frac{1}{6}$ — the probability of returning $c$ at random). The maximal value of the ratio is thus $4=e^{2\ln(2)}$, so your scheme is $\varepsilon$-differentially private with $\varepsilon=2\ln(2)$.