随机化回答

报告 $1$ 既可能是真实的 $1$，也可能来自被翻转的 $0$。收集者知道随机化规则，却不知道每个人的随机币，因而不能直接把一个报告当作事实。群体中币的平均影响可以扣除，所以仍能估计总体比例。

$p$ 接近 $1/2$ 时，两种输入几乎无法区分；但扣除随机化误差会同时放大抽样波动。隐私和精度在同一个分母里相遇。

无偏估计的推导 ​

设 $n\ge 1$，$X_i$ 独立服从参数为 $\theta$ 的Bernoulli 分布公理库Bernoulli 随机变量Bernoulli random variable只取 0 与 1 且成功概率为 p 的基本随机变量。，各用户独立随机化。报告 $1$ 的概率是

令 $\overline{Y}=n^{-1}\sum _i{Y}_i$，反演得到

这条方差包含了总体抽样和本地随机化的共同波动。若输入 bit 本身固定，只对随机化取方差，则结果为 $p(1-p)/(n(2p-1{)}^2)$，两种实验口径不要混用。

看见七十个 1，原始比例是多少 ​

取 $p=3/4$，则 $\epsilon =\log 3$。若 $n=100$ 个报告中有 $70$ 个为 $1$，估计为

$70\mathrm{\%}$ 是报告比例，经过已知噪声反演才得到 $90\mathrm{\%}$ 的原始比例估计。若真实 $\theta =1/2$，则 $q=1/2$，标准差为 $1/\sqrt{n}=0.1$；没有随机化时 Bernoulli 样本均值的标准差为 $0.05$。

估计有时会落到 $[0,1]$ 外，例如同样参数下 $\overline{Y}=0.1$ 给 $-0.3$。截断到合法区间是安全后处理，并不会增加相对真实 $\theta \in [0,1]$ 的平方误差，但通常失去严格无偏性。

边界值与重复询问 ​

$p=1/2$ 给完全与输入无关的报告，隐私参数为零，但反演分母为零，无法恢复比例。$p=1$ 则完全准确，却没有有限的纯 DP 保证。

向同一用户重复独立询问并公开全部报告，会累积其隐私预算。多位不同用户各报告一次与同一用户报告很多次是不同的保护对象；不能因为每次都掷币，就宣称永久使用同一 $\epsilon$。

当 $\epsilon$ 很小时，$2p-1=\tanh \left(\epsilon /2\right)\approx \epsilon /2$，方差上界约为 $1/(n{\epsilon }^2)$。要让均方误差缩小一半，需增加样本或放宽隐私，而不能只在服务器端重复处理相同报告。

本地差分隐私公理库本地差分隐私模型Local differential privacy · LDP model把隐私边界放在用户设备内，要求收集者看到的消息在任意两条原始记录下都难以区分。将这类二元信道推广到任意记录空间。随机化回答是其中可直接执行的最小例子：若把按公开参数采样一次 Bernoulli 币计作单位成本，每位用户用常数时间发送一 bit；服务器用 $O(n)$ 时间求和、常数个机器字保存计数。计数器本身需要 $O(\log (n+1))$ bit。