在之前的文章《DP-拉普拉斯机制》和《DP-指数机制》中，我们介绍了两个应用场景下的差分隐私算法设计。就像一般的运算一样，我们定义了某种运算就想知道这种运算的一些性质以便于后续更加方便的使用这种运算。本章节我们关心差分隐私的运算性质。

为什么有组合性质
组合性质
简单应用

为什么有组合性质

在《DP-Differential Privacy概念介绍》中的背景知识小节中，我们举了一个对数据库查询以得到某个具体记录的案例：

patient	has cancer
Amy	0
Tom	1
Jack	1

假设 $sum(n)$ 表示前n行的统计结果，则通过

$sum(3)-sum(2)=2-1=1$

可以得到 Jack 的患病信息（假设我们拥有背景知识是Jack在第三行）。

在使用了DP机制之后，由于 DP 对相邻数据集的不可区分性，$sum(3)-sum(2)$ 是很可能相等的，所以$sum(3)-sum(2)$ 得到的结果可能是 0，可能是 1，甚至可能是-1. 通过这种手段，敌手无法得知Jack的患病情况。

但是：为了保证数据可用性，添加的噪声均值必须为0。这就意味着

$E[sum(3)-sum(2)]=E[sum(3)]-E[sum(2)]=1$

即，如果敌手可以无限制地对数据集进行查询，最终一定会得到真实结果。

实际上，对于同一个查询来说，查询次数越多，得到的结果平均值越收敛于真实值，隐私保护等级就越低。

所以从这个角度来说，我们想知道随着连续的查询，隐私保护等级会如何变化呢？

组合性质

我们来看看什么是组合机制：

Composition Theorem: Let $\mathcal{M}_1: \mathbb{N}^{|\mathcal{X}|} \rightarrow \mathcal{R}_1$ be an $\epsilon_1$-differentially private algorithm, and let $\mathcal{M}_2: \mathbb{N}^{|\mathcal{X}|} \rightarrow \mathcal{R}_2$ be an $\epsilon_2$-differentially private algorithm. Then their combination, defined to be $\mathcal{M}_{1,2}: \mathbb{N}^{|\mathcal{X}|} \rightarrow \mathcal{R}_1 \times \mathcal{R}_2$ by the mapping: $\mathcal{M}_{1,2}(x) = (\mathcal{M}_1(x), \mathcal{M}_2(x))$ is $(\epsilon_1+\epsilon_2)$-differentially private.

组合机制的理解其实很简单，即如果算法$\mathcal{M}_1$是$\epsilon_1$-DP的，$\mathcal{M}_2$是$\epsilon_2$-DP的，那么把$\mathcal{M}_1$和$\mathcal{M}_2$放到一起就是$(\epsilon_1+\epsilon_2)$-DP的。证明过程如下：

Let $x,y\in\mathbb{N}^{|\mathcal{X}|}$ be such that $||x-y||_1 \le 1$. Fix any $(r_1, r_2)\in \mathcal{R}_1\times\mathcal{R}_2$. Then:
$\begin{align} \frac{\Pr[\mathcal{M}_{1,2}(x)=(r_1,r_2)]}{\Pr[\mathcal{M}_{1,2}(y)=(r_1,r_2)]} &= \frac{\Pr[\mathcal{M}_1(x)=r_1][\mathcal{M}_2(x)=r_2]}{\Pr[\mathcal{M}_1(y)=r_1][\mathcal{M}_2(y)=r_2]}\\ &= \frac{\Pr[\mathcal{M}_1(x)=r_1]}{\Pr[\mathcal{M}_1(y)=r_1]} \times \frac{\Pr[\mathcal{M}_2(x)=r_2]}{\Pr[\mathcal{M}_2(y)=r_2]}\\ &\le \exp(\epsilon_1) \exp(\epsilon_2)\\ &=\exp(\epsilon_1+\epsilon_2) \end{align}$

有了两个机制的组合机制之后，我们自然会将这个机制推广到 $n$ 个机制的组合情况，在这里总的结论就不放了。