隐私损失分布核算

区域 $B=\{p>e^{\epsilon }q\}$ 是最有利于暴露隐私差异的事件。在这个区域内，允许的乘法比较已经支付了 $e^{\epsilon }Q(B)$，$\delta$ 只补剩下的超额部分：

因此尾概率是一个方便的充分上界，却通常不等于最小 $\delta$。将 DP 解释成“概率 $\delta$ 的坏区域完全失去保护”会把已由乘法项支付的质量重复计算。

0.6 的尾概率，只有 0.1 的超额质量 ​

取两个输出 $a,b$，令 $P=(0.6,0.4)$、$Q=(0.4,0.6)$，$\epsilon =\log 1.25$。在 $a$ 处 $L=\log 1.5>\epsilon$，在 $b$ 处 $L=\log \left(2/3\right)<0$。故

反向由对称性同样为 $0.1$。若机制的相邻输入只有这一对，就满足 $(\log 1.25,0.1)$-DP，尽管越过损失阈值的概率为 $0.6$。这是对“$\delta$ 等于坏区域概率”的直接反例。

两轮独立报告怎样卷积 ​

对固定输入对，若两轮输出条件于输入独立，则联合密度连乘、损失相加，PLD 做概率测度的卷积；损失落在等距格点时，对应概率数组的离散卷积公理库离散卷积Discrete convolution · Sequence convolution对所有下标分解求和得到序列、概率质量函数或多项式系数的卷积。。以真实 bit 相反的两输入比较，两轮各使用 $p=3/4$ 的随机化回答。单轮损失为 $\log 3$，概率 $3/4$；或为 $-\log 3$，概率 $1/4$。两轮得到

取 $\epsilon =\log 3$，只有首项贡献，故 $\delta =(9/16)(1-1/3)=3/8$。取 $\epsilon =2\log 3$，所有正部均为零，恢复基本组合的纯隐私保证。

自适应时不能直接独立卷积 ​

自适应过程的总损失仍是条件损失之和，但后轮损失分布可能依赖之前的输出。直接卷积某几个边缘 PLD 会错误地假设独立。此时必须使用对全部历史有效的支配分布定理，或改用可自适应组合的 RDP 等界。

离散核算器可把损失值分桶，逐轮卷积后计算 $\sum _{\ell }{p}_{\ell }(1-e^{\epsilon -\ell }{)}_{+}$。两个长度 $m$ 的数组直接卷积用 $O(m^2)$ 运算，用FFT公理库快速 Fourier 变换Fast Fourier transform · FFT利用单位根的偶奇分解在 $O(n\log n)$ 时间计算离散 Fourier 变换。对适当零填充的数组作两次正变换、逐点相乘与一次逆变换，可降为 $O(m\log m)$（$m\ge 2$）；循环卷积的回绕质量不能当作线性卷积结果。

要返回严格上界，必须给舍入、截断尾部和浮点误差留出预算。把损失向上取整会增大正部贡献，但丢掉无穷损失质量会低估 $\delta$。数值精度是隐私证书的一部分，画出的曲线平滑不等于上界已经可靠。