Introduction
Differential privacy (DP) limits what a randomized computation reveals about any individual’s contribution, which creates plausible deniability and thereby provides privacy protection [15 , 17 ] . To satisfy DP, it requires the output distributions on neighboring datasets to be similar, and this similarity can be formalized either through divergences or through hypothesis testing. Concentrated differential privacy and Rényi differential privacy (RDP) bound divergences between the output distributions [9 , 24 ] . The f f f -DP framework instead quantifies their similarity through hypothesis tests that distinguish them, requiring that at type I error α \alpha α , every such test has type II error at least f ( α ) f(\alpha) f ( α ) , for a given function f f f [18 ] . Within this framework, Gaussian differential privacy (GDP) is the primary single-parameter framework, with f f f given by testing between unit-variance Gaussian distributions with mean difference μ \mu μ .
Zero-concentrated differential privacy (zCDP) and GDP are both one-parameter frameworks motivated by the Gaussian mechanism, and their parameters have similar interpretations. Moreover, μ \mu μ -GDP implies ( μ 2 / 2 ) (\mu^2/2) ( μ 2 /2 ) -zCDP, and the Gaussian mechanism attains both bounds exactly [18 ] . While zCDP is more commonly used in the computer science literature [9 , 21 , 7 , 12 ] , where it offers additive composition, covers bounded-range mechanisms such as the exponential mechanism through standard conversions, and underlies the noisy measurements of the 2020 Census [AACM+22], GDP is more common in statistics [18 , 8 , 2 , 5 , 4 , 32 , 13 , 27 , 26 ] , where its hypothesis-testing guarantee is directly interpretable, and [18 ] claim it is the tightest guarantee for the Gaussian mechanism, based on an argument on informativeness. Despite the similarities, it has not been established which GDP guarantee, if any, a zCDP budget implies, or whether the two frameworks are equivalent up to constants. Without such a result, a mechanism analyzed under the zCDP framework is hard to report in the more interpretable GDP framework of privacy accounting, and risk bounds proved in one framework cannot be transferred to the other.
The known implication from GDP to zCDP gives one direction, but its converse at the same calibration fails [18 ] . RDP-to-testing conversions derive trade-off functions from Rényi constraints, most recently the optimal one implied by RDP bounds at all orders [28 ] , but they do not identify the sharp GDP parameter implied by a zCDP budget.
Our results
In this paper, we establish the sharp zCDP-to-GDP conversion and use it to compare the mechanism classes and their minimax risks. We also derive privacy accounting consequences and a sharp bounded-range to GDP calculation. Specifically, our results are as follows:
Optimal conversion. Let Φ ( t ) \Phi(t) Φ ( t ) be the cumulative distribution function (CDF) of a standard Gaussian. Then, for every ρ > 0 \rho> 0 ρ > 0 , the tightest (smallest) GDP parameter guaranteed by ρ \rho ρ -zCDP is
μ z C D P ( ρ ) = 2 Φ − 1 ( σ ( t ρ ) ) , \mu_{\mathrm{zCDP}}(\rho) = 2\Phi^{-1}\bigl(\sigma(t_\rho)\bigr), μ zCDP ( ρ ) = 2 Φ − 1 ( σ ( t ρ ) ) ,
where t ρ t_\rho t ρ uniquely solves the calibration equation ρ = t ρ tanh ( t ρ / 2 ) \rho= t_\rho\tanh(t_\rho/2) ρ = t ρ tanh ( t ρ /2 ) and σ ( t ) = ( 1 + e − t ) − 1 \sigma(t) = (1 + e^{-t})^{-1} σ ( t ) = ( 1 + e − t ) − 1 is the logistic function. Our proof is by contraposition, and the tightness of the conversion is achieved by the binary randomized response mechanism.
Conversion loss and statistical equivalence. We simplify the above conversion to obtain π ρ ≤ μ z C D P ( ρ ) ≤ 8 ρ \sqrt{\pi\rho} \le\mu_{\mathrm{zCDP}}(\rho) \le\sqrt{8\rho} π ρ ≤ μ zCDP ( ρ ) ≤ 8 ρ , where μ z C D P ( ρ ) / ρ \mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho} μ zCDP ( ρ ) / ρ increases from π \sqrt{\pi} π to 8 \sqrt{8} 8 over ρ > 0 \rho> 0 ρ > 0 , so both constants are tight. Together with the known conversion from GDP to zCDP, this yields,
μ -GDP ⟹ ( μ 2 / 2 ) -zCDP ⟹ 2 μ -GDP . \mu\text{-GDP} \quad\Longrightarrow\quad(\mu^2/2)\text{-zCDP} \quad\Longrightarrow\quad2\mu\text{-GDP}. μ -GDP ⟹ ( μ 2 /2 ) -zCDP ⟹ 2 μ -GDP .
Figure 1. The three trade-off curves, G 2 ρ G_{\sqrt{2\rho}} G 2 ρ , the numerical ρ \rho ρ -zCDP testing boundary, and G μ z C D P ( ρ ) G_{\mu_{\mathrm{zCDP}}(\rho)} G μ zCDP ( ρ ) illustrate the GDP–zCDP round-trip loss.
This shows that zCDP and GDP are equivalent up to constants. In particular, for any estimation problem, this yields a general minimax comparison between GDP and zCDP up to constant-factor changes in the privacy budget.
Composition and group privacy. We prove that the squared conversion map ρ ↦ μ z C D P ( ρ ) 2 \rho\mapsto\mu_{\mathrm{zCDP}}(\rho)^2 ρ ↦ μ zCDP ( ρ ) 2 is strictly convex. This implies that converting individual zCDP budgets to GDP before applying composition or group privacy improves the resulting GDP bound.
GDP result for bounded-range and logistic mechanisms. Using similar techniques, we also prove the sharp conversion from logistic DP (including bounded-range mechanisms such as the exponential mechanism) to GDP. The square of the conversion map is strictly convex, favoring conversion to GDP before composition, while its concavity implies that group privacy should be applied before converting to GDP.
Remark 1 Figure 1 illustrates the conversion from ρ \rho ρ -zCDP to GDP at ρ = 1 \rho= 1 ρ = 1 . The trade-off function for ρ \rho ρ -zCDP is computed as follows: For a type I error α \alpha α and power q q q , let K z C D P ( α , q ) K_{\mathrm{zCDP}}(\alpha,q) K zCDP ( α , q ) denote the smallest ρ \rho ρ for which Bern ( α ) \operatorname{Bern}(\alpha) Bern ( α ) and Bern ( q ) \operatorname{Bern}(q) Bern ( q ) , viewed as the output distributions of a mechanism on two neighboring datasets, satisfy ρ \rho ρ -zCDP. The figure shows the ρ \rho ρ -zCDP testing boundary T z C D P ρ ( α ) = 1 − sup { q ∈ [ α , 1 ] : K z C D P ( α , q ) ≤ ρ } T_{\mathrm{zCDP}}^{\rho}(\alpha)=1-\sup\{q\in[\alpha,1]:K_{\mathrm{zCDP}}(\alpha,q)\leq\rho\} T zCDP ρ ( α ) = 1 − sup { q ∈ [ α , 1 ] : K zCDP ( α , q ) ≤ ρ } , which is the smallest type II error at level α \alpha α among such Bernoulli pairs, computed numerically by solving K z C D P ( α , q ) = ρ K_{\mathrm{zCDP}}(\alpha,q)=\rho K zCDP ( α , q ) = ρ for q q q [BBG+20, RGC+26]. This boundary lies above the curve G μ z C D P ( ρ ) G_{\mu_{\mathrm{zCDP}}(\rho)} G μ zCDP ( ρ ) , where G μ G_\mu G μ gives the smallest type II error at each type I error level when testing N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) against N ( μ , 1 ) N(\mu,1) N ( μ , 1 ) , and touches it where the type I and type II errors both equal σ ( − t ρ ) \sigma(-t_\rho) σ ( − t ρ ) , so μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) cannot be decreased. The shaded region is the loss when a 2 ρ \sqrt{2\rho} 2 ρ -GDP guarantee, such as that of the Gaussian mechanism, is converted to ρ \rho ρ -zCDP and back.
Related work
Divergence-based guarantees, such as zCDP and Rényi DP, control the moments of the privacy loss, which is the log-likelihood ratio between the output distributions on neighboring datasets [9 , 24 ] . zCDP is equivalent to bounding the Rényi divergence at every order by a fixed multiple of the order, which is based on the Rényi divergence between two unit-variance Gaussians with differing means. Conversions from divergence-based guarantees to approximate DP, which bounds the likelihood ratio except on an event of small probability, have been established in [9 , 24 ] and were sharpened by [12 ] . Pure DP, which bounds the privacy loss uniformly, converts sharply to RDP and zCDP, and binary randomized response attains these bounds [29 ] . Exact zCDP budgets have been derived for several mechanisms, including bounded-range mechanisms, whose privacy loss lies in an interval of fixed width [20 , 14 ] .
The f f f -DP framework, which includes GDP, was introduced by [18 ] , although previously the testing perspective has been used to study the composition of differential privacy mechanisms in [22 ] . [18 ] show that all popularly used divergence-based guarantees can be computed from f f f -DP without any loss. The reverse direction, from divergence bounds to testing errors, is studied by [BBG+20, ALC+21], where the latter also characterize the optimal approximate DP guarantee implied by an RDP bound, and by [33 ] through intersections of the sets of achievable type I and type II errors. The tightest f f f -DP guarantee implied by RDP bounds at all orders, including zCDP, has been characterized using Bernoulli experiments [28 ] , while numerical methods have been developed for identifying and reporting the GDP guarantees of specific mechanisms [23 , 19 ] .
Appendix § 6 provides additional context on the equations and formulae from the conversions discussed above.
Privacy definitions and randomized response
Let M M M be a Markov kernel (randomized mechanism) from an input measurable space to an output measurable space ( Ω , F ) (\Omega, \mathcal{F}) ( Ω , F ) , with a symmetric neighboring relation ∼ \sim ∼ on its input space. For datasets of a fixed size, the usual choice is x ∼ x ′ x \sim x' x ∼ x ′ when d H ( x , x ′ ) = 1 d_H(x,x') = 1 d H ( x , x ′ ) = 1 , where d H d_H d H denotes the Hamming distance. For fixed neighboring datasets x ∼ x ′ x \sim x' x ∼ x ′ , write P = M ( x ) P = M(x) P = M ( x ) and Q = M ( x ′ ) Q = M(x') Q = M ( x ′ ) . Let σ ( t ) = ( 1 + e − t ) − 1 \sigma(t) = (1 + e^{-t})^{-1} σ ( t ) = ( 1 + e − t ) − 1 denote the logistic function, and let Φ \Phi Φ and ϕ \phi ϕ denote the standard normal CDF and density functions respectively.
Privacy guarantees
In this section, we define the two guarantees we compare, first zCDP and then GDP. For probability measures P , Q P, Q P , Q dominated by a common measure ν \nu ν , with densities p = d P / d ν p = dP/d\nu p = d P / d ν and q = d Q / d ν q = dQ/d\nu q = d Q / d ν , the Rényi divergence of order η > 1 \eta> 1 η > 1 is D η ( P ∥ Q ) = 1 η − 1 log ∫ p η q 1 − η d ν D_\eta(P\|Q) = \frac{1}{\eta-1} \log\int p^\eta q^{1-\eta}\,d\nu D η ( P ∥ Q ) = η − 1 1 log ∫ p η q 1 − η d ν [VEH14]. Moreover, lim η ↓ 1 D η ( P ∥ Q ) \lim_{\eta\downarrow1} D_\eta(P\|Q) lim η ↓ 1 D η ( P ∥ Q ) results in the KL divergence. Rényi divergences are finite only if Q ( A ) = 0 Q(A) = 0 Q ( A ) = 0 implies P ( A ) = 0 P(A) = 0 P ( A ) = 0 for every measurable set A A A , denoted as the absolute continuity requirement P ≪ Q P \ll Q P ≪ Q . We say a mechanism M M M satisfies ( η , ε ) (\eta,\varepsilon) ( η , ε ) -RDP if D η ( M ( x ) ∥ M ( x ′ ) ) ≤ ε D_\eta(M(x)\|M(x')) \le\varepsilon D η ( M ( x ) ∥ M ( x ′ )) ≤ ε for every ordered neighboring pair [24 ] . Zero-concentrated DP (zCDP) requires such a bound at all η > 1 \eta> 1 η > 1 simultaneously, with ε = ρ η \varepsilon= \rho\eta ε = ρ η growing linearly in η \eta η .
Definition 2 (Zero-concentrated DP [9 ] ) A mechanism M M M satisfies ρ \rho ρ -zCDP if for every x ∼ x ′ x \sim x' x ∼ x ′ and every η > 1 \eta> 1 η > 1 , D η ( M ( x ) ∥ M ( x ′ ) ) ≤ ρ η D_\eta(M(x)\|M(x')) \le\rho\eta D η ( M ( x ) ∥ M ( x ′ )) ≤ ρ η .
This definition is motivated by the Gaussian mechanism. If M ( x ) = f ( x ) + Z M(x) = f(x) + Z M ( x ) = f ( x ) + Z with Z ∼ N ( 0 , σ 0 2 I ) Z \sim N(0,\sigma_0^2 I) Z ∼ N ( 0 , σ 0 2 I ) , then D η ( M ( x ) ∥ M ( x ′ ) ) = η ∥ f ( x ) − f ( x ′ ) ∥ 2 2 / ( 2 σ 0 2 ) D_\eta(M(x)\|M(x')) = \eta\|f(x)-f(x')\|_2^2/(2\sigma_0^2) D η ( M ( x ) ∥ M ( x ′ )) = η ∥ f ( x ) − f ( x ′ ) ∥ 2 2 / ( 2 σ 0 2 ) . Thus, if f f f has ℓ 2 \ell_2 ℓ 2 -sensitivity Δ \Delta Δ , that is sup x ∼ x ′ ∥ f ( x ) − f ( x ′ ) ∥ 2 ≤ Δ \sup_{x\sim x'}\|f(x)-f(x')\|_2 \le\Delta sup x ∼ x ′ ∥ f ( x ) − f ( x ′ ) ∥ 2 ≤ Δ , then the mechanism satisfies ρ \rho ρ -zCDP with ρ = Δ 2 / ( 2 σ 0 2 ) \rho= \Delta^2/(2\sigma_0^2) ρ = Δ 2 / ( 2 σ 0 2 ) . Intuitively, a mechanism satisfies zCDP if it is “more private” than the Gaussian mechanism, in terms of the Rényi divergences. Smaller ρ \rho ρ means that neighboring output distributions are closer, providing stronger privacy, and ρ \rho ρ -zCDP implies ρ ′ \rho' ρ ′ -zCDP for any ρ ′ ≥ ρ \rho' \ge\rho ρ ′ ≥ ρ .
For hypothesis testing, a measurable randomized test ϕ : Ω → [ 0 , 1 ] \phi:\Omega\to[0,1] ϕ : Ω → [ 0 , 1 ] rejects P P P with probability ϕ ( ω ) \phi(\omega) ϕ ( ω ) , based on the observation ω \omega ω . Its type I error and power are E P ϕ E_P\phi E P ϕ and E Q ϕ E_Q\phi E Q ϕ . The trade-off function is
T ( P , Q ) ( α ) = inf { ϕ : E P ϕ ≤ α } ( 1 − E Q ϕ ) T(P,Q)(\alpha)=\inf_{\{\phi:\mathbb{E}_{P}\phi\leq\alpha\}}(1-\mathbb{E}_{Q}\phi) T ( P , Q ) ( α ) = { ϕ : E P ϕ ≤ α } inf ( 1 − E Q ϕ )
for any α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] [30 , 18 ] . The trade-off function returns the smallest achievable type II error at a given type I error level. Let G μ ( α ) = Φ ( Φ − 1 ( 1 − α ) − μ ) G_{\mu}(\alpha)=\Phi\left(\Phi^{-1}(1-\alpha)-\mu\right) G μ ( α ) = Φ ( Φ − 1 ( 1 − α ) − μ ) be the trade-off function for N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) versus N ( μ , 1 ) N(\mu,1) N ( μ , 1 ) .
Definition 3 (Gaussian DP [18 ] ). A mechanism M M M satisfies μ \mu μ -GDP if for every x ∼ x ′ x\sim x' x ∼ x ′ and for every α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] , T ( M ( x ) , M ( x ′ ) ) ( α ) ≥ G μ ( α ) T(M(x),M(x'))(\alpha)\geq G_{\mu}(\alpha) T ( M ( x ) , M ( x ′ )) ( α ) ≥ G μ ( α ) .
Equivalently, μ \mu μ -GDP holds when every test on neighboring outputs whose type I error and power lie in ( 0 , 1 ) (0,1) ( 0 , 1 ) satisfies Φ − 1 ( E Q ϕ ) − Φ − 1 ( E P ϕ ) ≤ μ \Phi^{-1}(\mathbb{E}_{Q}\phi)-\Phi^{-1}(\mathbb{E}_{P}\phi)\leq\mu Φ − 1 ( E Q ϕ ) − Φ − 1 ( E P ϕ ) ≤ μ . Replacing G μ G_{\mu} G μ by a general trade-off function f f f gives the f f f -DP framework. A smaller μ \mu μ represents a stronger privacy guarantee with lower data usability, and μ \mu μ -GDP implies μ ′ \mu' μ ′ -GDP for any μ ′ ≥ μ \mu'\geq\mu μ ′ ≥ μ .
The Gaussian mechanism with variance σ 0 2 I \sigma_{0}^{2}I σ 0 2 I applied to a function with ℓ 2 \ell_{2} ℓ 2 -sensitivity Δ \Delta Δ satisfies Δ / σ 0 \Delta/\sigma_{0} Δ/ σ 0 -GDP. Similar to zCDP, a mechanism is GDP if it is “more private” than the Gaussian mechanism, in terms of hypothesis testing.
Proposition 4 (GDP implies zCDP [18 ] ). For any μ > 0 \mu>0 μ > 0 , if a mechanism satisfies μ \mu μ -GDP, then it also satisfies ( μ 2 / 2 ) (\mu^{2}/2) ( μ 2 /2 ) -zCDP.
It is equivalent to state Proposition 4 as 2 ρ \sqrt{2\rho} 2 ρ -GDP implies ρ \rho ρ -zCDP for every ρ > 0 \rho>0 ρ > 0 . However, the converse to Proposition 4 at the same calibration fails. [18 Proposition B.7] give a binary randomized-response counterexample showing that ρ \rho ρ -zCDP does not generally imply 2 ρ \sqrt{2\rho} 2 ρ -GDP.
Both zCDP and GDP frameworks have concise rules for composition and group privacy. Suppose releases M 1 , … , M n M_{1},\ldots,M_{n} M 1 , … , M n are composed adaptively, so that each M i M_{i} M i takes as input the dataset and the outputs of M 1 , … , M i − 1 M_{1},\ldots,M_{i-1} M 1 , … , M i − 1 . For group privacy, consider groups of size k k k , that is, datasets x ( 0 ) x^{(0)} x ( 0 ) and x ( k ) x^{(k)} x ( k ) connected by a chain x ( 0 ) ∼ x ( 1 ) ∼ ⋯ ∼ x ( k ) x^{(0)}\sim x^{(1)}\sim\cdots\sim x^{(k)} x ( 0 ) ∼ x ( 1 ) ∼ ⋯ ∼ x ( k ) .
Composition. If each M i M_{i} M i is ρ i \rho_{i} ρ i -zCDP for every fixed realization of the preceding outputs, with deterministic ρ i \rho_{i} ρ i , then the joint release is ( ∑ i = 1 n ρ i ) (\sum_{i=1}^{n}\rho_{i}) ( ∑ i = 1 n ρ i ) -zCDP [9 ] . If each M i M_{i} M i is instead μ i \mu_{i} μ i -GDP in the same sense, then the joint release is ∑ i = 1 n μ i 2 \sqrt{\sum_{i=1}^{n}\mu_{i}^{2}} ∑ i = 1 n μ i 2 -GDP [18 ] .
Group privacy. A ρ \rho ρ -zCDP mechanism satisfies D η ( M ( x ( 0 ) ) ∥ M ( x ( k ) ) ) ≤ k 2 ρ η D_{\eta}(M(x^{(0)})\mathbin\Vert M(x^{(k)}))\leq k^{2}\rho\eta D η ( M ( x ( 0 ) ) ∥ M ( x ( k ) )) ≤ k 2 ρ η for every η > 1 \eta>1 η > 1 [9 ] , and a μ \mu μ -GDP mechanism satisfies T ( M ( x ( 0 ) ) , M ( x ( k ) ) ) ≥ G k μ T(M(x^{(0)}),M(x^{(k)}))\geq G_{k\mu} T ( M ( x ( 0 ) ) , M ( x ( k ) )) ≥ G k μ [18 ] .
Randomized Response
For t ≥ 0 t\geq0 t ≥ 0 , binary randomized response R R t \mathrm{RR}_{t} RR t has input space and output space both as { 0 , 1 } \{0,1\} { 0 , 1 } . On input x ∈ { 0 , 1 } x\in\{0,1\} x ∈ { 0 , 1 } , it outputs x x x directly with probability σ ( t ) \sigma(t) σ ( t ) and outputs 1 − x 1-x 1 − x with probability σ ( − t ) = 1 − σ ( t ) \sigma(-t)=1-\sigma(t) σ ( − t ) = 1 − σ ( t ) .
Thus R R t ( 0 ) = d Bern ( σ ( − t ) ) \mathrm{RR}_{t}(0)\mathrel{\overset{d}{=}}\operatorname{Bern}(\sigma(-t)) RR t ( 0 ) = d Bern ( σ ( − t )) and R R t ( 1 ) = d Bern ( σ ( t ) ) \mathrm{RR}_{t}(1)\mathrel{\overset{d}{=}}\operatorname{Bern}(\sigma(t)) RR t ( 1 ) = d Bern ( σ ( t )) , and t = log { σ ( t ) / σ ( − t ) } t=\log\{\sigma(t)/\sigma(-t)\} t = log { σ ( t ) / σ ( − t )} is the log odds of reporting the input correctly. At t = 0 t=0 t = 0 the output is a fair coin regardless of the input, and larger t t t reports the input more accurately.
Proposition 5 (Exact privacy parameters of randomized response). For any t ≥ 0 t\geq0 t ≥ 0 , R R t \mathrm{RR}_{t} RR t is tightly t tanh ( t / 2 ) t\tanh(t/2) t tanh ( t /2 ) -zCDP and tightly 2 Φ − 1 ( σ ( t ) ) 2\Phi^{-1}(\sigma(t)) 2 Φ − 1 ( σ ( t )) -GDP. This tightness is in the sense that no smaller parameter is valid in either framework.
The zCDP budget in Proposition 5 was derived in [29 , 20 ] . Its value equals the KL limit t tanh ( t / 2 ) t\tanh(t/2) t tanh ( t /2 ) for this particular pair. The GDP budget follows from [4 Lemma 2] . The GDP bound is tight at the test that takes the output as its guess of the input, which has type I and type II errors both equal to σ ( − t ) \sigma(-t) σ ( − t ) .
Sharp conversion and its properties
In this section, we present our main result (Theorem 6) on the sharp conversion from zCDP to GDP, its statistical consequences, and its shape and privacy accounting properties, followed by the GDP result for bounded-range and logistic mechanisms.
The sharp zCDP-to-GDP conversion
The following theorem shows that every ρ \rho ρ -zCDP mechanism is μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) -GDP. For every non-negative budget, this is the smallest universally valid GDP parameter.
Theorem 6 (Sharp zCDP-to-GDP conversion). For ρ ≥ 0 \rho\ge0 ρ ≥ 0 , define
μ z C D P ( ρ ) = 2 Φ − 1 ( σ ( t ρ ) ) , ρ = t ρ tanh ( t ρ / 2 ) , (1) \mu_{\mathrm{zCDP}}(\rho) = 2\Phi^{-1}(\sigma(t_\rho)), \qquad\rho= t_\rho\tanh(t_\rho/2), \tag*{(1)} μ zCDP ( ρ ) = 2 Φ − 1 ( σ ( t ρ )) , ρ = t ρ tanh ( t ρ /2 ) , (1) where t ρ ≥ 0 t_\rho\ge0 t ρ ≥ 0 uniquely solves the second equation. Every ρ \rho ρ -zCDP mechanism is μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) -GDP. Randomized response with parameter t ρ t_\rho t ρ attains the bound by Proposition 5 .
Proof sketch. The proof is by contrapositive: Suppose a mechanism fails μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) -GDP. Any optimal test results in a Bernoulli pair, and by data processing it suffices to show that this pair violates ρ \rho ρ -zCDP. Evaluating the Rényi divergence at a specific chosen order according to the pair, instead of the supremum over all orders, gives a closed-form lower bound on its zCDP budget and turns the claim into a one-dimensional (though non-trivial) calculus problem (Appendix § 7 ). Figure 2 shows that this lower bound lies between the exact zCDP budget of the pair and the zCDP budget of randomized response with the same GDP parameter. Randomized response with parameter t ρ t_\rho t ρ attains the bound by Proposition 5 . ■
Figure 2. Comparison of zCDP budgets for Bernoulli pairs induced by Gaussian threshold tests. The horizontal axis is the centered threshold τ − μ z C D P ( ρ ) / 2 \tau-\mu_{\mathrm{zCDP}}(\rho)/2 τ − μ zCDP ( ρ ) /2 , and each budget on the vertical axis is divided by ρ \rho ρ . The exact budget K z C D P ( p , q ) K_{\mathrm{zCDP}}(p,q) K zCDP ( p , q ) lies above the selected-order bound K ( c , d ) K(c,d) K ( c , d ) , which lies above the randomized-response budget ρ \rho ρ , shown as the horizontal line at 1. Here ρ = 1 \rho=1 ρ = 1 .
To further interpret Figure 2 , consider the threshold test with cutoff value τ \tau τ that rejects N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) in favor of N ( μ z C D P ( ρ ) , 1 ) N(\mu_{\mathrm{zCDP}}(\rho),1) N ( μ zCDP ( ρ ) , 1 ) when the observation exceeds τ \tau τ . Its rejection probabilities are p = 1 − Φ ( τ ) p = 1 - \Phi(\tau) p = 1 − Φ ( τ ) (type I error) and q = 1 − Φ ( τ − μ z C D P ( ρ ) ) q = 1 - \Phi(\tau- \mu_{\mathrm{zCDP}}(\rho)) q = 1 − Φ ( τ − μ zCDP ( ρ )) (power). At the midpoint threshold τ = μ z C D P ( ρ ) / 2 \tau= \mu_{\mathrm{zCDP}}(\rho)/2 τ = μ zCDP ( ρ ) /2 , the type I and type II errors are equal, so the induced Bernoulli pair coincides with symmetric randomized response. All three budgets therefore equal ρ \rho ρ at this threshold. The figure centers the horizontal axis at this midpoint and divides each budget by ρ \rho ρ , so the three curves meet at ( 0 , 1 ) (0,1) ( 0 , 1 ) . A value above 1 for either K z C D P ( p , q ) / ρ K_{\mathrm{zCDP}}(p,q)/\rho K zCDP ( p , q ) / ρ or its lower bound K ( c , d ) / ρ K(c,d)/\rho K ( c , d ) / ρ shows that the Bernoulli pair violates ρ \rho ρ -zCDP.
The next theorem describes the shape of the conversion μ z C D P \mu_{\mathrm{zCDP}} μ zCDP from Theorem 6. Strict convexity of μ z C D P ( ρ ) 2 \mu_{\mathrm{zCDP}}(\rho)^2 μ zCDP ( ρ ) 2 implies that it is better to convert before applying composition or group privacy (Corollary 9), and the bounds π ρ ≤ μ z C D P ( ρ ) ≤ 8 ρ \sqrt{\pi\rho} \le\mu_{\mathrm{zCDP}}(\rho) \le\sqrt{8\rho} π ρ ≤ μ zCDP ( ρ ) ≤ 8 ρ show that zCDP and GDP are equivalent up to constants.
Theorem 7 (Shape and limiting scales of the zCDP to GDP conversion). The zCDP to GDP conversion map ρ ↦ μ z C D P ( ρ ) \rho\mapsto\mu_{\mathrm{zCDP}}(\rho) ρ ↦ μ zCDP ( ρ ) is strictly increasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) , and satisfies lim ρ → 0 μ z C D P ( ρ ) / ρ = π \lim_{\rho\to0}\mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho} = \sqrt{\pi} lim ρ → 0 μ zCDP ( ρ ) / ρ = π and lim ρ → ∞ μ z C D P ( ρ ) / ρ = 8 \lim_{\rho\to\infty}\mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho} = \sqrt{8} lim ρ → ∞ μ zCDP ( ρ ) / ρ = 8 . Moreover, ρ ↦ μ z C D P ( ρ ) 2 \rho\mapsto\mu_{\mathrm{zCDP}}(\rho)^2 ρ ↦ μ zCDP ( ρ ) 2 is strictly convex and ρ ↦ μ z C D P ( ρ ) / ρ \rho\mapsto\mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho} ρ ↦ μ zCDP ( ρ ) / ρ is strictly increasing on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , so π ρ ≤ μ z C D P ( ρ ) ≤ 8 ρ \sqrt{\pi\rho} \le\mu_{\mathrm{zCDP}}(\rho) \le\sqrt{8\rho} π ρ ≤ μ zCDP ( ρ ) ≤ 8 ρ for all ρ ≥ 0 \rho\ge0 ρ ≥ 0 .
Proof sketch. Parameterizing the conversion by the randomized response parameter t ρ t_\rho t ρ in Theorem 6, rather than by ρ \rho ρ , avoids differentiating the inverse Gaussian CDF and allows both limits to be taken in t ρ t_\rho t ρ , which tends to zero or infinity together with ρ \rho ρ . Showing that the inverse of μ z C D P 2 \mu_{\mathrm{zCDP}}^2 μ zCDP 2 is strictly increasing and strictly concave (Lemma 21 ) gives strict convexity of μ z C D P 2 \mu_{\mathrm{zCDP}}^2 μ zCDP 2 , which with μ z C D P ( 0 ) = 0 \mu_{\mathrm{zCDP}}(0)=0 μ zCDP ( 0 ) = 0 gives the strict increase of μ z C D P ( ρ ) / ρ \mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho} μ zCDP ( ρ ) / ρ (Appendix § 9 ). ■
Theorem 7 shows that zCDP and GDP are frameworks equivalent up to constants. Since μ z C D P ( ρ ) / ρ \mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho} μ zCDP ( ρ ) / ρ increases from π \sqrt{\pi} π to 8 \sqrt{8} 8 , every ρ \rho ρ -zCDP mechanism is 8 ρ \sqrt{8\rho} 8 ρ -GDP, and neither constant can be improved. Together with Proposition 4 , a μ \mu μ -GDP mechanism satisfies ( μ 2 / 2 ) (\mu^2/2) ( μ 2 /2 ) -zCDP and converting back gives at worst 2 μ 2\mu 2 μ -GDP, so passing through zCDP costs at most a factor of 2 in the GDP parameter. Figure 10 in Appendix § 9 illustrates the shape and the limits of μ z C D P \mu_{\mathrm{zCDP}} μ zCDP stated in Theorem 7.
Figure 10. Shape of the sharp conversion from zCDP to GDP. Left: ρ ↦ μ z C D P ( ρ ) 2 \rho\mapsto\mu_{\mathrm{zCDP}}(\rho)^2 ρ ↦ μ zCDP ( ρ ) 2 is strictly convex. Right: μ z C D P ( ρ ) 2 / ρ \mu_{\mathrm{zCDP}}(\rho)^2/\rho μ zCDP ( ρ ) 2 / ρ increases from π \pi π to 8 8 8 , the sharp limiting constants in the conversion bounds that hold for every ρ \rho ρ -zCDP mechanism.
Strict convexity of μ z C D P 2 \mu_{\mathrm{zCDP}}^2 μ zCDP 2 determines the order of accounting composition and group privacy in Corollary 9, and Figure 13 in Appendix § 9 illustrates both comparisons in the corollary.
Figure 13. Left: composition shows μ z C D P ( λ ρ ) 2 + μ z C D P ( ( 1 − λ ) ρ ) 2 / μ z C D P ( ρ ) ≤ 1 \sqrt{\mu_{\mathrm{zCDP}}(\lambda\rho)^2+\mu_{\mathrm{zCDP}}((1-\lambda)\rho)^2}/\mu_{\mathrm{zCDP}}(\rho)\le1 μ zCDP ( λ ρ ) 2 + μ zCDP (( 1 − λ ) ρ ) 2 / μ zCDP ( ρ ) ≤ 1 . Right: group privacy shows k μ z C D P ( ρ ) / μ z C D P ( k 2 ρ ) ≤ 1 k\mu_{\mathrm{zCDP}}(\rho)/\mu_{\mathrm{zCDP}}(k^2\rho)\le1 k μ zCDP ( ρ ) / μ zCDP ( k 2 ρ ) ≤ 1 .
Corollary 9 (Converting before accounting) For nonnegative ρ 1 , … , ρ n \rho_1,\ldots,\rho_n ρ 1 , … , ρ n and ρ \rho ρ , and an integer k ≥ 1 k\geq1 k ≥ 1 ,
∑ i = 1 n μ z C D P ( ρ i ) 2 ≤ μ z C D P ( ∑ i = 1 n ρ i ) \sqrt{\sum_{i=1}^{n}\mu_{\mathrm{zCDP}}(\rho_i)^2}\leq\mu_{\mathrm{zCDP}}\left(\sum_{i=1}^{n}\rho_i\right) ∑ i = 1 n μ zCDP ( ρ i ) 2 ≤ μ zCDP ( ∑ i = 1 n ρ i ) with strict inequality if at least two ρ i \rho_i ρ i are positive.
k μ z C D P ( ρ ) ≤ μ z C D P ( k 2 ρ ) k\mu_{\mathrm{zCDP}}(\rho)\leq\mu_{\mathrm{zCDP}}(k^2\rho) k μ zCDP ( ρ ) ≤ μ zCDP ( k 2 ρ ) , with strict inequality when ρ > 0 \rho>0 ρ > 0 and k > 1 k>1 k > 1 .
Proof sketch. Both inequalities follow from strict convexity of μ z C D P 2 \mu_{\mathrm{zCDP}}^2 μ zCDP 2 and μ z C D P ( 0 ) = 0 \mu_{\mathrm{zCDP}}(0)=0 μ zCDP ( 0 ) = 0 (Appendix § 9 ). ■
Both of the inequalities in Corollary 9 compare two ways of obtaining a GDP guarantee, and in each case the left side converts to GDP first. Corollary 9 provides direct consequences on the order of privacy accounting of composition and group privacy under zCDP and GDP. Under the adaptive composition introduced in § 2.1 with ρ i \rho_i ρ i -zCDP releases, composing in zCDP first gives μ z C D P ( ∑ i ρ i ) \mu_{\mathrm{zCDP}}(\sum_i\rho_i) μ zCDP ( ∑ i ρ i ) -GDP, while converting each release first and composing in GDP gives ∑ i μ z C D P ( ρ i ) 2 \sqrt{\sum_i\mu_{\mathrm{zCDP}}(\rho_i)^2} ∑ i μ zCDP ( ρ i ) 2 -GDP. Similarly, for a ρ \rho ρ -zCDP mechanism and groups of size k k k , applying zCDP group privacy first gives μ z C D P ( k 2 ρ ) \mu_{\mathrm{zCDP}}(k^2\rho) μ zCDP ( k 2 ρ ) -GDP, while converting first and applying GDP group privacy gives k μ z C D P ( ρ ) k\mu_{\mathrm{zCDP}}(\rho) k μ zCDP ( ρ ) -GDP. Corollary 9 therefore shows that converting first is superior in either case.
Tight GDP for bounded-range and logistic mechanisms
We next obtain a tight GDP guarantee for bounded-range and logistic mechanisms by converting directly to GDP rather than first through zCDP. First, we formally introduce these notions.
Definition 10 (Bounded range). A mechanism satisfies ε \varepsilon ε -bounded range (BR) if, for every neighboring pair P = M ( x ) , Q = M ( x ′ ) P=M(x), Q=M(x') P = M ( x ) , Q = M ( x ′ ) , the distributions are mutually absolutely continuous and there is a real ℓ \ell ℓ such that ℓ ≤ log ( d Q / d P ) ≤ ℓ + ε \ell\le\log(\mathrm{d}Q/\mathrm{d}P) \le\ell+\varepsilon ℓ ≤ log ( d Q / d P ) ≤ ℓ + ε P P P -almost surely.
Every ε \varepsilon ε -BR mechanism satisfies ( ε 2 / 8 ) (\varepsilon^2/8) ( ε 2 /8 ) -zCDP. The sharper bound of [20 Theorem 23] is ρ B R ( ε ) = ε e ε − 1 + log e ε − 1 ε − 1 \rho_{\mathrm{BR}}(\varepsilon)=\frac{\varepsilon}{e^\varepsilon-1}+\log\frac{e^\varepsilon-1}{\varepsilon}-1 ρ BR ( ε ) = e ε − 1 ε + log ε e ε − 1 − 1 for ε > 0 \varepsilon>0 ε > 0 , with ρ B R ( 0 ) = 0 \rho_{\mathrm{BR}}(0)=0 ρ BR ( 0 ) = 0 . Although ρ B R \rho_{\mathrm{BR}} ρ BR and μ z C D P \mu_{\mathrm{zCDP}} μ zCDP are each sharp as conversions from BR to zCDP and from zCDP to GDP, respectively, it does not follow that their composition gives the sharp conversion from BR to GDP. Theorem 13 establishes this direct, sharp conversion, while Figure 3 illustrates that converting to GDP through zCDP is loose.
Figure 3. The five trade-off curves, BR examples, the logistic envelope, direct GDP conversion, the numerical zCDP testing boundary at ρ B R ( ε ) \rho_{\mathrm{BR}}(\varepsilon) ρ BR ( ε ) , and GDP conversion through zCDP, displayed on [ 0 , 0.4 ] 2 [0,0.4]^2 [ 0 , 0.4 ] 2 . Here ε = 5 \varepsilon=5 ε = 5 .
Example 11 (Bounded-range mechanisms). (i) Exponential mechanism. Let a real-valued score function u ( x , y ) u(x,y) u ( x , y ) satisfy ∣ u ( x , y ) − u ( x ′ , y ) ∣ ≤ Δ |u(x,y)-u(x',y)|\le\Delta ∣ u ( x , y ) − u ( x ′ , y ) ∣ ≤ Δ for all x ∼ x ′ x\sim x' x ∼ x ′ and all outputs y y y . The mechanism with density (with respect to some common base measure) proportional to exp { ε u ( x , y ) / ( 2 Δ ) } \exp\{\varepsilon u(x,y)/(2\Delta)\} exp { ε u ( x , y ) / ( 2Δ )} has log ( d Q / d P ) ( y ) = ε 2 Δ { u ( x ′ , y ) − u ( x , y ) } + log ( Z x / Z x ′ ) \log(\mathrm{d}Q/\mathrm{d}P)(y)=\frac{\varepsilon}{2\Delta}\{u(x',y)-u(x,y)\}+\log(Z_x/Z_{x'}) log ( d Q / d P ) ( y ) = 2Δ ε { u ( x ′ , y ) − u ( x , y )} + log ( Z x / Z x ′ ) , where Z x Z_x Z x is its normalizing constant. The first term lies in an interval of width ε \varepsilon ε and the second does not depend on y y y , so the mechanism is ε \varepsilon ε -BR [14 ] . (ii) Pure DP mechanisms [15 ] . A mechanism is ε \varepsilon ε -DP if P ( A ) ≤ e ε Q ( A ) P(A)\le e^\varepsilon Q(A) P ( A ) ≤ e ε Q ( A ) for every neighboring pair P = M ( x ) , Q = M ( x ′ ) P=M(x),Q=M(x') P = M ( x ) , Q = M ( x ′ ) and every measurable set A A A . Since the neighboring relation is symmetric, this is equivalent to ∣ log ( d Q / d P ) ∣ ≤ ε |\log(\mathrm{d}Q/\mathrm{d}P)|\le\varepsilon ∣ log ( d Q / d P ) ∣ ≤ ε P P P -almost surely, so every ε \varepsilon ε -DP mechanism is 2 ε 2\varepsilon 2 ε -BR. In particular, randomized response R R ε \mathrm{RR}_\varepsilon RR ε from § 2.2 is ε \varepsilon ε -DP and hence 2 ε 2\varepsilon 2 ε -BR.
Bounded-range mechanisms are members of a broader class of mechanisms, which satisfy logistic DP. Logistic DP is a convenient framework because it is closed under composition and group privacy.
Definition 12 (Logistic differential privacy). For ε ≥ 0 \varepsilon\ge0 ε ≥ 0 , a mechanism is ε \varepsilon ε -logistic DP if every neighboring pair P = M ( x ) , Q = M ( x ′ ) P=M(x),Q=M(x') P = M ( x ) , Q = M ( x ′ ) satisfies T ( P , Q ) ( α ) ≥ L ε ( α ) : = 1 − α 1 + ( e ε − 1 ) α T(P,Q)(\alpha)\ge L_\varepsilon(\alpha):=\frac{1-\alpha}{1+(e^\varepsilon-1)\alpha} T ( P , Q ) ( α ) ≥ L ε ( α ) := 1 + ( e ε − 1 ) α 1 − α for all 0 ≤ α ≤ 1 0\le\alpha\le1 0 ≤ α ≤ 1 .
Every ε \varepsilon ε -BR mechanism is ε \varepsilon ε -logistic DP [16 ] . For any randomized test with rejection probabilities 0 < p < q < 1 0<p<q<1 0 < p < q < 1 , bounded range implies log { q ( 1 − p ) / ( p ( 1 − q ) ) } ≤ ε \log\{q(1-p)/(p(1-q))\}\le\varepsilon log { q ( 1 − p ) / ( p ( 1 − q ))} ≤ ε , which is equivalent to 1 − q ≥ L ε ( p ) 1-q\ge L_\varepsilon(p) 1 − q ≥ L ε ( p ) (Appendix § 8 ). The function L ε L_\varepsilon L ε is the trade-off function between logistic distributions with locations 0 0 0 and ε \varepsilon ε and unit scale. This trade-off function arises from the additive logistic mechanism. If a statistic T T T has sensitivity Δ \Delta Δ , then T + ( Δ / ε ) Z T+(\Delta/\varepsilon)Z T + ( Δ/ ε ) Z with Z ∼ Logistic ( 0 , 1 ) Z\sim\operatorname{Logistic}(0,1) Z ∼ Logistic ( 0 , 1 ) satisfies ε \varepsilon ε -logistic DP, and the logistic noise is the unique log-concave canonical noise distribution for ε \varepsilon ε -logistic DP [2 ] . The trade-off function L ε ( α ) L_\varepsilon(\alpha) L ε ( α ) is also the pointwise lower envelope of BR trade-off curves because, for each 0 < p < 1 0<p<1 0 < p < 1 , the ε \varepsilon ε -BR Bernoulli pair with q = 1 − L ε ( p ) q=1-L_\varepsilon(p) q = 1 − L ε ( p ) attains L ε L_\varepsilon L ε at α = p \alpha=p α = p . Thus BR remains our motivating class, while logistic DP is a broader class with convenient rules for adaptive composition and group privacy, which allows a common treatment of both. In particular, composition in logistic DP is additive in the ε \varepsilon ε parameters, and a mechanism that satisfies ε \varepsilon ε -logistic DP satisfies k ε k\varepsilon k ε -logistic DP for groups of size k k k [18 , 2 ] . More details and formal statements about Logistic DP can be found in Appendix § 11 .
Theorem 13 (Sharp bounded-range-to-GDP conversion). For ε ≥ 0 \varepsilon\ge0 ε ≥ 0 , define
μ B R ( ε ) = 2 Φ − 1 ( σ ( ε / 2 ) ) . \mu_{\mathrm{BR}}(\varepsilon)=2\Phi^{-1}\left(\sigma(\varepsilon/2)\right). μ BR ( ε ) = 2 Φ − 1 ( σ ( ε /2 ) ) . Every ε \varepsilon ε -BR mechanism is μ B R ( ε ) \mu_{\mathrm{BR}}(\varepsilon) μ BR ( ε ) -GDP. More generally, every ε \varepsilon ε -logistic DP mechanism is μ B R ( ε ) \mu_{\mathrm{BR}}(\varepsilon) μ BR ( ε ) -GDP. Tightness of both conversions is demonstrated by randomized response with parameter ε / 2 \varepsilon/2 ε /2 .
Proof sketch As in Theorem 6, we reduce to a Bernoulli pair. The BR parameter of a Bernoulli pair is the distance between the log-odds of its two success probabilities, and among Bernoulli pairs with BR budget 2 t 2t 2 t , R R t \mathrm{RR}_t RR t has the largest GDP parameter, so a pair failing μ B R ( ε ) \mu_{\mathrm{BR}}(\varepsilon) μ BR ( ε ) -GDP has BR budget above ε \varepsilon ε (Appendix C). The same argument covers logistic DP, whose constraint on a single test has the same log-odds bound. R R ε / 2 \mathrm{RR}_{\varepsilon/2} RR ε /2 attains the bound by Proposition 5 . ■
For every ε > 0 \varepsilon>0 ε > 0 , direct conversion μ B R ( ε ) \mu_{\mathrm{BR}}(\varepsilon) μ BR ( ε ) is no looser than μ z C D P ( ρ B R ( ε ) ) \mu_{\mathrm{zCDP}}(\rho_{\mathrm{BR}}(\varepsilon)) μ zCDP ( ρ BR ( ε )) by the sharpness in Theorem 13. Figure 3 also shows asymmetric Bernoulli BR examples, their pointwise lower envelope L ε L_\varepsilon L ε , and the numerical zCDP testing boundary at ρ B R ( ε ) \rho_{\mathrm{BR}}(\varepsilon) ρ BR ( ε ) , computed as above. The zCDP and GDP for BR are incomparable (numerically) because their curves cross each other. Both axes are restricted to [ 0 , 0.4 ] [0,0.4] [ 0 , 0.4 ] for display; the guarantees hold over the full testing interval [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Remark 14 (Recovery of the known pure-DP conversion) By Example 11 (ii), every ε \varepsilon ε -DP mechanism is 2 ε 2\varepsilon 2 ε -BR. Theorem 13 therefore recovers the sharp conversion of [4 Lemma 2] , which states that every ε \varepsilon ε -DP mechanism is μ B R ( 2 ε ) \mu_{\mathrm{BR}}(2\varepsilon) μ BR ( 2 ε ) -GDP with μ B R ( 2 ε ) = 2 Φ − 1 ( σ ( ε ) ) \mu_{\mathrm{BR}}(2\varepsilon)=2\Phi^{-1}(\sigma(\varepsilon)) μ BR ( 2 ε ) = 2 Φ − 1 ( σ ( ε )) , and R R ε \mathrm{RR}_{\varepsilon} RR ε attains this parameter by Proposition 5 .
Theorem 15 (Shape and limiting scales of the bounded-range conversion). The conversion map ε ↦ μ B R ( ε ) \varepsilon\mapsto\mu_{\mathrm{BR}}(\varepsilon) ε ↦ μ BR ( ε ) is strictly increasing and strictly concave on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) , and satisfies lim ε ↓ 0 μ B R ( ε ) / ε = π / 8 \lim_{\varepsilon\downarrow0}\mu_{\mathrm{BR}}(\varepsilon)/\varepsilon=\sqrt{\pi/8} lim ε ↓ 0 μ BR ( ε ) / ε = π /8 and lim ε → ∞ μ B R ( ε ) / ε = 2 \lim_{\varepsilon\to\infty}\mu_{\mathrm{BR}}(\varepsilon)/\varepsilon=2 lim ε → ∞ μ BR ( ε ) / ε = 2 . Moreover, μ B R ( ε ) 2 \mu_{\mathrm{BR}}(\varepsilon)^2 μ BR ( ε ) 2 is strictly convex, μ B R ( ε ) 2 / ε \mu_{\mathrm{BR}}(\varepsilon)^2/\varepsilon μ BR ( ε ) 2 / ε is strictly increasing, and μ B R ( ε ) / ε \mu_{\mathrm{BR}}(\varepsilon)/\varepsilon μ BR ( ε ) / ε is strictly decreasing on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) . It follows that μ B R ( ε ) ≤ min { π / 8 ε , 2 ε } \mu_{\mathrm{BR}}(\varepsilon)\le\min\{\sqrt{\pi/8}\,\varepsilon,2\varepsilon\} μ BR ( ε ) ≤ min { π /8 ε , 2 ε } for all ε ≥ 0 \varepsilon\ge0 ε ≥ 0 , with both constants sharp by the two limits.
Proof sketch Since the bounded-range conversion μ B R ( ε ) \mu_{\mathrm{BR}}(\varepsilon) μ BR ( ε ) is the GDP parameter 2 Φ − 1 ( σ ( t ) ) 2\Phi^{-1}(\sigma(t)) 2 Φ − 1 ( σ ( t )) of randomized response R R t \mathrm{RR}_t RR t at t = ε / 2 t=\varepsilon/2 t = ε /2 , as μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) is at t = t ρ t=t_\rho t = t ρ , the limits and the convexity of the square follow from the calculations for Theorem 7, with ε = 2 t \varepsilon=2t ε = 2 t in place of ρ = t tanh ( t / 2 ) \rho=t\tanh(t/2) ρ = t tanh ( t /2 ) . Strict concavity follows because the derivative of t ↦ Φ − 1 ( σ ( t ) ) t\mapsto\Phi^{-1}(\sigma(t)) t ↦ Φ − 1 ( σ ( t )) is strictly decreasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) (Appendix D). ■
The different limiting scales in Theorem 7 and Theorem 15 arise from how the privacy budgets parameterize the same randomized response mechanism R R t \mathrm{RR}_t RR t . Writing its GDP parameter as 2 Φ − 1 ( σ ( t ) ) 2\Phi^{-1}(\sigma(t)) 2 Φ − 1 ( σ ( t )) , the corresponding budgets are ρ = t tanh ( t / 2 ) \rho=t\tanh(t/2) ρ = t tanh ( t /2 ) and ε = 2 t \varepsilon=2t ε = 2 t . Near zero, the GDP parameter is linear in t t t , while ρ \rho ρ is quadratic and ε \varepsilon ε is linear, giving the respective scales ρ \sqrt{\rho} ρ and ε \varepsilon ε . At infinity, the Gaussian quantile map composed with the sigmoid grows as t \sqrt{t} t , while both budgets grow linearly in t t t , yielding square-root scaling in both budgets. Figure 4 illustrates the shape of μ B R \mu_{\mathrm{BR}} μ BR and the limits of μ B R \mu_{\mathrm{BR}} μ BR stated in Theorem 15, and Figure 12 in Appendix § 9 illustrates the shape of μ B R 2 \mu_{\mathrm{BR}}^2 μ BR 2 .
Figure 4. The sharp conversion ε ↦ μ B R ( ε ) \varepsilon\mapsto\mu_{\mathrm{BR}}(\varepsilon) ε ↦ μ BR ( ε ) is strictly concave and is at most the minimum of π / 8 ε \sqrt{\pi/8}\,\varepsilon π /8 ε and 2 ε 2\sqrt{\varepsilon} 2 ε .
Figure 12. The squared sharp conversion ε ↦ μ B R ( ε ) 2 \varepsilon\mapsto\mu_{\mathrm{BR}}(\varepsilon)^2 ε ↦ μ BR ( ε ) 2 from logistic DP to GDP is strictly convex. The dotted line ε μ B R ( 25 ) 2 / 25 \varepsilon\mu_{\mathrm{BR}(25)^2}/25 ε μ BR ( 25 ) 2 /25 is the chord from 0 to 25, and the curve lies below it.
Corollary 16 (Order of conversion and accounting for logistic DP). For nonnegative ε 1 , … , ε n \varepsilon_1,\ldots,\varepsilon_n ε 1 , … , ε n and ε \varepsilon ε , and an integer k ≥ 1 k\ge1 k ≥ 1 ,
∑ i = 1 n μ B R ( ε i ) 2 ≤ μ B R ( ∑ i = 1 n ε i ) \sqrt{\sum_{i=1}^{n}\mu_{\mathrm{BR}}(\varepsilon_i)^2}\le\mu_{\mathrm{BR}}\left(\sum_{i=1}^{n}\varepsilon_i\right) ∑ i = 1 n μ BR ( ε i ) 2 ≤ μ BR ( ∑ i = 1 n ε i ) with strict inequality if at least two ε i > 0 \varepsilon_i>0 ε i > 0 .
μ B R ( k ε ) ≤ k μ B R ( ε ) \mu_{\mathrm{BR}}(k\varepsilon)\le k\mu_{\mathrm{BR}}(\varepsilon) μ BR ( k ε ) ≤ k μ BR ( ε ) with strict inequality if ε > 0 \varepsilon>0 ε > 0 and k > 1 k>1 k > 1 .
Proof sketch. The first inequality follows from strict convexity of μ B R 2 \mu_{\mathrm{BR}}^2 μ BR 2 , and the second from strict concavity of μ B R \mu_{\mathrm{BR}} μ BR , along with μ B R ( 0 ) = 0 \mu_{\mathrm{BR}}(0)=0 μ BR ( 0 ) = 0 for each (Appendix § 9 ). ■
Corollary 16 provides direct consequences on the order of privacy accounting of composition and group privacy under logistic DP and GDP. Under the adaptive composition of ε i \varepsilon_i ε i -logistic DP releases, composing in logistic DP first gives μ B R ( ∑ i ε i ) \mu_{\mathrm{BR}}(\sum_i\varepsilon_i) μ BR ( ∑ i ε i ) -GDP, while converting each release first and composing in GDP gives ∑ i μ B R ( ε i ) 2 \sqrt{\sum_i\mu_{\mathrm{BR}}(\varepsilon_i)^2} ∑ i μ BR ( ε i ) 2 -GDP, so converting first gives the tighter result. For groups of size k k k , applying logistic group privacy first gives μ B R ( k ε ) \mu_{\mathrm{BR}}(k\varepsilon) μ BR ( k ε ) -GDP, while converting first and applying GDP group privacy gives k μ B R ( ε ) k\mu_{\mathrm{BR}}(\varepsilon) k μ BR ( ε ) -GDP, so applying group privacy first is tighter. Appendix § 11 introduces the accounting properties and their connection to the log-concavity of the logistic density.
Since every ε \varepsilon ε -BR mechanism is ε \varepsilon ε -logistic DP, both inequalities apply to BR mechanisms. Figure 14 in Appendix § 9 illustrates Corollary 16 by plotting the ratio of the quantities in each inequality.
Figure 14. Left: composition shows μ B R ( λ ε ) 2 + μ B R ( ( 1 − λ ) ε ) 2 / μ B R ( ε ) ≤ 1 \sqrt{\mu_{\mathrm{BR}}(\lambda\varepsilon)^2+\mu_{\mathrm{BR}}((1-\lambda)\varepsilon)^2}/\mu_{\mathrm{BR}}(\varepsilon)\le1 μ BR ( λ ε ) 2 + μ BR (( 1 − λ ) ε ) 2 / μ BR ( ε ) ≤ 1 . Right: group privacy shows k μ B R ( ε ) / μ B R ( k ε ) ≥ 1 k\mu_{\mathrm{BR}}(\varepsilon)/\mu_{\mathrm{BR}}(k\varepsilon)\ge1 k μ BR ( ε ) / μ BR ( k ε ) ≥ 1 .
Discussion
We established the sharp conversions from zCDP and from bounded-range and logistic DP to GDP. We also established that zCDP and GDP are equivalent up to constants. Our conversions allow for more mechanisms to be analyzed under GDP, which is growing in popularity [19 ] . Since it is superior to convert from zCDP to GDP before applying either composition or group privacy, this offers additional evidence that GDP is a natural framework for DP.
Our conversions hold for any generic mechanism with only a given zCDP or BR budget, so direct GDP analysis of specific mechanisms may be tighter. Likewise, when Rényi bounds at all orders are known, the optimal trade-off guarantee of [28 ] can be tighter than the Gaussian curve implied by the zCDP budget alone. Our analysis covers only zCDP, bounded-range DP, and logistic DP, and other mechanisms or other divergence-based guarantees are outside the scope of this paper.
Several questions remain open. The exception for group privacy under bounded-range DP has a simple algebraic reason, since group privacy scales the zCDP budget by the square of the group size and the bounded-range budget by the group size itself, but an intuitive explanation is unclear. Better understanding could clarify a general rule for when early conversion is or is not beneficial for a general privacy guarantee. The discrete Gaussian mechanism has a known zCDP guarantee [12 ] , which our result converts to GDP, but to our knowledge no direct GDP guarantee is currently available for this mechanism, and such an analysis may improve the converted parameter and offer insight into the privacy guarantees of the 2020 U.S. Decennial Census products. Finally, a bound at a single finite Rényi order does not generally imply any finite GDP guarantee; identifying useful additional conditions that permit such a conversion is a direction for future work.
Acknowledgment
This work was supported in part by NSF award SES-2610910 to University of Pittsburgh.
AI Disclosure. The authors derived the series expansion in the proof of Lemma 17 , and used Wolfram|Alpha and ChatGPT to double-check its correctness. Furthermore, the authors used ChatGPT to polish the wording of the manuscript and develop function visualizations from author-written code.
Additional related work and mechanism trade-off curves
Related work
The standard conversion of [24 ] states that ( η , ε ^ ) (\eta,\widehat{\varepsilon}) ( η , ε ) -RDP implies
( ε ^ + log ( 1 / δ ) η − 1 , δ ) -DP , (2) \left(\widehat{\varepsilon}+\frac{\log(1/\delta)}{\eta-1},\delta\right)\text{-DP}, \tag*{(2)} ( ε + η − 1 log ( 1/ δ ) , δ ) -DP , (2)
for δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . Applying (2) with ε ^ = ρ η \widehat{\varepsilon}=\rho\eta ε = ρ η at each order η > 1 \eta>1 η > 1 and optimizing over η \eta η gives the standard implication of [9 ] , that is, if a mechanism is ρ \rho ρ -zCDP, then it satisfies
( ρ + 2 ρ log ( 1 / δ ) , δ ) -DP . (3) \left(\rho+2\sqrt{\rho\log(1/\delta)},\delta\right)\text{-DP}. \tag*{(3)} ( ρ + 2 ρ log ( 1/ δ ) , δ ) -DP . (3)
The conversions in (2) –(3) are not generally optimal. Optimal approximate-DP guarantees from a given RDP constraint have been characterized in [ALC+21], while an improved conversion that can also be optimized over Rényi orders is given in [12 ] . ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP is shown to be equivalent to f ε , δ f_{\varepsilon,\delta} f ε , δ -DP [18 ] , where f ε , δ ( α ) = max { 0 , 1 − δ − e ε α , e − ε ( 1 − δ − α ) } f_{\varepsilon,\delta}(\alpha)=\max\{0,1-\delta-e^{\varepsilon}\alpha,e^{-\varepsilon}(1-\delta-\alpha)\} f ε , δ ( α ) = max { 0 , 1 − δ − e ε α , e − ε ( 1 − δ − α )} . GDP corresponds exactly to the family ( ε , δ μ ( ε ) ) (\varepsilon,\delta_{\mu}(\varepsilon)) ( ε , δ μ ( ε )) -DP for all ε ≥ 0 \varepsilon\ge0 ε ≥ 0 [10 ] , where
δ μ ( ε ) = Φ ( μ 2 − ε μ ) − e ε Φ ( − μ 2 − ε μ ) . \delta_{\mu}(\varepsilon)=\Phi\left(\frac{\mu}{2}-\frac{\varepsilon}{\mu}\right)-e^{\varepsilon}\Phi\left(-\frac{\mu}{2}-\frac{\varepsilon}{\mu}\right). δ μ ( ε ) = Φ ( 2 μ − μ ε ) − e ε Φ ( − 2 μ − μ ε ) .
The divergence comparison in [18 ] gives the GDP-to-zCDP implication stated in Proposition 4 .
Illustration of mechanism trade-off curves
The left panel of Figure 5 compares densities proportional to e ε x y e^{\varepsilon xy} e ε x y on [ 0 , 1 ] [0,1] [ 0 , 1 ] with Bernoulli success probabilities σ ( ε x − ε / 2 ) \sigma(\varepsilon x-\varepsilon/2) σ ( ε x − ε /2 ) for neighboring inputs x ∈ { 0 , 1 } x\in\{0,1\} x ∈ { 0 , 1 } . For the exponential mechanism, p ( y ∣ x = 0 ) = 1 p(y\mid x=0)=1 p ( y ∣ x = 0 ) = 1 and p ( y ∣ x = 1 ) = e ε y ε / ( e ε − 1 ) p(y\mid x=1)=e^{\varepsilon y}\varepsilon/(e^{\varepsilon}-1) p ( y ∣ x = 1 ) = e ε y ε / ( e ε − 1 ) . Thus, the type II error T E M ( α ) = ∫ 0 1 − α p ( y ∣ x = 1 ) d y = ( e ε ( 1 − α ) − 1 ) / ( e ε − 1 ) T_{\mathrm{EM}}(\alpha)=\int_{0}^{1-\alpha}p(y\mid x=1)\,dy=(e^{\varepsilon(1-\alpha)}-1)/(e^{\varepsilon}-1) T EM ( α ) = ∫ 0 1 − α p ( y ∣ x = 1 ) d y = ( e ε ( 1 − α ) − 1 ) / ( e ε − 1 ) and the log density ratio log [ p ( y ∣ x = 1 ) / p ( y ∣ x = 0 ) ] = ε y + log [ ε / ( e ε − 1 ) ] \log[p(y\mid x=1)/p(y\mid x=0)]=\varepsilon y+\log[\varepsilon/(e^{\varepsilon}-1)] log [ p ( y ∣ x = 1 ) / p ( y ∣ x = 0 )] = ε y + log [ ε / ( e ε − 1 )] . For randomized response, p ( y = 1 ∣ x = 0 ) = p ( y = 0 ∣ x = 1 ) = 1 / ( 1 + e ε / 2 ) p(y=1\mid x=0)=p(y=0\mid x=1)=1/(1+e^{\varepsilon/2}) p ( y = 1 ∣ x = 0 ) = p ( y = 0 ∣ x = 1 ) = 1/ ( 1 + e ε /2 ) and p ( y = 1 ∣ x = 1 ) = p ( y = 0 ∣ x = 0 ) = e ε / 2 / ( 1 + e ε / 2 ) p(y=1\mid x=1)=p(y=0\mid x=0)=e^{\varepsilon/2}/(1+e^{\varepsilon/2}) p ( y = 1 ∣ x = 1 ) = p ( y = 0 ∣ x = 0 ) = e ε /2 / ( 1 + e ε /2 ) . The most powerful test first rejects at Y = 1 Y=1 Y = 1 , randomizing to attain size α \alpha α . For α ≤ p ( y = 1 ∣ x = 0 ) \alpha\le p(y=1\mid x=0) α ≤ p ( y = 1 ∣ x = 0 ) , this gives type II error 1 − α p ( y = 1 ∣ x = 1 ) / p ( y = 1 ∣ x = 0 ) = 1 − e ε / 2 α 1-\alpha p(y=1\mid x=1)/p(y=1\mid x=0)=1-e^{\varepsilon/2}\alpha 1 − α p ( y = 1 ∣ x = 1 ) / p ( y = 1 ∣ x = 0 ) = 1 − e ε /2 α ; for α > p ( y = 1 ∣ x = 0 ) \alpha>p(y=1\mid x=0) α > p ( y = 1 ∣ x = 0 ) , it also rejects at Y = 0 Y=0 Y = 0 , giving p ( y = 0 ∣ x = 1 ) ( 1 − α ) / p ( y = 0 ∣ x = 0 ) = e − ε / 2 ( 1 − α ) p(y=0\mid x=1)(1-\alpha)/p(y=0\mid x=0)=e^{-\varepsilon/2}(1-\alpha) p ( y = 0 ∣ x = 1 ) ( 1 − α ) / p ( y = 0 ∣ x = 0 ) = e − ε /2 ( 1 − α ) . Hence T R R ( α ) = max { 1 − e ε / 2 α , e − ε / 2 ( 1 − α ) } T_{\mathrm{RR}}(\alpha)=\max\{1-e^{\varepsilon/2}\alpha,e^{-\varepsilon/2}(1-\alpha)\} T RR ( α ) = max { 1 − e ε /2 α , e − ε /2 ( 1 − α )} . Consequently, both mechanisms have exact ε \varepsilon ε -BR, but their trade-off curves cross, so neither uniformly dominates. Orange shading and blue hatching indicate where the trade-off curve of the binary randomized response T R R T_{\mathrm{RR}} T RR and that of the exponential mechanism T E M T_{\mathrm{EM}} T EM , respectively, are lower. Randomized response touches the Gaussian lower bound at its fixed (equal-error) point, establishing sharpness of the GDP parameter.
Figure 5. Left: T E M ( α ) = ( e ε ( 1 − α ) − 1 ) / ( e ε − 1 ) T_{\mathrm{EM}}(\alpha)=(e^{\varepsilon(1-\alpha)}-1)/(e^\varepsilon-1) T EM ( α ) = ( e ε ( 1 − α ) − 1 ) / ( e ε − 1 ) and T R R ( α ) = max { 1 − e ε / 2 α , e − ε / 2 ( 1 − α ) } T_{\mathrm{RR}}(\alpha)=\max\{1-e^{\varepsilon/2}\alpha,e^{-\varepsilon/2}(1-\alpha)\} T RR ( α ) = max { 1 − e ε /2 α , e − ε /2 ( 1 − α )} lie above G μ B R ( ε ) G_{\mu\mathrm{BR}}(\varepsilon) G μ BR ( ε ) with ε = 5 \varepsilon=5 ε = 5 . Right: trade-off curves of the Gaussian mechanism and binary randomized response satisfying ρ \rho ρ -zCDP with ρ = 1 \rho=1 ρ = 1 .
Similarly, the right panel compares the trade-off curves between ρ \rho ρ -zCDP Gaussian mechanism and randomized response mechanism. Orange shading and blue hatching indicate where the trade-off curve of the binary randomized response and that of the Gaussian mechanism, respectively, are lower. Again, randomized response touches the Gaussian lower bound at its fixed (equal-error) point, establishing sharpness of the GDP parameter.
Proof of the sharp zCDP-to-GDP conversion
In the zCDP case, a failed GDP guarantee means
T ( P , Q ) ( α ) < G μ z C D P ( ρ ) ( α ) (4) T(P,Q)(\alpha)<G_{\mu_{\mathrm{zCDP}}(\rho)}(\alpha) \tag*{(4)} T ( P , Q ) ( α ) < G μ zCDP ( ρ ) ( α ) (4)
for some neighboring pair of output distributions P P P , Q Q Q and at some testing level α \alpha α . Thus starting with (4) , the desired contradiction should end with
D η ( P ∥ Q ) > ρ η or D η ( Q ∥ P ) > ρ η (5) D_{\eta}(P\|Q) > \rho\eta\quad\text{or} \quad D_{\eta}(Q\|P) > \rho\eta \tag*{(5)} D η ( P ∥ Q ) > ρ η or D η ( Q ∥ P ) > ρ η (5)
for some order η > 1 \eta> 1 η > 1 .
Bernoulli reduction
Let μ > 0 \mu> 0 μ > 0 , and suppose that T ( P , Q ) ( α ) < G μ ( α ) T(P,Q)(\alpha) < G_{\mu}(\alpha) T ( P , Q ) ( α ) < G μ ( α ) for some P = M ( x ) P = M(x) P = M ( x ) , Q = M ( x ′ ) Q = M(x') Q = M ( x ′ ) with neighboring x ∼ x ′ x \sim x' x ∼ x ′ . Then there exists a measurable test ϕ \phi ϕ such that p : = E P ϕ ≤ α p := \mathbb{E}_{P}\phi\le\alpha p := E P ϕ ≤ α and 1 − q : = 1 − E Q ϕ < G μ ( α ) 1-q := 1-\mathbb{E}_{Q}\phi< G_{\mu}(\alpha) 1 − q := 1 − E Q ϕ < G μ ( α ) .
The identity Φ − 1 ( 1 − α ) = − Φ − 1 ( α ) \Phi^{-1}(1-\alpha)=-\Phi^{-1}(\alpha) Φ − 1 ( 1 − α ) = − Φ − 1 ( α ) gives 1 − G μ ( α ) = 1 − Φ ( Φ − 1 ( α ) − μ ) = Φ ( Φ − 1 ( α ) + μ ) 1-G_{\mu}(\alpha)=1-\Phi(\Phi^{-1}(\alpha)-\mu)=\Phi(\Phi^{-1}(\alpha)+\mu) 1 − G μ ( α ) = 1 − Φ ( Φ − 1 ( α ) − μ ) = Φ ( Φ − 1 ( α ) + μ ) . Since p ≤ α p\le\alpha p ≤ α , monotonicity implies
E Q ϕ = q > Φ ( Φ − 1 ( α ) + μ ) ≥ Φ ( Φ − 1 ( p ) + μ ) . (6) \mathbb{E}_{Q}\phi=q>\Phi(\Phi^{-1}(\alpha)+\mu)\ge\Phi(\Phi^{-1}(p)+\mu). \tag*{(6)} E Q ϕ = q > Φ ( Φ − 1 ( α ) + μ ) ≥ Φ ( Φ − 1 ( p ) + μ ) . (6)
Thus violation of μ \mu μ -GDP yields a test ϕ \phi ϕ satisfying (6) . Here Φ − 1 ( 0 ) = − ∞ \Phi^{-1}(0)=-\infty Φ − 1 ( 0 ) = − ∞ and Φ − 1 ( 1 ) = + ∞ \Phi^{-1}(1)=+\infty Φ − 1 ( 1 ) = + ∞ , with Φ ( − ∞ ) = 0 \Phi(-\infty)=0 Φ ( − ∞ ) = 0 and Φ ( + ∞ ) = 1 \Phi(+\infty)=1 Φ ( + ∞ ) = 1 , so (6) also covers p = 0 p=0 p = 0 . The cases p = 0 p=0 p = 0 and q = 1 q=1 q = 1 are treated after (7) . For interior probabilities 0 < p < q < 1 0<p<q<1 0 < p < q < 1 , solving q = Φ ( Φ − 1 ( p ) + m ) q=\Phi(\Phi^{-1}(p)+m) q = Φ ( Φ − 1 ( p ) + m ) for m m m gives m p , q : = Φ − 1 ( q ) − Φ − 1 ( p ) m_{p,q}:=\Phi^{-1}(q)-\Phi^{-1}(p) m p , q := Φ − 1 ( q ) − Φ − 1 ( p ) . The quantity m p , q m_{p,q} m p , q is the Gaussian mean separation that reproduces type I error p p p and power q q q . Equation (6) implies a key inequality
m p , q = Φ − 1 ( q ) − Φ − 1 ( p ) > μ . m_{p,q}=\Phi^{-1}(q)-\Phi^{-1}(p)>\mu. m p , q = Φ − 1 ( q ) − Φ − 1 ( p ) > μ .
The binary decision and data processing
The benefit of using testing formulation is as follows. Given any mechanism output ω ∈ Ω \omega\in\Omega ω ∈ Ω , one can come up with a binary decision B ∣ ω ∼ Bern ( ϕ ( ω ) ) B\mid\omega\sim\operatorname{Bern}(\phi(\omega)) B ∣ ω ∼ Bern ( ϕ ( ω )) , where B = 1 B=1 B = 1 favors x ′ x' x ′ and B = 0 B=0 B = 0 favors x x x . Averaging
over the output distribution gives
Pr ( B = 1 ∣ input = x ) = ∫ Ω ϕ ( ω ) P ( d ω ) = E P ϕ = p , \Pr(B=1 \mid\text{input}=x)=\int_{\Omega}\phi(\omega)P(d\omega)=\mathbb{E}_{P}\phi=p, Pr ( B = 1 ∣ input = x ) = ∫ Ω ϕ ( ω ) P ( d ω ) = E P ϕ = p ,
Pr ( B = 1 ∣ input = x ′ ) = ∫ Ω ϕ ( ω ) Q ( d ω ) = E Q ϕ = q . \Pr(B=1 \mid\text{input}=x')=\int_{\Omega}\phi(\omega)Q(d\omega)=\mathbb{E}_{Q}\phi=q. Pr ( B = 1 ∣ input = x ′ ) = ∫ Ω ϕ ( ω ) Q ( d ω ) = E Q ϕ = q .
Thus B B B has distribution P ′ = Bern ( p ) P'=\operatorname{Bern}(p) P ′ = Bern ( p ) under input x x x and distribution Q ′ = Bern ( q ) Q'=\operatorname{Bern}(q) Q ′ = Bern ( q ) under input x ′ x' x ′ . Since this construction applies the same randomized post-processing to both output distributions, the Rényi data-processing inequality [31 Theorem 9 and Example 2] gives, for every η > 1 \eta>1 η > 1 ,
D η ( P ′ ∥ Q ′ ) ≤ D η ( P ∥ Q ) , D η ( Q ′ ∥ P ′ ) ≤ D η ( Q ∥ P ) . (7) D_{\eta}(P'\mathbin\Vert Q')\le D_{\eta}(P\mathbin\Vert Q),\qquad D_{\eta}(Q'\mathbin\Vert P')\le D_{\eta}(Q\mathbin\Vert P). \tag*{(7)} D η ( P ′ ∥ Q ′ ) ≤ D η ( P ∥ Q ) , D η ( Q ′ ∥ P ′ ) ≤ D η ( Q ∥ P ) . (7)
Here P = M ( x ) P=M(x) P = M ( x ) and Q = M ( x ′ ) Q=M(x') Q = M ( x ′ ) . Consequently, if either of (7) exceeds ρ η \rho\eta ρ η , that corresponding pair would have divergence exceeding ρ η \rho\eta ρ η . For boundary cases, (6) implies p < q p<q p < q . If p = 0 < q p=0<q p = 0 < q , then D η ( Q ′ ∥ P ′ ) = ∞ D_{\eta}(Q'\mathbin\Vert P')=\infty D η ( Q ′ ∥ P ′ ) = ∞ for every η > 1 \eta>1 η > 1 . If p < q = 1 p<q=1 p < q = 1 , then D η ( P ′ ∥ Q ′ ) = ∞ D_{\eta}(P'\mathbin\Vert Q')=\infty D η ( P ′ ∥ Q ′ ) = ∞ . By (7) , these cases immediately give (5) . It therefore remains to consider 0 < p < q < 1 0<p<q<1 0 < p < q < 1 .
Bernoulli divergence
For a Bernoulli pair,
D η ( Bern ( p ) ∥ Bern ( q ) ) = 1 η − 1 log [ q ( p q ) η + ( 1 − q ) ( 1 − p 1 − q ) η ] . (8) D_{\eta}(\operatorname{Bern}(p)\mathbin\Vert\operatorname{Bern}(q))=\frac{1}{\eta-1}\log\left[q\left(\frac{p}{q}\right)^{\eta}+(1-q)\left(\frac{1-p}{1-q}\right)^{\eta}\right]. \tag*{(8)} D η ( Bern ( p ) ∥ Bern ( q )) = η − 1 1 log [ q ( q p ) η + ( 1 − q ) ( 1 − q 1 − p ) η ] . (8)
Note that for η > 1 \eta>1 η > 1 , the bound D η ≤ ρ η D_{\eta}\le\rho\eta D η ≤ ρ η is equivalently a bound of e ρ η ( η − 1 ) e^{\rho\eta(\eta-1)} e ρ η ( η − 1 ) on the expression inside the logarithm. Define
K z C D P ( p , q ) : = sup η > 1 1 η max { D η ( Bern ( p ) ∥ Bern ( q ) ) , D η ( Bern ( q ) ∥ Bern ( p ) ) } . (9) K_{\mathrm{zCDP}}(p,q):=\sup_{\eta>1}\frac{1}{\eta}\max\{D_{\eta}(\operatorname{Bern}(p)\mathbin\Vert\operatorname{Bern}(q)),D_{\eta}(\operatorname{Bern}(q)\mathbin\Vert\operatorname{Bern}(p))\}. \tag*{(9)} K zCDP ( p , q ) := η > 1 sup η 1 max { D η ( Bern ( p ) ∥ Bern ( q )) , D η ( Bern ( q ) ∥ Bern ( p ))} . (9)
By (7) , it suffices to show that the binary pair obtained from a GDP violation satisfies K z C D P ( p , q ) > ρ K_{\mathrm{zCDP}}(p,q)>\rho K zCDP ( p , q ) > ρ .
From Gaussian separation to zCDP budget
For 0 < p < q < 1 0<p<q<1 0 < p < q < 1 , write m p , q : = Φ − 1 ( q ) − Φ − 1 ( p ) m_{p,q}:=\Phi^{-1}(q)-\Phi^{-1}(p) m p , q := Φ − 1 ( q ) − Φ − 1 ( p ) . The implication we need becomes
m p , q > μ z C D P ( ρ ) ⟹ K z C D P ( p , q ) > ρ . m_{p,q}>\mu_{\mathrm{zCDP}}(\rho)\Longrightarrow K_{\mathrm{zCDP}}(p,q)>\rho. m p , q > μ zCDP ( ρ ) ⟹ K zCDP ( p , q ) > ρ .
To compare a separation with a budget, we invert μ z C D P \mu_{\mathrm{zCDP}} μ zCDP . For a separation m ≥ 0 m\ge0 m ≥ 0 , let
a = log { Φ ( m / 2 ) Φ ( − m / 2 ) } . (10) a=\log\left\{\frac{\Phi(m/2)}{\Phi(-m/2)}\right\}. \tag*{(10)} a = log { Φ ( − m /2 ) Φ ( m /2 ) } . (10)
so that 2 Φ − 1 ( σ ( a ) ) = m 2\Phi^{-1}(\sigma(a))=m 2 Φ − 1 ( σ ( a )) = m . Setting t ρ = a t_{\rho}=a t ρ = a in (1) gives μ z C D P ( a tanh ( a / 2 ) ) = 2 Φ − 1 ( σ ( a ) ) = m \mu_{\mathrm{zCDP}}(a\tanh(a/2))=2\Phi^{-1}(\sigma(a))=m μ zCDP ( a tanh ( a /2 )) = 2 Φ − 1 ( σ ( a )) = m . Since σ ( a ) = Φ ( m / 2 ) \sigma(a)=\Phi(m/2) σ ( a ) = Φ ( m /2 ) and tanh ( a / 2 ) = 2 σ ( a ) − 1 \tanh(a/2)=2\sigma(a)-1 tanh ( a /2 ) = 2 σ ( a ) − 1 , the inverse conversion for m ≥ 0 m\ge0 m ≥ 0 is
μ z C D P − 1 ( m ) : = ( 2 Φ ( m / 2 ) − 1 ) log Φ ( m / 2 ) Φ ( − m / 2 ) . (11) \mu_{\mathrm{zCDP}}^{-1}(m):=(2\Phi(m/2)-1)\log\frac{\Phi(m/2)}{\Phi(-m/2)}. \tag*{(11)} μ zCDP − 1 ( m ) := ( 2Φ ( m /2 ) − 1 ) log Φ ( − m /2 ) Φ ( m /2 ) . (11)
Both factors in (11) equal zero at m = 0 m=0 m = 0 and have positive derivatives φ ( m / 2 ) \varphi(m/2) φ ( m /2 ) and φ ( m / 2 ) 2 [ 1 / Φ ( m / 2 ) + 1 / Φ ( − m / 2 ) ] \frac{\varphi(m/2)}{2}[1/\Phi(m/2)+1/\Phi(-m/2)] 2 φ ( m /2 ) [ 1/Φ ( m /2 ) + 1/Φ ( − m /2 )] , so μ z C D P − 1 \mu_{\mathrm{zCDP}}^{-1} μ zCDP − 1 is strictly increasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) . Once Lemma 20 is established, applying (11) at m = m p , q m=m_{p,q} m = m p , q shows that a GDP violation gives
K z C D P ( p , q ) ≥ μ z C D P − 1 ( m p , q ) > μ z C D P − 1 ( μ z C D P ( ρ ) ) = ρ , K_{\mathrm{zCDP}}(p,q)\ge\mu_{\mathrm{zCDP}}^{-1}(m_{p,q})>\mu_{\mathrm{zCDP}}^{-1}(\mu_{\mathrm{zCDP}}(\rho))=\rho, K zCDP ( p , q ) ≥ μ zCDP − 1 ( m p , q ) > μ zCDP − 1 ( μ zCDP ( ρ )) = ρ ,
contradicting zCDP by data processing.
The selected Rényi order
A direct approach to (25) would write p = Φ ( x ) p = \Phi(x) p = Φ ( x ) and q = Φ ( x + m ) q = \Phi(x + m) q = Φ ( x + m ) , substituting into (8) to get D η ( Bern ( p ) ∥ Bern ( q ) ) = 1 η − 1 log [ Φ ( x ) η Φ ( x + m p , q ) 1 − η + Φ ( − x ) η Φ ( − x − m p , q ) 1 − η ] D_{\eta}(\operatorname{Bern}(p)\Vert\operatorname{Bern}(q)) = \frac{1}{\eta-1}\log[\Phi(x)^{\eta}\Phi(x + m_{p,q})^{1-\eta} + \Phi(-x)^{\eta}\Phi(-x - m_{p,q})^{1-\eta}] D η ( Bern ( p ) ∥ Bern ( q )) = η − 1 1 log [ Φ ( x ) η Φ ( x + m p , q ) 1 − η + Φ ( − x ) η Φ ( − x − m p , q ) 1 − η ] . This is very cumbersome to deal with.
Instead, we use log-odds coordinates for (8) as u : = log p 1 − p u := \log\frac{p}{1-p} u := log 1 − p p and v : = log q 1 − q v := \log\frac{q}{1-q} v := log 1 − q q with u < v u < v u < v , so p = σ ( u ) p = \sigma(u) p = σ ( u ) and q = σ ( v ) q = \sigma(v) q = σ ( v ) . For the convenience of communication, we define
g ( t ) = Φ − 1 ( σ ( t ) ) . g(t) = \Phi^{-1}(\sigma(t)). g ( t ) = Φ − 1 ( σ ( t )) .
The Gaussian separation remains m p , q = g ( v ) − g ( u ) m_{p,q} = g(v) - g(u) m p , q = g ( v ) − g ( u ) .
Since p = e u / ( 1 + e u ) p = e^u/(1 + e^u) p = e u / ( 1 + e u ) and 1 − p = 1 / ( 1 + e u ) 1 - p = 1/(1 + e^u) 1 − p = 1/ ( 1 + e u ) , and similarly for q q q with v v v , the terms p η q 1 − η p^{\eta}q^{1-\eta} p η q 1 − η and ( 1 − p ) η ( 1 − q ) 1 − η (1-p)^{\eta}(1-q)^{1-\eta} ( 1 − p ) η ( 1 − q ) 1 − η in (8) equal e η u + ( 1 − η ) v e^{\eta u+(1-\eta)v} e η u + ( 1 − η ) v and 1 1 1 , each divided by ( 1 + e u ) η ( 1 + e v ) 1 − η (1+e^u)^{\eta}(1+e^v)^{1-\eta} ( 1 + e u ) η ( 1 + e v ) 1 − η . Their sum is therefore ( 1 + e η u + ( 1 − η ) v ) / [ ( 1 + e u ) η ( 1 + e v ) 1 − η ] (1+e^{\eta u+(1-\eta)v})/[(1+e^u)^{\eta}(1+e^v)^{1-\eta}] ( 1 + e η u + ( 1 − η ) v ) / [( 1 + e u ) η ( 1 + e v ) 1 − η ] . With A ( s ) : = log ( 1 + e s ) A(s) := \log(1+e^s) A ( s ) := log ( 1 + e s ) and h ( s ) : = log cosh ( s / 2 ) h(s) := \log\cosh(s/2) h ( s ) := log cosh ( s /2 ) , so that A ( s ) = s / 2 + log 2 + h ( s ) A(s) = s/2+\log2+h(s) A ( s ) = s /2 + log 2 + h ( s ) , taking logarithms gives
( η − 1 ) D η ( Bern ( p ) ∥ Bern ( q ) ) = A ( η u + ( 1 − η ) v ) − η A ( u ) − ( 1 − η ) A ( v ) = h ( η u + ( 1 − η ) v ) − η h ( u ) − ( 1 − η ) h ( v ) . (12) \begin{aligned}
(\eta-1)D_{\eta}(\operatorname{Bern}(p)\Vert\operatorname{Bern}(q)) &= A(\eta u+(1-\eta)v)-\eta A(u)-(1-\eta)A(v)\\
&= h(\eta u+(1-\eta)v)-\eta h(u)-(1-\eta)h(v). \tag*{(12)}
\end{aligned} ( η − 1 ) D η ( Bern ( p ) ∥ Bern ( q )) = A ( η u + ( 1 − η ) v ) − η A ( u ) − ( 1 − η ) A ( v ) = h ( η u + ( 1 − η ) v ) − η h ( u ) − ( 1 − η ) h ( v ) . (12)
The second equality holds because the affine part s / 2 + log 2 s/2+\log2 s /2 + log 2 contributes zero.
Since h h h is even, a suitable choice of η \eta η simplifies this expression. First suppose u + v > 0 u+v>0 u + v > 0 . In (12) , η \eta η enters h h h only through the argument v − η ( v − u ) v-\eta(v-u) v − η ( v − u ) of the first term. We choose η \eta η so that this equals − v -v − v , allowing us to use h ( − v ) = h ( v ) h(-v)=h(v) h ( − v ) = h ( v ) . Solving v − η ( v − u ) = − v v-\eta(v-u)=-v v − η ( v − u ) = − v gives
η ∗ = 2 v v − u = 1 + v + u v − u . \eta_* = \frac{2v}{v-u}=1+\frac{v+u}{v-u}. η ∗ = v − u 2 v = 1 + v − u v + u .
and η ∗ > 1 \eta_*>1 η ∗ > 1 because u + v > 0 u+v>0 u + v > 0 and v − u > 0 v-u>0 v − u > 0 . At this specific order, ( η ∗ − 1 ) D η ∗ ( Bern ( p ) ∥ Bern ( q ) ) = h ( − v ) − η ∗ h ( u ) − ( 1 − η ∗ ) h ( v ) = η ∗ [ h ( v ) − h ( u ) ] (\eta_*-1)D_{\eta_*}(\operatorname{Bern}(p)\Vert\operatorname{Bern}(q)) = h(-v)-\eta_*h(u)-(1-\eta_*)h(v)=\eta_*[h(v)-h(u)] ( η ∗ − 1 ) D η ∗ ( Bern ( p ) ∥ Bern ( q )) = h ( − v ) − η ∗ h ( u ) − ( 1 − η ∗ ) h ( v ) = η ∗ [ h ( v ) − h ( u )] , which reduces to
D η ∗ ( Bern ( p ) ∥ Bern ( q ) ) / η ∗ = ( v − u ) ( h ( v ) − h ( u ) ) / ( u + v ) . D_{\eta_*}(\operatorname{Bern}(p)\Vert\operatorname{Bern}(q))/\eta_*=(v-u)(h(v)-h(u))/(u+v). D η ∗ ( Bern ( p ) ∥ Bern ( q )) / η ∗ = ( v − u ) ( h ( v ) − h ( u )) / ( u + v ) .
If u + v < 0 u+v<0 u + v < 0 , replacing ( p , q ) (p,q) ( p , q ) by ( 1 − q , 1 − p ) (1-q,1-p) ( 1 − q , 1 − p ) maps ( u , v ) (u,v) ( u , v ) to ( − v , − u ) (-v,-u) ( − v , − u ) . This preserves K z C D P K_{\mathrm{zCDP}} K zCDP and the Gaussian separation and makes u + v > 0 u+v>0 u + v > 0 . We may therefore assume u + v ≥ 0 u+v\geq0 u + v ≥ 0 . The case u + v = 0 u+v=0 u + v = 0 corresponds to the continuous extension of K K K at c = 0 c=0 c = 0 described after (13) .
For convenience, we introduce c : = ( u + v ) / 2 ≥ 0 c := (u+v)/2\geq0 c := ( u + v ) /2 ≥ 0 and d : = ( v − u ) / 2 > 0 d := (v-u)/2>0 d := ( v − u ) /2 > 0 , so u = c − d u=c-d u = c − d , v = c + d v=c+d v = c + d , p = σ ( c − d ) p=\sigma(c-d) p = σ ( c − d ) , and q = σ ( c + d ) q=\sigma(c+d) q = σ ( c + d ) . Symmetry corresponds to c = 0 c=0 c = 0 . For c > 0 c>0 c > 0 , the selected order and its lower bound become η ∗ = 1 + c / d \eta_*=1+c/d η ∗ = 1 + c / d and
K z C D P ( p , q ) ≥ D η ∗ ( Bern ( p ) ∥ Bern ( q ) ) η ∗ = K ( c , d ) : = d c [ h ( c + d ) − h ( c − d ) ] . (13) K_{\mathrm{zCDP}}(p,q)\geq\frac{D_{\eta_*}(\operatorname{Bern}(p)\Vert\operatorname{Bern}(q))}{\eta_*}=K(c,d):=\frac{d}{c}[h(c+d)-h(c-d)]. \tag*{(13)} K zCDP ( p , q ) ≥ η ∗ D η ∗ ( Bern ( p ) ∥ Bern ( q )) = K ( c , d ) := c d [ h ( c + d ) − h ( c − d )] . (13)
The corresponding Gaussian separation is m p , q = g ( c + d ) − g ( c − d ) m_{p,q}=g(c+d)-g(c-d) m p , q = g ( c + d ) − g ( c − d ) . Note that g g g is odd (since σ ( − s ) = 1 − σ ( s ) \sigma(-s)=1-\sigma(s) σ ( − s ) = 1 − σ ( s ) and Φ \Phi Φ is symmetric), with g ′ ( s ) = σ ′ ( s ) / ϕ ( g ( s ) ) > 0 g'(s)=\sigma'(s)/\phi(g(s))>0 g ′ ( s ) = σ ′ ( s ) / ϕ ( g ( s )) > 0 .
At c = 0 c=0 c = 0 , we have p = σ ( − d ) p=\sigma(-d) p = σ ( − d ) , q = σ ( d ) = 1 − p q=\sigma(d)=1-p q = σ ( d ) = 1 − p , and η ∗ = 1 \eta_*=1 η ∗ = 1 , where the formula for K K K is undefined. The Rényi divergence at order one is the KL divergence, KL ( Bern ( σ ( − d ) ) ∥ Bern ( σ ( d ) ) ) = p ( − d ) + ( 1 − p ) d = d tanh ( d / 2 ) \operatorname{KL}(\operatorname{Bern}(\sigma(-d))\Vert\operatorname{Bern}(\sigma(d)))=p(-d)+(1-p)d=d\tanh(d/2) KL ( Bern ( σ ( − d )) ∥ Bern ( σ ( d ))) = p ( − d ) + ( 1 − p ) d = d tanh ( d /2 ) . This agrees with the limit of K K K . By evenness of h h h , h ( c + d ) − h ( c − d ) = c ∫ − 1 1 h ′ ( d + c t ) d t h(c+d)-h(c-d)=c\int_{-1}^{1}h'(d+ct)\,dt h ( c + d ) − h ( c − d ) = c ∫ − 1 1 h ′ ( d + c t ) d t , so K ( c , d ) = d ∫ − 1 1 h ′ ( d + c t ) d t K(c,d)=d\int_{-1}^{1}h'(d+ct)\,dt K ( c , d ) = d ∫ − 1 1 h ′ ( d + c t ) d t , which tends to 2 d h ′ ( d ) = d tanh ( d / 2 ) 2dh'(d)=d\tanh(d/2) 2 d h ′ ( d ) = d tanh ( d /2 ) as c → 0 c\to0 c → 0 . We therefore set K ( 0 , d ) = d tanh ( d / 2 ) K(0,d)=d\tanh(d/2) K ( 0 , d ) = d tanh ( d /2 ) .
Figure 6. Ratio of g ′ g' g ′ to w w w demonstrates the inequality of Lemma 17 .
Symmetrization at fixed Gaussian separation
Equation (13) gives K z C D P ( p , q ) ≥ K ( c , d ) K_{\mathrm{zCDP}}(p,q) \ge K(c,d) K zCDP ( p , q ) ≥ K ( c , d ) , so (25) follows from
K ( c , d ) ≥ μ z C D P − 1 ( g ( c + d ) − g ( c − d ) ) . (14) K(c,d) \ge\mu_{\mathrm{zCDP}}^{-1}\left(g(c+d)-g(c-d)\right). \tag*{(14)} K ( c , d ) ≥ μ zCDP − 1 ( g ( c + d ) − g ( c − d ) ) . (14)
Let a > 0 a>0 a > 0 solve 2 g ( a ) = g ( c + d ) − g ( c − d ) 2g(a)=g(c+d)-g(c-d) 2 g ( a ) = g ( c + d ) − g ( c − d ) , which has a unique solution because g g g is strictly increasing from zero to infinity on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) . The symmetric pair with log-odds − a , a -a,a − a , a has the same Gaussian separation, and the derivation of (11) with m = 2 g ( a ) m=2g(a) m = 2 g ( a ) gives
μ z C D P − 1 ( 2 g ( a ) ) = a tanh ( a / 2 ) = K ( 0 , a ) . (15) \mu_{\mathrm{zCDP}}^{-1}\left(2g(a)\right)=a\tanh(a/2)=K(0,a). \tag*{(15)} μ zCDP − 1 ( 2 g ( a ) ) = a tanh ( a /2 ) = K ( 0 , a ) . (15)
Thus (14) is equivalent to K ( c , d ) ≥ K ( 0 , a ) K(c,d)\ge K(0,a) K ( c , d ) ≥ K ( 0 , a ) , that is, among pairs with the same Gaussian separation, the symmetric pair minimizes K K K .
To prove this, we fix the separation 2 g ( a ) 2g(a) 2 g ( a ) and vary the midpoint c c c , choosing the half-distance d ( c ) d(c) d ( c ) so that g ( c + d ( c ) ) − g ( c − d ( c ) ) = 2 g ( a ) g(c+d(c))-g(c-d(c))=2g(a) g ( c + d ( c )) − g ( c − d ( c )) = 2 g ( a ) with d ( 0 ) = a d(0)=a d ( 0 ) = a . As c c c grows, the interval [ c − d ( c ) , c + d ( c ) ] [c-d(c),c+d(c)] [ c − d ( c ) , c + d ( c )] moves toward the tail where g ′ g' g ′ is smaller, so d ( c ) d(c) d ( c ) must grow to keep the separation, and the two comparisons below show that this growth keeps K K K from decreasing. Then, it suffices to show that c ↦ K ( c , d ( c ) ) c\mapsto K(c,d(c)) c ↦ K ( c , d ( c )) is non-decreasing. The proof of Lemma 19 in Appendix B.3 shows that, with x = c − d ( c ) x=c-d(c) x = c − d ( c ) and y = c + d ( c ) y=c+d(c) y = c + d ( c ) , this holds if
g ′ ( y ) g ′ ( x ) ≤ w ( y ) w ( x ) ≤ K d + K c K d − K c . (16) \frac{g'(y)}{g'(x)}\le\frac{w(y)}{w(x)}\le\frac{K_d+K_c}{K_d-K_c}. \tag*{(16)} g ′ ( x ) g ′ ( y ) ≤ w ( x ) w ( y ) ≤ K d − K c K d + K c . (16)
where K c K_c K c and K d K_d K d are the derivatives of K K K with respect to c c c and d d d , evaluated at ( c , d ( c ) ) (c,d(c)) ( c , d ( c )) , and w ( u ) = tanh ( u / 2 ) / u w(u)=\sqrt{\tanh(u/2)/u} w ( u ) = tanh ( u /2 ) / u for u ≠ 0 u\ne0 u = 0 and w ( 0 ) = 1 / 2 w(0)=1/\sqrt{2} w ( 0 ) = 1/ 2 . Lemmas 17 and 18 give the first and second inequalities, respectively. Note that the weight w w w is smooth, positive, and even, and the expansion tanh ( u / 2 ) / u = 1 2 − u 2 24 + O ( u 4 ) \tanh(u/2)/u=\frac{1}{2}-\frac{u^2}{24}+O(u^4) tanh ( u /2 ) / u = 2 1 − 24 u 2 + O ( u 4 ) explains its continuous value at zero.
Lemma 17 (Gaussian derivative comparison) The function u ↦ g ′ ( u ) / w ( u ) u\mapsto g'(u)/w(u) u ↦ g ′ ( u ) / w ( u ) is nonincreasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) . Consequently, for y > ∣ x ∣ y>|x| y > ∣ x ∣ , g ′ ( y ) / g ′ ( x ) ≤ w ( y ) / w ( x ) g'(y)/g'(x)\le w(y)/w(x) g ′ ( y ) / g ′ ( x ) ≤ w ( y ) / w ( x ) .
Figure 7. The trends of functions Λ \Lambda Λ , C C C , r 2 r^2 r 2 used in Lemma 17 .
Proof of Lemma 17. We aim to show that r : = g ′ / w r := g'/w r := g ′ / w satisfies r ′ ≤ 0 r' \le0 r ′ ≤ 0 by reducing this to the nonnegativity of a function Λ \Lambda Λ and ruling out a negative interior minimum of Λ \Lambda Λ .
All derivatives in this proof are with respect to u u u . Let s ( u ) : = tanh ( u / 2 ) s(u) := \tanh(u/2) s ( u ) := tanh ( u /2 ) and κ ( u ) : = − w ′ ( u ) / w ( u ) \kappa(u) := -w'(u)/w(u) κ ( u ) := − w ′ ( u ) / w ( u ) . Recall that the function w w w is smooth, positive, and even, so κ ( 0 ) = 0 \kappa(0) = 0 κ ( 0 ) = 0 . Differentiating Φ ( g ) = σ \Phi(g) = \sigma Φ ( g ) = σ gives φ ( g ) g ′ = σ ′ > 0 \varphi(g)g' = \sigma' > 0 φ ( g ) g ′ = σ ′ > 0 , so r > 0 r > 0 r > 0 .
Since r > 0 r > 0 r > 0 , it suffices to determine the sign of r ′ / r = g ′ ′ / g ′ − w ′ / w r'/r = g''/g' - w'/w r ′ / r = g ′′ / g ′ − w ′ / w . For u > 0 u > 0 u > 0 , w 2 = s / u w^2 = s/u w 2 = s / u gives w ′ / w = 1 2 ( s ′ / s − 1 / u ) w'/w = \frac{1}{2}(s'/s - 1/u) w ′ / w = 2 1 ( s ′ / s − 1/ u ) , and s ′ = 1 2 sech 2 ( u / 2 ) s' = \frac{1}{2}\operatorname{sech}^2(u/2) s ′ = 2 1 sech 2 ( u /2 ) gives s ′ / s = 1 / sinh u s'/s = 1/\sinh u s ′ / s = 1/ sinh u . Consequently, κ = 1 2 ( 1 / u − 1 / sinh u ) \kappa= \frac{1}{2}(1/u - 1/\sinh u) κ = 2 1 ( 1/ u − 1/ sinh u ) and κ ′ = − 1 / ( 2 u 2 ) + cosh u / ( 2 sinh 2 u ) \kappa' = -1/(2u^2) + \cosh u/(2\sinh^2 u) κ ′ = − 1/ ( 2 u 2 ) + cosh u / ( 2 sinh 2 u ) . Taking logarithms of φ ( g ) g ′ = σ ′ \varphi(g)g' = \sigma' φ ( g ) g ′ = σ ′ and differentiating gives − g g ′ + g ′ ′ / g ′ = σ ′ ′ / σ ′ = 1 − 2 σ = − s -gg' + g''/g' = \sigma''/\sigma' = 1 - 2\sigma= -s − g g ′ + g ′′ / g ′ = σ ′′ / σ ′ = 1 − 2 σ = − s . Therefore
r ′ / r = g g ′ − s + κ = − N , r'/r = gg' - s + \kappa= -N, r ′ / r = g g ′ − s + κ = − N ,
where N : = s − κ − g g ′ N := s - \kappa- gg' N := s − κ − g g ′ , and it suffices to show N ≥ 0 N \ge0 N ≥ 0 on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) .
Since g g g has no closed form and is complicated to deal with, we study N N N through a differential equation instead of bounding it directly. Differentiating and using g ′ ′ = g ′ ( g g ′ − s ) g'' = g'(gg' - s) g ′′ = g ′ ( g g ′ − s ) gives N ′ = s ′ − κ ′ − ( g ′ ) 2 − g g ′ ( g g ′ − s ) N' = s' - \kappa' - (g')^2 - gg'(gg' - s) N ′ = s ′ − κ ′ − ( g ′ ) 2 − g g ′ ( g g ′ − s ) . Expansion gives ( κ − g g ′ ) N − g g ′ ( g g ′ − s ) = κ ( s − κ ) (\kappa- gg')N - gg'(gg' - s) = \kappa(s - \kappa) ( κ − g g ′ ) N − g g ′ ( g g ′ − s ) = κ ( s − κ ) , so the terms containing g g ′ gg' g g ′ combine with N N N into
N ′ + ( κ − g g ′ ) N = s ′ − κ ′ + κ ( s − κ ) − ( g ′ ) 2 . (17) N' + (\kappa- gg')N = s' - \kappa' + \kappa(s - \kappa) - (g')^2. \tag*{(17)} N ′ + ( κ − g g ′ ) N = s ′ − κ ′ + κ ( s − κ ) − ( g ′ ) 2 . (17)
This is a linear first-order equation in N N N . We therefore consider the usual integrating factor A > 0 A > 0 A > 0 with A ′ / A = κ − g g ′ A'/A = \kappa- gg' A ′ / A = κ − g g ′ , which turns its left side into ( A N ) ′ / A (AN)'/A ( A N ) ′ / A . Since κ = − ( log w ) ′ \kappa= -(\log w)' κ = − ( log w ) ′ and − g g ′ = ( log φ ( g ) ) ′ -gg' = (\log\varphi(g))' − g g ′ = ( log φ ( g ) ) ′ , we take A : = φ ( g ) / w A := \varphi(g)/w A := φ ( g ) / w and define
Λ : = A N = φ ( g ) w N = φ ( g ) ( s − κ ) − g σ ′ w , (18) \Lambda:= AN = \frac{\varphi(g)}{w}N = \frac{\varphi(g)(s-\kappa)-g\sigma'}{w}, \tag*{(18)} Λ := A N = w φ ( g ) N = w φ ( g ) ( s − κ ) − g σ ′ , (18)
where the last equality uses φ ( g ) g ′ = σ ′ \varphi(g)g' = \sigma' φ ( g ) g ′ = σ ′ . Since A > 0 A > 0 A > 0 , Λ \Lambda Λ has the same sign as N N N . Multiplying (17) by A A A , and writing ( g ′ ) 2 = w 2 r 2 (g')^2 = w^2r^2 ( g ′ ) 2 = w 2 r 2 and C : = ( s ′ − κ ′ + κ ( s − κ ) ) / w 2 C := (s' - \kappa' + \kappa(s - \kappa))/w^2 C := ( s ′ − κ ′ + κ ( s − κ )) / w 2 , gives
Λ ′ = φ ( g ) w ( C − r 2 ) . (19) \Lambda' = \varphi(g)w(C-r^2). \tag*{(19)} Λ ′ = φ ( g ) w ( C − r 2 ) . (19)
Since Λ \Lambda Λ is smooth and s ( 0 ) = κ ( 0 ) = g ( 0 ) = 0 s(0) = \kappa(0) = g(0) = 0 s ( 0 ) = κ ( 0 ) = g ( 0 ) = 0 , (18) gives Λ ( 0 ) = 0 \Lambda(0) = 0 Λ ( 0 ) = 0 . For u > 0 u > 0 u > 0 , the identity coth u − 1 / sinh u = s \coth u - 1/\sinh u = s coth u − 1/ sinh u = s gives s − κ = 1 2 ( s + coth u − 1 / u ) > 0 s - \kappa= \frac{1}{2}(s + \coth u - 1/u) > 0 s − κ = 2 1 ( s + coth u − 1/ u ) > 0 (since s > 0 s > 0 s > 0 , and coth u > 1 / u \coth u > 1/u coth u > 1/ u because u cosh u − sinh u u\cosh u-\sinh u u cosh u − sinh u equals zero at u = 0 u=0 u = 0 and has derivative u sinh u > 0 u\sinh u>0 u sinh u > 0 ). Dropping the positive term in the last expression of (18) gives Λ ≥ − E \Lambda\geq-E Λ ≥ − E with E : = g σ ′ / w E:=g\sigma'/w E := g σ ′ / w . Since 1 − Φ ( g ( u ) ) = 1 − σ ( u ) = 1 / ( 1 + e u ) 1-\Phi(g(u))=1-\sigma(u)=1/(1+e^u) 1 − Φ ( g ( u )) = 1 − σ ( u ) = 1/ ( 1 + e u ) , the Chernoff bound 1 − Φ ( x ) ≤ e − x 2 / 2 1-\Phi(x)\leq e^{-x^2/2} 1 − Φ ( x ) ≤ e − x 2 /2 at x = g ( u ) > 0 x=g(u)>0 x = g ( u ) > 0 gives 1 / ( 1 + e u ) ≤ e − g ( u ) 2 / 2 1/(1+e^u)\leq e^{-g(u)^2/2} 1/ ( 1 + e u ) ≤ e − g ( u ) 2 /2 , so g ( u ) ≤ 2 log ( 1 + e u ) ≤ 2 ( u + log 2 ) g(u)\leq\sqrt{2\log(1+e^u)}\leq\sqrt{2(u+\log2)} g ( u ) ≤ 2 log ( 1 + e u ) ≤ 2 ( u + log 2 ) . Also σ ′ ( u ) ≤ e − u \sigma'(u)\leq e^{-u} σ ′ ( u ) ≤ e − u , and 1 / w ( u ) ≤ u / tanh ( 1 / 2 ) 1/w(u)\leq\sqrt{u}/\tanh(1/2) 1/ w ( u ) ≤ u / tanh ( 1/2 ) for u ≥ 1 u\geq1 u ≥ 1 . Hence 0 ≤ E ( u ) ≤ e − u 2 u ( u + log 2 ) / tanh ( 1 / 2 ) → 0 0\leq E(u)\leq e^{-u}\sqrt{2u(u+\log2)}/\tanh(1/2)\to0 0 ≤ E ( u ) ≤ e − u 2 u ( u + log 2 ) / tanh ( 1/2 ) → 0 , so lim inf u → ∞ Λ ( u ) ≥ 0 \liminf_{u\to\infty}\Lambda(u)\geq0 lim inf u → ∞ Λ ( u ) ≥ 0 .
Now, we aim to prove that C C C is strictly decreasing on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) . We write C ′ C' C ′ as a negative factor times a function H H H and show H > 0 H>0 H > 0 from its power series. Substituting s ′ = s / sinh u s'=s/\sinh u s ′ = s / sinh u and s = ( cosh u − 1 ) / sinh u s=(\cosh u-1)/\sinh u s = ( cosh u − 1 ) / sinh u ,
s ′ − κ ′ + ( s − κ ) κ = s 2 sinh u + s 2 u + 1 4 u 2 + 1 2 u sinh u − 2 cosh u + 1 4 sinh 2 u = 1 4 u 2 + cosh u 2 u sinh u − 3 4 sinh 2 u . s'-\kappa'+(s-\kappa)\kappa=\frac{s}{2\sinh u}+\frac{s}{2u}+\frac{1}{4u^2}+\frac{1}{2u\sinh u}-\frac{2\cosh u+1}{4\sinh^2u}
=\frac{1}{4u^2}+\frac{\cosh u}{2u\sinh u}-\frac{3}{4\sinh^2u}. s ′ − κ ′ + ( s − κ ) κ = 2 sinh u s + 2 u s + 4 u 2 1 + 2 u sinh u 1 − 4 sinh 2 u 2 cosh u + 1 = 4 u 2 1 + 2 u sinh u cosh u − 4 sinh 2 u 3 .
Since 1 / w 2 = u coth ( u / 2 ) 1/w^2=u\coth(u/2) 1/ w 2 = u coth ( u /2 ) , C ( u ) = coth ( u / 2 ) B ( u ) / 4 C(u)=\coth(u/2)B(u)/4 C ( u ) = coth ( u /2 ) B ( u ) /4 with B ( u ) : = 1 / u + 2 coth u − 3 u / sinh 2 u B(u):=1/u+2\coth u-3u/\sinh^2u B ( u ) := 1/ u + 2 coth u − 3 u / sinh 2 u . Then B ′ = − 1 / u 2 − 5 / sinh 2 u + 6 u cosh u / sinh 3 u B'=-1/u^2-5/\sinh^2u+6u\cosh u/\sinh^3u B ′ = − 1/ u 2 − 5/ sinh 2 u + 6 u cosh u / sinh 3 u and d d u coth ( u / 2 ) = − coth ( u / 2 ) / sinh u \frac{d}{du}\coth(u/2)=-\coth(u/2)/\sinh u d u d coth ( u /2 ) = − coth ( u /2 ) / sinh u , so the product rule gives
C ′ ( u ) = coth ( u / 2 ) 4 ( B ′ − B sinh u ) = − coth ( u / 2 ) 4 u 2 sinh 3 u H ( u ) . C'(u)=\frac{\coth(u/2)}{4}\left(B'-\frac{B}{\sinh u}\right)=-\frac{\coth(u/2)}{4u^2\sinh^3u}H(u). C ′ ( u ) = 4 coth ( u /2 ) ( B ′ − sinh u B ) = − 4 u 2 sinh 3 u coth ( u /2 ) H ( u ) .
where H ( u ) = sinh 3 u + u sinh 2 u + u 2 ( 5 + 2 cosh u ) sinh u − 3 u 3 ( 2 cosh u + 1 ) H(u)=\sinh^3u+u\sinh^2u+u^2(5+2\cosh u)\sinh u-3u^3(2\cosh u+1) H ( u ) = sinh 3 u + u sinh 2 u + u 2 ( 5 + 2 cosh u ) sinh u − 3 u 3 ( 2 cosh u + 1 ) . The factor multiplying − H ( u ) -H(u) − H ( u ) is positive for u > 0 u>0 u > 0 , so it remains to prove H ( u ) > 0 H(u)>0 H ( u ) > 0 . Using sinh 3 u = ( sinh ( 3 u ) − 3 sinh u ) / 4 \sinh^3u=(\sinh(3u)-3\sinh u)/4 sinh 3 u = ( sinh ( 3 u ) − 3 sinh u ) /4 , sinh 2 u = ( cosh ( 2 u ) − 1 ) / 2 \sinh^2u=(\cosh(2u)-1)/2 sinh 2 u = ( cosh ( 2 u ) − 1 ) /2 , and 2 cosh u sinh u = sinh ( 2 u ) 2\cosh u\sinh u=\sinh(2u) 2 cosh u sinh u = sinh ( 2 u ) ,
H ( u ) = sinh ( 3 u ) − 3 sinh u 4 + u 2 ( cosh ( 2 u ) − 1 ) + u 2 ( 5 sinh u + sinh ( 2 u ) ) − 6 u 3 cosh u − 3 u 3 . H(u)=\frac{\sinh(3u)-3\sinh u}{4}+\frac{u}{2}(\cosh(2u)-1)+u^2(5\sinh u+\sinh(2u))-6u^3\cosh u-3u^3. H ( u ) = 4 sinh ( 3 u ) − 3 sinh u + 2 u ( cosh ( 2 u ) − 1 ) + u 2 ( 5 sinh u + sinh ( 2 u )) − 6 u 3 cosh u − 3 u 3 .
Each term of H H H is odd in u u u , so H H H is odd and its power series contains only the powers u 2 n + 1 u^{2n+1} u 2 n + 1 . The coefficients of u u u , u 3 u^3 u 3 , and u 5 u^5 u 5 equal zero because 3 4 − 3 4 = 0 \frac{3}{4}-\frac{3}{4}=0 4 3 − 4 3 = 0 , 1 + 1 + 7 − 6 − 3 = 0 1+1+7-6-3=0 1 + 1 + 7 − 6 − 3 = 0 , and 1 2 + 1 3 + 13 6 − 3 = 0 \frac{1}{2}+\frac{1}{3}+\frac{13}{6}-3=0 2 1 + 3 1 + 6 13 − 3 = 0 . For n ≥ 2 n\geq2 n ≥ 2 , the coefficient of u 2 n + 1 / ( 2 n + 1 ) ! u^{2n+1}/(2n+1)! u 2 n + 1 / ( 2 n + 1 )! is 3 2 n + 1 / 4 3^{2n+1}/4 3 2 n + 1 /4 from 1 4 sinh ( 3 u ) \frac{1}{4}\sinh(3u) 4 1 sinh ( 3 u ) , − 3 / 4 -3/4 − 3/4 from − 3 4 sinh u -\frac{3}{4}\sinh u − 4 3 sinh u , ( 2 n + 1 ) 2 2 n − 1 (2n+1)2^{2n-1} ( 2 n + 1 ) 2 2 n − 1 from u 2 cosh ( 2 u ) \frac{u}{2}\cosh(2u) 2 u cosh ( 2 u ) , 2 n ( 2 n + 1 ) ( 5 + 2 2 n − 1 ) 2n(2n+1)(5+2^{2n-1}) 2 n ( 2 n + 1 ) ( 5 + 2 2 n − 1 ) from u 2 ( 5 sinh u + sinh ( 2 u ) ) u^2(5\sinh u+\sinh(2u)) u 2 ( 5 sinh u + sinh ( 2 u )) , and − 6 ( 2 n − 1 ) ( 2 n ) ( 2 n + 1 ) -6(2n-1)(2n)(2n+1) − 6 ( 2 n − 1 ) ( 2 n ) ( 2 n + 1 ) from − 6 u 3 cosh u -6u^3\cosh u − 6 u 3 cosh u , while − u / 2 -u/2 − u /2 and − 3 u 3 -3u^3 − 3 u 3 affect only u u u and u 3 u^3 u 3 . Hence H ( u ) = ∑ n = 3 ∞ A n u 2 n + 1 ( 2 n + 1 ) ! H(u)=\sum_{n=3}^{\infty}A_n\frac{u^{2n+1}}{(2n+1)!} H ( u ) = ∑ n = 3 ∞ A n ( 2 n + 1 )! u 2 n + 1 , where
A n = 3 2 n + 1 − 3 4 + ( 2 n + 1 ) 2 2 n − 1 + 2 n ( 2 n + 1 ) ( 5 + 2 2 n − 1 ) − 6 ( 2 n − 1 ) ( 2 n ) ( 2 n + 1 ) = 3 2 n + 1 − 3 4 + ( 2 n + 1 ) 2 2 n − 1 − 2 n ( 2 n + 1 ) ( 12 n − 11 ) . \begin{aligned}
A_n=\frac{3^{2n+1}-3}{4}+(2n+1)2^{2n-1}+2n(2n+1)(5+2^{2n-1})-6(2n-1)(2n)(2n+1) \\
&=\frac{3^{2n+1}-3}{4}+(2n+1)2^{2n-1}-2n(2n+1)(12n-11).
\end{aligned} A n = 4 3 2 n + 1 − 3 + ( 2 n + 1 ) 2 2 n − 1 + 2 n ( 2 n + 1 ) ( 5 + 2 2 n − 1 ) − 6 ( 2 n − 1 ) ( 2 n ) ( 2 n + 1 ) = 4 3 2 n + 1 − 3 + ( 2 n + 1 ) 2 2 n − 1 − 2 n ( 2 n + 1 ) ( 12 n − 11 ) .
For n ≥ 3 n\geq3 n ≥ 3 , 2 2 n − 1 ≥ 12 n − 11 2^{2n-1}\geq12n-11 2 2 n − 1 ≥ 12 n − 11 by induction, since 2 5 = 32 ≥ 25 2^5=32\geq25 2 5 = 32 ≥ 25 and 2 2 n + 1 = 4 ⋅ 2 2 n − 1 ≥ 48 n − 44 ≥ 12 ( n + 1 ) − 11 2^{2n+1}=4\cdot2^{2n-1}\geq48n-44\geq12(n+1)-11 2 2 n + 1 = 4 ⋅ 2 2 n − 1 ≥ 48 n − 44 ≥ 12 ( n + 1 ) − 11 . Hence ( 2 n + 1 ) 2 2 n − 1 > 2 n ( 2 n + 1 ) ( 12 n − 11 ) (2n+1)2^{2n-1}>2n(2n+1)(12n-11) ( 2 n + 1 ) 2 2 n − 1 > 2 n ( 2 n + 1 ) ( 12 n − 11 ) , and with ( 3 2 n + 1 − 3 ) / 4 > 0 (3^{2n+1}-3)/4>0 ( 3 2 n + 1 − 3 ) /4 > 0 this gives A n > 0 A_n>0 A n > 0 . Every term of the series for H ( u ) H(u) H ( u ) is therefore positive for u > 0 u>0 u > 0 , so H ( u ) > 0 H(u)>0 H ( u ) > 0 and C ′ ( u ) < 0 C'(u)<0 C ′ ( u ) < 0 .
The facts Λ ( 0 ) = 0 \Lambda(0)=0 Λ ( 0 ) = 0 , lim inf u → ∞ Λ ( u ) ≥ 0 \liminf_{u\to\infty}\Lambda(u)\geq0 lim inf u → ∞ Λ ( u ) ≥ 0 , and C ′ < 0 C'<0 C ′ < 0 now combine to show that Λ \Lambda Λ cannot take a negative value. Suppose Λ ( u 0 ) < 0 \Lambda(u_0)<0 Λ ( u 0 ) < 0 for some u 0 > 0 u_0>0 u 0 > 0 . Since lim inf u → ∞ Λ ( u ) ≥ 0 \liminf_{u\to\infty}\Lambda(u)\geq0 lim inf u → ∞ Λ ( u ) ≥ 0 , there is R > u 0 R>u_0 R > u 0 with Λ ( R ) > Λ ( u 0 ) \Lambda(R)>\Lambda(u_0) Λ ( R ) > Λ ( u 0 ) . Since Λ ( 0 ) = 0 > Λ ( u 0 ) \Lambda(0)=0>\Lambda(u_0) Λ ( 0 ) = 0 > Λ ( u 0 ) , the minimum of Λ \Lambda Λ on [ 0 , R ] [0,R] [ 0 , R ] is attained at an interior point v v v , where Λ ( v ) < 0 \Lambda(v)<0 Λ ( v ) < 0 , Λ ′ ( v ) = 0 \Lambda'(v)=0 Λ ′ ( v ) = 0 , and Λ ′ ′ ( v ) ≥ 0 \Lambda''(v)\geq0 Λ ′′ ( v ) ≥ 0 . First, Λ ( v ) < 0 \Lambda(v)<0 Λ ( v ) < 0 gives N ( v ) < 0 N(v)<0 N ( v ) < 0 , so r ′ ( v ) = − r ( v ) N ( v ) > 0 r'(v)=-r(v)N(v)>0 r ′ ( v ) = − r ( v ) N ( v ) > 0 . Second, Λ ′ ( v ) = 0 \Lambda'(v)=0 Λ ′ ( v ) = 0 and (19) give C ( v ) = r ( v ) 2 C(v)=r(v)^2 C ( v ) = r ( v ) 2 . Third, differentiating (19) gives Λ ′ ′ ( v ) = φ ( g ( v ) ) w ( v ) [ C ′ ( v ) − 2 r ( v ) r ′ ( v ) ] < 0 \Lambda''(v)=\varphi(g(v))w(v)[C'(v)-2r(v)r'(v)]<0 Λ ′′ ( v ) = φ ( g ( v )) w ( v ) [ C ′ ( v ) − 2 r ( v ) r ′ ( v )] < 0 , because C ′ ( v ) < 0 C'(v)<0 C ′ ( v ) < 0 , r ( v ) > 0 r(v)>0 r ( v ) > 0 , and r ′ ( v ) > 0 r'(v)>0 r ′ ( v ) > 0 . This contradicts Λ ′ ′ ( v ) ≥ 0 \Lambda''(v)\geq0 Λ ′′ ( v ) ≥ 0 .
This contradiction shows that Λ ≥ 0 \Lambda\geq0 Λ ≥ 0 on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) . Since A > 0 A>0 A > 0 and r > 0 r>0 r > 0 , it follows that N = Λ / A ≥ 0 N=\Lambda/A\geq0 N = Λ/ A ≥ 0 and hence r ′ = − r N ≤ 0 r'=-rN\leq0 r ′ = − r N ≤ 0 on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) . Since r r r is continuous on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) , the function r = g ′ / w r=g'/w r = g ′ / w is therefore nonincreasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) . Finally, let y > ∣ x ∣ y>|x| y > ∣ x ∣ . Since 0 ≤ ∣ x ∣ < y 0\leq|x|<y 0 ≤ ∣ x ∣ < y and g ′ g' g ′ and w w w are even, g ′ ( y ) / w ( y ) ≤ g ′ ( ∣ x ∣ ) / w ( ∣ x ∣ ) = g ′ ( x ) / w ( x ) g'(y)/w(y)\leq g'(|x|)/w(|x|)=g'(x)/w(x) g ′ ( y ) / w ( y ) ≤ g ′ ( ∣ x ∣ ) / w ( ∣ x ∣ ) = g ′ ( x ) / w ( x ) , which rearranges to g ′ ( y ) / g ′ ( x ) ≤ w ( y ) / w ( x ) g'(y)/g'(x)\leq w(y)/w(x) g ′ ( y ) / g ′ ( x ) ≤ w ( y ) / w ( x ) because g ′ g' g ′ and w w w are positive.
Figure 8. Illustration of the inequality of Lemma 18.
Lemma 18 (Hyperbolic integral comparison) For y > ∣ x ∣ y > \lvert x\rvert y > ∣ x ∣ ,
4 [ h ( y ) − h ( x ) ] ≤ ( y 2 − x 2 ) w ( x ) w ( y ) . (20) 4[h(y)-h(x)] \le(y^2-x^2)w(x)w(y). \tag*{(20)} 4 [ h ( y ) − h ( x )] ≤ ( y 2 − x 2 ) w ( x ) w ( y ) . (20)
Proof of Lemma 18 Define
W ( t ) = { tanh ( t / 2 ) / t , t > 0 , 1 / 2 , t = 0 , W(t)=
\begin{cases}
\tanh(\sqrt{t}/2)/\sqrt{t}, & t>0,\\
1/2, & t=0,
\end{cases} W ( t ) = { tanh ( t /2 ) / t , 1/2 , t > 0 , t = 0 ,
so that W ( u 2 ) = w ( u ) 2 W(u^2)=w(u)^2 W ( u 2 ) = w ( u ) 2 and d d t h ( t ) = 1 4 W ( t ) \frac{\mathrm{d}}{\mathrm{d}t}h(\sqrt{t})=\frac{1}{4}W(t) d t d h ( t ) = 4 1 W ( t ) . Since h h h is even, 4 [ h ( y ) − h ( x ) ] = ∫ x 2 y 2 W ( t ) d t 4[h(y)-h(x)]=\int_{x^2}^{y^2}W(t)\,\mathrm{d}t 4 [ h ( y ) − h ( x )] = ∫ x 2 y 2 W ( t ) d t , and (20) becomes
1 y 2 − x 2 ∫ x 2 y 2 W ( t ) d t ≤ W ( x 2 ) W ( y 2 ) . (21) \frac{1}{y^2-x^2}\int_{x^2}^{y^2}W(t)\,\mathrm{d}t\le\sqrt{W(x^2)W(y^2)}. \tag*{(21)} y 2 − x 2 1 ∫ x 2 y 2 W ( t ) d t ≤ W ( x 2 ) W ( y 2 ) . (21)
To write W W W as a sum of simple terms, take logarithms in the Euler product cosh z = ∏ n = 1 ∞ ( 1 + 4 z 2 π 2 ( 2 n − 1 ) 2 ) \cosh z=\prod_{n=1}^{\infty}\left(1+\frac{4z^2}{\pi^2(2n-1)^2}\right) cosh z = ∏ n = 1 ∞ ( 1 + π 2 ( 2 n − 1 ) 2 4 z 2 ) [25 ] at z = t / 2 z=\sqrt{t}/2 z = t /2 . With λ n = π 2 ( 2 n − 1 ) 2 \lambda_n=\pi^2(2n-1)^2 λ n = π 2 ( 2 n − 1 ) 2 , this gives log cosh ( t / 2 ) = ∑ n = 1 ∞ log ( 1 + t / λ n ) \log\cosh(\sqrt{t}/2)=\sum_{n=1}^{\infty}\log(1+t/\lambda_n) log cosh ( t /2 ) = ∑ n = 1 ∞ log ( 1 + t / λ n ) , and differentiating in t t t gives
W ( t ) = 4 ∑ n = 1 ∞ f n ( t ) , (22) W(t)=4\sum_{n=1}^{\infty}f_n(t), \tag*{(22)} W ( t ) = 4 n = 1 ∑ ∞ f n ( t ) , (22)
where f n ( t ) : = 1 t + λ n f_n(t):=\frac{1}{t+\lambda_n} f n ( t ) := t + λ n 1 . Each f n f_n f n satisfies (21) with W W W replaced by f n f_n f n . With a n = x 2 + λ n a_n=x^2+\lambda_n a n = x 2 + λ n and b n = y 2 + λ n b_n=y^2+\lambda_n b n = y 2 + λ n , the average of f n f_n f n over [ x 2 , y 2 ] [x^2,y^2] [ x 2 , y 2 ] is ( log b n − log a n ) / ( b n − a n ) (\log b_n-\log a_n)/(b_n-a_n) ( log b n − log a n ) / ( b n − a n ) , the reciprocal of the logarithmic mean of a n a_n a n and b n b_n b n . Since the logarithmic mean is at least the geometric mean a n b n \sqrt{a_nb_n} a n b n [11 ] ,
1 y 2 − x 2 ∫ x 2 y 2 f n ( t ) d t ≤ 1 a n b n = f n ( x 2 ) f n ( y 2 ) . (23) \frac{1}{y^2-x^2}\int_{x^2}^{y^2}f_n(t)\,\mathrm{d}t\le\frac{1}{\sqrt{a_nb_n}}=\sqrt{f_n(x^2)f_n(y^2)}. \tag*{(23)} y 2 − x 2 1 ∫ x 2 y 2 f n ( t ) d t ≤ a n b n 1 = f n ( x 2 ) f n ( y 2 ) . (23)
Integrating the positive series (22) term by term, then applying (23) and Cauchy–Schwarz,
1 y 2 − x 2 ∫ x 2 y 2 W ( t ) d t ≤ 4 ∑ n = 1 ∞ f n ( x 2 ) f n ( y 2 ) ≤ 4 ( ∑ n = 1 ∞ f n ( x 2 ) ) ( ∑ n = 1 ∞ f n ( y 2 ) ) . \frac{1}{y^2-x^2}\int_{x^2}^{y^2}W(t)\,\mathrm{d}t\le4\sum_{n=1}^{\infty}\sqrt{f_n(x^2)}\sqrt{f_n(y^2)}
\le4\sqrt{\left(\sum_{n=1}^{\infty}f_n(x^2)\right)\left(\sum_{n=1}^{\infty}f_n(y^2)\right)}. y 2 − x 2 1 ∫ x 2 y 2 W ( t ) d t ≤ 4 n = 1 ∑ ∞ f n ( x 2 ) f n ( y 2 ) ≤ 4 ( n = 1 ∑ ∞ f n ( x 2 ) ) ( n = 1 ∑ ∞ f n ( y 2 ) ) .
This proves (21) , and hence (20) follows.
We now combine Lemmas 17 and 18 . Along a curve of fixed Gaussian separation, they imply that the lower bound K K K in (13) cannot decrease as the midpoint moves away from zero (Figure 9 ).
Figure 9. Ratio of the selected-order bound to the zCDP budget of randomized response, plotted against the midpoint c c c of the log-odds of the two Bernoulli distributions, for Bernoulli pairs with a fixed GDP parameter. The ratio is at least one and equals one at c = 0 c = 0 c = 0 , which corresponds to R R t \mathrm{RR}_{t} RR t .
Lemma 19 (Symmetrization at fixed Gaussian separation). Let c ≥ 0 c \ge0 c ≥ 0 , d > 0 d > 0 d > 0 , and a > 0 a > 0 a > 0 satisfy g ( c + d ) − g ( c − d ) = 2 g ( a ) g(c+d) - g(c-d) = 2g(a) g ( c + d ) − g ( c − d ) = 2 g ( a ) . Then K ( c , d ) ≥ K ( 0 , a ) = a tanh ( a / 2 ) K(c,d) \ge K(0,a) = a \tanh(a/2) K ( c , d ) ≥ K ( 0 , a ) = a tanh ( a /2 ) .
Proof of Lemma 19. We show that K K K does not decrease along the curve of Gaussian separation 2 g ( a ) 2g(a) 2 g ( a ) as c c c moves away from zero. For each c ≥ 0 c \ge0 c ≥ 0 , the function d ↦ g ( c + d ) − g ( c − d ) d \mapsto g(c+d) - g(c-d) d ↦ g ( c + d ) − g ( c − d ) increases strictly from zero at d = 0 d = 0 d = 0 to infinity because its derivative is g ′ ( c + d ) + g ′ ( c − d ) > 0 g'(c+d) + g'(c-d) > 0 g ′ ( c + d ) + g ′ ( c − d ) > 0 . So, there exists a unique d ( c ) > 0 d(c) > 0 d ( c ) > 0 that satisfies g ( c + d ( c ) ) − g ( c − d ( c ) ) = 2 g ( a ) g(c+d(c))-g(c-d(c)) = 2g(a) g ( c + d ( c )) − g ( c − d ( c )) = 2 g ( a ) , and d ( 0 ) = a d(0) = a d ( 0 ) = a because g g g is odd. By the implicit function theorem and uniqueness, d ( ⋅ ) d(\cdot) d ( ⋅ ) is smooth, so d ( c ) → a d(c) \to a d ( c ) → a as c ↓ 0 c \downarrow0 c ↓ 0 . Since K K K is continuous at c = 0 c = 0 c = 0 (Appendix § 7 .§ 2 ), the map c ↦ K ( c , d ( c ) ) c \mapsto K(c,d(c)) c ↦ K ( c , d ( c )) is continuous at zero with value K ( 0 , a ) K(0,a) K ( 0 , a ) , and it suffices to show d d c K ( c , d ( c ) ) ≥ 0 \frac{d}{dc}K(c,d(c)) \ge0 d c d K ( c , d ( c )) ≥ 0 for c > 0 c > 0 c > 0 .
Given c > 0 c > 0 c > 0 and write d = d ( c ) d = d(c) d = d ( c ) , x = c − d x = c-d x = c − d , y = c + d y = c+d y = c + d , L = h ( y ) − h ( x ) L = h(y)-h(x) L = h ( y ) − h ( x ) , and B = y 2 − x 2 = 4 c d B = y^{2}-x^{2} = 4cd B = y 2 − x 2 = 4 c d . Since y − x = 2 d > 0 y-x = 2d > 0 y − x = 2 d > 0 and y + x = 2 c > 0 y+x = 2c > 0 y + x = 2 c > 0 , we have y > ∣ x ∣ y > \lvert x\rvert y > ∣ x ∣ , so L > 0 L > 0 L > 0 and B > 0 B > 0 B > 0 . Differentiating the constraint g ( c + d ( c ) ) − g ( c − d ( c ) ) = 2 g ( a ) g(c+d(c))-g(c-d(c)) = 2g(a) g ( c + d ( c )) − g ( c − d ( c )) = 2 g ( a ) gives g ′ ( y ) ( 1 + d ′ ( c ) ) − g ′ ( x ) ( 1 − d ′ ( c ) ) = 0 g'(y)(1+d'(c))-g'(x)(1-d'(c)) = 0 g ′ ( y ) ( 1 + d ′ ( c )) − g ′ ( x ) ( 1 − d ′ ( c )) = 0 , so d ′ ( c ) = ( g ′ ( x ) − g ′ ( y ) ) / ( g ′ ( x ) + g ′ ( y ) ) d'(c) = (g'(x)-g'(y))/(g'(x)+g'(y)) d ′ ( c ) = ( g ′ ( x ) − g ′ ( y )) / ( g ′ ( x ) + g ′ ( y )) . By the chain rule,
d d c K ( c , d ( c ) ) = K c + K d d ′ ( c ) = g ′ ( x ) ( K d + K c ) − g ′ ( y ) ( K d − K c ) g ′ ( x ) + g ′ ( y ) . (24) \frac{d}{dc}K(c,d(c)) = K_c + K_d d'(c) = \frac{g'(x)(K_d+K_c)-g'(y)(K_d-K_c)}{g'(x)+g'(y)}. \tag*{(24)} d c d K ( c , d ( c )) = K c + K d d ′ ( c ) = g ′ ( x ) + g ′ ( y ) g ′ ( x ) ( K d + K c ) − g ′ ( y ) ( K d − K c ) . (24)
Differentiating K ( c , d ) = d [ h ( c + d ) − h ( c − d ) ] / c K(c,d) = d[h(c+d)-h(c-d)]/c K ( c , d ) = d [ h ( c + d ) − h ( c − d )] / c gives K c = − d L / c 2 + d [ h ′ ( y ) − h ′ ( x ) ] / c K_c = -dL/c^2 + d[h'(y)-h'(x)]/c K c = − d L / c 2 + d [ h ′ ( y ) − h ′ ( x )] / c and K d = L / c + d [ h ′ ( y ) + h ′ ( x ) ] / c K_d = L/c + d[h'(y)+h'(x)]/c K d = L / c + d [ h ′ ( y ) + h ′ ( x )] / c . Adding and subtracting, with B = 4 c d B = 4cd B = 4 c d , yields K d + K c = N / ( 2 c 2 ) K_d+K_c = N/(2c^2) K d + K c = N / ( 2 c 2 ) and K d − K c = D / ( 2 c 2 ) K_d-K_c = D/(2c^2) K d − K c = D / ( 2 c 2 ) , where N : = 2 x L + B h ′ ( y ) N := 2xL + Bh'(y) N := 2 xL + B h ′ ( y ) and D : = 2 y L + B h ′ ( x ) D := 2yL + Bh'(x) D := 2 y L + B h ′ ( x ) .
The sign of (24) can be read off once we know D > 0 D > 0 D > 0 . If x ≥ 0 x \ge0 x ≥ 0 , then 2 y L > 0 2yL > 0 2 y L > 0 and B h ′ ( x ) ≥ 0 Bh'(x) \ge0 B h ′ ( x ) ≥ 0 . If x = − t < 0 x = -t < 0 x = − t < 0 , then 0 < t < y 0 < t < y 0 < t < y , and evenness and convexity of h h h give L = h ( y ) − h ( t ) ≥ ( y − t ) h ′ ( t ) L = h(y)-h(t) \ge(y-t)h'(t) L = h ( y ) − h ( t ) ≥ ( y − t ) h ′ ( t ) . Since h ′ ( x ) = − h ′ ( t ) h'(x) = -h'(t) h ′ ( x ) = − h ′ ( t ) , it follows that D = 2 y L − ( y 2 − t 2 ) h ′ ( t ) ≥ [ 2 y ( y − t ) − ( y 2 − t 2 ) ] h ′ ( t ) = ( y − t ) 2 h ′ ( t ) > 0 D = 2yL-(y^2-t^2)h'(t) \ge[2y(y-t)-(y^2-t^2)]h'(t) = (y-t)^2h'(t) > 0 D = 2 y L − ( y 2 − t 2 ) h ′ ( t ) ≥ [ 2 y ( y − t ) − ( y 2 − t 2 )] h ′ ( t ) = ( y − t ) 2 h ′ ( t ) > 0 . Thus D > 0 D>0 D > 0 in both cases, so K d − K c > 0 K_d-K_c>0 K d − K c > 0 . Since also g ′ ( x ) > 0 g'(x)>0 g ′ ( x ) > 0 , (24) shows that d d c K ( c , d ( c ) ) ≥ 0 \frac{d}{dc}K(c,d(c))\geq0 d c d K ( c , d ( c )) ≥ 0 if and only if g ′ ( y ) / g ′ ( x ) ≤ ( K d + K c ) / ( K d − K c ) = N / D g'(y)/g'(x)\leq(K_d+K_c)/(K_d-K_c)=N/D g ′ ( y ) / g ′ ( x ) ≤ ( K d + K c ) / ( K d − K c ) = N / D .
We verify this condition through the intermediate ratio w ( y ) / w ( x ) w(y)/w(x) w ( y ) / w ( x ) , as in (16) . Since y > ∣ x ∣ y>|x| y > ∣ x ∣ , Lemma 17 yields g ′ ( y ) / g ′ ( x ) ≤ w ( y ) / w ( x ) g'(y)/g'(x)\leq w(y)/w(x) g ′ ( y ) / g ′ ( x ) ≤ w ( y ) / w ( x ) . To compare w ( y ) / w ( x ) w(y)/w(x) w ( y ) / w ( x ) with N / D N/D N / D , use h ′ ( u ) = u w ( u ) 2 / 2 h'(u)=uw(u)^2/2 h ′ ( u ) = u w ( u ) 2 /2 to calculate
N w ( x ) − D w ( y ) = 2 L [ x w ( x ) − y w ( y ) ] + B [ h ′ ( y ) w ( x ) − h ′ ( x ) w ( y ) ] = 2 L [ x w ( x ) − y w ( y ) ] + B 2 w ( x ) w ( y ) [ y w ( y ) − x w ( x ) ] = [ y w ( y ) − x w ( x ) ] [ B 2 w ( x ) w ( y ) − 2 L ] . \begin{aligned}
Nw(x)-Dw(y)&=2L[xw(x)-yw(y)]+B[h'(y)w(x)-h'(x)w(y)]\\
&=2L[xw(x)-yw(y)]+\frac{B}{2}w(x)w(y)[yw(y)-xw(x)]\\
&=[yw(y)-xw(x)]\left[\frac{B}{2}w(x)w(y)-2L\right].
\end{aligned} N w ( x ) − D w ( y ) = 2 L [ x w ( x ) − y w ( y )] + B [ h ′ ( y ) w ( x ) − h ′ ( x ) w ( y )] = 2 L [ x w ( x ) − y w ( y )] + 2 B w ( x ) w ( y ) [ y w ( y ) − x w ( x )] = [ y w ( y ) − x w ( x )] [ 2 B w ( x ) w ( y ) − 2 L ] .
The first factor is positive because y > ∣ x ∣ y>|x| y > ∣ x ∣ , and u w ( u ) uw(u) u w ( u ) is odd and equals u tanh ( u / 2 ) \sqrt{u}\tanh(u/2) u tanh ( u /2 ) for u > 0 u>0 u > 0 , which is strictly increasing because u u u and tanh ( u / 2 ) \tanh(u/2) tanh ( u /2 ) are. The second factor is nonnegative by Lemma 18, since 4 L ≤ B w ( x ) w ( y ) 4L\leq Bw(x)w(y) 4 L ≤ B w ( x ) w ( y ) . Hence N w ( x ) ≥ D w ( y ) Nw(x)\geq Dw(y) N w ( x ) ≥ D w ( y ) , and dividing by D w ( x ) > 0 Dw(x)>0 D w ( x ) > 0 yields w ( y ) / w ( x ) ≤ N / D w(y)/w(x)\leq N/D w ( y ) / w ( x ) ≤ N / D . Combining the two comparisons gives g ′ ( y ) / g ′ ( x ) ≤ N / D g'(y)/g'(x)\leq N/D g ′ ( y ) / g ′ ( x ) ≤ N / D , so d d c K ( c , d ( c ) ) ≥ 0 \frac{d}{dc}K(c,d(c))\geq0 d c d K ( c , d ( c )) ≥ 0 .
Thus, c ↦ K ( c , d ( c ) ) c\mapsto K(c,d(c)) c ↦ K ( c , d ( c )) is nondecreasing on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , and by continuity at zero, K ( c , d ( c ) ) ≥ K ( 0 , a ) = a tanh ( a / 2 ) K(c,d(c))\geq K(0,a)=a\tanh(a/2) K ( c , d ( c )) ≥ K ( 0 , a ) = a tanh ( a /2 ) for every c ≥ 0 c\geq0 c ≥ 0 . Since uniqueness gives d = d ( c ) d=d(c) d = d ( c ) for the pair ( c , d ) (c,d) ( c , d ) in the lemma, this proves Lemma 19. ■
Completing the zCDP Bernoulli bound and conversion
Equation (13) and Lemma 19 now give the zCDP comparison between the divergence budget K z C D P K_{\mathrm{zCDP}} K zCDP in (9) and the inverse conversion μ z C D P − 1 \mu_{\mathrm{zCDP}}^{-1} μ zCDP − 1 in (11) . The symmetric case follows by taking the Rényi order to one.
Lemma 20 (The zCDP Bernoulli comparison). ** For every 0 < p < q < 1 0<p<q<1 0 < p < q < 1 ,
K z C D P ( p , q ) ≥ μ z C D P − 1 ( m p , q ) . (25) K_{\mathrm{zCDP}}(p,q)\geq\mu_{\mathrm{zCDP}}^{-1}(m_{p,q}). \tag*{(25)} K zCDP ( p , q ) ≥ μ zCDP − 1 ( m p , q ) . (25) Equality holds for the symmetric pair p = σ ( − a ) p=\sigma(-a) p = σ ( − a ) , q = σ ( a ) q=\sigma(a) q = σ ( a ) with Gaussian separation m p , q = 2 Φ − 1 ( σ ( a ) ) m_{p,q}=2\Phi^{-1}(\sigma(a)) m p , q = 2 Φ − 1 ( σ ( a )) .
Proof of Lemma 20. By the reflection in Appendix B.2, we may assume c ≥ 0 c\geq0 c ≥ 0 , with p = σ ( c − d ) p=\sigma(c-d) p = σ ( c − d ) , q = σ ( c + d ) q=\sigma(c+d) q = σ ( c + d ) , and d > 0 d>0 d > 0 . We first show K z C D P ( p , q ) ≥ K ( c , d ) K_{\mathrm{zCDP}}(p,q)\geq K(c,d) K zCDP ( p , q ) ≥ K ( c , d ) . For c > 0 c>0 c > 0 , this is (13) . For c = 0 c=0 c = 0 , letting η ↓ 1 \eta\downarrow1 η ↓ 1 in (9) gives K z C D P ( p , q ) ≥ KL ( Bern ( p ) ∥ Bern ( q ) ) = d tanh ( d / 2 ) = K ( 0 , d ) K_{\mathrm{zCDP}}(p,q)\geq\operatorname{KL}(\operatorname{Bern}(p)\mathbin\Vert\operatorname{Bern}(q))=d\tanh(d/2)=K(0,d) K zCDP ( p , q ) ≥ KL ( Bern ( p ) ∥ Bern ( q )) = d tanh ( d /2 ) = K ( 0 , d ) . Now let a > 0 a>0 a > 0 satisfy 2 g ( a ) = m p , q 2g(a)=m_{p,q} 2 g ( a ) = m p , q , as in Appendix B.3. Lemma 19 and (15) give
K z C D P ( p , q ) ≥ K ( c , d ) ≥ K ( 0 , a ) = μ z C D P − 1 ( 2 g ( a ) ) = μ z C D P − 1 ( m p , q ) . K_{\mathrm{zCDP}}(p,q)\geq K(c,d)\geq K(0,a)=\mu_{\mathrm{zCDP}}^{-1}(2g(a))=\mu_{\mathrm{zCDP}}^{-1}(m_{p,q}). K zCDP ( p , q ) ≥ K ( c , d ) ≥ K ( 0 , a ) = μ zCDP − 1 ( 2 g ( a )) = μ zCDP − 1 ( m p , q ) . For p = σ ( − a ) p=\sigma(-a) p = σ ( − a ) and q = σ ( a ) q=\sigma(a) q = σ ( a ) , Proposition 5 gives K z C D P ( p , q ) = a tanh ( a / 2 ) K_{\mathrm{zCDP}}(p,q)=a\tanh(a/2) K zCDP ( p , q ) = a tanh ( a /2 ) , so equality holds. ■
Theorem 6 (Sharp zCDP-to-GDP conversion). ** For ρ ≥ 0 \rho\geq0 ρ ≥ 0 , define
μ z C D P ( ρ ) = 2 Φ − 1 ( σ ( t ρ ) ) , ρ = t ρ tanh ( t ρ / 2 ) , (26) \mu_{\mathrm{zCDP}}(\rho)=2\Phi^{-1}(\sigma(t_\rho)),\qquad\rho=t_\rho\tanh(t_\rho/2), \tag*{(26)} μ zCDP ( ρ ) = 2 Φ − 1 ( σ ( t ρ )) , ρ = t ρ tanh ( t ρ /2 ) , (26) where t ρ ≥ 0 t_\rho\geq0 t ρ ≥ 0 uniquely solves the second equation. Every ρ \rho ρ -zCDP mechanism is μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) -GDP. Randomized response with parameter t ρ t_\rho t ρ attains the bound by Proposition 5.
Proof of Theorem 6. For ρ = 0 \rho=0 ρ = 0 , the divergence bound forces neighboring output distributions to coincide, giving 0 0 0 -GDP. Given any ρ > 0 \rho>0 ρ > 0 , suppose a ρ \rho ρ -zCDP mechanism fails μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) -GDP, and let p < q p<q p < q be the type I error and power of the test from Appendix B.1. If p = 0 p=0 p = 0 or q = 1 q=1 q = 1 , a direct Rényi divergence of the binary pair is infinite. Otherwise, as 0 < p < q < 1 0<p<q<1 0 < p < q < 1 and m p , q > μ z C D P ( ρ ) m_{p,q}>\mu_{\mathrm{zCDP}}(\rho) m p , q > μ zCDP ( ρ ) , Lemma 20 and strict monotonicity of μ z C D P − 1 \mu_{\mathrm{zCDP}}^{-1} μ zCDP − 1 give
K z C D P ( p , q ) ≥ μ z C D P − 1 ( m p , q ) > μ z C D P − 1 ( μ z C D P ( ρ ) ) = ρ , K_{\mathrm{zCDP}}(p,q)\geq\mu_{\mathrm{zCDP}}^{-1}(m_{p,q})>\mu_{\mathrm{zCDP}}^{-1}(\mu_{\mathrm{zCDP}}(\rho))=\rho, K zCDP ( p , q ) ≥ μ zCDP − 1 ( m p , q ) > μ zCDP − 1 ( μ zCDP ( ρ )) = ρ ,
and hence, by (9) , there exist an order η > 1 \eta> 1 η > 1 and a direction that gives a binary divergence greater than ρ η \rho\eta ρ η . In either case, (7) transfers the violation to the original neighboring distributions, which contradicts ρ \rho ρ -zCDP because the neighboring relation is symmetric.
By Proposition 5 , randomized response with parameter t ρ t_{\rho} t ρ is exactly ρ \rho ρ -zCDP and exactly μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) -GDP, so no smaller universal parameter is possible. ■
Proof of the sharp bounded-range-to-GDP conversion
The proof follows the contrapositive of Appendix § 7 , with privacy-loss width in place of Rényi divergence. The only analytic ingredient reused is Lemma 17 .
With a a a as in (10) , μ B R ( 2 a ) = m \mu_{\mathrm{BR}}(2a)=m μ BR ( 2 a ) = m , so the functional inverse m ≥ 0 m \ge0 m ≥ 0 is
μ B R − 1 ( m ) = 2 log Φ ( m / 2 ) Φ ( − m / 2 ) . (27) \mu_{\mathrm{BR}}^{-1}(m)=2\log\frac{\Phi(m/2)}{\Phi(-m/2)}. \tag*{(27)} μ BR − 1 ( m ) = 2 log Φ ( − m /2 ) Φ ( m /2 ) . (27)
It is strictly increasing, since the numerator increases and the positive denominator decreases with m m m .
Suppose an ε \varepsilon ε -BR mechanism fails μ B R ( ε ) \mu_{\mathrm{BR}}(\varepsilon) μ BR ( ε ) -GDP. The construction of Appendix § 7 .§ 1 with μ = μ B R ( ε ) \mu=\mu_{\mathrm{BR}}(\varepsilon) μ = μ BR ( ε ) gives a test ϕ \phi ϕ and a binary pair Bern ( p ) , Bern ( q ) \operatorname{Bern}(p),\operatorname{Bern}(q) Bern ( p ) , Bern ( q ) satisfying q > Φ ( Φ − 1 ( p ) + μ B R ( ε ) ) q>\Phi(\Phi^{-1}(p)+\mu_{\mathrm{BR}}(\varepsilon)) q > Φ ( Φ − 1 ( p ) + μ BR ( ε )) , so p < q p<q p < q and
m p , q = Φ − 1 ( q ) − Φ − 1 ( p ) > μ B R ( ε ) . m_{p,q}=\Phi^{-1}(q)-\Phi^{-1}(p)>\mu_{\mathrm{BR}}(\varepsilon). m p , q = Φ − 1 ( q ) − Φ − 1 ( p ) > μ BR ( ε ) .
The binary pair also preserves bounded range. Since P P P and Q Q Q are mutually absolutely continuous, p = 0 p=0 p = 0 would force q = 0 q=0 q = 0 and q = 1 q=1 q = 1 would force p = 1 p=1 p = 1 , so 0 < p < q < 1 0<p<q<1 0 < p < q < 1 . The bounded-range assumption provides L = d Q / d P L=\mathrm{d}Q/\mathrm{d}P L = d Q / d P and constants 0 < A ≤ B < ∞ 0<A\le B<\infty 0 < A ≤ B < ∞ such that A ≤ L ≤ B A\le L\le B A ≤ L ≤ B and log ( B / A ) ≤ ε \log(B/A)\le\varepsilon log ( B / A ) ≤ ε . The binary likelihood ratios satisfy
q p = E P [ L ϕ ] E P ϕ ∈ [ A , B ] , 1 − q 1 − p = E P [ L ( 1 − ϕ ) ] E P [ 1 − ϕ ] ∈ [ A , B ] , \frac{q}{p}=\frac{\mathbb{E}_{P}[L\phi]}{\mathbb{E}_{P}\phi}\in[A,B],\qquad
\frac{1-q}{1-p}=\frac{\mathbb{E}_{P}[L(1-\phi)]}{\mathbb{E}_{P}[1-\phi]}\in[A,B], p q = E P ϕ E P [ L ϕ ] ∈ [ A , B ] , 1 − p 1 − q = E P [ 1 − ϕ ] E P [ L ( 1 − ϕ )] ∈ [ A , B ] ,
since both are weighted averages of L L L . Since p < q p<q p < q , the binary width satisfies
K B R ( p , q ) = log q p − log 1 − q 1 − p ≤ log ( B / A ) ≤ ε . K_{\mathrm{BR}}(p,q)=\log\frac{q}{p}-\log\frac{1-q}{1-p}\le\log(B/A)\le\varepsilon. K BR ( p , q ) = log p q − log 1 − p 1 − q ≤ log ( B / A ) ≤ ε .
For an ε \varepsilon ε -logistic DP mechanism, the same test instead satisfies 1 − q ≥ L ε ( p ) 1-q\ge L_{\varepsilon}(p) 1 − q ≥ L ε ( p ) . Since L ε ( 0 ) = 1 L_{\varepsilon}(0)=1 L ε ( 0 ) = 1 and L ε ( p ) > 0 L_{\varepsilon}(p)>0 L ε ( p ) > 0 for p < 1 p<1 p < 1 , a pair with p < q p<q p < q is again interior. Rearrangement gives q ( 1 − p ) ≤ e ε p ( 1 − q ) q(1-p)\le e^{\varepsilon}p(1-q) q ( 1 − p ) ≤ e ε p ( 1 − q ) and K B R ( p , q ) ≤ ε K_{\mathrm{BR}}(p,q)\le\varepsilon K BR ( p , q ) ≤ ε .
In the coordinates of Appendix § 7 .§ 2 , p = σ ( c − d ) p=\sigma(c-d) p = σ ( c − d ) and q = σ ( c + d ) q=\sigma(c+d) q = σ ( c + d ) , so
K B R ( p , q ) = log q ( 1 − p ) p ( 1 − q ) = 2 d , K_{\mathrm{BR}}(p,q)=\log\frac{q(1-p)}{p(1-q)}=2d, K BR ( p , q ) = log p ( 1 − q ) q ( 1 − p ) = 2 d ,
and the separation is m p , q = g ( c + d ) − g ( c − d ) m_{p,q}=g(c+d)-g(c-d) m p , q = g ( c + d ) − g ( c − d ) . Since the width depends only on d d d , we maximize the separation over c c c at fixed d d d .
Lemma 17 gives a positive nonincreasing ratio g ′ / w g'/w g ′ / w , and w w w is strictly decreasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) because
w ′ ( u ) w ( u ) = 1 2 ( 1 sinh u − 1 u ) < 0 for u > 0. \frac{w'(u)}{w(u)}=\frac{1}{2}\left(\frac{1}{\sinh u}-\frac{1}{u}\right)<0\quad\text{for }u>0. w ( u ) w ′ ( u ) = 2 1 ( sinh u 1 − u 1 ) < 0 for u > 0.
Hence g ′ = ( g ′ / w ) w g'=(g'/w)w g ′ = ( g ′ / w ) w is positive and strictly decreasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) , and it is even because g g g is odd. Oddness of g g g also makes the separation even in c c c , and for c > 0 c>0 c > 0 its derivative g ′ ( c + d ) − g ′ ( ∣ c − d ∣ ) g'(c+d)-g'(\lvert c-d\rvert) g ′ ( c + d ) − g ′ (∣ c − d ∣) is negative because c + d > ∣ c − d ∣ c+d>\lvert c-d\rvert c + d > ∣ c − d ∣ . The separation is therefore maximized at c = 0 c=0 c = 0 , which gives
m p , q = g ( c + d ) − g ( c − d ) ≤ 2 g ( d ) . m_{p,q}=g(c+d)-g(c-d)\le2g(d). m p , q = g ( c + d ) − g ( c − d ) ≤ 2 g ( d ) .
Take a a a from (10) with m = m p , q m=m_{p,q} m = m p , q , so that 2 g ( a ) = m p , q ≤ 2 g ( d ) 2g(a)=m_{p,q}\le2g(d) 2 g ( a ) = m p , q ≤ 2 g ( d ) . Strict monotonicity of g g g gives a ≤ d a\le d a ≤ d , and by (27) ,
K B R ( p , q ) = 2 d ≥ 2 a = μ B R − 1 ( m p , q ) . (28) K_{\mathrm{BR}}(p,q)=2d\ge2a=\mu_{\mathrm{BR}}^{-1}(m_{p,q}). \tag*{(28)} K BR ( p , q ) = 2 d ≥ 2 a = μ BR − 1 ( m p , q ) . (28)
Theorem 13 (Sharp bounded-range-to-GDP conversion). For ε ≥ 0 \varepsilon\ge0 ε ≥ 0 , define
μ B R ( ε ) = 2 Φ − 1 ( σ ( ε / 2 ) ) . \mu_{\mathrm{BR}}(\varepsilon) = 2\Phi^{-1}\left(\sigma(\varepsilon/2)\right). μ BR ( ε ) = 2 Φ − 1 ( σ ( ε /2 ) ) . Every ε \varepsilon ε -BR mechanism is μ B R ( ε ) \mu_{\mathrm{BR}}(\varepsilon) μ BR ( ε ) -GDP. More generally, every ε \varepsilon ε -logistic DP mechanism is μ B R ( ε ) \mu_{\mathrm{BR}}(\varepsilon) μ BR ( ε ) -GDP. Tightness of both conversions is demonstrated by randomized response with parameter ε / 2 \varepsilon/2 ε /2 .
Proof of Theorem 13 For ε > 0 \varepsilon> 0 ε > 0 , suppose an ε \varepsilon ε -BR or ε \varepsilon ε -logistic DP mechanism fails μ B R ( ε ) \mu_{\mathrm{BR}}(\varepsilon) μ BR ( ε ) -GDP. Then, K B R ( p , q ) ≤ ε K_{\mathrm{BR}}(p,q) \le\varepsilon K BR ( p , q ) ≤ ε and m p , q > μ B R ( ε ) m_{p,q} > \mu_{\mathrm{BR}}(\varepsilon) m p , q > μ BR ( ε ) . By (28) and strict monotonicity of μ B R − 1 \mu_{\mathrm{BR}}^{-1} μ BR − 1 ,
ε ≥ K B R ( p , q ) ≥ μ B R − 1 ( m p , q ) > μ B R − 1 ( μ B R ( ε ) ) = ε , \varepsilon\ge K_{\mathrm{BR}}(p,q) \ge\mu_{\mathrm{BR}}^{-1}(m_{p,q}) > \mu_{\mathrm{BR}}^{-1}(\mu_{\mathrm{BR}}(\varepsilon)) = \varepsilon, ε ≥ K BR ( p , q ) ≥ μ BR − 1 ( m p , q ) > μ BR − 1 ( μ BR ( ε )) = ε ,
a contradiction. For ε = 0 \varepsilon= 0 ε = 0 , bounded range makes the likelihood ratio constant and normalization makes it one; logistic DP gives T ( P , Q ) ( α ) ≥ 1 − α T(P,Q)(\alpha) \ge1-\alpha T ( P , Q ) ( α ) ≥ 1 − α . In either case neighboring distributions coincide and satisfy 0-GDP.
For sharpness, randomized response with parameter ε / 2 \varepsilon/2 ε /2 has privacy-loss values ± ε / 2 \pm\varepsilon/2 ± ε /2 , so it is exactly ε \varepsilon ε -BR and hence ε \varepsilon ε -logistic DP. By Proposition 5 , its exact GDP parameter is 2 Φ − 1 ( σ ( ε / 2 ) ) = μ B R ( ε ) 2\Phi^{-1}(\sigma(\varepsilon/2)) = \mu_{\mathrm{BR}}(\varepsilon) 2 Φ − 1 ( σ ( ε /2 )) = μ BR ( ε ) , so no smaller parameter is valid for either class. ■
Proofs of conversion properties and privacy accounting
Our main question here is whether to convert each component before composition or to compose the zCDP or logistic DP budgets before conversion. We first establish a Gaussian integral identity that makes the inverse-conversion derivatives tractable.
Lemma 21 (Gaussian integral identity). Let Θ ∼ Unif [ 0 , π / 4 ] \Theta\sim\operatorname{Unif}[0,\pi/4] Θ ∼ Unif [ 0 , π /4 ] and define A ( Θ ) = 1 / ( 8 cos 2 Θ ) A(\Theta) = 1/(8\cos^2\Theta) A ( Θ ) = 1/ ( 8 cos 2 Θ ) . For every s ≥ 0 s \ge0 s ≥ 0 ,
4 Φ ( s / 2 ) Φ ( − s / 2 ) = 4 π ∫ 0 π / 4 exp ( − s 8 cos 2 θ ) d θ = E [ e − s A ] . 4\Phi(\sqrt{s}/2)\Phi(-\sqrt{s}/2) = \frac{4}{\pi}\int_{0}^{\pi/4}\exp\left(-\frac{s}{8\cos^2\theta}\right)\,d\theta= \mathbb{E}\left[e^{-sA}\right]. 4Φ ( s /2 ) Φ ( − s /2 ) = π 4 ∫ 0 π /4 exp ( − 8 cos 2 θ s ) d θ = E [ e − s A ] .
Proof Put t = s / 2 t=\sqrt{s}/2 t = s /2 , and let Z 1 , Z 2 Z_1,Z_2 Z 1 , Z 2 be independent standard normal variables. Independence gives Pr ( max ( ∣ Z 1 ∣ , ∣ Z 2 ∣ ) > t ) = 1 − ( 2 Φ ( t ) − 1 ) 2 = 4 Φ ( t ) Φ ( − t ) \Pr(\max(|Z_1|,|Z_2|)>t)=1-(2\Phi(t)-1)^2=4\Phi(t)\Phi(-t) Pr ( max ( ∣ Z 1 ∣ , ∣ Z 2 ∣ ) > t ) = 1 − ( 2Φ ( t ) − 1 ) 2 = 4Φ ( t ) Φ ( − t ) . In polar coordinates, a point in the sector 0 ≤ θ ≤ π / 4 0\le\theta\le\pi/4 0 ≤ θ ≤ π /4 lies outside [ − t , t ] 2 [-t,t]^2 [ − t , t ] 2 precisely when r > t / cos θ r>t/\cos\theta r > t / cos θ . The eight sectors have equal probability, so
Pr ( max ( ∣ Z 1 ∣ , ∣ Z 2 ∣ ) > t ) = 8 2 π ∫ 0 π / 4 ∫ t / cos θ ∞ e − r 2 / 2 r d r d θ = 4 π ∫ 0 π / 4 exp ( − t 2 2 cos 2 θ ) d θ . \Pr(\max(|Z_1|,|Z_2|)>t)=\frac{8}{2\pi}\int_{0}^{\pi/4}\int_{t/\cos\theta}^{\infty}e^{-r^2/2}r\,dr\,d\theta=\frac{4}{\pi}\int_{0}^{\pi/4}\exp\left(-\frac{t^2}{2\cos^2\theta}\right)\,d\theta. Pr ( max ( ∣ Z 1 ∣ , ∣ Z 2 ∣ ) > t ) = 2 π 8 ∫ 0 π /4 ∫ t / c o s θ ∞ e − r 2 /2 r d r d θ = π 4 ∫ 0 π /4 exp ( − 2 cos 2 θ t 2 ) d θ .
Substituting t 2 = s / 4 t^2=s/4 t 2 = s /4 , the expectation representation follows because Θ \Theta Θ has density 4 / π 4/\pi 4/ π on [ 0 , π / 4 ] [0,\pi/4] [ 0 , π /4 ] . ■
Lemma 21 expresses the product as the Laplace transform of the random variable A = ( 8 cos 2 Θ ) − 1 A=(8\cos^2\Theta)^{-1} A = ( 8 cos 2 Θ ) − 1 , where Θ ∼ Unif [ 0 , π / 4 ] \Theta\sim\operatorname{Unif}[0,\pi/4] Θ ∼ Unif [ 0 , π /4 ] . This representation makes differentiation with respect to s s s particularly convenient because
d k d s k E [ e − s A ] = ( − 1 ) k E [ A k e − s A ] . \frac{d^k}{ds^k}\mathbb{E}[e^{-sA}]=(-1)^k\mathbb{E}[A^k e^{-sA}]. d s k d k E [ e − s A ] = ( − 1 ) k E [ A k e − s A ] .
Theorem 7 (Shape and limiting scales of the zCDP to GDP conversion). The zCDP to GDP conversion map ρ ↦ μ z C D P ( ρ ) \rho\mapsto\mu_{\mathrm{zCDP}}(\rho) ρ ↦ μ zCDP ( ρ ) is strictly increasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) , and satisfies lim ρ ↓ 0 μ z C D P ( ρ ) / ρ = π \lim_{\rho\downarrow0}\mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho}=\sqrt{\pi} lim ρ ↓ 0 μ zCDP ( ρ ) / ρ = π and lim ρ → ∞ μ z C D P ( ρ ) / ρ = 8 \lim_{\rho\to\infty}\mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho}=\sqrt{8} lim ρ → ∞ μ zCDP ( ρ ) / ρ = 8 . Moreover, ρ ↦ μ z C D P ( ρ ) 2 \rho\mapsto\mu_{\mathrm{zCDP}}(\rho)^2 ρ ↦ μ zCDP ( ρ ) 2 is strictly convex and ρ ↦ μ z C D P ( ρ ) / ρ \rho\mapsto\mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho} ρ ↦ μ zCDP ( ρ ) / ρ is strictly increasing on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , so π ρ ≤ μ z C D P ( ρ ) ≤ 8 ρ \sqrt{\pi\rho}\le\mu_{\mathrm{zCDP}}(\rho)\le\sqrt{8\rho} π ρ ≤ μ zCDP ( ρ ) ≤ 8 ρ for all $\rho\ge 0.
Proof of Theorem 7 Write F z C D P ( ρ ) = μ z C D P ( ρ ) 2 F_{\mathrm{zCDP}}(\rho)=\mu_{\mathrm{zCDP}}(\rho)^2 F zCDP ( ρ ) = μ zCDP ( ρ ) 2 , with F z C D P ( 0 ) = 0 F_{\mathrm{zCDP}}(0)=0 F zCDP ( 0 ) = 0 . Since this expression involves the inverse Gaussian CDF, we study its inverse to work instead with the Gaussian CDF, whose derivative is explicit. This also avoids implicitly differentiating ρ = t ρ tanh ( t ρ / 2 ) \rho=t_\rho\tanh(t_\rho/2) ρ = t ρ tanh ( t ρ /2 ) to obtain t ρ ′ ( ρ ) t_\rho'(\rho) t ρ ′ ( ρ ) . It suffices to show that F z C D P F_{\mathrm{zCDP}} F zCDP is strictly increasing and strictly concave, which we do by proving that its derivative is positive and strictly decreasing.
To express the inverse, take s = μ z C D P ( ρ ) 2 s=\mu_{\mathrm{zCDP}}(\rho)^2 s = μ zCDP ( ρ ) 2 as the input, so F z C D P − 1 ( s ) = μ z C D P − 1 ( s ) F_{\mathrm{zCDP}}^{-1}(s)=\mu_{\mathrm{zCDP}}^{-1}(\sqrt{s}) F zCDP − 1 ( s ) = μ zCDP − 1 ( s ) is the corresponding zCDP budget ρ \rho ρ . For squared Gaussian separation s ≥ 0 s\geq0 s ≥ 0 , let t ( s ) t(s) t ( s ) denote the corresponding randomized-response parameter. The identity s = 2 Φ − 1 ( σ ( t ) ) \sqrt{s}=2\Phi^{-1}(\sigma(t)) s = 2 Φ − 1 ( σ ( t )) gives Φ ( s / 2 ) = σ ( t ) \Phi(\sqrt{s}/2)=\sigma(t) Φ ( s /2 ) = σ ( t ) . Taking logistic odds and then logarithms yields t ( s ) = log Φ ( s / 2 ) Φ ( − s / 2 ) t(s)=\log\frac{\Phi(\sqrt{s}/2)}{\Phi(-\sqrt{s}/2)} t ( s ) = log Φ ( − s /2 ) Φ ( s /2 ) and F z C D P − 1 ( s ) = t ( s ) tanh ( t ( s ) / 2 ) F_{\mathrm{zCDP}}^{-1}(s)=t(s)\tanh(t(s)/2) F zCDP − 1 ( s ) = t ( s ) tanh ( t ( s ) /2 ) . As s s s increases, the numerator in the odds increases and the denominator decreases, so t ( s ) t(s) t ( s ) is strictly increasing. Notice that t ( μ z C D P ( ρ ) 2 ) = t ρ t(\mu_{\mathrm{zCDP}}(\rho)^2)=t_\rho t ( μ zCDP ( ρ ) 2 ) = t ρ ; this is the same randomized-response parameter, now expressed as a function of the squared GDP parameter.
The derivative of the inverse conversion. We want an expression for ( F z C D P − 1 ) ′ ( s ) (F_{\mathrm{zCDP}}^{-1})'(s) ( F zCDP − 1 ) ′ ( s ) whose positivity and monotonicity can be studied separately. For s > 0 s>0 s > 0 , differentiating gives
( F z C D P − 1 ) ′ ( s ) = tanh ( t ( s ) / 2 ) t ′ ( s ) + t ( s ) 2 sech 2 ( t ( s ) / 2 ) t ′ ( s ) . (F_{\mathrm{zCDP}}^{-1})'(s)=\tanh(t(s)/2)t'(s)+\frac{t(s)}{2}\operatorname{sech}^{2}(t(s)/2)t'(s). ( F zCDP − 1 ) ′ ( s ) = tanh ( t ( s ) /2 ) t ′ ( s ) + 2 t ( s ) sech 2 ( t ( s ) /2 ) t ′ ( s ) .
Factoring out tanh ( t ( s ) / 2 ) t ′ ( s ) \tanh(t(s)/2)t'(s) tanh ( t ( s ) /2 ) t ′ ( s ) leaves the factor 1 + t ( s ) / sinh t ( s ) 1+t(s)/\sinh t(s) 1 + t ( s ) / sinh t ( s ) . This factorization follows from the double-angle identity for the hyperbolic sine. Define J ( s ) : = 2 log cosh ( t ( s ) / 2 ) J(s):=2\log\cosh(t(s)/2) J ( s ) := 2 log cosh ( t ( s ) /2 ) ; its derivative is precisely the extracted factor. Thus
( F z C D P − 1 ) ′ ( s ) = ( 1 + t ( s ) sinh t ( s ) ) J ′ ( s ) . (29) (F_{\mathrm{zCDP}}^{-1})'(s)=\left(1+\frac{t(s)}{\sinh t(s)}\right)J'(s). \tag*{(29)} ( F zCDP − 1 ) ′ ( s ) = ( 1 + sinh t ( s ) t ( s ) ) J ′ ( s ) . (29)
We will show that both factors are positive and strictly decreasing.
The choice of J J J also connects the derivative calculation to the Gaussian integral identity. Since Φ ( s / 2 ) = σ ( t ( s ) ) \Phi(\sqrt{s}/2)=\sigma(t(s)) Φ ( s /2 ) = σ ( t ( s )) and Φ ( − s / 2 ) = 1 − σ ( t ( s ) ) \Phi(-\sqrt{s}/2)=1-\sigma(t(s)) Φ ( − s /2 ) = 1 − σ ( t ( s )) , their product satisfies 4 Φ ( s / 2 ) Φ ( − s / 2 ) = 1 / cosh 2 ( t ( s ) / 2 ) 4\Phi(\sqrt{s}/2)\Phi(-\sqrt{s}/2)=1/\cosh^{2}(t(s)/2) 4Φ ( s /2 ) Φ ( − s /2 ) = 1/ cosh 2 ( t ( s ) /2 ) . Taking negative logarithms and applying Lemma 21 gives
J ( s ) = − log [ 4 Φ ( s / 2 ) Φ ( − s / 2 ) ] = − log E [ e − s A ] , J(s)=-\log[4\Phi(\sqrt{s}/2)\Phi(-\sqrt{s}/2)]=-\log\mathbb{E}[e^{-sA}], J ( s ) = − log [ 4Φ ( s /2 ) Φ ( − s /2 )] = − log E [ e − s A ] ,
大小规律 where A = ( 8 cos 2 Θ ) − 1 A = (8\cos^{2}\Theta)^{-1} A = ( 8 cos 2 Θ ) − 1 and Θ ∼ Unif [ 0 , π / 4 ] \Theta\sim\operatorname{Unif}[0,\pi/4] Θ ∼ Unif [ 0 , π /4 ] . This representation allows us to determine the signs of J ′ J' J ′ and J ′ ′ J'' J ′′ without differentiating the Gaussian CDF product twice. Because A A A is bounded, differentiation under the expectation is valid, and
Figure 11. The negative log-Laplace transform used in the zCDP inverse calculation. The signs J ′ > 0 J' > 0 J ′ > 0 and J ′ ′ < 0 J'' < 0 J ′′ < 0 give a positive decreasing factor in (29) .
J ′ ( s ) = E [ A e − s A ] E [ e − s A ] = E s [ A ] > 0 , J'(s) = \frac{\mathbb{E}[Ae^{-sA}]}{\mathbb{E}[e^{-sA}]} = \mathbb{E}_{s}[A] > 0, J ′ ( s ) = E [ e − s A ] E [ A e − s A ] = E s [ A ] > 0 ,
J ′ ′ ( s ) = − E [ A 2 e − s A ] E [ e − s A ] + ( E [ A e − s A ] E [ e − s A ] ) 2 = − Var s ( A ) < 0. J''(s) = -\frac{\mathbb{E}[A^{2}e^{-sA}]}{\mathbb{E}[e^{-sA}]} + \left(\frac{\mathbb{E}[Ae^{-sA}]}{\mathbb{E}[e^{-sA}]}\right)^{2} = -\operatorname{Var}_{s}(A) < 0. J ′′ ( s ) = − E [ e − s A ] E [ A 2 e − s A ] + ( E [ e − s A ] E [ A e − s A ] ) 2 = − Var s ( A ) < 0.
Here E s [ f ( A ) ] : = E [ f ( A ) e − s A ] / E [ e − s A ] \mathbb{E}_{s}[f(A)] := \mathbb{E}[f(A)e^{-sA}]/\mathbb{E}[e^{-sA}] E s [ f ( A )] := E [ f ( A ) e − s A ] / E [ e − s A ] is expectation under the distribution obtained by weighting by e − s A e^{-sA} e − s A and normalizing. The weights are strictly positive, so A A A remains nonconstant and the variance is strictly positive. Hence J ′ J' J ′ is positive and strictly decreasing.
For the other factor, u / sinh u u/\sinh u u / sinh u is strictly decreasing on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , since its derivative ( sinh u − u cosh u ) / sinh 2 u (\sinh u-u\cosh u)/\sinh^{2}u ( sinh u − u cosh u ) / sinh 2 u is negative by u cosh u − sinh u > 0 u\cosh u-\sinh u>0 u cosh u − sinh u > 0 (proof of Lemma 17). Since t ( s ) t(s) t ( s ) is strictly increasing, 1 + t ( s ) / sinh t ( s ) 1+t(s)/\sinh t(s) 1 + t ( s ) / sinh t ( s ) is positive and strictly decreasing in s s s .
Strict convexity. The inverse derivative in (29) is a product of two positive, strictly decreasing functions. Therefore F z C D P − 1 F_{\mathrm{zCDP}}^{-1} F zCDP − 1 is strictly increasing and strictly concave on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) . Its continuous extension to zero is concave on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) ; strictness for a segment starting at zero follows by comparing average slopes of its strictly decreasing derivative. The inverse of an increasing, strictly concave function is strictly convex, so F z C D P F_{\mathrm{zCDP}} F zCDP is strictly increasing and strictly convex on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) .
The two limits. Recall that ρ = t ρ tanh ( t ρ / 2 ) \rho= t_{\rho}\tanh(t_{\rho}/2) ρ = t ρ tanh ( t ρ /2 ) and μ z C D P ( ρ ) = 2 g ( t ρ ) \mu_{\mathrm{zCDP}}(\rho) = 2g(t_{\rho}) μ zCDP ( ρ ) = 2 g ( t ρ ) . The map t ↦ t tanh ( t / 2 ) t \mapsto t\tanh(t/2) t ↦ t tanh ( t /2 ) is strictly increasing from zero to infinity. Consequently, ρ ↓ 0 \rho\downarrow0 ρ ↓ 0 corresponds to t ρ ↓ 0 t_{\rho} \downarrow0 t ρ ↓ 0 , and ρ → ∞ \rho\to\infty ρ → ∞ corresponds to t ρ → ∞ t_{\rho} \to\infty t ρ → ∞ . We use this parameterization to compare the numerator and denominator of F z C D P ( ρ ) / ρ F_{\mathrm{zCDP}}(\rho)/\rho F zCDP ( ρ ) / ρ .
As ρ ↓ 0 \rho\downarrow0 ρ ↓ 0 . First, tanh ( t / 2 ) = t / 2 + o ( t ) \tanh(t/2) = t/2 + o(t) tanh ( t /2 ) = t /2 + o ( t ) , so ρ = t ρ 2 / 2 + o ( t ρ 2 ) \rho= t_{\rho}^{2}/2 + o(t_{\rho}^{2}) ρ = t ρ 2 /2 + o ( t ρ 2 ) . Next, we expand 2 Φ − 1 ( σ ( t ) ) 2\Phi^{-1}(\sigma(t)) 2 Φ − 1 ( σ ( t )) at t = 0 t=0 t = 0 . The inverse function rule gives ( Φ − 1 ) ′ ( 1 / 2 ) = 1 / φ ( Φ − 1 ( 1 / 2 ) ) = 1 / φ ( 0 ) = 2 π (\Phi^{-1})'(1/2) = 1/\varphi(\Phi^{-1}(1/2)) = 1/\varphi(0) = \sqrt{2\pi} ( Φ − 1 ) ′ ( 1/2 ) = 1/ φ ( Φ − 1 ( 1/2 )) = 1/ φ ( 0 ) = 2 π . Since σ ( 0 ) = 1 / 2 \sigma(0) = 1/2 σ ( 0 ) = 1/2 and σ ′ ( 0 ) = 1 / 4 \sigma'(0) = 1/4 σ ′ ( 0 ) = 1/4 , the chain rule gives 2 g ( t ) = 2 ( 2 π t / 4 ) + o ( t ) = π / 2 t + o ( t ) 2g(t) = 2(\sqrt{2\pi}\,t/4) + o(t) = \sqrt{\pi/2}\,t + o(t) 2 g ( t ) = 2 ( 2 π t /4 ) + o ( t ) = π /2 t + o ( t ) . Consequently, F z C D P ( ρ ) = F_{\mathrm{zCDP}}(\rho) = F zCDP ( ρ ) = ( π / 2 ) t ρ 2 + o ( t ρ 2 ) (\pi/2)t_{\rho}^{2}+o(t_{\rho}^{2}) ( π /2 ) t ρ 2 + o ( t ρ 2 ) . Both numerator and denominator are of order t ρ 2 t_{\rho}^{2} t ρ 2 , so dividing their expansions yields
lim ρ ↓ 0 F z C D P ( ρ ) ρ = lim t ↓ 0 4 g ( t ) 2 t tanh ( t / 2 ) = π / 2 1 / 2 = π . \lim_{\rho\downarrow0}\frac{F_{\mathrm{zCDP}}(\rho)}{\rho}
=\lim_{t\downarrow0}\frac{4g(t)^{2}}{t\tanh(t/2)}
=\frac{\pi/2}{1/2}=\pi. ρ ↓ 0 lim ρ F zCDP ( ρ ) = t ↓ 0 lim t tanh ( t /2 ) 4 g ( t ) 2 = 1/2 π /2 = π .
As ρ → ∞ \rho\to\infty ρ → ∞ . Write z = μ z C D P ( ρ ) / 2 = g ( t ρ ) z=\mu_{\mathrm{zCDP}}(\rho)/2=g(t_{\rho}) z = μ zCDP ( ρ ) /2 = g ( t ρ ) . From the conversion formula, t ρ = log { Φ ( z ) / Φ ( − z ) } t_{\rho}=\log\{\Phi(z)/\Phi(-z)\} t ρ = log { Φ ( z ) /Φ ( − z )} and tanh ( t ρ / 2 ) = 2 Φ ( z ) − 1 \tanh(t_{\rho}/2)=2\Phi(z)-1 tanh ( t ρ /2 ) = 2Φ ( z ) − 1 , so
F z C D P ( ρ ) ρ = 4 z 2 ( 2 Φ ( z ) − 1 ) log { Φ ( z ) / Φ ( − z ) } . \frac{F_{\mathrm{zCDP}}(\rho)}{\rho}
=\frac{4z^{2}}{(2\Phi(z)-1)\log\{\Phi(z)/\Phi(-z)\}}. ρ F zCDP ( ρ ) = ( 2Φ ( z ) − 1 ) log { Φ ( z ) /Φ ( − z )} 4 z 2 .
As ρ → ∞ \rho\to\infty ρ → ∞ , z → ∞ z\to\infty z → ∞ and 2 Φ ( z ) − 1 → 1 2\Phi(z)-1\to1 2Φ ( z ) − 1 → 1 . It remains to evaluate the logarithmic factor relative to z 2 z^{2} z 2 . Both log { Φ ( z ) / Φ ( − z ) } \log\{\Phi(z)/\Phi(-z)\} log { Φ ( z ) /Φ ( − z )} and z 2 z^{2} z 2 tend to infinity. The derivative ratio in L’Hôpital’s rule is
φ ( z ) / Φ ( z ) + φ ( z ) / Φ ( − z ) 2 z = 1 2 [ φ ( z ) z Φ ( z ) + φ ( z ) z Φ ( − z ) ] . \frac{\varphi(z)/\Phi(z)+\varphi(z)/\Phi(-z)}{2z}
=\frac{1}{2}\left[\frac{\varphi(z)}{z\Phi(z)}+\frac{\varphi(z)}{z\Phi(-z)}\right]. 2 z φ ( z ) /Φ ( z ) + φ ( z ) /Φ ( − z ) = 2 1 [ z Φ ( z ) φ ( z ) + z Φ ( − z ) φ ( z ) ] .
The first term in brackets tends to zero. For the second, the Mills bounds z 1 + z 2 φ ( z ) ≤ Φ ( − z ) ≤ φ ( z ) / z \frac{z}{1+z^{2}}\varphi(z)\leq\Phi(-z)\leq\varphi(z)/z 1 + z 2 z φ ( z ) ≤ Φ ( − z ) ≤ φ ( z ) / z give z 2 / ( 1 + z 2 ) ≤ z Φ ( − z ) / φ ( z ) ≤ 1 z^{2}/(1+z^{2})\leq z\Phi(-z)/\varphi(z)\leq1 z 2 / ( 1 + z 2 ) ≤ z Φ ( − z ) / φ ( z ) ≤ 1 . Taking reciprocals yields 1 ≤ φ ( z ) / ( z Φ ( − z ) ) ≤ 1 + 1 / z 2 1\leq\varphi(z)/(z\Phi(-z))\leq1+1/z^{2} 1 ≤ φ ( z ) / ( z Φ ( − z )) ≤ 1 + 1/ z 2 , so this term tends to one by the squeeze theorem. L’Hôpital’s rule therefore gives lim z → ∞ log { Φ ( z ) / Φ ( − z ) } / z 2 = 1 / 2 \lim_{z\to\infty}\log\{\Phi(z)/\Phi(-z)\}/z^{2}=1/2 lim z → ∞ log { Φ ( z ) /Φ ( − z )} / z 2 = 1/2 and lim ρ → ∞ F z C D P ( ρ ) / ρ = 4 / ( 1 / 2 ) = 8 \lim_{\rho\to\infty}F_{\mathrm{zCDP}}(\rho)/\rho=4/(1/2)=8 lim ρ → ∞ F zCDP ( ρ ) / ρ = 4/ ( 1/2 ) = 8 . The same calculation also gives lim t → ∞ 4 g ( t ) 2 / t = 8 \lim_{t\to\infty}4g(t)^{2}/t=8 lim t → ∞ 4 g ( t ) 2 / t = 8 , which we will use for the bounded-range limit below.
Ratio monotonicity and sharp bounds. For 0 < x < y 0<x<y 0 < x < y , strict convexity and F z C D P ( 0 ) = 0 F_{\mathrm{zCDP}}(0)=0 F zCDP ( 0 ) = 0 give F z C D P ( x ) < x y F z C D P ( y ) F_{\mathrm{zCDP}}(x)<\frac{x}{y}F_{\mathrm{zCDP}}(y) F zCDP ( x ) < y x F zCDP ( y ) . Thus, F z C D P ( ρ ) / ρ F_{\mathrm{zCDP}}(\rho)/\rho F zCDP ( ρ ) / ρ is strictly increasing, and hence so is its positive square root μ z C D P ( ρ ) / ρ \mu_{\mathrm{zCDP}}(\rho)/\sqrt{\rho} μ zCDP ( ρ ) / ρ . Its endpoint limits then give π ρ < μ z C D P ( ρ ) < 8 ρ \sqrt{\pi\rho}<\mu_{\mathrm{zCDP}}(\rho)<\sqrt{8\rho} π ρ < μ zCDP ( ρ ) < 8 ρ for ρ > 0 \rho>0 ρ > 0 , and both sides equal zero at ρ = 0 \rho=0 ρ = 0 . Both constants are sharp by those limits. This completes all zCDP assertions. ■
Theorem 15 (Shape and limiting scales of the bounded-range conversion) The conversion map ε ↦ μ B R ( ε ) \varepsilon\mapsto\mu_{\mathrm{BR}}(\varepsilon) ε ↦ μ BR ( ε ) is strictly increasing and strictly concave on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) , and satisfies lim ε ↓ 0 μ B R ( ε ) / ε = π / 8 \lim_{\varepsilon\downarrow0}\mu_{\mathrm{BR}}(\varepsilon)/\varepsilon=\sqrt{\pi/8} lim ε ↓ 0 μ BR ( ε ) / ε = π /8 and lim ε → ∞ μ B R ( ε ) / ε = 2 \lim_{\varepsilon\to\infty}\mu_{\mathrm{BR}}(\varepsilon)/\sqrt{\varepsilon}=2 lim ε → ∞ μ BR ( ε ) / ε = 2 . Moreover, μ B R ( ε ) 2 \mu_{\mathrm{BR}}(\varepsilon)^{2} μ BR ( ε ) 2 is strictly convex, μ B R ( ε ) 2 / ε \mu_{\mathrm{BR}}(\varepsilon)^{2}/\varepsilon μ BR ( ε ) 2 / ε is strictly increasing, and μ B R ( ε ) / ε \mu_{\mathrm{BR}}(\varepsilon)/\varepsilon μ BR ( ε ) / ε is strictly decreasing on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) . It follows that μ B R ( ε ) ≤ min { π / 8 ε , 2 ε } \mu_{\mathrm{BR}}(\varepsilon)\leq\min\{\sqrt{\pi/8}\,\varepsilon,2\sqrt{\varepsilon}\} μ BR ( ε ) ≤ min { π /8 ε , 2 ε } for all ε ≥ 0 \varepsilon\geq0 ε ≥ 0 , with both constants sharp by the two limits.
Proof of the Theorem 15 Strict convexity of the squared conversion. Write F B R ( ε ) = μ B R ( ε ) 2 F_{\mathrm{BR}}(\varepsilon)=\mu_{\mathrm{BR}}(\varepsilon)^{2} F BR ( ε ) = μ BR ( ε ) 2 . This function is continuous and strictly increasing from zero to infinity, with F B R ( 0 ) = 0 F_{\mathrm{BR}}(0)=0 F BR ( 0 ) = 0 . Solving s = 2 Φ − 1 ( σ ( ε / 2 ) ) \sqrt{s}=2\Phi^{-1}(\sigma(\varepsilon/2)) s = 2 Φ − 1 ( σ ( ε /2 )) gives F B R − 1 ( s ) = 2 log Φ ( s / 2 ) Φ ( − s / 2 ) = 2 t ( s ) F_{\mathrm{BR}}^{-1}(s)=2\log\frac{\Phi(\sqrt{s}/2)}{\Phi(-\sqrt{s}/2)}=2t(s) F BR − 1 ( s ) = 2 log Φ ( − s /2 ) Φ ( s /2 ) = 2 t ( s ) . Using J ′ ( s ) = tanh ( t ( s ) / 2 ) t ′ ( s ) J'(s)=\tanh(t(s)/2)t'(s) J ′ ( s ) = tanh ( t ( s ) /2 ) t ′ ( s ) from the proof of Theorem 7, we obtain
( F B R − 1 ) ′ ( s ) = 2 J ′ ( s ) tanh ( t ( s ) / 2 ) . \left(F_{\mathrm{BR}}^{-1}\right)'(s)=\frac{2J'(s)}{\tanh(t(s)/2)}. ( F BR − 1 ) ′ ( s ) = tanh ( t ( s ) /2 ) 2 J ′ ( s ) .
The numerator is positive and strictly decreasing; the denominator is positive and strictly increasing. The inverse slope is therefore positive and strictly decreasing. The inverse is strictly increasing and strictly concave, including its continuous extension to zero by the endpoint argument used above. Hence F B R F_{\mathrm{BR}} F BR is strictly increasing and strictly convex on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) .
Concavity of the unsquared conversion. Lemma 17 gives ( g ′ / w ) ′ ≤ 0 (g'/w)'\leq0 ( g ′ / w ) ′ ≤ 0 . For t > 0 t>0 t > 0 , w ′ ( t ) < 0 w'(t)<0 w ′ ( t ) < 0 and g ′ / w > 0 g'/w>0 g ′ / w > 0 , so differentiating g ′ = ( g ′ / w ) w g'=(g'/w)w g ′ = ( g ′ / w ) w yields g ′ ′ ( t ) < 0 g''(t)<0 g ′′ ( t ) < 0 . Since μ B R ( ε ) = 2 g ( ε / 2 ) \mu_{\mathrm{BR}}(\varepsilon)=2g(\varepsilon/2) μ BR ( ε ) = 2 g ( ε /2 ) , μ B R ( ε ) ′ = g ′ ( ε / 2 ) > 0 \mu'_{\mathrm{BR}(\varepsilon)}=g'(\varepsilon/2)>0 μ BR ( ε ) ′ = g ′ ( ε /2 ) > 0 and μ B R ′ ′ ( ε ) = 1 2 g ′ ′ ( ε / 2 ) < 0 \mu''_{\mathrm{BR}}(\varepsilon)=\frac{1}{2}g''(\varepsilon/2)<0 μ BR ′′ ( ε ) = 2 1 g ′′ ( ε /2 ) < 0 for ε > 0 \varepsilon>0 ε > 0 . Continuity extends strict concavity to [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) .
The two limits. The bounded-range conversion is μ B R ( ε ) = 2 g ( ε / 2 ) \mu_{\mathrm{BR}}(\varepsilon)=2g(\varepsilon/2) μ BR ( ε ) = 2 g ( ε /2 ) . Thus the limits ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 and ε → ∞ \varepsilon\to\infty ε → ∞ correspond directly to t = ε / 2 ↓ 0 t=\varepsilon/2\downarrow0 t = ε /2 ↓ 0 and t → ∞ t\to\infty t → ∞ . We can use the Gaussian quantile calculations above without repeating their derivations.
As ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 . Substitute t = ε / 2 t=\varepsilon/2 t = ε /2 into 2 g ( t ) = π / 2 t + o ( t ) 2g(t)=\sqrt{\pi/2}\,t+o(t) 2 g ( t ) = π /2 t + o ( t ) to obtain μ B R ( ε ) = π / 8 ε + o ( ε ) \mu_{\mathrm{BR}}(\varepsilon)=\sqrt{\pi/8}\,\varepsilon+o(\varepsilon) μ BR ( ε ) = π /8 ε + o ( ε ) . Squaring gives F B R ( ε ) = ( π / 8 ) ε 2 + o ( ε 2 ) F_{\mathrm{BR}}(\varepsilon)=(\pi/8)\varepsilon^2+o(\varepsilon^2) F BR ( ε ) = ( π /8 ) ε 2 + o ( ε 2 ) . Consequently, lim ε ↓ 0 μ B R ( ε ) / ε = π / 8 \lim_{\varepsilon\downarrow0}\mu_{\mathrm{BR}}(\varepsilon)/\varepsilon=\sqrt{\pi/8} lim ε ↓ 0 μ BR ( ε ) / ε = π /8 and lim ε ↓ 0 F B R ( ε ) / ε = 0 \lim_{\varepsilon\downarrow0}F_{\mathrm{BR}}(\varepsilon)/\varepsilon=0 lim ε ↓ 0 F BR ( ε ) / ε = 0 .
As ε → ∞ \varepsilon\to\infty ε → ∞ . The zCDP limit calculation established lim t → ∞ 4 g ( t ) 2 / t = 8 \lim_{t\to\infty}4g(t)^2/t=8 lim t → ∞ 4 g ( t ) 2 / t = 8 . Since the bounded-range budget is 2 t 2t 2 t , it follows that
lim ε → ∞ F B R ( ε ) ε = 1 2 lim t → ∞ 4 g ( t ) 2 t = 4. \lim_{\varepsilon\to\infty}\frac{F_{\mathrm{BR}}(\varepsilon)}{\varepsilon}=\frac{1}{2}\lim_{t\to\infty}\frac{4g(t)^2}{t}=4. ε → ∞ lim ε F BR ( ε ) = 2 1 t → ∞ lim t 4 g ( t ) 2 = 4.
Ratio monotonicity. For 0 < x < y 0<x<y 0 < x < y , strict convexity gives F B R ( x ) < ( x / y ) F B R ( y ) F_{\mathrm{BR}}(x)<(x/y)F_{\mathrm{BR}}(y) F BR ( x ) < ( x / y ) F BR ( y ) , whereas strict concavity gives μ B R ( x ) > ( x / y ) μ B R ( y ) \mu_{\mathrm{BR}}(x)>(x/y)\mu_{\mathrm{BR}}(y) μ BR ( x ) > ( x / y ) μ BR ( y ) . Hence μ B R ( ε ) 2 / ε \mu_{\mathrm{BR}}(\varepsilon)^2/\varepsilon μ BR ( ε ) 2 / ε strictly increases and μ B R ( ε ) / ε \mu_{\mathrm{BR}}(\varepsilon)/\varepsilon μ BR ( ε ) / ε strictly decreases. The ratio μ B R ( ε ) 2 / ε \mu_{\mathrm{BR}}(\varepsilon)^2/\varepsilon μ BR ( ε ) 2 / ε tends to 0 as ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 and to 4 as ε → ∞ \varepsilon\to\infty ε → ∞ . These monotonicities and the limits π / 8 \sqrt{\pi/8} π /8 and 4 give μ B R ( ε ) / ε < π / 8 \mu_{\mathrm{BR}}(\varepsilon)/\varepsilon<\sqrt{\pi/8} μ BR ( ε ) / ε < π /8 and μ B R ( ε ) 2 / ε < 4 \mu_{\mathrm{BR}}(\varepsilon)^2/\varepsilon<4 μ BR ( ε ) 2 / ε < 4 for ε > 0 \varepsilon>0 ε > 0 , and hence μ B R ( ε ) < min { π / 8 ε , 2 ε } \mu_{\mathrm{BR}}(\varepsilon)<\min\{\sqrt{\pi/8}\,\varepsilon,2\sqrt{\varepsilon}\} μ BR ( ε ) < min { π /8 ε , 2 ε } . This completes the proof. ■
Corollary 9 (Converting before accounting). For nonnegative ρ 1 , … , ρ n \rho_1,\ldots,\rho_n ρ 1 , … , ρ n and ρ \rho ρ , and an integer k ≥ 1 k\ge1 k ≥ 1 ,
∑ i = 1 n μ z C D P ( ρ i ) 2 ≤ μ z C D P ( ∑ i = 1 n ρ i ) \sqrt{\sum_{i=1}^{n}\mu_{\mathrm{zCDP}}(\rho_i)^2}\le\mu_{\mathrm{zCDP}}\left(\sum_{i=1}^{n}\rho_i\right) ∑ i = 1 n μ zCDP ( ρ i ) 2 ≤ μ zCDP ( ∑ i = 1 n ρ i ) with strict inequality if at least two ρ i \rho_i ρ i are positive.
k μ z C D P ( ρ ) ≤ μ z C D P ( k 2 ρ ) k\mu_{\mathrm{zCDP}}(\rho)\le\mu_{\mathrm{zCDP}}(k^2\rho) k μ zCDP ( ρ ) ≤ μ zCDP ( k 2 ρ ) , with strict inequality when ρ > 0 \rho>0 ρ > 0 and k > 1 k>1 k > 1 .
Corollary 16 (Order of conversion and accounting for logistic DP). For nonnegative ε 1 , … , ε n \varepsilon_1,\ldots,\varepsilon_n ε 1 , … , ε n and ε \varepsilon ε , and an integer k ≥ 1 k\ge1 k ≥ 1 ,
∑ i = 1 n μ B R ( ε i ) 2 ≤ μ B R ( ∑ i = 1 n ε i ) \sqrt{\sum_{i=1}^{n}\mu_{\mathrm{BR}}(\varepsilon_i)^2}\le\mu_{\mathrm{BR}}\left(\sum_{i=1}^{n}\varepsilon_i\right) ∑ i = 1 n μ BR ( ε i ) 2 ≤ μ BR ( ∑ i = 1 n ε i ) with strict inequality if at least two ε i > 0 \varepsilon_i>0 ε i > 0 .
μ B R ( k ε ) ≤ k μ B R ( ε ) \mu_{\mathrm{BR}}(k\varepsilon)\le k\mu_{\mathrm{BR}}(\varepsilon) μ BR ( k ε ) ≤ k μ BR ( ε ) with strict inequality if ε > 0 \varepsilon>0 ε > 0 and k > 1 k>1 k > 1 .
Proof of the first inequalities in Corollaries 9 and 16. Let F F F be either F z C D P = μ z C D P 2 F_{\mathrm{zCDP}}=\mu_{\mathrm{zCDP}}^2 F zCDP = μ zCDP 2 or F B R = μ B R 2 F_{\mathrm{BR}}=\mu_{\mathrm{BR}}^2 F BR = μ BR 2 , both of which are strictly convex on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) with F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 . For nonnegative s 1 , … , s n s_1,\ldots,s_n s 1 , … , s n , let s = ∑ i s i s=\sum_i s_i s = ∑ i s i . If s = 0 s=0 s = 0 , both sides equal zero. Otherwise, writing s i = ( s i / s ) s + ( 1 − s i / s ) ⋅ 0 s_i=(s_i/s)s+(1-s_i/s)\cdot0 s i = ( s i / s ) s + ( 1 − s i / s ) ⋅ 0 , convexity gives $F(s_i)\le ( s i / s ) F ( s ) (s_i/s)F(s) ( s i / s ) F ( s ) . Summing over i i i gives ∑ i F ( s i ) ≤ F ( s ) \sum_i F(s_i)\le F(s) ∑ i F ( s i ) ≤ F ( s ) , and taking square roots gives the first inequality of each corollary, with s i = ρ i s_i=\rho_i s i = ρ i or s i = ε i s_i=\varepsilon_i s i = ε i . If at least two s i s_i s i are positive, each positive s i s_i s i lies strictly between 0 and s s s , so strict convexity gives F ( s i ) < ( s i / s ) F ( s ) F(s_i)<(s_i/s)F(s) F ( s i ) < ( s i / s ) F ( s ) for these i i i , and the inequality is strict. ■
Proof of the second inequalities in Corollaries 9 and 16 If k = 1 k=1 k = 1 , or if ρ = 0 \rho=0 ρ = 0 or ε = 0 \varepsilon=0 ε = 0 , both sides are equal. Let k > 1 k>1 k > 1 . For zCDP with ρ > 0 \rho>0 ρ > 0 , write ρ = k − 2 ( k 2 ρ ) + ( 1 − k − 2 ) ⋅ 0 \rho=k^{-2}(k^2\rho)+(1-k^{-2})\cdot0 ρ = k − 2 ( k 2 ρ ) + ( 1 − k − 2 ) ⋅ 0 . Strict convexity of F z C D P F_{\mathrm{zCDP}} F zCDP and F z C D P ( 0 ) = 0 F_{\mathrm{zCDP}}(0)=0 F zCDP ( 0 ) = 0 give F z C D P ( ρ ) < k − 2 F z C D P ( k 2 ρ ) F_{\mathrm{zCDP}}(\rho)<k^{-2}F_{\mathrm{zCDP}}(k^2\rho) F zCDP ( ρ ) < k − 2 F zCDP ( k 2 ρ ) , and taking square roots gives k μ z C D P ( ρ ) < μ z C D P ( k 2 ρ ) k\mu_{\mathrm{zCDP}}(\rho)<\mu_{\mathrm{zCDP}}(k^2\rho) k μ zCDP ( ρ ) < μ zCDP ( k 2 ρ ) . For logistic DP with ε > 0 \varepsilon>0 ε > 0 , write ε = k − 1 ( k ε ) + ( 1 − k − 1 ) ⋅ 0 \varepsilon=k^{-1}(k\varepsilon)+(1-k^{-1})\cdot0 ε = k − 1 ( k ε ) + ( 1 − k − 1 ) ⋅ 0 . Strict concavity of μ B R \mu_{\mathrm{BR}} μ BR and μ B R ( 0 ) = 0 \mu_{\mathrm{BR}}(0)=0 μ BR ( 0 ) = 0 give μ B R ( ε ) > k − 1 μ B R ( k ε ) \mu_{\mathrm{BR}}(\varepsilon)>k^{-1}\mu_{\mathrm{BR}}(k\varepsilon) μ BR ( ε ) > k − 1 μ BR ( k ε ) , that is, μ B R ( k ε ) < k μ B R ( ε ) \mu_{\mathrm{BR}}(k\varepsilon)<k\mu_{\mathrm{BR}}(\varepsilon) μ BR ( k ε ) < k μ BR ( ε ) . ■
Minimax comparison between zCDP and GDP
Let P \mathcal{P} P be a class of distributions on X \mathcal{X} X , let θ : P → Θ \theta:\mathcal{P}\to\Theta θ : P → Θ be the parameter of interest, let d d d be a metric on Θ \Theta Θ , and let ℓ : [ 0 , ∞ ) → [ 0 , ∞ ) \ell:[0,\infty)\to[0,\infty) ℓ : [ 0 , ∞ ) → [ 0 , ∞ ) be nondecreasing with ℓ ( 0 ) = 0 \ell(0)=0 ℓ ( 0 ) = 0 . Given n n n i.i.d. observations X 1 : n X_{1:n} X 1 : n from P ∈ P P\in\mathcal{P} P ∈ P , a mechanism Q Q Q produces Z ∼ Q ( ⋅ ∣ X 1 : n ) Z\sim Q(\cdot\mid X_{1:n}) Z ∼ Q ( ⋅ ∣ X 1 : n ) , with the neighboring relation of § 2 . For a fixed mechanism Q Q Q , define M n ( θ ( P ) , ℓ ∘ d ; Q ) : = inf θ ^ sup P ∈ P E P , Q [ ℓ ( d ( θ ^ ( Z ) , θ ( P ) ) ) ] \mathcal{M}_n(\theta(\mathcal{P}),\ell\circ d;Q):=\inf_{\widehat{\theta}}\sup_{P\in\mathcal{P}}\mathbb{E}_{P,Q}[\ell(d(\widehat{\theta}(Z),\theta(P)))] M n ( θ ( P ) , ℓ ∘ d ; Q ) := inf θ sup P ∈ P E P , Q [ ℓ ( d ( θ ( Z ) , θ ( P )))] , where the infimum is over estimators based only on the privatized output Z Z Z . Define the private minimax risks by
M n G D P ( θ ( P ) , ℓ ∘ d ; μ ) : = inf { M n ( θ ( P ) , ℓ ∘ d ; Q ) : Q is μ -GDP } , \mathcal{M}^{\mathrm{GDP}}_n(\theta(\mathcal{P}),\ell\circ d;\mu):=\inf\{\mathcal{M}_n(\theta(\mathcal{P}),\ell\circ d;Q):Q\text{ is }\mu\text{-GDP}\}, M n GDP ( θ ( P ) , ℓ ∘ d ; μ ) := inf { M n ( θ ( P ) , ℓ ∘ d ; Q ) : Q is μ -GDP } ,
M n z C D P ( θ ( P ) , ℓ ∘ d ; ρ ) : = inf { M n ( θ ( P ) , ℓ ∘ d ; Q ) : Q is ρ -zCDP } . \mathcal{M}^{\mathrm{zCDP}}_n(\theta(\mathcal{P}),\ell\circ d;\rho):=\inf\{\mathcal{M}_n(\theta(\mathcal{P}),\ell\circ d;Q):Q\text{ is }\rho\text{-zCDP}\}. M n zCDP ( θ ( P ) , ℓ ∘ d ; ρ ) := inf { M n ( θ ( P ) , ℓ ∘ d ; Q ) : Q is ρ -zCDP } .
Since both guarantees are preserved under post-processing, they equal the minimax risks over estimators that themselves satisfy μ \mu μ -GDP or ρ \rho ρ -zCDP.
Corollary 22 (Minimax comparisons with GDP). For every statistical problem ( P , θ , d , ℓ ) (\mathcal{P},\theta,d,\ell) ( P , θ , d , ℓ ) , every n ≥ 1 n\ge1 n ≥ 1 , and every ρ > 0 \rho>0 ρ > 0 ,
M n G D P ( θ ( P ) , ℓ ∘ d ; 8 ρ ) ≤ M n G D P ( θ ( P ) , ℓ ∘ d ; μ z C D P ( ρ ) ) \mathcal{M}^{\mathrm{GDP}}_n(\theta(\mathcal{P}),\ell\circ d;\sqrt{8\rho})\le\mathcal{M}^{\mathrm{GDP}}_n(\theta(\mathcal{P}),\ell\circ d;\mu_{\mathrm{zCDP}}(\rho)) M n GDP ( θ ( P ) , ℓ ∘ d ; 8 ρ ) ≤ M n GDP ( θ ( P ) , ℓ ∘ d ; μ zCDP ( ρ )) ≤ M n z C D P ( θ ( P ) , ℓ ∘ d ; ρ ) ≤ M n G D P ( θ ( P ) , ℓ ∘ d ; 2 ρ ) . \le\mathcal{M}^{\mathrm{zCDP}}_n(\theta(\mathcal{P}),\ell\circ d;\rho)\le\mathcal{M}^{\mathrm{GDP}}_n(\theta(\mathcal{P}),\ell\circ d;\sqrt{2\rho}). ≤ M n zCDP ( θ ( P ) , ℓ ∘ d ; ρ ) ≤ M n GDP ( θ ( P ) , ℓ ∘ d ; 2 ρ ) .
Proof. The infimum of the same worst-case risk can only decrease when it is taken over more mechanisms. Every 2 ρ \sqrt{2\rho} 2 ρ -GDP mechanism is ρ \rho ρ -zCDP by Proposition 4 , which gives the last inequality. Every ρ \rho ρ -zCDP mechanism is μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) -GDP by Theorem 6, which gives the middle inequality. Finally, μ z C D P ( ρ ) < 8 ρ \mu_{\mathrm{zCDP}}(\rho)<\sqrt{8\rho} μ zCDP ( ρ ) < 8 ρ by Theorem 7, and μ \mu μ -GDP implies ν \nu ν -GDP for every ν ≥ μ \nu\ge\mu ν ≥ μ because G μ G_\mu G μ is decreasing in μ \mu μ , which gives the first inequality. ■
The statistical problem and sample size are fixed throughout. Thus any risk upper bound achieved under 2 ρ \sqrt{2\rho} 2 ρ -GDP also holds under ρ \rho ρ -zCDP, and any minimax lower bound under μ z C D P ( ρ ) \mu_{\mathrm{zCDP}}(\rho) μ zCDP ( ρ ) -GDP, or under 8 ρ \sqrt{8\rho} 8 ρ -GDP, applies under ρ \rho ρ -zCDP. The comparison does not depend on the method used to prove a lower bound.
Background on logistic differential privacy
Let Z Z Z be the standard logistic distribution, with CDF σ ( z ) = ( 1 + e − z ) − 1 \sigma(z)=(1+e^{-z})^{-1} σ ( z ) = ( 1 + e − z ) − 1 and density
r ( z ) = e − z ( 1 + e − z ) 2 = 1 4 cosh 2 ( z / 2 ) . r(z)=\frac{e^{-z}}{(1+e^{-z})^2}=\frac{1}{4\cosh^2(z/2)}. r ( z ) = ( 1 + e − z ) 2 e − z = 4 cosh 2 ( z /2 ) 1 .
The density is symmetric and strictly log-concave because d 2 d z 2 log r ( z ) = − 1 2 sech 2 ( z / 2 ) < 0 \frac{d^2}{dz^2}\log r(z)=-\frac{1}{2}\operatorname{sech}^2(z/2)<0 d z 2 d 2 log r ( z ) = − 2 1 sech 2 ( z /2 ) < 0 . Log-concavity implies that the location family has monotone likelihood ratios. Thus a most powerful test of Z Z Z against Z + ε Z+\varepsilon Z + ε rejects for large observations. At type I error α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , its threshold is c = σ − 1 ( 1 − α ) c=\sigma^{-1}(1-\alpha) c = σ − 1 ( 1 − α ) , giving
T ( Z , Z + ε ) ( α ) = Pr ( Z + ε ≤ c ) = σ ( σ − 1 ( 1 − α ) − ε ) = L ε ( α ) . T(Z,Z+\varepsilon)(\alpha)=\Pr(Z+\varepsilon\le c)=\sigma\left(\sigma^{-1}(1-\alpha)-\varepsilon\right)=L_\varepsilon(\alpha). T ( Z , Z + ε ) ( α ) = Pr ( Z + ε ≤ c ) = σ ( σ − 1 ( 1 − α ) − ε ) = L ε ( α ) .
This is the location-shift representation used in the proof of [16 Proposition 7.2.2] . More generally, the relationship between log-concave noise distributions and functional composition is developed in [2 Section 3] .
For trade-off functions f = T ( P , Q ) f=T(P,Q) f = T ( P , Q ) and g = T ( P ′ , Q ′ ) g=T(P',Q') g = T ( P ′ , Q ′ ) , we define their tensor product as f ⊗ g : = T ( P × P ′ , Q × Q ′ ) f\otimes g:=T(P\times P',Q\times Q') f ⊗ g := T ( P × P ′ , Q × Q ′ ) . By the adaptive composition theorem, if each release has conditional guarantee f i f_i f i for every fixed realization of preceding outputs, the joint release satisfies ( f 1 ⊗ ⋯ ⊗ f m ) (f_1\otimes\cdots\otimes f_m) ( f 1 ⊗ ⋯ ⊗ f m ) -DP [18 Theorem 4] . In contrast, group privacy for an f f f -DP mechanism is governed by functional composition f [ k ] : = 1 − ( 1 − f ) ∘ k f^{[k]} := 1 - (1-f)^{\circ k} f [ k ] := 1 − ( 1 − f ) ∘ k , where ∘ k \circ k ∘ k denotes k k k -fold function composition [18 Theorem 3] . For the logistic family, define the corresponding power bound
h ε ( α ) : = 1 − L ε ( α ) = e ε α 1 − α + e ε α = σ ( σ − 1 ( α ) + ε ) . h_{\varepsilon}(\alpha) := 1 - L_{\varepsilon}(\alpha) = \frac{e^{\varepsilon}\alpha}{1-\alpha+e^{\varepsilon}\alpha} = \sigma\left(\sigma^{-1}(\alpha)+\varepsilon\right). h ε ( α ) := 1 − L ε ( α ) = 1 − α + e ε α e ε α = σ ( σ − 1 ( α ) + ε ) .
Its location-shift representation gives h b ∘ h a = h a + b h_b \circ h_a = h_{a+b} h b ∘ h a = h a + b for a , b ≥ 0 a,b \ge0 a , b ≥ 0 . Consequently, the general group-privacy formula specializes to 1 − ( 1 − L ε ) ∘ k = 1 − h ε ∘ k = L k ε 1-(1-L_{\varepsilon})^{\circ k}=1-h_{\varepsilon}^{\circ k}=L_{k\varepsilon} 1 − ( 1 − L ε ) ∘ k = 1 − h ε ∘ k = L k ε . An ε \varepsilon ε -logistic DP mechanism therefore satisfies k ε k\varepsilon k ε -logistic DP for groups of size k k k .
For composition, the comparison between tensor and functional composition for symmetric trade-off functions [2 Lemma A.2] , translated into our decreasing trade-off convention, yields
L a ⊗ L b ≥ 1 − ( 1 − L b ) ∘ ( 1 − L a ) = 1 − h b ∘ h a = L a + b . L_a \otimes L_b \ge1-(1-L_b)\circ(1-L_a)=1-h_b\circ h_a=L_{a+b}. L a ⊗ L b ≥ 1 − ( 1 − L b ) ∘ ( 1 − L a ) = 1 − h b ∘ h a = L a + b .
Iterating this inequality gives L ε 1 ⊗ ⋯ ⊗ L ε m ≥ L ∑ i = 1 m ε i L_{\varepsilon_1}\otimes\cdots\otimes L_{\varepsilon_m}\ge L^{\sum_{i=1}^{m}\varepsilon_i} L ε 1 ⊗ ⋯ ⊗ L ε m ≥ L ∑ i = 1 m ε i . Consequently, if each release in an adaptive composition is ε i \varepsilon_i ε i -logistic DP for every fixed realization of the preceding outputs, with deterministic ε i \varepsilon_i ε i , then the joint release is ( ∑ i = 1 m ε i ) (\sum_{i=1}^{m}\varepsilon_i) ( ∑ i = 1 m ε i ) -logistic DP.
Finally, the class of ε \varepsilon ε -BR mechanisms is not closed under mixtures, whereas a fixed f f f -DP class is closed under mixtures with dataset-independent weights [16 Section 7.3] . Consequently, mixtures of ε \varepsilon ε -logistic DP mechanisms remain ε \varepsilon ε -logistic DP.