Differential Privacy: is the bound for group privacy tight?
Yes, this bound is tight.
The optimal partition selection mechanism introduced in this paper achieves the bound: every step &quot;uses up&quot; 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$.
(Disclaimer: I'm one of the authors of this paper.)