3
$\begingroup$

We define randomized responses as follows:

In a question that can be responded with a "Yes" or "No", a respondent is asked to flip a fair coin, in secret, and answer the truth if it comes up tails. Otherwise he/she flips another coin in secret, and answers "Yes" if comes up tails, "No" otherwise.

According to the introduction this paper [1], the $\epsilon$-differential privacy of surveys relying on randomized responses is: $$ \ln(0.75/(1-0.75)) = \ln(3) $$ I am wondering how was this calculated. Note that the proofs contained in paper are related to the RAPPOR protocol.

[1]Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova,"RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response" https://research.google.com/pubs/archive/42852.pdf

$\endgroup$
  • $\begingroup$ There is a full proof in the paper, so you need to be more specific. $\endgroup$ – kodlu Feb 22 '18 at 3:50
  • $\begingroup$ The proofs contained in paper are related to the RAPPOR protocol. What I am asking is how the differential privacy of the "randomized responses" was calculated. I have edited my question accordingly. $\endgroup$ – Nikos Fotiou Feb 22 '18 at 11:09
4
$\begingroup$

I found the answer in this book https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf at page 30

Fix a respondent. A case analysis shows that $$Pr[Response = Yes|Truth = Yes] = 3/4$$ Specifically, when the truth is “Yes” the outcome will be “Yes” if the first coin comes up tails (probability 1/2) or the first and second come up heads (probability 1/4), while $$Pr[Response = Yes|Truth = No] = 1/4$$ (first comes up heads and second comes up tails; probability 1/4). Applying similar reasoning to the case of a “No” answer, we obtain: $$ \frac{Pr[Response = Yes|Truth = Yes]}{Pr[Response = Yes|Truth = No]}= \frac{3/4}{1/4}= \frac{Pr[Response = No|Truth = No]}{ Pr[Response = No|Truth = Yes]} = 3$$

$\endgroup$
  • $\begingroup$ Feel free to accept your own answer =) $\endgroup$ – Ted Mar 3 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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