Definition. Two distribution μ\mu and μ′\mu' are (ϵ,δ)(\epsilon, \delta) close, denoted as μ≃(ϵ,δ)μ′\mu \simeq_{(\epsilon, \delta) } \mu', if for all measurable set AA, we have

μ(A)≤eϵμ′(A)+δ,μ′(A)≤eϵμ(A)+δ. \begin{aligned} \mu(A) &\le e^\epsilon \mu'(A) + \delta, \\ \mu'(A) &\le e^\epsilon \mu(A) + \delta. \end{aligned}

Theorem. Let q∈(0,1)q \in (0, 1) and let μ\mu and μ′\mu' be two distributions such that μ≃(ϵ,δ)μ′\mu \simeq_{(\epsilon, \delta)} \mu'. For ν=(1−q)μ+qμ′\nu = (1 - q) \mu + q \mu', it holds that

ν≃(ϵ′,qδ)μ, \nu \simeq_{ (\epsilon', q \delta) } \mu,

where ϵ′=ln⁡(q(eϵ−1)+1)\epsilon' = \ln ( q (e^\epsilon - 1) + 1 ).

Proof. For each measurable set AA

ν(A)=(1−q)μ(A)+qμ′(A)≤(1−q)μ(A)+q(eϵμ(A)+δ)=(q(eϵ−1)+1)μ(A)+qδ. \begin{aligned} \nu(A) &= (1 - q) \mu(A) + q \mu' (A) \\ &\le (1 - q) \mu(A) + q (e^\epsilon \mu (A) + \delta) \\ &= ( q (e^\epsilon - 1) + 1 ) \mu(A) + q \delta. \end{aligned}

Next we prove the other direction. Denote t=eϵ−1t = e^{\epsilon} - 1. Then

eϵ′=1+qt, e^{\epsilon'} = 1 + qt,

and

ν(A)=(1−q)μ(A)+qμ′(A)≥(1−q)μ(A)+qe−ϵ(μ(A)−δ)=(1−q)μ(A)+q1+t(μ(A)−δ)=μ(A)−qt1+tμ(A)−q1+tδ=(1−qt1+t)μ(A)−11+tqδ≥(1−qt1+qt)μ(A)−11+qtqδ=11+qt(μ(A)−qδ). \begin{aligned} \nu(A) &= (1 - q) \mu(A) + q \mu' (A) \\ &\ge (1 - q) \mu(A) + q e^{-\epsilon} (\mu (A) - \delta) \\ &= (1 - q) \mu(A) + \frac{q}{1 + t} (\mu (A) - \delta) \\ &= \mu(A) - \frac{qt}{1 + t} \mu (A) - \frac{q}{1 + t} \delta \\ &= \left( 1 - \frac{qt}{1 + t} \right) \mu (A) - \frac{1}{1 + t} q \delta \\ &\ge \left( 1 - \frac{qt}{1 + qt} \right) \mu (A) - \frac{1}{1 + qt} q \delta \\ &= \frac{1}{1 + qt} \left( \mu (A) - q \delta \right). \end{aligned}

□\square

Reference

[1] Ú. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta, “Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity,”