The randomized response protocol is an algorithm originally used to survey people for sensitive true/false questions. The goal is to ensure plausible deniability—that if someone knew our survey response, they can't make any immediate conclusions.

To do this, we follow the below procedure:

1. Flip a coin. If it's heads, answer the question truthfully.
2. If it's tails, flip another coin. Answer "yes" if it's heads and "no" if it's tails.

Even though our answers are somewhat randomized, we can get the truth proportion of "yes" with some math. Let and be the true answer and "yes" and "no" be our survey results. By our coin flipping process,

If is the fraction of our population that has true yes, we have

and can solve for by computing the left hand side using survey responses.

Differential Privacy Analysis#

Randomized response is a differentially private algorithm, and we prove it below.

Consider the distribution of outputs from all participants. Let , and assuming independence across individuals,

Our dataset , and a single change to one component gives us the neighboring dataset . WLOG, let this change be between saying "yes" and the truth being yes or no. Then,

This is the proportionate change in our total dataset probabilities, so setting , we have and thus randomized response is -differentially private.

Generated Analysis#

Assume our first coin is biased; with probability , we tell the truth, and with probability , so flip the second coin. Then, we have

Applying the same analysis as above, we get the -randomized response has