In the setting of randomized response, there is a coordinator and a set of nn players each having a secrete bit xi∈{0,1}x_i \in \{0, 1\}. Instead of sending xix_i to the coordinator directly, the player sends a randomly perturbed version XiX_i, such that

Xi={xi,with probability 0.5+ϵxˉi,with probability 0.5−ϵ X_i = \begin{cases} x_i, \qquad \text{with probability } 0.5 + \epsilon \\ \bar{ x}_i, \qquad \text{with probability } 0.5 - \epsilon \\ \end{cases}

where ϵ∈[0,0.5]\epsilon \in [0, 0.5] and xˉi=1−xi\bar{x}_i = 1 - x_i. If ϵ=0\epsilon = 0, then the response from play ii is totally random. On the other hand, if ϵ=0.5\epsilon = 0.5, there isn't noise in XiX_i.

The coordinator would like to estimate the ratio of 11's among the xix_i's. Let

Xˉ=1n∑i∈[n]Xi. \bar{X} = \frac{1}{n} \sum_{i \in [n] } X_i.

Denote μ=1n∑i∈[n]xi\mu = \frac{1}{n} \sum_{i \in [n] } x_i the true ratio. Now

E[Xˉ]=1n∑i∈[n]E[Xi]=1n∑i∈[n][(0.5+ϵ)xi+(0.5−ϵ)xˉi]=1n∑i∈[n][2ϵxi+(0.5−ϵ)(xi+xˉi)]=1n∑i∈[n][2ϵxi+(0.5−ϵ)]=1−2ϵ2n+2ϵμ \begin{aligned} \mathbb{E} [ \bar{X} ] &= \frac{1}{n} \sum_{i \in [n] } \mathbb{E}[ X_i ] \\ &= \frac{1}{n} \sum_{i \in [n] } [ (0.5 + \epsilon) x_i + (0.5 - \epsilon )\bar{x}_i ] \\ &= \frac{1}{n} \sum_{i \in [n] } [ 2 \epsilon x_i + (0.5 - \epsilon) (x_i + \bar{x}_i) ] \\ &= \frac{1}{n} \sum_{i \in [n] } [ 2 \epsilon x_i + (0.5 - \epsilon) ] \\ &= \frac{1 - 2\epsilon }{2n} + 2\epsilon \mu \end{aligned}

and

Var[Xˉ]=1n∑i∈[n]Var[Xi]≤14n \begin{aligned} \mathbb{Var} [ \bar{X} ] = \frac{1}{n} \sum_{i \in [n] } \mathbb{Var}[ X_i ] \le \frac{1}{4n} \end{aligned}

Hence,

μ=E[12ϵ(Xˉ+2ϵ−12n)] \mu = \mathbb{E}[ \frac{1}{2\epsilon} (\bar X + \frac{2\epsilon - 1}{2n}) ]

and μ^≐12ϵ(Xˉ+2ϵ−12n)\hat \mu \doteq \frac{1}{2\epsilon} (\bar X + \frac{2\epsilon - 1}{2n}) is an unbiased estimator of μ\mu. As

Var[μ^]=14ϵ2Var[Xˉ]≤116nϵ2 \mathbb{Var}[ \hat \mu ] = \frac{1}{4 \epsilon^2 } \mathbb{Var}[\bar{X} ] \le \frac{1}{16 n \epsilon^2}

By Chebyshev's inequality,

Pr⁡[∣μ^−μ∣≥2⋅14ϵn]≤Var[μ^](2⋅14ϵn)2=12 \Pr[ |\hat \mu - \mu | \ge \sqrt{2} \cdot \frac{1 }{4\epsilon \sqrt{n} } ] \le \frac{ \mathbb{Var}[ \hat \mu ] }{ ( \sqrt{2} \cdot \frac{1 }{4 \epsilon \sqrt{n} } )^2 } = \frac{1}{2}

Or we can apply Hoeffding inequality to show that, with probability at least 1−δ1 - \delta,

∣Xˉ−E[Xˉ]∣≤log⁡2δ2n |\bar{X} - \mathbb{E} [ \bar{X} ] | \le \sqrt{ \frac{\log \frac{2}{\delta} }{2n} }

i.e.,

∣μ^−μ∣=12ϵ∣Xˉ−E[Xˉ]∣≤12ϵlog⁡2δ2n |\hat \mu - \mu | = \frac{1}{2 \epsilon} |\bar{X} - \mathbb{E} [ \bar{X} ] | \le \frac{1}{ 2 \epsilon } \sqrt{ \frac{\log \frac{2}{\delta} }{2n} }

which is much tighter than Chebyshev inequality.

Finally, observe that to get a meaningful estimate μ^\hat \mu, we require that 1ϵn≤1\frac{ 1 }{\epsilon \sqrt{n} } \le 1, i.e., n∈Ω(1ϵ2)n \in \Omega(\frac{1}{\epsilon^2}) or ϵ∈Ω(1n)\epsilon \in \Omega( \frac{1}{ \sqrt{n} } ).

□\square