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

  • $\begingroup$ There is a full proof in the paper, so you need to be more specific. $\endgroup$
    – kodlu
    Commented Feb 22, 2018 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$ Commented Feb 22, 2018 at 11:09

1 Answer 1


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$$

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

Your Answer

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

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