Warner's randomized response

An example of an algorithm which is locally differentially private (local differential privacy) is Warner’s method for survey responses. The idea is to enable respondents to answer potentially sensitive survey questions while maintaining plausible deniability.

Consider a survey with a sensitive yes/no question and fix some $r\in (0,1]$. The respondent answers truthfully with probability $r$, otherwise flips an unbiased coin. That is, the privatized response is

$$Z\sim \{\begin{array}{ll}X,& \text{w.p. }r\\ Y\sim \text{Bernoulli(1/2)},& \text{w.p }1-r\end{array}$$

Note that $\mathbb{P}(Z=z|X=x)=r1(z=x)+(1-r)/2$. Therefore,

${\max }_z{\max }_x\frac{\mathbb{P}(Z|X=x)}{\mathbb{P}(Z|X=x^{\prime })}={\max }_x{\max }_z\frac{r1(z=x)+(1-r)/2}{r1(z=x^{\prime })+(1-r)/2}=1+\frac{2r}{1-r}.$

If we set $ϵ=\log (1+2r/(1-r))$, we see that Warner’s randomized response is $ϵ$-locally differentiably private.

\newcommand{\eps}{\epsilon} \newcommand{\ind}{\mathbf{1}}