# Differential Privacy: is the bound for group privacy tight?

Suppose mechanism $$M$$ is $$(\epsilon, \delta)$$-differentially private. For datasets $$x$$ and $$x''$$ that differ by 2 elements, we have $$Pr[M(x)=y] \le e^{\epsilon} Pr[M(x')=y] + \delta \le e^{2\epsilon} Pr[M(x'')=y] + (1+e^\epsilon)\delta$$ where $$x$$ and $$x'$$ are adjacent, $$x'$$ and $$x''$$ are adjacent. This bound is the one from group privacy. Is this bound tight? If so, can anyone give me a specific example of the mechanism to illustrate that this bound is tight? I'm thinking of randomized response but seems doesn't achieve the $$(2\epsilon, (1+e^\epsilon)\delta))$$-indistinguishability for $$M(x)$$ and $$M(x'')$$.

Thanks a lot!

• which inequality are you checking for tightness? motivate a bit more. – kodlu Sep 13 '20 at 1:10
• @kodlu $Pr[M(x)=y] \le e^{2\epsilon} Pr[M(x'')=y] + (1+e^\epsilon)\delta$ for $x$ and $x''$ differ by two records. – Piggy Wenzhou Sep 13 '20 at 2:19

The optimal partition selection mechanism introduced in this paper achieves the bound: every step "uses up" all the $$(\varepsilon,\delta)$$ budget available, and for the particular case of $$k=2$$, the probability of releasing the partition is exactly $$(1+e^\varepsilon)\delta$$, while this probability is $$0$$ for $$k=0$$. The recurrence relationship gives you a tight bound for any $$k$$.