# Prior-itizing Privacy: A Bayesian Approach to Setting the Privacy Budget in
Differential Privacy

Zeki Kazan
Department of Statistical Science
Duke University
Durham, NC 27708
<EMAIL_ADDRESS>&Jerome P. Reiter
Department of Statistical Science
Duke University
Durham, NC 27708
<EMAIL_ADDRESS>
###### Abstract

When releasing outputs from confidential data, agencies need to balance the
analytical usefulness of the released data with the obligation to protect data
subjects’ confidentiality. For releases satisfying differential privacy, this
balance is reflected by the privacy budget, $\varepsilon$. We provide a
framework for setting $\varepsilon$ based on its relationship with Bayesian
posterior probabilities of disclosure. The agency responsible for the data
release decides how much posterior risk it is willing to accept at various
levels of prior risk, which implies a unique $\varepsilon$. Agencies can
evaluate different risk profiles to determine one that leads to an acceptable
trade-off in risk and utility.

##  1 Introduction

Differential privacy (DP) [10] is a gold standard definition of what it means
for data curators, henceforth referred to as agencies, to protect individuals’
confidentiality when releasing sensitive data. The confidentiality guarantee
of DP is determined principally by a parameter typically referred to as the
privacy budget $\varepsilon$. Smaller values of $\varepsilon$ generally imply
greater confidentiality protection at the cost of injecting more noise into
the released data. Thus, agencies must choose $\varepsilon$ to balance
confidentiality protection with analytical usefulness. This balancing act has
resulted in a wide range of values of $\varepsilon$ in practice. For example,
early advice in the field recommends $\varepsilon$ of “0.01, 0.1, or in some
cases, $\log(2)$ or $\log(3)$” [9], whereas recent large-scale implementations
use $\varepsilon=8.6$ in OnTheMap [29], $\varepsilon=14$ in Apple’s use of
local DP for iOS 10.1.1 [42], and an equivalent of $\varepsilon=17.14$ in the
2020 decennial census redistricting data release [1].

Some decision makers may find interpreting and selecting $\varepsilon$
difficult [18, 22, 27, 35, 41]. For example, a recent study of practitioners
using DP Creator [41] found that users wished for more explanation about how
to select privacy parameters and better understanding of the effects of this
choice. One potential path for providing guidance is to convert the task of
selecting $\varepsilon$ to setting bounds on the allowable probabilities of
adversaries learning sensitive information from the released data, as in the
classical disclosure limitation literature [7, 12, 39]. There is precedent for
this approach: prior work in the literature suggests that “privacy semantics
in terms of Bayesian inference can shed more light on a privacy definition
than privacy semantics in terms of indistinguishable pairs of neighboring
databases” [26] and prevailing advice for setting $\delta$ in
$(\varepsilon,\delta)$-DP originates from such Bayesian semantics [23].

We propose that agencies utilize relationships between DP and Bayesian
semantics [2, 10, 23, 24, 25, 26, 27, 31] to select values of $\varepsilon$
that accord with their desired confidentiality guarantees. The basic idea is
as follows. First, the agency constructs a function that summarizes the
maximum posterior probability of disclosure permitted for any prior
probability of disclosure. For example, for a prior risk of 0.001, the agency
may be comfortable with a ten-fold (or more) increase in the ratio of
posterior risk to prior risk, whereas for a prior risk of 0.4, the agency may
require the increase not exceed, say, 1.2. Second, for each prior risk value,
the agency converts the posterior-to-prior ratio into the largest
$\varepsilon$ that still ensures the ratio is satisfied. Third, the agency
selects the smallest $\varepsilon$ among these values, using that value for
the data release. Importantly, the agency does not use the confidential data
in these computations—they are theoretical and data free—so that they do not
use up part of the overall privacy budget. Our main contributions include:

  * •

We propose a framework for selecting $\varepsilon$ under certain conditions
(see Section 3) that applies to any DP mechanism, does not use additional
privacy budget, and can account for disclosure risk from both an individual’s
inclusion and the sensitivity of values in the data.

  * •

We enable agencies to tune the choice of $\varepsilon$ to achieve their
desired posterior-to-prior risk profile. This can avoid setting $\varepsilon$
unnecessarily small if, for example, the agency tolerates larger posterior-to-
prior ratios for certain prior risks. In turn, this can help agencies better
manage trade-offs in disclosure risk and data utility.

  * •

We give theoretic justification for the framework and derive closed-form
solutions for the $\varepsilon$ implied by several risk profiles. For more
complex risk profiles, we also provide a general form for $\varepsilon$ as a
minimization problem.

##  2 Background and Motivation

We first describe some aspects of DP and Bayesian probabilities of disclosure
relevant for our approach. We summarize all notation and definitions in Tables
1 and 2 in Appendix A.1.

###  2.1 Differential Privacy

Let ${\mathbf{P}}$ represent a population of individuals. The agency has a
subset of ${\mathbf{P}}$, which we call ${\mathbf{Y}}$, comprising $n$
individuals measured on $d$ variables. For any individual $i$, let $Y_{i}$ be
the length-$d$ vector of values corresponding to individual $i$, and let
$I_{i}=1$ when individual $i$ is in ${\mathbf{Y}}$ and $I_{i}=0$ otherwise.
For all $i$ such that $I_{i}=1$, let ${\mathbf{Y}}_{-i}$ be the $(n-1)\times
d$ matrix of values for the $n-1$ individuals in ${\mathbf{Y}}$ excluding
individual $i$.111For all $i$ such that $I_{i}=0$ we let ${\mathbf{Y}}_{-i}$
be an $(n-1)\times d$ matrix of individuals not including individual $i$. The
agency wishes to release some function of the data, $T({\mathbf{Y}})$. We
assume ${\mathbf{Y}}$ and $T({\mathbf{Y}})$ each have discrete support but may
be many-dimensional. The agency turns to DP and will release
$T^{*}({\mathbf{Y}})$, a noisy version of $T({\mathbf{Y}})$ under
$\varepsilon$-DP.

Our work focuses on unbounded DP as defined in [8], which involves the removal
or addition of one individual’s information.222This is in contrast to bounded
DP [10], which involves the change of one individual’s information. If a
function $T^{*}({\mathbf{Y}})$ with discrete support satisfies unbounded
$\varepsilon$-DP, then for all $i$, all $y$ in the support of $Y_{i}$, all
${\mathbf{y}}_{-i}$ in the support of ${\mathbf{Y}}_{-i}$, and all $t^{*}$ in
the support of $T^{*}({\mathbf{Y}})$,

$e^{-\varepsilon}\leq\frac{P[T^{*}({\mathbf{Y}})=t^{*}\mid
Y_{i}=y,I_{i}=1,{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i}]}{P[T^{*}({\mathbf{Y}}_{-i})=t^{*}\mid
I_{i}=0,{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i}]}\leq e^{\varepsilon}.$ (1)

In settings where the statistic of interest is a count, a commonly used
algorithm to satisfy DP is the geometric mechanism [16].

######  Definition 1 (Geometric Mechanism).

Let $T({\mathbf{Y}})\in{\mathbb{Z}}$ be a count statistic and suppose we wish
to release a noisy count $T^{*}({\mathbf{Y}})\in{\mathbb{Z}}$ satisfying
$\varepsilon$-DP. The geometric mechanism produces a count centered at
$T({\mathbf{Y}})$ with noise from a two-sided geometric distribution with
parameter $e^{-\varepsilon}$. That is,

$P[T^{*}({\mathbf{Y}})=t^{*}\mid
T({\mathbf{Y}})=t]=\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}}e^{-\varepsilon|t^{*}-t|},\qquad
t^{*}\in{\mathbb{Z}}.$ (2)

Under the geometric mechanism, the variance of $T^{*}({\mathbf{Y}})$ is
$2e^{-\varepsilon}/(1-e^{-\varepsilon})^{2}$. The variance increases as
$\varepsilon$ decreases, reflecting the potential loss in data usefulness when
setting $\varepsilon$ to a small value.

Of course, data usefulness is only one side of the coin. Agencies also need to
assess the implications of the choice of $\varepsilon$ for disclosure risks
[6, 40, 41]. Prior works on setting $\varepsilon$ focus on settings where (i)
the data have yet to be collected, and the goal is to simultaneously select
$\varepsilon$ and determine how much to compensate individuals for their loss
in privacy [5, 13, 21, 28], (ii) the population is already public information,
and the goal is to protect which subset of individuals is included in a
release [27, 34], or (iii) data holders can utilize representative test data
or the confidential data itself [4, 15, 18, 34]. We focus on the common
setting where data have already been collected, the population they are drawn
from is not public information, and no data are available for tuning
$\varepsilon$.

###  2.2 Bayesian Measures of Disclosure Risk

Consider an adversary who desires to learn about some particular individual
$i$ in ${\mathbf{Y}}$ using the release of $T^{*}({\mathbf{Y}})$. We suppose
that the adversary has a model, ${\mathcal{M}}$, for making predictions about
the components of $Y_{i}$ that they do not already know.333To be technically
precise, we suppose the adversary assigns zero probability to predictions of
$Y_{i}$ with values of components that they know to be incorrect. For example,
the adversary could know some demographic information about individual $i$ but
not some other sensitive variable. The adversary might predict this sensitive
variable from the demographic information using a model estimated with
proprietary information or data from sources like administrative records. We
assume that the release mechanism for $T^{*}({\mathbf{Y}})$ is known to the
adversary, that the DP release mechanism does not depend on ${\mathcal{M}}$,
and that, under ${\mathcal{M}}$, the observations are independent but not
necessarily identically distributed. These conditions are formalized in
Section 3. For our ultimate purpose, i.e., helping agencies set $\varepsilon$,
the exact form of the adversary’s ${\mathcal{M}}$ is immaterial. In fact, as
we shall discuss, we are not concerned whether the adversary’s predictions
from ${\mathcal{M}}$ are highly accurate or completely awful.

On a technical note, we make the distinction that the agency views
${\mathbf{Y}}$ and $I_{i}$ as fixed quantities, since it knows which rows are
in the collected data and what values are associated to each row. The
adversary, however, views ${\mathbf{Y}}$ and $I_{i}$ as random variables, and
thus probabilistic statements about these quantities are well defined from the
adversary’s perspective. Notationally, we signify that a probabilistic
statement is from the adversary’s perspective via the subscript
${\mathcal{M}}$.

Let ${\mathcal{S}}$ be the subset of the support of $Y_{i}$ that the agency
considers a privacy violation. For example, if $d=1$ and ${\mathbf{Y}}$ is
income data, then ${\mathcal{S}}$ may be the set of possible incomes within
$5{,}000$ or within $5\%$ of the true income for individual $i$.
Alternatively, if $d=1$ and ${\mathbf{Y}}$ is binary, then ${\mathcal{S}}$ is
a subset of $\\{0,1\\}$. The selection of ${\mathcal{S}}$ must not depend on
${\mathbf{P}}$, as this might constitute a privacy violation.

The agency may be concerned about the risk that the adversary determines
individual $i$ is in ${\mathbf{Y}}$ or the risk that the adversary makes a
disclosure for individual $i$; that is, $I_{i}=1$ and $Y_{i}\in{\mathcal{S}}$,
respectively. Assuming that the adversary’s model puts nonzero probability
mass on these events, we can express their relevant prior probabilities as
follows.

$P_{\mathcal{M}}[I_{i}=1]=p_{i},\qquad
P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid I_{i}=1]=q_{i}.$ (3)

For fixed $p_{i}$ and $q_{i}$, we can measure the risk of disclosure for
individual $i$ in a number of ways. Drawing from [31], one measure is the
relative disclosure risk, $r_{i}(p_{i},q_{i},t^{*})$. Writing the noisy
statistic as $T^{*}$ and suppressing the dependence on ${\mathbf{Y}}$ or
${\mathbf{Y}}_{-i}$, this is defined as follows.

######  Definition 2 (Relative Disclosure Risk).

For fixed data $\mathbf{Y}$, individual $i$, adversary’s model
${\mathcal{M}}$, and released $T^{*}=t^{*}$, the relative disclosure risk is
the posterior-to-prior risk ratio,

$r_{i}(p_{i},q_{i},t^{*})=\frac{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1\mid
T^{*}=t^{*}]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1]}.$ (4)

The relative risk can be decomposed into the posterior-to-prior ratio from
inclusion ($I_{i}$) and the posterior-to-prior ratio from the values
($Y_{i}$). We have

$r_{i}(p_{i},q_{i},t^{*})=\frac{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
I_{i}=1,T^{*}=t^{*}]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
I_{i}=1]}\cdot\frac{P_{\mathcal{M}}[I_{i}=1\mid
T^{*}=t^{*}]}{P_{\mathcal{M}}[I_{i}=1]}.$ (5)

The relative risk, however, does not tell the full story. As discussed in
[20], the data holder also may care about absolute disclosure risks,
$a_{i}(p_{i},q_{i},t^{*})$.

######  Definition 3 (Absolute Disclosure Risk).

For fixed data $\mathbf{Y}$, individual $i$, adversary’s model
${\mathcal{M}}$, and released $T^{*}=t^{*}$, the absolute disclosure risk is
the posterior probability,

$a_{i}(p_{i},q_{i},t^{*})=P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1\mid
T^{*}=t^{*}].$ (6)

Since $r_{i}(p_{i},q_{i},t^{*})=a_{i}(p_{i},q_{i},t^{*})/(p_{i}q_{i})$, we can
convert between these risk measures.

###  2.3 Risk Profiles

The quantities from Section 2.2 can inform the choice of $\varepsilon$. For
example, DP implies that

$\displaystyle r_{i}(p_{i},q_{i},t^{*})\leq e^{2\varepsilon}$ (7)

for all $(p_{i},q_{i},t^{*})$.444[17] prove this under bounded DP in the case
where $|{\mathcal{S}}|=1$. We show in Corollary 1 in the appendix that, under
our assumptions, it holds for larger sets and for unbounded DP (with
$\varepsilon$ replaced by $2\varepsilon$). The inequality in (7) implies a
naive strategy for setting $\varepsilon$: select a desired bound on the
relative risk, $r^{*}$, and set $\varepsilon=\log(r^{*})/2$. Practically,
however, this strategy suffers from two drawbacks that could result in a
smaller recommended $\varepsilon$ than necessary. First, for any particular
$p_{i}$ and $q_{i}$, the bound in (7) need not be tight. In fact, this bound
is actually quite loose across a wide range of values. Second, this strategy
does not account for agencies willing to tolerate different relative risks for
different prior probabilities. For example, if $p_{i}q_{i}=0.25$, an agency
may wish to limit the adversary’s posterior to $a_{i}(p_{i},q_{i},t^{*})\leq
2\times 0.25=0.5$, but for $p_{i}q_{i}=10^{-6}$, the same agency may find a
limit of $a_{i}(p_{i},q_{i},t^{*})\leq 2\times 10^{-6}$ unnecessarily
restrictive.

Rather than restricting to a constant bound, the agency can consider tolerable
relative risks as a function of a hypothetical adversary’s prior
probabilities. We refer to this function as the agency’s risk profile, denoted
$r^{*}(p_{i},q_{i})$. Thus, the agency establishes a $r^{*}(p_{i},q_{i})$ so
that, for all $p_{i}$, $q_{i}$, and $t^{*}$,

$r_{i}(p_{i},q_{i},t^{*})\leq r^{*}(p_{i},q_{i}).$ (8)

As the following results show, the requirement in (8) translates to a maximum
value of $\varepsilon$.

##  3 Theoretical Results

In this section, we describe our main theoretical results. To devote more
space to examples and applications, we describe supporting results in Appendix
B.1 and provide all proofs in Appendix E.

We begin by formalizing the assumptions on the release mechanism for $T^{*}$
and the adversary’s model, ${\mathcal{M}}$. We emphasize that
$P[T^{*}({\mathbf{Y}})=t^{*}\mid
Y_{i}=y,{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i},I_{i}=1]$ and
$P[T^{*}({\mathbf{Y}}_{-i})=t^{*}\mid{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i},I_{i}=0]$
are probabilities under the actual DP mechanism used for the release of
$T^{*}({\mathbf{Y}})$ when $i$ is and is not included, respectively. We use
these probabilities in two assumptions as follows.

######  Assumption 1.

For all $y$ in the support of $Y_{i}$, ${\mathbf{y}}_{-i}$ in the support of
${\mathbf{Y}}_{-i}$, and $t^{*}$ in the support of $T^{*}$,

$\begin{matrix}P_{\mathcal{M}}[T^{*}({\mathbf{Y}})=t^{*}\mid
Y_{i}=y,{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i},I_{i}=1]=P[T^{*}({\mathbf{Y}})=t^{*}\mid
Y_{i}=y,{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i},I_{i}=1]\\\
P_{\mathcal{M}}[T^{*}({\mathbf{Y}}_{-i})=t^{*}\mid{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i},I_{i}=0]=P[T^{*}({\mathbf{Y}}_{-i})=t^{*}\mid{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i},I_{i}=0].\end{matrix}$

Assumption 1 implies that the mechanism for releasing $T^{*}$ given
${\mathbf{Y}}$ is known to the adversary and that the adversary uses the
actual release mechanism. It may be violated if the adversary decides not to
follow the laws of probability or ignores the mechanism used to create
$T^{*}$. Assumption 1 also rules out edge cases for ${\mathcal{M}}$ such as
the adversary using irregularities in DP floating-point implementations [33]
to learn the amount of noise added.

######  Assumption 2.

For all $y$ in the support of $Y_{i}$ and ${\mathbf{y}}_{-i}$ in the support
of ${\mathbf{Y}}_{-i}$,

$\displaystyle P_{\mathcal{M}}[{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i}\mid
I_{i}=1,Y_{i}=y]=P_{\mathcal{M}}[{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i}\mid
I_{i}=0].$ (9)

Assumption 2 implies that the adversary’s beliefs about the distribution of
${\mathbf{Y}}_{-i}$ do not change whether individual $i$ is included in the
data or not, nor do they depend on individual $i$’s confidential values. This
assumption is similar to one explored in [26], who consider the case where
“the presence/absence/record-value of each individual is independent of the
presence/absence/record-values of other individuals,” although we do not
require that (9) holds for all $i$. Assumption 2 can be violated if an
adversary might reasonably believe they can use individual $i$’s information
to learn about ${\mathbf{Y}}_{-i}$; for example, in data with a network or
hierarchical structure. We believe these two assumptions are weaker than those
in related work on choosing $\varepsilon$, which we discuss in Section 6.

Under Assumption 1 and Assumption 2, we can relate $\varepsilon$ to the
distribution of $T^{*}$ unconditional on ${\mathbf{Y}}_{-i}$ via the following
lemma. This result is similar, but not identical to, Theorem 6.1 in [26].

######  Lemma 1.

Under Assumption 1 and Assumption 2, if the release of $T^{*}=t^{*}$ satisfies
$\varepsilon$-DP, then for any subset ${\mathcal{S}}$ of the domain of
$Y_{i}$, we have

$e^{-\varepsilon}\leq\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}\leq
e^{\varepsilon},\qquad
e^{-2\varepsilon}\leq\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\notin{\mathcal{S}},I_{i}=1]}\leq e^{2\varepsilon}.$ (10)

We emphasize that Lemma 1 and all subsequent results require Assumption 2.
Without it, generalizable knowledge from the release can lead to arbitrarily
large relative risk, as demonstrated by examples in [23, 25].

For a given function $r^{*}$ selected by the data holder, we can determine the
$\varepsilon$ that should be used for the release. This is due to the
following result relating the relative risk to $\varepsilon$.

######  Theorem 1.

Under Assumption 1 and Assumption 2, if the release of $T^{*}=t^{*}$ satisfies
$\varepsilon$-DP, then

$r_{i}(p_{i},q_{i},t^{*})\leq\frac{1}{q_{i}p_{i}+e^{-2\varepsilon}(1-q_{i})p_{i}+e^{-\varepsilon}(1-p_{i})}.$
(11)

One can solve for $e^{-\varepsilon}$ in (11) to determine the recommended
$\varepsilon$, which is given by Theorem 2.

######  Theorem 2.

For any individual $i$, fix the prior probabilities, $p_{i}$ and $q_{i}$, and
a desired bound on the relative disclosure risk, $r^{*}(p_{i},q_{i})$. Define
$\varepsilon_{i}(p_{i},q_{i})$ to be the function

$\varepsilon_{i}(p_{i},q_{i})=\begin{cases}\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}-(1-p_{i})}\right),&\mbox{
if }0<q_{i}<1;\\\
\log\left(\frac{1-p_{i}}{\frac{1}{r^{*}(p_{i},1)}-p_{i}}\right),&\mbox{ if
}q_{i}=1.\end{cases}$ (12)

Under the conditions of Theorem 1, any statistic $T^{*}=t^{*}$ released under
$\varepsilon$-DP with $\varepsilon\leq\varepsilon_{i}(p_{i},q_{i})$ will
satisfy $r_{i}(p_{i},q_{i},t^{*})\leq r^{*}(p_{i},q_{i})$.

By Theorem 2, to achieve $r_{i}(p_{i},q_{i},t^{*})\leq r^{*}(p_{i},q_{i})$ for
all $(p_{i},q_{i})$, the agency should set $\varepsilon$ via the following
minimization problem:

$\varepsilon=\min_{p_{i},q_{i}\in(0,1]}\varepsilon_{i}(p_{i},q_{i}).$ (13)

Closed forms for the $\varepsilon$ resulting from a few specific risk profiles
are included in the appendix.

##  4 Using Posterior-to-prior Risks for Setting $\varepsilon$

In this section, we illustrate how an agency can use the results of Section 3
to select $\varepsilon$. Notationally, for a given quantity $x$, we use
$\tilde{x}$ to indicate the agency has fixed $x$ to a particular constant.

Given ${\mathcal{S}}$, the agency must select a form for $r^{*}(p_{i},q_{i})$.
A default choice, equivalent to the naive strategy using (7) discussed above,
is to set the bound to a constant ${\tilde{r}}>1$, i.e.,

$r^{*}(p_{i},q_{i})={\tilde{r}}.$ (14)

As we prove in Theorem 3 in the appendix, the bound in (14) implies the agency
should set $\varepsilon=\log({\tilde{r}})/2$. While a constant bound on
relative risk is simple, agencies that tolerate different risk profiles may be
able to set $\varepsilon$ to larger values, as we now illustrate.

Consider an agency that seeks to bound the relative risks for high prior
probabilities and bound the absolute disclosure risk for low prior
probabilities. For example, the agency may not want adversaries whose prior
probabilities are low to use $t^{*}$ to increase those probabilities beyond
0.10. Simultaneously, the agency may want to ensure adversaries with prior
probabilities around, for example, 0.20 cannot use $t^{*}$ to triple their
posterior probability. Such an agency can specify a risk profile that requires
either the relative risk be less than some ${\tilde{r}}>1$ or the absolute
risk be less than some ${\tilde{a}}<1$, as we now illustrate via the following
two examples.

Figure 1: Each column corresponds to a particular hypothetical agency. The
first row presents the agency’s risk profile and the second row presents the
profile’s implied maximal allowable $\varepsilon$ at each point on the curve.
Agency 1’s risk profile is given by (15) with ${\tilde{a}}=0.1$,
${\tilde{q}}=1$, and ${\tilde{r}}=3$, while Agency 2’s risk profile is given
by (16) with ${\tilde{a}}=0.1$, ${\tilde{p}}=0.05$, and ${\tilde{r}}=3$.

The first example is a setting inspired by a case study in [11].

######  Example 1.

A healthcare provider possesses a data set comprising demographic information
about individuals diagnosed with a particular form of cancer in a region of
interest. They plan to release the count of individuals diagnosed with this
form of cancer in various demographic groups via the geometric mechanism, but
are concerned this release, if insufficient noise is added, could reveal which
individuals in the community have cancer. They wish to choose $\varepsilon$
appropriately.

In this example, the primary concern is with respect to inclusion in the data
set. That is, for a given individual $i$, the adversary’s prior probability
$p_{i}$ is the key quantity, whereas the $q_{i}$ is not as important for any
given ${\mathcal{S}}$. The agency can fix some ${\tilde{q}}\in(0,1]$, for
example ${\tilde{q}}=1$ to focus on adversaries who already know individual
$i$’s demographic information. A reasonable risk profile for this agency then
might be of the form, for some ${\tilde{r}}>1$ and ${\tilde{a}}<1$,555The
second equality in (15) assumes ${\tilde{q}}>{\tilde{a}}/{\tilde{r}}$. If
${\tilde{q}}\leq{\tilde{a}}/{\tilde{r}}$, then
$r^{*}(p_{i},{\tilde{q}})={\tilde{a}}/(p_{i}{\tilde{q}})$ for all $0<p_{i}\leq
1$.

$\displaystyle
r^{*}(p_{i},q_{i})=\begin{cases}\max\left\\{\frac{{\tilde{a}}}{p_{i}{\tilde{q}}},{\tilde{r}}\right\\},&\mbox{if
}q_{i}={\tilde{q}};\\\ \infty,&\mbox{if
}q_{i}\neq{\tilde{q}}.\end{cases}=\begin{cases}\frac{{\tilde{a}}}{p_{i}{\tilde{q}}},&\mbox{
if }q_{i}={\tilde{q}}\mbox{ and
}0<p_{i}<\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}};\\\ {\tilde{r}},&\mbox{ if
}q_{i}={\tilde{q}}\mbox{ and }\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}}\leq
p_{i}\leq 1;\\\ \infty,&\mbox{ if }q_{i}\neq{\tilde{q}}.\end{cases}$ (15)

An example visualization of this risk function is presented in the first
column of Figure 1. The upper plot displays the risk profile as a function of
$p_{i}$ when $q_{i}={\tilde{q}}$, and the lower plot displays the maximal
$\varepsilon$ for which the relative risk bound holds for each $p_{i}$. We can
derive a closed form for $\varepsilon$ under this risk profile; see Table 3 in
Appendix A.2 for a summary and Theorem 5 in Appendix B.1 for details.

We now consider a second example, inspired by Example 16 in [43], that alters
Example 1.

######  Example 2.

A survey is performed on a sample of individuals in the region of interest. 5%
of the region is surveyed, and respondents are asked whether they have this
particular form of cancer along with a series of demographic questions. The
agency plans to release the counts of surveyed individuals who have and do not
have the cancer in various demographic groups via the geometric mechanism, but
is concerned this release, if insufficient noise is added, could reveal which
individuals in the community have cancer. The agency wishes to choose
$\varepsilon$ appropriately.

In this example, the primary concern is with respect to the values in the data
set. For ease of notation, let $Y_{i}$ be a $d$-vector of binary values, and
let the first element, $Y_{1i}$, be an indicator for whether individual $i$
has this form of cancer. Set ${\mathcal{S}}$ to be the subset of the support
of $Y_{i}$ for which individual $i$ has the cancer, i.e.,
${\mathcal{S}}=\\{y\in\\{0,1\\}^{d}:y_{1}=1\\}$. For individual $i$, the
adversary’s $q_{i}$ is the key quantity, and their $p_{i}$ is not of interest.
The agency can fix some ${\tilde{p}}\in(0,1]$; for example, if the agency is
most concerned about adversaries whose only prior knowledge is that individual
$i$ is in the population, but not whether they were surveyed, they might set
${\tilde{p}}=0.05$. Alternatively, they might set ${\tilde{p}}=1$ to imply an
adversary that knows a priori that individual $i$ is included in
${\mathbf{Y}}$. A reasonable risk profile for this agency might be of the
form, for some ${\tilde{a}}<1$ and ${\tilde{r}}>1$, 666The second equality in
(16) assumes ${\tilde{p}}>{\tilde{a}}/{\tilde{r}}$. If
${\tilde{p}}\leq{\tilde{a}}/{\tilde{r}}$, then
$r^{*}({\tilde{p}},q_{i})={\tilde{a}}/({\tilde{p}}q_{i})$ for all $0<q_{i}\leq
1$.

$\displaystyle
r^{*}(p_{i},q_{i})=\begin{cases}\max\left\\{\frac{{\tilde{a}}}{{\tilde{p}}q_{i}},{\tilde{r}}\right\\},&\mbox{if
}p_{i}={\tilde{p}};\\\ \infty,&\mbox{if
}p_{i}\neq{\tilde{p}}.\end{cases}=\begin{cases}\frac{{\tilde{a}}}{{\tilde{p}}q_{i}},&\mbox{
if }p_{i}={\tilde{p}}\mbox{ and
}0<q_{i}<\frac{{\tilde{a}}}{{\tilde{p}}{\tilde{r}}};\\\ {\tilde{r}},&\mbox{ if
}p_{i}={\tilde{p}}\mbox{ and }\frac{{\tilde{a}}}{{\tilde{p}}{\tilde{r}}}\leq
q_{i}\leq 1;\\\ \infty,&\mbox{ if }p_{i}\neq{\tilde{p}}.\end{cases}$ (16)

An example visualization of this risk function is presented in the second
column of Figure 1. The upper plot displays the risk profile as a function of
$q_{i}$ when $p_{i}={\tilde{p}}$, and the lower plot displays the maximal
$\varepsilon$ for which the relative risk bound holds for each $p_{i}$. The
agency can select the smallest $\varepsilon$ on this curve for their release.
We can derive a closed form the minimum; see Table 3 in Appendix A.2 for a
summary and Theorem 4 in Appendix B.1 for details. Notably, it can be shown
that the $\varepsilon$ selected under these two profiles is bounded below by
$\log({\tilde{r}})/2$ and may be much larger. We provide further exploration
and visualizations for these two examples in Appendix C.

A particular agency’s risk profile may not be characterized by one of the
forms described above. For example, an agency may be equally concerned about
$p_{i}$ and $q_{i}$, rather than focusing on one; see Appendix C.3 for an
example of this setting. Or, as argued in [30], in some settings, agencies
might be most concerned about the difference between the posterior and prior
probabilities (rather than their ratio).777Requiring the difference between
the posterior and prior probabilities to be bounded by some
${\tilde{b}}\in(0,1)$ is equivalent to requiring the relative risk be bounded
by $(p_{i}q_{i}+{\tilde{b}})/(p_{i}q_{i})$. See Appendix B.2 for details. In
such settings, it is straightforward to write down the corresponding risk
function, $r^{*}(p_{i},q_{i})$, and the optimal $\varepsilon$ can be
determined by numerically solving the minimization problem in (13).888We
provide R code at https://github.com/zekicankazan/choosing_dp_epsilon to
determine the recommended $\varepsilon$ for a provided risk profile. This code
was used to determine closed forms for $\varepsilon$ for the additional risk
profiles described in Appendix B.2. The example in Appendix C.3 demonstrates
the use of this code.

Regardless of the agency’s desiderata for a risk profile, we recommend that
they keep the following in mind when setting its functional form. First, for
any region where $r^{*}(p_{i},q_{i})>1/(p_{i}q_{i})$, the risk profile
generates a bound on the posterior probability that exceeds $1$. Of course,
the posterior probabilities themselves cannot exceed $1$; thus, in these
regions, the risk profile effectively does not bound the posterior risk. For
example, an agency that sets $r^{*}(p_{i},1)=3$ in the region where $p_{i}\geq
1/3$ (as in the left column of Figure 1) implicitly is willing to accept an
unbounded $\varepsilon$ for prior probabilities $p_{i}\geq 1/3$. Second, when
bounding the absolute disclosure risk below some ${\tilde{a}}$ in some region
of $(p_{i},q_{i})$, the agency should require $p_{i}q_{i}<{\tilde{a}}$ in that
region. When $p_{i}q_{i}={\tilde{a}}$, the recommended $\varepsilon=0$ since
the data holder requires $T^{*}$ to offer no information about $Y_{i}$. This
also suggests that an agency bounding absolute disclosure risk in a region of
$(p_{i},q_{i})$ that sets ${\tilde{a}}$ close to some value of $p_{i}q_{i}$ in
the region is willing to accept only small $\varepsilon$ values.

##  5 Managing the Trade-off in Privacy and Utility

Agencies can use the framework to manage trade-offs in disclosure risk and
data utility. In particular, the agency can evaluate potential impacts of the
DP algorithm using data quality metrics under different risk profiles,
choosing an $\varepsilon$ that leads to a satisfactory trade-off. We
demonstrate this in the below example, using data on infant mortality in
Durham county, N.C. We note that these data may not require the use of DP in
reality, but they do allow us to illustrate the process with public data.

######  Example 3.

Suppose that an agency in Durham county, N.C., wishes to release a
differentially private version of the number of infant deaths the county
experienced in the year 2020. The agency plans to use the geometric mechanism
to release this value. Of particular interest is whether the county infant
death rate meets the U. S. Department of Health and Human Services’ Healthy
People 2020 target of $6.0$ or fewer deaths per $1{,}000$ live births [19].
The agency wishes to minimize the probability that they release a noisy count
that changes whether or not the $6.0$ target is met; their goal is to ensure
this probability is below 10%. It is public information that there were
$4{,}012$ live births in Durham county in 2020 [37].

The primary concern in Example 3 is with respect to inclusion in the data.
Thus, the agency focuses on adversaries with $q_{i}=1$ and varying $p_{i}$.
The agency is generally willing to incur large relative risks if $p_{i}$ is
small and small relative risks if $p_{i}$ is large. Furthermore, due to
possible policy ramifications of appearing not to meet the target rate, the
agency is open to accepting greater privacy risks for greater accuracy in the
released count, within reason as determined by agency decision makers.

The agency’s privacy experts determine that they can characterize the agency’s
risk profiles reasonably well using the following general class of risk
profiles.

$\displaystyle
r^{*}(p_{i},q_{i})=\begin{cases}\max\left\\{\frac{{\tilde{a}}}{p_{i}},{\tilde{r}}\right\\},&\mbox{if
}q_{i}=1;\\\ \infty,&\mbox{if }q_{i}\neq 1.\end{cases}$ (17)

To allow for consideration of the effects on accuracy of different
specifications of (17), the agency considers combinations of
${\tilde{r}}\in\\{1.2,2,5\\}$ and ${\tilde{a}}\in\\{0.1,0.25,0.5\\}$. They
also examine ${\tilde{a}}=0$, which corresponds to a constant risk profile
$r^{*}(p_{i},q_{i})={\tilde{r}}$. The agency could consider other combinations
of parameters or risk profiles classes should these not lead to a satisfactory
trade-off in risk and utility.

Figure 2: The top panel presents the probability that the differentially
private algorithm switches whether Durham county’s released rate is above or
below the 6.0 target—e.g., the added noise makes the released rate 6.5 but the
actual rate is 5.5—for four hypothetical absolute differences in the true and
target rate. The middle panel presents RMSEs of the noisy count of infant
deaths. The bottom panel presents the implied $\varepsilon$. Each bar
corresponds to a different risk profile of the form in (17).

Figure 2 summarizes an analysis of the risk/utility trade-offs. For all
${\tilde{r}}$, the recommended $\varepsilon$ is larger when ${\tilde{a}}>0$
than under the corresponding constant risk profile. Similar increases in
$\varepsilon$ also are evident for the risk profiles of Section 4; see
Appendix C. Naturally, increases in ${\tilde{r}}$ and ${\tilde{a}}$ decrease
the RMSEs999Since $T^{*}$ is unbiased for the true count, the RMSE is the
standard deviation of the noise distribution. of the noisy counts due to
larger $\varepsilon$. The switching probabilities in the top panel do not use
the true count of infant deaths; rather, they consider hypothetical deviations
of $0.25$, $0.5$, $1$, and $2$ in the true rate from the target rate of $6.0$.
In this way, the agency avoids additional privacy leakage. The probability
differs substantially for each of the four deviations, with the deviation of
$0.25$ leading to the largest probability of a switch. To ensure the
probability is below $10\%$ for the deviation of $0.25$, the agency would need
to use the most aggressive of the risk profiles, which allows absolute
disclosure risk of ${\tilde{a}}=0.5$ or relative disclosure risk of
${\tilde{r}}=5$. This leads to $\varepsilon\approx 2.20$ with RMSE $\approx
0.53$. If they are willing to allow the probability to exceed $10\%$ or to
place priority on deviations exceeding $0.25$, the agency could select a less
aggressive risk profile that yields a smaller $\varepsilon$.

In actuality, there were $6.2$ infant deaths per $1{,}000$ live births in
Durham County in 2020 [36]. As the truth is close to the $6.0$ target, the
agency would need to use a large $\varepsilon$ to achieve their goal.

##  6 Relationship to Prior Work

The most similar work we are aware of is Lee and Clifton [27]’s “How Much is
Enough? Choosing $\varepsilon$ for Differential Privacy,” which also uses a
Bayesian approach to set $\varepsilon$. The authors focus on settings where
the population is public information and the adversary’s goal is to determine
which subset of individuals in the population was used for a differentially
private release of a statistic. Their method for selecting $\varepsilon$ is
tailored to the setting where only disclosure of an individual’s inclusion in
the data is of concern and the values of the entire population can be used to
inform the choice of $\varepsilon$. [27] focuses on the setting where the
Laplace mechanism is used and the population size is known; their proposal was
extended to any DP mechanism by [22, 38] and settings where the population
size is unknown by [32]. In Appendix D.1, we compare the recommended
$\varepsilon$ from the proposal in [27] and our framework in several examples.
We find that the approach of [27], for particular statistics and populations,
can recommend a larger $\varepsilon$ than the one resulting from our approach.
However, our framework may be used in settings where the values of the entire
population are not public and settings where the privacy of the values in the
release is of primary concern.

Another series of related work involves using Bayesian semantics to
communicate the meaning of $\varepsilon$ to potential study participants. For
an overview of recent work in this area, see [14], [35], and citations
therein. We highlight an example in [43] (corrected in [44]), which considers
an individual deciding whether or not to participate in a survey for which
results will be released via DP with a particular $\varepsilon$. The authors
suggest that the individual consider a bound on a posterior-to-posterior ratio
similar to the bound in (11) to make an informed decision about whether to
participate in the survey. We describe the advice of [43] using our notation
in Appendix D.2. While their and our bounds have similar expressions, the goal
in [43] differs from ours. They use the bound to characterize the individual’s
disclosure risks for a fixed $\varepsilon$, whereas we establish the agency’s
disclosure risk profile in order to set $\varepsilon$.

There are a number of other works that examine Bayesian semantics of
$\varepsilon$-DP, which we now briefly summarize. In their seminal work
proposing DP, [10] showed that, under some conditions, bounded DP is
equivalent to a bound on the relative risk when all but one data point is
fixed. [23] showed that bounded DP implies a bound on the total variation
distance between the posterior distribution with all data points included and
the posterior distribution with one data point removed. [26] showed that both
bounded and unbounded DP are equivalent to a bound on the posterior-to-prior
odds ratio exactly when the presence/absence/record-value of each individual
is independent of that of other individuals. Finally, [25] showed that both
bounded and unbounded DP imply bounds on the ratio of the posterior
distribution with all data points included to the posterior with one
observation replaced with a draw from the posterior with their observation
removed. These works do not discuss how these semantic characterizations of DP
can be used to select $\varepsilon$.

##  7 Commentary

In this article, we propose a framework for selecting $\varepsilon$ for DP by
establishing disclosure risk profiles. Essentially, we provide a method for
agencies to trade the problem of selecting $\varepsilon$ for a release for the
problem of specifying their desired disclosure risk profile. This process
involves focusing on particular classes of adversaries the agency is most
concerned about and tuning $\varepsilon$ to ensure the risk from these
adversaries is sufficiently low. We emphasize that, once applied, DP will
protect against all attacks with the guarantee of DP, not just the attack used
to tune $\varepsilon$.

We primarily focus on the risk from one class of adversary attacks on one
individual, assuming all individuals are exchangeable. If agencies assign
different risk profiles for different classes of adversaries, they could
repeat the analysis for each class and select the minimum of the recommended
$\varepsilon$ values that satisfactorily manages the risk/utility trade-off.
Similarly, if an agency does not treat individuals in the data as
exchangeable—for example, if an agency seeks to ensure lesser disclosure risks
for groups with some characteristics than for not-necessarily-disjoint groups
without those characteristics —the agency could repeat this analysis for each
group and select the minimum of the recommended $\varepsilon$ values. It is
important to consider, however, how assigning different risk profiles for
individuals with different characteristics could affect data equity.

One avenue for future work involves incorporating a version of this framework
into differentially private data analysis tools. Recently developed interfaces
for DP data releases such as [22] and [34] use the framework of [27] to guide
users in setting $\varepsilon$. Our framework could be similarly incorporated
to provide guidance in settings that do not satisfy the assumption of [27]
that the values of the population are public. Other future extensions involve
examining whether similar results follow under weaker assumptions. This
includes settings with multiple differentially private releases via existing
results that relate the relative risk to DP composition theorems (e.g., S5 of
[24]). Additionally, it may be possible to extend the results in this article
from posterior-to-prior risks to the sorts of posterior-to-posterior risks
discussed in Section 6.

## Acknowledgments and Disclosure of Funding

This research was supported by NSF grant SES-2217456. We would like to thank
Salil Vadhan and Jörg Drechsler for insightful discussion about a preliminary
version of this work.

## References

  * [1] John M Abowd, Robert Ashmead, Ryan Cumings-Menon, Simson Garfinkel, Micah Heineck, Christine Heiss, Robert Johns, Daniel Kifer, Philip Leclerc, Ashwin Machanavajjhala, et al.  The 2020 census disclosure avoidance system topdown algorithm.  arXiv preprint arXiv:2204.08986, 2022.
  * [2] John M Abowd and Lars Vilhuber.  How protective are synthetic data?  In International Conference on Privacy in Statistical Databases, pages 239–246. Springer, 2008.
  * [3] Borja Balle, Gilles Barthe, and Marco Gaboardi.  Privacy amplification by subsampling: Tight analyses via couplings and divergences.  Advances in Neural Information Processing Systems, 31, 2018.
  * [4] Mihai Budiu, Pratiksha Thaker, Parikshit Gopalan, Udi Wieder, and Matei Zaharia.  Overlook: Differentially private exploratory visualization for big data.  Journal of Privacy and Confidentiality, 12(1), 2022.
  * [5] Pranav Dandekar, Nadia Fawaz, and Stratis Ioannidis.  Privacy auctions for recommender systems.  ACM Transactions on Economics and Computation (TEAC), 2(3):1–22, 2014.
  * [6] Jörg Drechsler.  Differential privacy for government agencies—are we there yet?  Journal of the American Statistical Association, 118(541):761–773, 2023.
  * [7] George T Duncan and Diane Lambert.  Disclosure-limited data dissemination.  Journal of the American Statistical Association, 81(393):10–18, 1986.
  * [8] Cynthia Dwork.  Differential privacy.  In International colloquium on automata, languages, and programming, pages 1–12. Springer, 2006.
  * [9] Cynthia Dwork.  A firm foundation for private data analysis.  Communications of the ACM, 54(1):86–95, 2011.
  * [10] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography Conference, pages 265–284. Springer, 2006.
  * [11] Amalie Dyda, Michael Purcell, Stephanie Curtis, Emma Field, Priyanka Pillai, Kieran Ricardo, Haotian Weng, Jessica C Moore, Michael Hewett, Graham Williams, et al.  Differential privacy for public health data: An innovative tool to optimize information sharing while protecting data confidentiality.  Patterns, 2(12):100366, 2021.
  * [12] Stephen E Fienberg and Ashish P Sanil.  A Bayesian approach to data disclosure: Optimal intruder behavior for continuous data.  Journal of Official Statistics, 13(1):75, 1997.
  * [13] Lisa K Fleischer and Yu-Han Lyu.  Approximately optimal auctions for selling privacy when costs are correlated with data.  In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 568–585, 2012.
  * [14] Daniel Franzen, Saskia Nuñez von Voigt, Peter Sörries, Florian Tschorsch, and Claudia Müller-Birn.  Am i private and if so, how many? communicating privacy guarantees of differential privacy with risk communication formats.  In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 1125–1139, 2022.
  * [15] Marco Gaboardi, James Honaker, Gary King, Jack Murtagh, Kobbi Nissim, Jonathan Ullman, and Salil Vadhan.  Psi ($\\{$$\backslash$Psi$\\}$): a private data sharing interface.  arXiv preprint arXiv:1609.04340, 2016.
  * [16] Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan.  Universally utility-maximizing privacy mechanisms.  SIAM Journal on Computing, 41(6):1673–1693, 2012.
  * [17] Ruobin Gong and Xiao-Li Meng.  Congenial differential privacy under mandated disclosure.  In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference, pages 59–70, 2020.
  * [18] Michael Hay, Ashwin Machanavajjhala, Gerome Miklau, Yan Chen, Dan Zhang, and George Bissias.  Exploring privacy-accuracy tradeoffs using dpcomp.  In Proceedings of the 2016 International Conference on Management of Data, pages 2101–2104, 2016.
  * [19] HHS.  Healthy people 2020.  Office of Disease Prevention and Health Promotion, U.S. Department of Health and Human Services, 2020.  Accessed on 22 April 2024.
  * [20] V Joseph Hotz, Christopher R Bollinger, Tatiana Komarova, Charles F Manski, Robert A Moffitt, Denis Nekipelov, Aaron Sojourner, and Bruce D Spencer.  Balancing data privacy and usability in the federal statistical system.  Proceedings of the National Academy of Sciences, 119(31), 2022.
  * [21] Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C Pierce, and Aaron Roth.  Differential privacy: An economic method for choosing epsilon.  In 2014 IEEE 27th Computer Security Foundations Symposium, pages 398–410. IEEE, 2014.
  * [22] Mark F St John, Grit Denker, Peeter Laud, Karsten Martiny, Alisa Pankova, and Dusko Pavlovic.  Decision support for sharing data using differential privacy.  In 2021 IEEE Symposium on Visualization for Cyber Security (VizSec), pages 26–35. IEEE, 2021.
  * [23] Shiva P Kasiviswanathan and Adam Smith.  On the’semantics’ of differential privacy: A Bayesian formulation.  Journal of Privacy and Confidentiality, 6(1), 2014.
  * [24] Zeki Kazan and Jerome Reiter.  Assessing statistical disclosure risk for differentially private, hierarchical count data, with application to the 2020 us decennial census.  Statistica Sinica, 34:to appear, 2024.
  * [25] Daniel Kifer, John M Abowd, Robert Ashmead, Ryan Cumings-Menon, Philip Leclerc, Ashwin Machanavajjhala, William Sexton, and Pavel Zhuravlev.  Bayesian and frequentist semantics for common variations of differential privacy: Applications to the 2020 census.  arXiv preprint arXiv:2209.03310, 2022.
  * [26] Daniel Kifer and Ashwin Machanavajjhala.  Pufferfish: A framework for mathematical privacy definitions.  ACM Transactions on Database Systems (TODS), 39(1):1–36, 2014.
  * [27] Jaewoo Lee and Chris Clifton.  How much is enough? choosing $\varepsilon$ for differential privacy.  In International Conference on Information Security, pages 325–340. Springer, 2011.
  * [28] Chao Li, Daniel Yang Li, Gerome Miklau, and Dan Suciu.  A theory of pricing private data.  ACM Transactions on Database Systems (TODS), 39(4):1–28, 2014.
  * [29] Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber.  Privacy: Theory meets practice on the map.  In 2008 IEEE 24th International Conference on Data Engineering, pages 277–286. IEEE, 2008.
  * [30] Charles F Manski.  The lure of incredible certitude.  Economics & Philosophy, 36(2):216–245, 2020.
  * [31] David McClure and Jerome P Reiter.  Differential privacy and statistical disclosure risk measures: An investigation with binary synthetic data.  Transactions on Data Privacy, 5(3):535–552, 2012.
  * [32] Luise Mehner, Saskia Nuñez von Voigt, and Florian Tschorsch.  Towards explaining epsilon: A worst-case study of differential privacy risks.  In 2021 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW), pages 328–331. IEEE, 2021.
  * [33] Ilya Mironov.  On significance of the least significant bits for differential privacy.  In Proceedings of the 2012 ACM Conference on Computer and Communications Security, pages 650–661, 2012.
  * [34] Priyanka Nanayakkara, Johes Bater, Xi He, Jessica Hullman, and Jennie Rogers.  Visualizing privacy-utility trade-offs in differentially private data releases.  Proceedings on Privacy Enhancing Technologies, 2022.
  * [35] Priyanka Nanayakkara, Mary Anne Smart, Rachel Cummings, Gabriel Kaptchuk, and Elissa M Redmiles.  What are the chances? explaining the epsilon parameter in differential privacy.  In 32nd USENIX Security Symposium (USENIX Security 23), pages 1613–1630, 2023.
  * [36] NCDHHS.  2020 north carolina infant mortality report, table 1.  NC State Center for Health Statistics, 2020.  Accessed on 22 April 2024.
  * [37] NCDHHS.  Cy2020 north carolina resident births by county of residence and month.  NC State Center for Health Statistics, 2020.  Accessed on 22 April 2024.
  * [38] Alisa Pankova and Peeter Laud.  Interpreting epsilon of differential privacy in terms of advantage in guessing or approximating sensitive attributes.  In 2022 IEEE 35th Computer Security Foundations Symposium (CSF), pages 96–111. IEEE, 2022.
  * [39] Jerome P Reiter.  Estimating risks of identification disclosure in microdata.  Journal of the American Statistical Association, 100(472):1103–1112, 2005.
  * [40] Jerome P Reiter.  Differential privacy and federal data releases.  Annual Review of Statistics and Its Application, 6:85–101, 2019.
  * [41] Jayshree Sarathy, Sophia Song, Audrey Haque, Tania Schlatter, and Salil Vadhan.  Don’t look at the data! how differential privacy reconfigures the practices of data science.  arXiv preprint arXiv:2302.11775, 2023.
  * [42] Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang.  Privacy loss in Apple’s implementation of differential privacy on macos 10.12.  arXiv preprint arXiv:1709.02753, 2017.
  * [43] Alexandra Wood, Micah Altman, Aaron Bembenek, Mark Bun, Marco Gaboardi, James Honaker, Kobbi Nissim, David R O’Brien, Thomas Steinke, and Salil Vadhan.  Differential privacy: A primer for a non-technical audience.  Vanderbilt Journal of Entertainment & Technology Law, 21:209, 2018.
  * [44] Alexandra Wood, Micah Altman, Kobbi Nissim, and Salil Vadhan.  Designing access with differential privacy.  In Handbook on Using Administrative Data for Research and Evidence-based Policy. Abdul Latif Jameel Poverty Action Lab, Cambridge, MA, 2020.

##  Appendix A Supplemental Tables

###  A.1 Notation Summary

Table 1 summarizes the notation of Section 2. Table 2 summarizes the
definitions of key probabilistic quantities.

Symbol | Description
---|---
${\mathbf{P}}$ | Population of individuals the data is drawn from
${\mathbf{Y}}$ |  $n\times d$ confidential data set
$Y_{i}$ | Length-$d$ vector of values for individual $i$
$I_{i}$ | Indicator for whether individual $i$ is included in ${\mathbf{Y}}$
${\mathbf{Y}}_{-i}$ |  $(n-1)\times d$ matrix of the values in ${\mathbf{Y}}$ excluding those for individual $i$
${\mathcal{S}}$ | Subset of the support of $Y_{i}$ constituting a privacy violation
$r^{*}(p_{i},q_{i})$ | Function describing the agency’s desired relative risk bound
${\mathcal{M}}$ | Adversary’s model for predicting $Y_{i}$
$T^{*}$ | Noisy estimate of $T({\mathbf{Y}})$, the function being released
Table 1: Summary of notation. Symbol | Definition | Description
---|---|---
$p_{i}$ | $P_{\mathcal{M}}[I_{i}=1]$ | Prior probability of inclusion
$q_{i}$ | $P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid I_{i}=1]$ | Prior probability values disclosed
$r_{i}(p_{i},q_{i},t^{*})$ | $\frac{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1\mid T^{*}=t^{*}]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1]}$ | Relative disclosure risk
$a_{i}(p_{i},q_{i},t^{*})$ | $P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1\mid T^{*}=t^{*}]$ | Absolute disclosure risk
Table 2: Summary of definitions.

###  A.2 Closed Forms for $\varepsilon$

In this section, we provide a reference for all derived closed forms for
$\varepsilon$. Corresponding formal theorem statements are provided in
Appendix B.1 and discussion of closed forms not referenced in the main text is
provided in Appendix B.2. Table 3 provides the closed forms.

Risk Profile | Condition | Recommended $\varepsilon$
---|---|---
(14); ${\tilde{r}}$ |  | $\frac{1}{2}\log({\tilde{r}})$
| $0<{\tilde{q}}\leq\frac{{\tilde{a}}}{{\tilde{r}}}$ | $\frac{1}{2}\log\left(\frac{{\tilde{a}}(1-{\tilde{q}})}{{\tilde{q}}(1-{\tilde{a}})}\right)$
(15) | $0<{\tilde{q}}\leq\frac{1}{{\tilde{r}}+1}\mbox{ and }\frac{{\tilde{a}}}{{\tilde{r}}}<{\tilde{q}}<1$ | $\frac{1}{2}\log\left(\frac{1-{\tilde{q}}}{\frac{1}{{\tilde{r}}}-{\tilde{q}}}\right)$
$\max\left\\{\frac{{\tilde{a}}}{p_{i}{\tilde{q}}},{\tilde{r}}\right\\}$ | $\frac{1}{{\tilde{r}}+1}<{\tilde{q}}<1\mbox{ and }\frac{{\tilde{a}}}{{\tilde{r}}}<{\tilde{q}}<1$ | $\log\left(\frac{2{\tilde{a}}(1-{\tilde{q}})}{\sqrt{({\tilde{r}}{\tilde{q}}-{\tilde{a}})^{2}+4{\tilde{a}}{\tilde{q}}(1-{\tilde{q}})\left(1-{\tilde{a}}\right)}-({\tilde{r}}{\tilde{q}}-{\tilde{a}})}\right)$
| ${\tilde{q}}=1$ | $\log\left(\frac{{\tilde{r}}-{\tilde{a}}}{1-{\tilde{a}}}\right)$
(16) | $0<{\tilde{p}}\leq\frac{{\tilde{a}}}{{\tilde{r}}}$ | $\log\left(\frac{{\tilde{a}}(1-{\tilde{p}})}{{\tilde{p}}(1-{\tilde{a}})}\right)$
$\max\left\\{\frac{{\tilde{a}}}{{\tilde{p}}q_{i}},{\tilde{r}}\right\\}$ | $\frac{{\tilde{a}}}{{\tilde{r}}}<{\tilde{p}}\leq 1$ | $\log\left(\frac{2({\tilde{p}}{\tilde{r}}-{\tilde{a}})}{\sqrt{{\tilde{r}}^{2}(1-{\tilde{p}})^{2}+4({\tilde{p}}{\tilde{r}}-{\tilde{a}})\left(1-{\tilde{a}}\right)}-{\tilde{r}}(1-{\tilde{p}})}\right)$
(25) | $0\leq{\tilde{q}}_{0}\leq\frac{1}{{\tilde{r}}+1}$ | $\log\left(\frac{2{\tilde{p}}_{1}(1-{\tilde{q}}_{0})}{\sqrt{(1-{\tilde{p}}_{1})^{2}+4{\tilde{p}}_{1}(1-{\tilde{q}}_{0})\left(\frac{1}{{\tilde{r}}}-{\tilde{p}}_{1}{\tilde{q}}_{0}\right)}-(1-{\tilde{p}}_{1})}\right)$
${\tilde{r}}$ | $\frac{1}{{\tilde{r}}+1}<{\tilde{q}}_{0}<1\mbox{ and }{\tilde{p}}_{0}>0$ | $\log\left(\frac{2{\tilde{p}}_{0}(1-{\tilde{q}}_{0})}{\sqrt{(1-{\tilde{p}}_{0})^{2}+4{\tilde{p}}_{0}(1-{\tilde{q}}_{0})\left(\frac{1}{{\tilde{r}}}-{\tilde{p}}_{0}{\tilde{q}}_{0}\right)}-(1-{\tilde{p}}_{0})}\right)$
$\mbox{if }{\tilde{p}}_{0}\leq p_{i}\leq{\tilde{p}}_{1}$ | $\frac{1}{{\tilde{r}}+1}<{\tilde{q}}_{0}<1\mbox{ and }{\tilde{p}}_{0}=0$ | $\log\left({\tilde{r}}\right)$
$\mbox{and }{\tilde{q}}_{0}\leq q_{i}\leq{\tilde{q}}_{1}$ | ${\tilde{q}}_{0}=1$ | $\log\left(\frac{1-{\tilde{p}}_{0}}{\frac{1}{{\tilde{r}}}-{\tilde{p}}_{0}}\right)$
(28); $\frac{p_{i}q_{i}+{\tilde{b}}}{p_{i}q_{i}}$ |  | $\log\left(\frac{1+{\tilde{b}}}{1-{\tilde{b}}}\right)$
Table 3: Closed forms for $\varepsilon$ for various $r^{*}(p_{i},q_{i})$.

##  Appendix B Additional Results

###  B.1 Omitted Results

In this section, we present all results omitted from the paper. Proofs of
these results are included in Appendix E.

First, we state a corollary to Theorem 1, which generalizes Theorem 1.3 in
[17] to sets where $|{\mathcal{S}}|>1$ and to unbounded DP.

######  Corollary 1.

Under the conditions of Theorem 1, for all $p_{i},q_{i}\in(0,1]$ and all
$t^{*}$,

$\displaystyle r_{i}(p_{i},q_{i},t^{*})\leq e^{2\varepsilon}.$ (18)

Next, we state a corollary to Theorem 2 which considers the special case where
$p_{i}=1$. This corresponds to a setting where individual $i$’s inclusion in
the data is known a priori by the adversary, for example data from a census or
public social media platform.

######  Corollary 2.

Under the conditions of Theorem 2, if $p_{i}=1$ and $0<q_{i}<1$, any statistic
$T^{*}=t^{*}$ released under $\varepsilon$-DP with

$\varepsilon\leq\frac{1}{2}\log\left(\frac{1-q_{i}}{\frac{1}{r^{*}(1,q_{i})}-q_{i}}\right),$
(19)

will satisfy $r_{i}(1,q_{i},t^{*})\leq r^{*}(1,q_{i})$.

For particular forms of $r^{*}$, the optimization in (13) has a closed form
solution. This is detailed by the following theorems, which are preceded by
two lemmas used in the proofs.

######  Lemma 2.

Fix $p_{i},q_{i}\in(0,1)$ and let
$r^{*}(p_{i},q_{i})=\frac{{\tilde{a}}}{p_{i}q_{i}}$. Then the function

$\varepsilon(p_{i},q_{i})=\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}-(1-p_{i})}\right)$
(20)

has partial derivatives such that

  1. 1.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial p_{i}}<0$ for all
$0<p_{i}<1$ and $0<q_{i}<1$

  2. 2.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial q_{i}}<0$ for all
$0<p_{i}<1$ and $0<q_{i}<1$.

######  Lemma 3.

Fix $p_{i},q_{i}\in(0,1)$ and let $r^{*}(p_{i},q_{i})={\tilde{r}}$. Then the
function

$\varepsilon(p_{i},q_{i})=\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}-(1-p_{i})}\right)$
(21)

has partial derivatives such that

  1. 1.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial p_{i}}<0$ if
$0<q_{i}<\frac{1}{{\tilde{r}}+1}$ and $0<p_{i}<1$

  2. 2.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial p_{i}}=0$ if
$q_{i}=\frac{1}{{\tilde{r}}+1}$ and $0<p_{i}<1$

  3. 3.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial p_{i}}>0$ if
$\frac{1}{{\tilde{r}}+1}<q_{i}<1$ and $0<p_{i}<1$

  4. 4.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial q_{i}}>0$ for all
$0<p_{i}<1$ and $0<q_{i}<1$.

######  Theorem 3.

Under the conditions of Theorem 2, if $r^{*}(p_{i},q_{i})={\tilde{r}}>1$, the
solution to the minimization problem in (13) is

$\varepsilon=\frac{1}{2}\log\left({\tilde{r}}\right).$ (22)

######  Theorem 4.

Under the conditions of Theorem 2, let ${\tilde{a}}<1$, ${\tilde{p}}\leq 1$,
and ${\tilde{r}}>1$, and $0<q_{i}<1$. If the function $r^{*}$ is such that
$r^{*}({\tilde{p}},q_{i})=\max\\{{\tilde{a}}/({\tilde{p}}q_{i}),{\tilde{r}}\\}$
and $r^{*}(p_{i},q_{i})=\infty$ if $p_{i}\neq{\tilde{p}}$, then the solution
to the minimization problem in (13) is

$\varepsilon=\begin{cases}\log\left(\frac{{\tilde{a}}(1-{\tilde{p}})}{{\tilde{p}}(1-{\tilde{a}})}\right),&\mbox{
if }0<{\tilde{p}}\leq\frac{{\tilde{a}}}{{\tilde{r}}};\\\
\log\left(\frac{2({\tilde{p}}{\tilde{r}}-{\tilde{a}})}{\sqrt{{\tilde{r}}^{2}(1-{\tilde{p}})^{2}+4({\tilde{p}}{\tilde{r}}-{\tilde{a}})\left(1-{\tilde{a}}\right)}-{\tilde{r}}(1-{\tilde{p}})}\right),&\mbox{
if }\frac{{\tilde{a}}}{{\tilde{r}}}<{\tilde{p}}\leq 1.\end{cases}$ (23)

######  Theorem 5.

Under the conditions of Theorem 2, let ${\tilde{a}}<1$, ${\tilde{q}}\leq 1$,
and ${\tilde{r}}>1$, and $0<p_{i}<1$. If the function $r^{*}$ is such that
$r^{*}(p_{i},{\tilde{q}})=\max\\{{\tilde{a}}/(p_{i}{\tilde{q}}),{\tilde{r}}\\}$
and $r^{*}(p_{i},q_{i})=\infty$ for $q_{i}\neq{\tilde{q}}$, then the solution
to the minimization problem in (13) is

$\varepsilon=\begin{cases}\frac{1}{2}\log\left(\frac{{\tilde{a}}(1-{\tilde{q}})}{{\tilde{q}}(1-{\tilde{a}})}\right),&\mbox{if
}0<{\tilde{q}}\leq\frac{{\tilde{a}}}{{\tilde{r}}};\\\
\frac{1}{2}\log\left(\frac{1-{\tilde{q}}}{\frac{1}{{\tilde{r}}}-{\tilde{q}}}\right),&\mbox{if
}0<{\tilde{q}}\leq\frac{1}{{\tilde{r}}+1}\mbox{ and
}\frac{{\tilde{a}}}{{\tilde{r}}}<{\tilde{q}}<1;\\\
\log\left(\frac{2{\tilde{a}}(1-{\tilde{q}})}{\sqrt{({\tilde{r}}{\tilde{q}}-{\tilde{a}})^{2}+4{\tilde{a}}{\tilde{q}}(1-{\tilde{q}})\left(1-{\tilde{a}}\right)}-({\tilde{r}}{\tilde{q}}-{\tilde{a}})}\right),&\mbox{if
}\frac{1}{{\tilde{r}}+1}<{\tilde{q}}<1\mbox{ and
}\frac{{\tilde{a}}}{{\tilde{r}}}<{\tilde{q}}<1;\\\
\log\left(\frac{{\tilde{r}}-{\tilde{a}}}{1-{\tilde{a}}}\right),&\mbox{if
}{\tilde{q}}=1.\end{cases}$ (24)

###  B.2 Additional Closed Forms

In this section, we present closed form results for the $\varepsilon$ implied
by additional disclosure risk profiles not discussed in the main text. Proofs
of these results are not provided, although we note that proofs would have a
structure similar to the proofs of Theorems 3–5. It is straightforward to
verify these results empirically.

First, consider an agency that requires a constant relative risk bound to hold
on a subset of the $(p_{i},q_{i})$ space and does not have any bounds outside
that space. That is, rather than enforcing $r^{*}(p_{i},q_{i})={\tilde{r}}$
for all $0\leq p_{i},q_{i}\leq 1$, the agency only enforces this condition for
${\tilde{p}}_{0}\leq p_{i}\leq{\tilde{p}}_{1}$ and ${\tilde{q}}_{0}\leq
q_{i}\leq{\tilde{q}}_{1}$, where $0\leq{\tilde{p}}_{0}\leq{\tilde{p}}_{1}\leq
1$ and $0\leq{\tilde{q}}_{0}\leq{\tilde{q}}_{1}\leq 1$ (for
${\tilde{p}}_{1},{\tilde{q}}_{1}>0$). Formally,

$\displaystyle r^{*}(p_{i},q_{i})=\begin{cases}{\tilde{r}},&\mbox{if
}{\tilde{p}}_{0}\leq p_{i}\leq{\tilde{p}}_{1}\mbox{ and }{\tilde{q}}_{0}\leq
q_{i}\leq{\tilde{q}}_{1};\\\ \infty,&\mbox{otherwise}.\end{cases}$ (25)

The recommended $\varepsilon$ for an agency with the risk profile in (25) is

$\varepsilon=\begin{cases}\log\left(\frac{2{\tilde{p}}_{1}(1-{\tilde{q}}_{0})}{\sqrt{(1-{\tilde{p}}_{1})^{2}+4{\tilde{p}}_{1}(1-{\tilde{q}}_{0})\left(\frac{1}{{\tilde{r}}}-{\tilde{p}}_{1}{\tilde{q}}_{0}\right)}-(1-{\tilde{p}}_{1})}\right),&\mbox{if
}0\leq{\tilde{q}}_{0}\leq\frac{1}{{\tilde{r}}+1};\\\
\log\left(\frac{2{\tilde{p}}_{0}(1-{\tilde{q}}_{0})}{\sqrt{(1-{\tilde{p}}_{0})^{2}+4{\tilde{p}}_{0}(1-{\tilde{q}}_{0})\left(\frac{1}{{\tilde{r}}}-{\tilde{p}}_{0}{\tilde{q}}_{0}\right)}-(1-{\tilde{p}}_{0})}\right),&\mbox{if
}\frac{1}{{\tilde{r}}+1}<{\tilde{q}}_{0}<1\mbox{ and }{\tilde{p}}_{0}>0;\\\
\log\left({\tilde{r}}\right),&\mbox{if
}\frac{1}{{\tilde{r}}+1}<{\tilde{q}}_{0}<1\mbox{ and }{\tilde{p}}_{0}=0;\\\
\log\left(\frac{1-{\tilde{p}}_{0}}{\frac{1}{{\tilde{r}}}-{\tilde{p}}_{0}}\right),&\mbox{if
}{\tilde{q}}_{0}=1.\end{cases}$ (26)

Next, consider an agency that desires a constant bound on the difference
between the posterior and the prior. That is, for some ${\tilde{b}}\in(0,1)$,
they would like to enforce

$P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1\mid
T^{*}=t^{*}]-P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1]\leq{\tilde{b}}.$
(27)

This constraint corresponds to the following risk profile.

$r^{*}(p_{i},q_{i})=\frac{p_{i}q_{i}+{\tilde{b}}}{p_{i}q_{i}}=1+\frac{{\tilde{b}}}{p_{i}q_{i}}.$
(28)

The recommended $\varepsilon$ for an agency with this risk profile is

$\varepsilon=\log\left(\frac{1+{\tilde{b}}}{1-{\tilde{b}}}\right).$ (29)

Notably, by a Taylor series approximation,
$-\log(1-{\tilde{b}})\approx{\tilde{b}}+{\tilde{b}}^{2}/2$. Thus, for small
${\tilde{b}}$, it follows that the recommended $\varepsilon$ can be
approximated by

$\varepsilon=\log(1+{\tilde{b}})-\log(1-{\tilde{b}})\approx\left({\tilde{b}}-\frac{{\tilde{b}}^{2}}{2}\right)+\left({\tilde{b}}+\frac{{\tilde{b}}^{2}}{2}\right)=2{\tilde{b}}.$
(30)

##  Appendix C Additional Examples

This section provides additional examples of risk profiles.

###  C.1 Extended Example 1

Here we provide an extended analysis of Example 1. The setting is restated
below.

######  Example 1.

A healthcare provider possesses a data set comprising demographic information
about individuals diagnosed with a particular form of cancer in a region of
interest. They plan to release the count of individuals diagnosed with this
form of cancer in various demographic groups via the geometric mechanism, but
are concerned this release, if insufficient noise is added, could reveal which
individuals in the community have cancer. They wish to choose $\varepsilon$
appropriately.

Figure 3: The risk profiles for three agencies with risk profile given by
(31). The lines in the lower panels represent the risk profiles for $q_{i}=1$
as a function of $p_{i}$, and the colors represent the implied $\varepsilon$
at each point on the curve. The lines in the upper panels represent the
corresponding baseline $r^{*}(p_{i},1)={\tilde{r}}$. The left plots set
${\tilde{r}}=1.5$, the center plots set ${\tilde{r}}=3$, and the right plots
set ${\tilde{r}}=6$.

As discussed in Section 4, a reasonable risk profile for this setting might
focus on $p_{i}$ and set $q_{i}=1$. Additionally, suppose the agency is
generally willing to accept a maximum absolute disclosure risk of $0.25$ for
adversaries with small prior probabilities. A risk profile for this agency
might be of the form, for some ${\tilde{r}}>1$,

$r^{*}(p_{i},q_{i})=\begin{cases}\max\left\\{\frac{0.25}{p_{i}},{\tilde{r}}\right\\},&\mbox{if
}q_{i}=1;\\\ \infty,&\mbox{if }q_{i}\neq 1.\end{cases}$ (31)

Agency | ${\tilde{r}}$ |  $\varepsilon$ Recommendation | Noise Std. Dev. | Prob. Exact
---|---|---|---|---
1 | $1.5$ | $0.51$ | $2.74$ | 25%
2 | $3$ | $1.30$ | $1.02$ | 57%
3 | $6$ | $2.04$ | $0.59$ | 77%
Table 4: For each of the three risk profiles in Figure 3, we present the
$\varepsilon$ recommended by our framework. For a release satisfying
$\varepsilon$-DP using the geometric mechanism, we present the corresponding
standard deviation of the noise distribution and the probability that the
exact value is released, i.e., the noise distribution’s probability mass at
zero.

Three example risk functions of this form are presented in Figure 3. Agency 1
is risk averse, agency 3 is utility seeking, and agency 2 sits in between in
terms of risk and utility. For adversaries with high prior probabilities,
agencies 1, 2, and 3 bound the relative disclosure risk at ${\tilde{r}}=1.5$,
${\tilde{r}}=3$, and ${\tilde{r}}=6$, respectively. Table 4 presents the
maximal $\varepsilon$ which satisfies the desired risk profile for each
agency, computed via the formulas in Appendix A.2. To provide intuition on the
amount of noise implied by these $\varepsilon$, in Table 4 we display the
standard deviation of the noise distribution for each statistic under the
geometric mechanism and the probability that the geometric mechanism will
output the exact value of each statistic. The risk averse agency is
recommended a $\varepsilon$ that results in a release with a high standard
deviation and fairly low probability of releasing the exact value of the
statistic. The utility seeking agency is recommended a $\varepsilon$ that
results in a release with a fairly low standard deviation and high probability
of releasing the exact value of the statistic.

The $\varepsilon$ recommendations from these risk profiles, which are tailored
to the specific setting and agency preferences, are much higher than the
recommendations from a corresponding simple risk profile of
$r^{*}(p_{i},q_{i})={\tilde{r}}$ for all prior probabilities. For comparison,
this simple profile yields $\varepsilon\approx 0.20$, $\varepsilon\approx
0.55$, and $\varepsilon\approx 0.90$ for ${\tilde{r}}=1.5$, ${\tilde{r}}=3$,
and ${\tilde{r}}=6$, respectively, which are less than half the recommended
$\varepsilon$ values above.

###  C.2 Extended Example 2

Here we provide an extended analysis of Example 2. The setting is restated
below.

######  Example 2.

A survey is performed on a sample of individuals in the region of interest. 5%
of the region is surveyed, and respondents are asked whether they have this
particular form of cancer along with a series of demographic questions. The
agency plans to release the counts of surveyed individuals who have and do not
have the cancer in various demographic groups via the geometric mechanism, but
is concerned this release, if insufficient noise is added, could reveal which
individuals in the community have cancer. The agency wishes to choose
$\varepsilon$ appropriately.

Figure 4: The risk profiles for three agencies with risk profile given by (32). The lines represent the risk profiles for $p_{i}=0.05$ as a function of $q_{i}$, and the colors represent the implied $\varepsilon$ at each point on the curve. The left plot sets ${\tilde{a}}=0.025$, the center sets ${\tilde{a}}=0.15$, and the right sets ${\tilde{a}}=0.3$. Agency | ${\tilde{a}}$ |  $\varepsilon$ Recommendation | Noise Std. Dev. | Prob. Exact
---|---|---|---|---
1 | $0.025$ | $1.09$ | $1.24$ | 50%
2 | $0.15$ | $1.21$ | $1.10$ | 54%
3 | $0.3$ | $2.10$ | $0.56$ | 78%
Table 5: For each of the three risk profiles in Figure 4, we present the
$\varepsilon$ recommended by our framework. For a release satisfying
$\varepsilon$-DP using the geometric mechanism, we present the corresponding
standard deviation of the noise distribution and the probability that the
exact value is released (i.e., the noise distribution’s probability mass at
zero).

As discussed in Section 4, a reasonable risk profile for this setting might
set ${\mathcal{S}}=\\{y\in\\{0,1\\}^{d}:y_{1}=1\\}$ and focus on $q_{i}$,
while fixing $p_{i}=0.05$. Additionally, suppose the agency is generally
willing to accept a maximum relative disclosure risk of $3$ for adversaries
with large prior probabilities. A reasonable risk profile for this agency
might be of the form, for some ${\tilde{a}}<1$,

$\displaystyle
r^{*}(p_{i},q_{i})=\begin{cases}\max\left\\{\frac{{\tilde{a}}}{0.05q_{i}},3\right\\},&\mbox{if
}p_{i}=0.05;\\\ \infty,&\mbox{if }p_{i}\neq 0.05.\end{cases}$ (32)

Three example risk functions of this form are presented in Figure 4. Once
again, agency 1 is risk averse, agency 3 corresponds is utility seeking, and
agency 2 sits in between on risk and utility. Agencies 1, 2, and 3 are willing
to allow adversaries to achieve an absolute disclosure risk of
${\tilde{a}}=0.025$, ${\tilde{a}}=0.15$, and ${\tilde{a}}=0.3$, respectively.
Table 5 presents the $\varepsilon$ recommendations for each agency along with
the standard deviation of the noise and probability of releasing the exact
value of each statistic under the geometric mechanism.

As in Table 4, the $\varepsilon$ recommendations reflect trade offs between
privacy and accuracy. They also are much higher than the recommendations from
a corresponding simple risk profile of $r^{*}(p_{i},q_{i})=3$ for all prior
probabilities, which implies $\varepsilon\approx 0.55$. Even the most risk
averse agency is recommended an $\varepsilon$ that is much larger than this
baseline risk profile. This gain is primarily due to the assumptions that the
survey is a simple random sample from the population, and the adversary has no
prior knowledge about which individuals are surveyed. Essentially, the
additional uncertainty from the sampling mechanism allows for an $\varepsilon$
recommendation with less noise injected. This is consistent with prior work
showing that DP mechanisms applied to random subsamples provide better privacy
guarantees [3]. The recommended $\varepsilon$ will increase as the proportion
of individuals from the population surveyed (${\tilde{p}}$) decreases. For
example, for the risk function in (32) with ${\tilde{a}}=0.025$ and
${\tilde{r}}=3$, if ${\tilde{p}}=0.005$, we recommend $\varepsilon\approx
1.63$; if ${\tilde{p}}=0.0005$, we recommend $\varepsilon\approx 3.94$.

###  C.3 Two-dimensional Example

The examples in Appendices C.1 and C.2 focus on settings where only one of
$p_{i}$ and $q_{i}$ is important and the other can be reasonably fixed to a
constant. Now we consider the setting where both may be simultaneously
important. For example, in Example 2, the agency may wish to consider
adversaries with various $p_{i}$, rather than only ${\tilde{p}}=0.05$. Perhaps
the agency wishes to limit the absolute disclosure to be below
$\tilde{a}=0.25$ when total prior probability of disclosure, $p_{i}q_{i}$, is
low and limit relative disclosure to be below $\tilde{r}=3$ when $p_{i}q_{i}$
is high. This corresponds to the following risk profile.

$\displaystyle
r^{*}(p_{i},q_{i})=\max\left\\{\frac{{\tilde{a}}}{p_{i}q_{i}},{\tilde{r}}\right\\}=\max\left\\{\frac{0.25}{p_{i}q_{i}},3\right\\}.$
(33)

Figure 5: The top panel presents the $r^{*}(p_{i},q_{i})$ from (33) as a
function of $p_{i}$ and $q_{i}$. The bottom panel presents the implied
$\varepsilon_{i}(p_{i},q_{i})$ as a function of $p_{i}$ and $q_{i}$. The red
point represents
$\operatorname*{argmin}_{(p_{i},q_{i})}\varepsilon_{i}(p_{i},q_{i})$. For
clarity of presentation, all $r^{*}(p_{i},q_{i})>100$ are truncated to $100$
and all $\varepsilon_{i}(p_{i},q_{i})>4$ are truncated to $4$.

A plot of this desired bound on pairs $(p_{i},q_{i})$ on the space
$(0,1]\times(0,1]$ is presented in the top panel of Figure 5. Notably, if
$p_{i}$ is fixed at ${\tilde{p}}\in(0,1]$, a plot of
$r^{*}({\tilde{p}},q_{i})$ as a function of $q_{i}$ has a form similar to the
plots of Figure 4. Similarly, if $q_{i}$ is fixed at ${\tilde{q}}\in(0,1]$, a
plot of $r^{*}(p_{i},{\tilde{q}})$ as a function of $p_{i}$ has a form similar
to the plots of Figure 3.

To determine the $\varepsilon$ recommended by this profile, we numerically
solve the minimization problem in (13). A plot of
$\varepsilon_{i}(p_{i},q_{i})$ as a function of pairs $(p_{i},q_{i})$ on the
space $(0,1]\times(0,1]$ is presented in the bottom panel of Figure 5. Our
framework recommends $\varepsilon\approx 0.65$, which corresponds to $p_{i}=1$
and $q_{i}=0.083={\tilde{a}}/{\tilde{r}}$.

##  Appendix D Additional Discussion of Prior Work

In this section, we describe two previous works with similar aims to our
framework using the notation in Section 2.2, expanding on the discussion in
Section 6.

###  D.1 “How Much is Enough? Choosing $\varepsilon$ for Differential Privacy"

[27] focus on settings where the population, ${\mathbf{P}}$, of size $n$ is
public information and the adversary’s goal is to determine which subset of
individuals in ${\mathbf{P}}$ was used for a differentially private release of
a statistic. We can characterize their setting with the notation of Section
2.2 as follows. We define ${\mathbf{Y}}$ to be the subset of individuals’
values in ${\mathbf{P}}$ used to compute the statistic of interest,
$T({\mathbf{Y}})$, and its released DP counterpart, $T^{*}({\mathbf{Y}})$. In
their examples, the authors focus on the setting where only one individual is
removed from ${\mathbf{P}}$ to create ${\mathbf{Y}}$, and the adversary’s goal
is to determine which $i$ was removed.

We can apply our framework to this setting with a minor modification. For this
comparison, we assume the adversary’s
$q_{i}=P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid I_{i}=0]=1$ for any set
${\mathcal{S}}$ (although we note that this is a weaker assumption than that
of Lee and Clifton, since we do not assume ${\mathbf{P}}$ is public). We
redefine $p_{i}$ and the risk measures to be in terms of $I_{i}=0$, rather
than $I_{i}=1$.

$\displaystyle p_{i}$ $\displaystyle=P_{\mathcal{M}}[I_{i}=0]$ (34)
$\displaystyle r_{i}(p_{i},1,t^{*})$
$\displaystyle=\frac{P_{\mathcal{M}}[I_{i}=0\mid
T^{*}=t^{*}]}{P_{\mathcal{M}}[I_{i}=0]}$ (35) $\displaystyle
a_{i}(p_{i},1,t^{*})$ $\displaystyle=P_{\mathcal{M}}[I_{i}=0\mid
T^{*}=t^{*}].$ (36)

[27] focus on the case of $p_{i}=1/n$, and seek to enforce the bound
$a_{i}(1/n,1,t^{*})\leq{\tilde{a}}$ for some constant ${\tilde{a}}$ and all
$t^{*}$, which implies the relative risk bound

$\displaystyle r^{*}(p_{i},q_{i})=\begin{cases}n{\tilde{a}},&\mbox{ if
}p_{i}=\frac{1}{n},q_{i}=1;\\\ \infty,&\mbox{otherwise}.\end{cases}$ (37)

From an analogy to Theorem 2 with the redefined $p_{i}$, it follows that under
these conditions, our method sets

$\displaystyle\varepsilon=\log\left(\frac{1-\frac{1}{n}}{\frac{1}{n{\tilde{a}}}-\frac{1}{n}}\right)=\log\left(\frac{(n-1){\tilde{a}}}{1-{\tilde{a}}}\right).$
(38)

In the motivating example from their paper, the authors set $n=4$ and
${\tilde{a}}=1/3$, giving $r^{*}(1/n,1)=4/3$. This results in
$\varepsilon=\log(3/2)\approx 0.41$ from our method. When the release
mechanism is the addition of Laplace noise, [27]’s method arrives at a similar
form, but with the recommendation scaled by a factor of $\Delta T/\Delta v$.

$\displaystyle\varepsilon$ $\displaystyle=\frac{\Delta T}{\Delta
v}\log\left(\frac{(n-1){\tilde{a}}}{1-{\tilde{a}}}\right),$ (39)
$\displaystyle\Delta T$
$\displaystyle=\max\left\\{|T({\mathbf{Y}}_{1})-T({\mathbf{Y}}_{2})|:{\mathbf{Y}}_{2}\subset{\mathbf{Y}}_{1}\subset{\mathbf{P}},|{\mathbf{Y}}_{1}|=n-1,|{\mathbf{Y}}_{2}|=n-2\right\\}$
(40) $\displaystyle\Delta v$
$\displaystyle=\max\left\\{|T({\mathbf{Y}}_{1})-T({\mathbf{Y}}_{2})|:{\mathbf{Y}}_{1}\subset{\mathbf{P}},{\mathbf{Y}}_{2}\subset{\mathbf{P}},|{\mathbf{Y}}_{1}|=|{\mathbf{Y}}_{2}|=n-1\right\\}.$
(41)

The recommendation of [27]’s method thus depends on both the population and
the particular release function. This results in different $\varepsilon$
values for the same $n$ and ${\tilde{a}}$, as low as $0.34$ and as high as
$1.62$ in the authors’ examples, depending on the statistic of interest and
the values in the data.

###  D.2 “Differential Privacy: A Primer for a Non-Technical Audience"

The example in [43] considers an individual deciding whether or not to
participate in a survey for which results will be released via DP with a
particular $\varepsilon$. Using our notation, let
$Z_{i}=f(Y_{i},I_{i})\in\\{0,1\\}$ be a quantity of interest to the adversary,
who wishes to learn whether $Z_{i}=1$. They have some prior
$q_{i}=P_{\mathcal{M}}[Z_{i}=1]$. Rather than considering the relative or
absolute disclosure risk, the individual is interested in comparing the
adversary’s posterior probability if they participate in the survey,
$a_{1i}(q_{i},t^{*})=P_{\mathcal{M}}[Z_{i}=1\mid I_{i}=1,T^{*}=t^{*}]$, to the
adversary’s posterior probability if they do not participate,
$a_{0i}(q_{i},t^{*})=P_{\mathcal{M}}[Z_{i}=1\mid I_{i}=0,T^{*}=t^{*}]$. The
authors of [43] state that for all $q_{i}$ and all $t^{*}$,

$\displaystyle
a_{1i}(q_{i},t^{*})\leq\frac{a_{0i}(q_{i},t^{*})}{a_{0i}(q_{i},t^{*})+e^{-2\varepsilon}(1-a_{0i}(q_{i},t^{*}))}.$
(42)

This expression is in the same spirit as the results from our framework with
$p_{i}=1$. By Theorem 1, we have

$r_{i}(1,q_{i},t^{*})\leq\frac{1}{q_{i}+e^{-2\varepsilon}(1-q_{i})}\quad\implies\quad
a_{i}(1,q_{i},t^{*})\leq\frac{q_{i}}{q_{i}+e^{-2\varepsilon}(1-q_{i})}.$ (43)

The authors of [43] suggest that the individual considering survey
participation use (42) to bound $a_{1i}$ for various values of $a_{0i}$. The
individual can examine these bounds to make an informed decision about whether
to participate in the survey.

##  Appendix E Proofs

This section provides proofs of results from Section 3 and Appendix B.1.

######  Lemma 1.

Under Assumption 1 and Assumption 2, if the release of $T^{*}=t^{*}$ satisfies
DP, then for any subset ${\mathcal{S}}$ of the domain of $Y_{i}$, we have

$e^{-\varepsilon}\leq\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}\leq
e^{\varepsilon},\qquad
e^{-2\varepsilon}\leq\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\notin{\mathcal{S}},I_{i}=1]}\leq e^{2\varepsilon}.$ (10)

###### Proof.

To begin, we demonstrate that for all $y$ in the support of $Y_{i}$ and
$t^{*}$ in the support of $T^{*}$,

$e^{-\varepsilon}\leq\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}=y,I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}\leq
e^{\varepsilon}.$ (44)

Let $\mathcal{Y}_{-i}$ be the support of ${\mathbf{Y}}_{-i}$ under
${\mathcal{M}}$. Then,

$\displaystyle P_{\mathcal{M}}[$ $\displaystyle T^{*}=t^{*}\mid
Y_{i}=y,I_{i}=1]$
$\displaystyle=\sum_{{\mathbf{y}}_{-i}\in\mathcal{Y}_{-i}}P[T^{*}=t^{*}\mid
Y_{i}=y,{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i},I_{i}=1]\,P_{\mathcal{M}}[{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i}\mid
Y_{i}=y,I_{i}=1]$ (45)
$\displaystyle\leq\sum_{{\mathbf{y}}_{-i}\in\mathcal{Y}_{-i}}e^{\varepsilon}P[T^{*}=t^{*}\mid{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i},I_{i}=0]\,P_{\mathcal{M}}[{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i}\mid
Y_{i}=y,I_{i}=1]$ (46)
$\displaystyle=e^{\varepsilon}\sum_{{\mathbf{y}}_{-i}\in\mathcal{Y}_{-i}}P_{\mathcal{M}}[T^{*}=t^{*}\mid{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i},I_{i}=0]\,P[{\mathbf{Y}}_{-i}={\mathbf{y}}_{-i}\mid
I_{i}=0]$ (47) $\displaystyle=e^{\varepsilon}P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=0].$ (48)

The equality in (45) follows from the law of total probability and Assumption
1. The inequality in (46) follows from DP via (1). The equality in (47)
follows from Assumption 2. The equality in (48) follows from the law of total
probability and Assumption 1. This completes the proof of the right
inequality. The proof of the left inequality is identical with the other
inequality in (1) applied in (46).

Now, we apply Bayes’ Theorem to $P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]$.

$\displaystyle\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}$
$\displaystyle=\frac{\frac{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
T^{*}=t^{*},I_{i}=1]\,P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=1]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
I_{i}=1]}}{P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}$ (49)
$\displaystyle=\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=1]\,P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
T^{*}=t^{*},I_{i}=1]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
I_{i}=1]\,P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}$ (50)

We can then break the second term in the numerator into a summation and apply
Bayes’ Theorem to each term in the sum.

$\displaystyle\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}$
$\displaystyle\hskip 36.135pt=\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=1]\,\sum_{y\in{\mathcal{S}}}P_{\mathcal{M}}[Y_{i}=y\mid
T^{*}=t^{*},I_{i}=1]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
I_{i}=1]\,P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}$ (51) $\displaystyle\hskip
36.135pt=\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=1]\,\sum_{y\in{\mathcal{S}}}\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}=y,I_{i}=1]\,P_{\mathcal{M}}[Y_{i}=y\mid
I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=1]}}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
I_{i}=1]\,P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}$ (52) $\displaystyle\hskip
36.135pt=\frac{\sum_{y\in{\mathcal{S}}}\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}=y,I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=0]}\,P_{\mathcal{M}}[Y_{i}=y\mid
I_{i}=1]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid I_{i}=1]}$ (53)

We apply (44) to achieve the left bound in the first expression of (10).

$\displaystyle\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}$
$\displaystyle\geq\frac{\sum_{y\in{\mathcal{S}}}e^{-\varepsilon}P_{\mathcal{M}}[Y_{i}=y\mid
I_{i}=1]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
I_{i}=1]}=e^{-\varepsilon}.$ (54)

We achieve the right bound in the first expression of (10) in a similar
fashion.

$\displaystyle\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}$
$\displaystyle\leq\frac{\sum_{y\in{\mathcal{S}}}e^{\varepsilon}P_{\mathcal{M}}[Y_{i}=y\mid
I_{i}=1]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
I_{i}=1]}=e^{\varepsilon}.$ (55)

We now turn to the second expression in (10). First note that

$\displaystyle\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\notin{\mathcal{S}},I_{i}=1]}$ $\displaystyle\hskip
36.135pt=\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=0]}\cdot\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=0]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid Y_{i}\notin{\mathcal{S}},I_{i}=1]}.$
(56)

By applying the bounds in the first expression in (10) to ${\mathcal{S}}$ and
${\mathcal{S}}^{C}$,

$\displaystyle e^{-\varepsilon}$
$\displaystyle\leq\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]}\leq
e^{\varepsilon},$ (57) $\displaystyle e^{-\varepsilon}$
$\displaystyle\leq\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\notin{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=0]}\leq e^{\varepsilon}.$ (58)

Thus, to achieve the left inequality in the second expression in (10),

$\displaystyle\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\notin{\mathcal{S}},I_{i}=1]}\geq
e^{-\varepsilon}\cdot\left(e^{\varepsilon}\right)^{-1}=e^{-2\varepsilon}.$
(59)

To achieve the right inequality in the second expression in (10),

$\displaystyle\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\notin{\mathcal{S}},I_{i}=1]}\leq
e^{\varepsilon}\cdot\left(e^{-\varepsilon}\right)^{-1}=e^{2\varepsilon}.$ (60)

∎

######  Theorem 1.

Under Assumption 1 and Assumption 2, if the release of $T^{*}=t^{*}$ satisfies
DP, then

$r_{i}(p_{i},q_{i},t^{*})\leq\frac{1}{q_{i}p_{i}+e^{-2\varepsilon}(1-q_{i})p_{i}+e^{-\varepsilon}(1-p_{i})}.$
(11)

###### Proof.

We begin by applying Bayes’ Theorem to reverse the conditional in the relative
risk.

$\displaystyle r_{i}(p_{i},q_{i},t^{*})$
$\displaystyle=\frac{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1\mid
T^{*}=t^{*}]}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1]}$ (61)
$\displaystyle=\frac{\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]\,P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}]}}{P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}},I_{i}=1]}$
(62) $\displaystyle=\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}]}.$ (63)

We may decompose the denominator via the law of total probability.

$\displaystyle P_{\mathcal{M}}[T^{*}=t^{*}]$
$\displaystyle=P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]\,P_{\mathcal{M}}[Y_{i}\in{\mathcal{S}}\mid
I_{i}=1]\,P_{\mathcal{M}}[I_{i}=1]$
$\displaystyle\qquad+P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\notin{\mathcal{S}},I_{i}=1]\,P_{\mathcal{M}}[Y_{i}\notin{\mathcal{S}}\mid
I_{i}=1]\,P_{\mathcal{M}}[I_{i}=1]$
$\displaystyle\qquad+P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=0]\,P_{\mathcal{M}}[I_{i}=0]$ (64)
$\displaystyle=P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]\,q_{i}p_{i}$
$\displaystyle\qquad+P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\notin{\mathcal{S}},I_{i}=1]\,(1-q_{i})p_{i}$
$\displaystyle\qquad+P_{\mathcal{M}}[T^{*}=t^{*}\mid I_{i}=0]\,(1-p_{i}).$
(65)

Using this expansion in the expression for $r_{i}$ and dividing through by the
numerator yields

$\displaystyle r_{i}(p_{i},q_{i},t^{*})$
$\displaystyle=\frac{1}{q_{i}p_{i}+\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\notin{\mathcal{S}},I_{i}=1]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}\,(1-q_{i})p_{i}+\frac{P_{\mathcal{M}}[T^{*}=t^{*}\mid
I_{i}=0]}{P_{\mathcal{M}}[T^{*}=t^{*}\mid
Y_{i}\in{\mathcal{S}},I_{i}=1]}\,(1-p_{i})}.$ (66)

Using Lemma 1, we then have

$\displaystyle r_{i}(p_{i},q_{i},t^{*})$
$\displaystyle\leq\frac{1}{q_{i}p_{i}+e^{-2\varepsilon}(1-q_{i})p_{i}+e^{-\varepsilon}(1-p_{i})}.$
(67)

∎

######  Theorem 2.

For any individual $i$, fix the prior probabilities, $p_{i}$ and $q_{i}$, and
a desired bound on the relative disclosure risk, $r^{*}(p_{i},q_{i})$. Define
$\varepsilon_{i}(p_{i},q_{i})$ to be the function.

$\varepsilon_{i}(p_{i},q_{i})=\begin{cases}\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}-(1-p_{i})}\right),&\mbox{
if }0<q_{i}<1;\\\
\log\left(\frac{1-p_{i}}{\frac{1}{r^{*}(p_{i},1)}-p_{i}}\right),&\mbox{ if
}q_{i}=1.\end{cases}$ (12)

Under the conditions of Theorem 1, any statistic $T^{*}=t^{*}$ released under
$\varepsilon$-DP with $\varepsilon\leq\varepsilon_{i}(p_{i},q_{i})$ will
satisfy $r_{i}(p_{i},q_{i},t^{*})\leq r^{*}(p_{i},q_{i})$.

###### Proof.

We begin with the simpler case where $q_{i}=1$. By Theorem 1,

$\displaystyle r_{i}(p_{i},1,t^{*})$
$\displaystyle\leq\frac{1}{p_{i}+e^{-\varepsilon}(1-p_{i})}.$ (68)

Since $\varepsilon\leq\log\left((1-p_{i})/(1/r^{*}(p_{i},1)-p_{i})\right)$, it
follows that $e^{-\varepsilon}\geq(1/r^{*}(p_{i},1)-p_{i})/(1-p_{i})$. Thus,
as desired,

$\displaystyle
r_{i}(p_{i},1,t^{*})\leq\frac{1}{p_{i}+\frac{\frac{1}{r^{*}(p_{i},1)}-p_{i}}{1-p_{i}}\,(1-p_{i})}=\frac{1}{p_{i}+\left(\frac{1}{r^{*}(p_{i},1)}-p_{i}\right)}=r^{*}(p_{i},1).$
(69)

Now consider the case where $0<q_{i}<1$. By Theorem 1,

$\displaystyle r_{i}(p_{i},q_{i},t^{*})$
$\displaystyle\leq\frac{1}{q_{i}p_{i}+e^{-2\varepsilon}(1-q_{i})p_{i}+e^{-\varepsilon}(1-p_{i})}.$
(70)

Since

$\displaystyle\varepsilon\leq\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}-(1-p_{i})}\right),$
(71)

it follows that

$\displaystyle
e^{-\varepsilon}\geq\frac{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}-(1-p_{i})}{2p_{i}(1-q_{i})}.$
(72)

Taking the square gives

$\displaystyle e^{-2\varepsilon}$
$\displaystyle\geq\frac{4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)+2(1-p_{i})^{2}}{4p_{i}^{2}(1-q_{i})^{2}}$
$\displaystyle\qquad-\frac{2(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}}{4p_{i}^{2}(1-q_{i})^{2}}$
(73)
$\displaystyle=\frac{\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}}{p_{i}(1-q_{i})}+\frac{(1-p_{i})^{2}-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}}{2p_{i}^{2}(1-q_{i})^{2}}.$
(74)

Thus,

$\displaystyle q_{i}p_{i}+$ $\displaystyle
e^{-2\varepsilon}(1-q_{i})p_{i}+e^{-\varepsilon}(1-p_{i})$ $\displaystyle\geq
q_{i}p_{i}+\frac{\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}}{p_{i}(1-q_{i})}\cdot(1-q_{i})p_{i}$
$\displaystyle\qquad+\frac{(1-p_{i})^{2}-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}}{2p_{i}^{2}(1-q_{i})^{2}}\cdot(1-q_{i})p_{i}$
$\displaystyle\qquad+\frac{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}-(1-p_{i})}{2p_{i}(1-q_{i})}\cdot(1-p_{i})$
(75)
$\displaystyle=q_{i}p_{i}+\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)$
$\displaystyle\qquad+\left((1-p_{i})-\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}\right)\frac{1-p_{i}}{2p_{i}(1-q_{i})}$
$\displaystyle\qquad-\left((1-p_{i})-\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}\right)\frac{1-p_{i}}{2p_{i}(1-q_{i})}$
(76) $\displaystyle=\frac{1}{r^{*}(p_{i},q_{i})}.$ (77)

It is then immediate that

$\displaystyle r_{i}(p_{i},q_{i},t^{*})$
$\displaystyle\leq\frac{1}{q_{i}p_{i}+e^{-2\varepsilon}(1-q_{i})p_{i}+e^{-\varepsilon}(1-p_{i})}\leq\frac{1}{\frac{1}{r^{*}(p_{i},q_{i})}}=r^{*}(p_{i},q_{i}).$
(78)

∎

######  Corollary 1.

Under the conditions of Theorem 1, for all $p_{i},q_{i}\in(0,1]$ and all
$t^{*}$,

$\displaystyle r_{i}(p_{i},q_{i},t^{*})\leq e^{2\varepsilon}.$ (79)

###### Proof.

First note that since, $0\leq e^{-\varepsilon}\leq 1$, it follows that
$e^{-2\varepsilon}\leq e^{-\varepsilon}$. Then, applying the result of Theorem
1,

$\displaystyle
r_{i}(p_{i},q_{i},t^{*})\leq\frac{1}{q_{i}p_{i}+e^{-2\varepsilon}(1-q_{i})p_{i}+e^{-\varepsilon}(1-p_{i})}\leq\frac{1}{q_{i}p_{i}+e^{-2\varepsilon}(1-q_{i})p_{i}+e^{-2\varepsilon}(1-p_{i})}$
(80)

Combining terms and using the fact that $q_{i}p_{i}\geq 0$ gives

$\displaystyle
r_{i}(p_{i},q_{i},t^{*})\leq\frac{1}{q_{i}p_{i}+e^{-2\varepsilon}(1-q_{i}p_{i})}\leq\frac{1}{e^{-2\varepsilon}+q_{i}p_{i}(1-e^{-2\varepsilon})}\leq\frac{1}{e^{-2\varepsilon}+0}=e^{2\varepsilon}.$
(81)

∎

######  Corollary 2.

Under the conditions of Theorem 2, if $p_{i}=1$ and $0<q_{i}<1$, then any
statistic $T^{*}=t^{*}$ released under $\varepsilon$-DP with

$\varepsilon\leq\frac{1}{2}\log\left(\frac{1-q_{i}}{\frac{1}{r^{*}(1,q_{i})}-q_{i}}\right),$
(82)

will satisfy $r_{i}(1,q_{i},t^{*})\leq r^{*}(1,q_{i})$.

###### Proof.

Plugging $p_{i}=1$ into the expression from Theorem 2 yields

$\displaystyle\varepsilon$
$\displaystyle\leq\log\left(\frac{2(1-q_{i})}{\sqrt{0+4(1-q_{i})\left(\frac{1}{r^{*}(1,q_{i})}-q_{i}\right)}-0}\right)$
(83)
$\displaystyle=\log\left(\sqrt{\frac{1-q_{i}}{\frac{1}{r^{*}(1,q_{i})}-q_{i}}}\right)$
(84)
$\displaystyle=\frac{1}{2}\log\left(\frac{1-q_{i}}{\frac{1}{r^{*}(1,q_{i})}-q_{i}}\right).$
(85)

∎

######  Lemma 2.

Fix $p_{i},q_{i}\in(0,1)$ and let
$r^{*}(p_{i},q_{i})={\tilde{a}}/(p_{i}q_{i})$. Then the function

$\varepsilon(p_{i},q_{i})=\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}-(1-p_{i})}\right)$
(86)

has partial derivatives such that

  1. 1.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial p_{i}}<0$ for all
$0<p_{i}<1$ and $0<q_{i}<1$

  2. 2.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial q_{i}}<0$ for all
$0<p_{i}<1$ and $0<q_{i}<1$.

###### Proof.

To begin, we re-express the function of interest in the form

$\displaystyle\varepsilon(p_{i},q_{i})$
$\displaystyle=\log\left(2p_{i}(1-q_{i})\right)-\log\left(\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{p_{i}q_{i}}{{\tilde{a}}}-p_{i}q_{i}\right)}-(1-p_{i})\right)$
(87)
$\displaystyle=\log\left(2p_{i}(1-q_{i})\right)-\log\left(\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})\right).$
(88)

We first examine $\partial\varepsilon(p_{i},q_{i})/\partial p_{i}$. Taking the
partial derivative with respect to $q_{i}$ gives

$\displaystyle\frac{\partial\varepsilon(p_{i},q_{i})}{\partial
p_{i}}=\frac{1}{p_{i}}-\frac{\frac{-2(1-p_{i})+8p_{i}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}{2\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}+1}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})}$
(89) $\displaystyle\hskip
18.06749pt=\frac{1}{p_{i}}+\frac{\frac{(1-p_{i})-4p_{i}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)-\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})}$
(90) $\displaystyle\hskip
18.06749pt=\frac{\frac{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)+p_{i}(1-p_{i})-4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)-[(1-p_{i})-p_{i}]\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}}{p_{i}\left[\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})\right]}$
(91) $\displaystyle\hskip
18.06749pt=\frac{\frac{[(1-p_{i})+p_{i}](1-p_{i})-\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}}{p_{i}\left[\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})\right]}$
(92) $\displaystyle\hskip
18.06749pt=\frac{\frac{-\left[\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})\right]}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}}{p_{i}\left[\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})\right]}$
(93) $\displaystyle\hskip
18.06749pt=-\frac{1}{p_{i}\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}.$
(94)

Certainly, the denominator of (94) is positive. Thus,
$\partial\varepsilon(p_{i},q_{i})/\partial p_{i}<0$, as desired.

We now examine $\partial\varepsilon(p_{i},q_{i})/\partial q_{i}$. Taking the
partial derivative with respect to $q_{i}$ gives

$\displaystyle\frac{\partial\varepsilon(p_{i},q_{i})}{\partial
q_{i}}=-\frac{1}{1-q_{i}}-\frac{\frac{4p_{i}^{2}\left(\frac{1}{{\tilde{a}}}-1\right)\frac{\partial}{\partial
q_{i}}\left[q_{i}(1-q_{i})\right]}{2\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})}$
(95) $\displaystyle\hskip
18.06749pt=-\frac{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})+\frac{2p_{i}^{2}\left(\frac{1}{{\tilde{a}}}-1\right)(1-q_{i})\frac{\partial}{\partial
q_{i}}\left[q_{i}(1-q_{i})\right]}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}}{(1-q_{i})\left[\sqrt{(1-p_{i})^{2}+4^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})\right]}$
(96) $\displaystyle\hskip
18.06749pt=-\frac{\frac{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}+2p_{i}^{2}\left(\frac{1}{{\tilde{a}}}-1\right)(1-q_{i})\frac{\partial}{\partial
q_{i}}\left[q_{i}(1-q_{i})\right]}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}}}{(1-q_{i})\left[\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})\right]}.$
(97)

Consider the three parts of (97). Since ${\tilde{a}}<1$, we have that in the
denominator of the numerator,
$\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}>0$.
The denominator is also positive, since $(1-q_{i})>0$ and

$\left[\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}-(1-p_{i})\right]>\left[\sqrt{(1-p_{i})^{2}}-(1-p_{i})\right]=0.$
(98)

This leaves the numerator of the numerator of (97). Let us denote this
expression as $g(q_{i})$. If $g(q_{i})>0$, then it follows that
$\partial\varepsilon(p_{i},q_{i})/\partial q_{i}<0$. To show this, we begin by
simplifying the expression for $g(q_{i})$:

$\displaystyle g(q_{i})$
$\displaystyle=(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}^{2}q_{i}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}$
$\displaystyle\qquad+2p_{i}^{2}\left(\frac{1}{{\tilde{a}}}-1\right)(1-q_{i})\frac{\partial}{\partial
q_{i}}\left[q_{i}(1-q_{i})\right]$ (99)
$\displaystyle=(1-p_{i})^{2}+2p_{i}^{2}(1-q_{i})(2q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}^{2}(1-q_{i})q_{i}\left(\frac{1}{{\tilde{a}}}-1\right)}$
$\displaystyle\qquad+2p_{i}^{2}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)(1-2q_{i})$
(100)
$\displaystyle=(1-p_{i})^{2}-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}^{2}(1-q_{i})q_{i}\left(\frac{1}{{\tilde{a}}}-1\right)}+2p_{i}^{2}(1-q_{i})\left(\frac{1}{{\tilde{a}}}-1\right).$
(101)

Taking the derivative of $g$, we find that

$\displaystyle\frac{\partial g(q_{i})}{\partial q_{i}}$
$\displaystyle=-(1-p_{i})\,\frac{4p_{i}^{2}(1-2q_{i})\left(\frac{1}{{\tilde{a}}}-1\right)}{2\sqrt{(1-p_{i})^{2}+4p_{i}^{2}(1-q_{i})q_{i}\left(\frac{1}{{\tilde{a}}}-1\right)}}-2p_{i}^{2}\left(\frac{1}{{\tilde{a}}}-1\right)$
(102)
$\displaystyle=-2p_{i}^{2}\left(\frac{1}{{\tilde{a}}}-1\right)\left[(1-p_{i})\,\frac{1-2q_{i}}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}(1-q_{i})q_{i}\left(\frac{1}{{\tilde{a}}}-1\right)}}+1\right].$
(103)

For $0<q_{i}\leq 1/2$, $1-2q_{i}\geq 0$ and so $\partial g(q_{i})/\partial
q_{i}<0$. For $1/2<q_{i}<1$, since $2q_{i}-1<1$ and
$\sqrt{(1-p_{i})^{2}+4p_{i}^{2}(1-q_{i})q_{i}\left(1/{\tilde{a}}-1\right)}>1-p_{i}$,

$\displaystyle\frac{\partial g(q_{i})}{\partial q_{i}}$
$\displaystyle=-2p_{i}^{2}\left(\frac{1}{{\tilde{a}}}-1\right)\left[1-(1-p_{i})\,\frac{2q_{i}-1}{\sqrt{(1-p_{i})^{2}+4p_{i}^{2}(1-q_{i})q_{i}\left(\frac{1}{{\tilde{a}}}-1\right)}}\right]$
(104)
$\displaystyle<-2p_{i}^{2}\left(\frac{1}{{\tilde{a}}}-1\right)\left[1-(1-p_{i})\,\frac{1}{1-p_{i}}\right]$
(105) $\displaystyle<0.$ (106)

Thus, $g(q_{i})$ strictly decreasing as a function of $q_{i}$ on $0<q_{i}<1$.
Since

$g\left(1\right)=(1-p_{i})^{2}-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}^{2}(1-1)1\left(\frac{1}{{\tilde{a}}}-1\right)}+2p_{i}^{2}(1-1)\left(\frac{1}{{\tilde{a}}}-1\right)=0,$
(107)

it follows that $g(q_{i})>0$ for $0<q_{i}<1$ and so
$\partial\varepsilon(p_{i},q_{i})/\partial q_{i}<0$ in this range. ∎

######  Lemma 3.

Fix $p_{i},q_{i}\in(0,1)$ and let
$r^{*}(p_{i},q_{i})={\tilde{r}}<1/(p_{i}q_{i})$. Then the function

$\varepsilon(p_{i},q_{i})=\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{r^{*}(p_{i},q_{i})}-p_{i}q_{i}\right)}-(1-p_{i})}\right)$
(108)

has partial derivatives such that

  1. 1.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial p_{i}}<0$ if
$0<q_{i}<\frac{1}{{\tilde{r}}+1}$ and $0<p_{i}<1$

  2. 2.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial p_{i}}=0$ if
$q_{i}=\frac{1}{{\tilde{r}}+1}$ and $0<p_{i}<1$

  3. 3.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial p_{i}}>0$ if
$\frac{1}{{\tilde{r}}+1}<q_{i}<1$ and $0<p_{i}<\frac{1}{q_{i}{\tilde{r}}}$

  4. 4.

$\frac{\partial\varepsilon(p_{i},q_{i})}{\partial q_{i}}>0$ if $0<p_{i}<1$ and
$0<q_{i}<\frac{1}{p_{i}{\tilde{r}}}$.

###### Proof.

To begin, we re-express the function of interest in the form

$\varepsilon(p_{i},q_{i})=\log\left(2p_{i}(1-q_{i})\right)-\log\left(\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})\right).$
(109)

We now examine $\partial\varepsilon(p_{i},q_{i})/\partial p_{i}$. Taking the
partial derivative of with respect to $p_{i}$ and simplifying gives

$\displaystyle\frac{\partial\varepsilon(p_{i},q_{i})}{\partial
p_{i}}=\frac{1}{p_{i}}-\frac{\frac{\frac{\partial}{\partial
p_{i}}\left[(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)\right]}{2\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}+1}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})}$
(110) $\displaystyle\hskip
10.84006pt=\frac{1}{p_{i}}-\frac{\frac{-2(1-p_{i})+4(1-q_{i})(\frac{1}{{\tilde{r}}}-p_{i}q_{i})-4p_{i}(1-q_{i})q_{i}+2\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}{2\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})}$
(111) $\displaystyle\hskip
10.84006pt=\frac{\frac{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}{{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}}}{p_{i}\left[\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})\right]}$
$\displaystyle\hskip
10.84006pt\qquad+\frac{\frac{p_{i}(1-p_{i})-2p_{i}(1-q_{i})(\frac{1}{{\tilde{r}}}-p_{i}q_{i})+2p_{i}^{2}(1-q_{i})q_{i}-p_{i}\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}}{p_{i}\left[\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})\right]}$
(112) $\displaystyle\hskip
10.84006pt=\frac{\frac{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)+p_{i}(1-p_{i})-2p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)+2p_{i}^{2}(1-q_{i})q_{i}-\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}{{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}}}{p_{i}\left[\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})\right]}$
(113) $\displaystyle\hskip
10.84006pt=\frac{2p_{i}(1-q_{i})\frac{1}{{\tilde{r}}}+(1-p_{i})-\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}{p_{i}\left[\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})\right]\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}.$
(114)

We can rearrange the expression in (114) to the following form.

$\displaystyle\frac{\partial\varepsilon(p_{i},q_{i})}{\partial
p_{i}}=\frac{\frac{2p_{i}(1-q_{i})\frac{1}{{\tilde{r}}}}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})}-1}{p_{i}\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}.$
(115)

The denominator of (115) is certainly always positive, so the sign of
$\partial\varepsilon(p_{i},q_{i})/\partial p_{i}$ is determined by the sign of
the numerator. To determine the sign, we will use the following equality.

$\displaystyle 2p_{i}$ $\displaystyle(1-q_{i})\frac{1}{{\tilde{r}}}$
$\displaystyle=\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)+4p_{i}^{2}(1-q_{i})\frac{{\tilde{r}}^{2}-1}{{\tilde{r}}^{2}}\left(q_{i}-\frac{1}{{\tilde{r}}+1}\right)}-(1-p_{i}).$
(116)

To demonstrate that (116) holds, note the following.

$\displaystyle\bigg{(}2p_{i}(1-q_{i})\frac{1}{{\tilde{r}}}+$
$\displaystyle(1-p_{i})\bigg{)}^{2}=4p_{i}^{2}(1-q_{i})^{2}\frac{1}{{\tilde{r}}^{2}}+4p_{i}(1-p_{i})(1-q_{i})\frac{1}{{\tilde{r}}}+(1-p_{i})^{2}$
(117)
$\displaystyle=4p_{i}^{2}(1-q_{i})^{2}\frac{1}{{\tilde{r}}^{2}}+4p_{i}(1-p_{i})(1-q_{i})\frac{1}{{\tilde{r}}}-4p_{i}^{2}(1-q_{i})\frac{{\tilde{r}}^{2}-1}{{\tilde{r}}^{2}}\left(q_{i}-\frac{1}{{\tilde{r}}+1}\right)$
$\displaystyle\qquad\qquad+4p_{i}^{2}(1-q_{i})\frac{{\tilde{r}}^{2}-1}{{\tilde{r}}^{2}}\left(q_{i}-\frac{1}{{\tilde{r}}+1}\right)+(1-p_{i})^{2}$
(118)
$\displaystyle=4p_{i}(1-q_{i})\left[p_{i}(1-q_{i})\frac{1}{{\tilde{r}}^{2}}+(1-p_{i})\frac{1}{{\tilde{r}}}-p_{i}\frac{{\tilde{r}}^{2}-1}{{\tilde{r}}^{2}}\left(q_{i}-\frac{1}{{\tilde{r}}+1}\right)\right]$
$\displaystyle\qquad\qquad+4p_{i}^{2}(1-q_{i})\frac{{\tilde{r}}^{2}-1}{{\tilde{r}}^{2}}\left(q_{i}-\frac{1}{{\tilde{r}}+1}\right)+(1-p_{i})^{2}$
(119)
$\displaystyle=4p_{i}(1-q_{i})\left[\frac{1}{{\tilde{r}}}+p_{i}\left(\frac{1}{{\tilde{r}}^{2}}-\frac{1}{{\tilde{r}}}+\frac{{\tilde{r}}-1}{{\tilde{r}}^{2}}\right)-p_{i}q_{i}\left(\frac{1}{{\tilde{r}}^{2}}+\frac{{\tilde{r}}^{2}-1}{{\tilde{r}}^{2}}\right)\right]$
$\displaystyle\qquad\qquad+4p_{i}^{2}(1-q_{i})\frac{{\tilde{r}}^{2}-1}{{\tilde{r}}^{2}}\left(q_{i}-\frac{1}{{\tilde{r}}+1}\right)+(1-p_{i})^{2}$
(120)
$\displaystyle=4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)+4p_{i}^{2}(1-q_{i})\frac{{\tilde{r}}^{2}-1}{{\tilde{r}}^{2}}\left(q_{i}-\frac{1}{{\tilde{r}}+1}\right)+(1-p_{i})^{2}.$
(121)

Rearranging (121) gives (116).

Now note that, from (116), if $q_{i}=1/({\tilde{r}}+1)$, then

$2p_{i}(1-q_{i})\frac{1}{{\tilde{r}}}=\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i}).$
(122)

It follows that the ratio in the numerator of (115) equals $1$ and thus
$\partial\varepsilon(p_{i},q_{i})/\partial p_{i}=0$. If
$0<q_{i}<\frac{1}{{\tilde{r}}+1}$, then the term
$4p_{i}^{2}(1-q_{i})({\tilde{r}}^{2}-1)/{\tilde{r}}^{2}(q_{i}-1/({\tilde{r}}+1))<0$
and so

$2p_{i}(1-q_{i})\frac{1}{{\tilde{r}}}<\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i}).$
(123)

It follows that the ratio in the numerator of (115) is less than $1$ and thus
$\partial\varepsilon(p_{i},q_{i})/\partial p_{i}<0$. If
$\frac{1}{{\tilde{r}}+1}<q_{i}<1$, then the term
$4p_{i}^{2}(1-q_{i})({\tilde{r}}^{2}-1)/{\tilde{r}}^{2}(q_{i}-1/({\tilde{r}}+1))>0$
and so

$2p_{i}(1-q_{i})\frac{1}{{\tilde{r}}}>\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i}).$
(124)

It follows that the ratio in the numerator of (115) is greater than $1$ and
thus $\partial\varepsilon(p_{i},q_{i})/\partial p_{i}>0$.

We now examine $\partial\varepsilon(p_{i},q_{i})/\partial q_{i}$. Taking the
partial derivative of with respect to $q_{i}$ gives

$\displaystyle\frac{\partial\varepsilon(p_{i},q_{i})}{\partial
q_{i}}=-\frac{1}{1-q_{i}}-\frac{\frac{4p_{i}\frac{\partial}{\partial
q_{i}}\left[(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)\right]}{2\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})}$
(125) $\displaystyle\hskip
18.06749pt=-\frac{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})+\frac{2p_{i}(1-q_{i})\frac{\partial}{\partial
q_{i}}\left[(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)\right]}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}}{(1-q_{i})\left[\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})\right]}$
(126) $\displaystyle\hskip
18.06749pt=-\frac{\frac{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}+2p_{i}(1-q_{i})\frac{\partial}{\partial
q_{i}}\left[(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)\right]}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}}{(1-q_{i})\left[\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})\right]}.$
(127)

Consider the three parts of (127). Since ${\tilde{r}}<1/(p_{i}q_{i})$, it
follows that $\left(1/{\tilde{r}}-p_{i}q_{i}\right)>0$. Thus, in the
denominator of the numerator,
$\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(1/{\tilde{r}}-p_{i}q_{i}\right)}>0$.
The denominator is also positive, since $(1-q_{i})>0$ and

$\left[\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})\right]>\left[\sqrt{(1-p_{i})^{2}}-(1-p_{i})\right]=0.$
(128)

This leaves the numerator of the numerator of (127). Let us denote this
expression as $g(q_{i})$. If $g(q_{i})<0$, then it follows that
$\partial\varepsilon(p_{i},q_{i})/\partial q_{i}>0$. To show this, we begin by
simplifying the expression for $g(q_{i})$:

$\displaystyle g(q_{i})$
$\displaystyle=(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}$
$\displaystyle\qquad+2p_{i}(1-q_{i})\frac{\partial}{\partial
q_{i}}\left[(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)\right]$
(129)
$\displaystyle=(1-p_{i})^{2}+2p_{i}(1-q_{i})\left(\frac{2}{{\tilde{r}}}-2p_{i}q_{i}\right)-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}$
$\displaystyle\qquad+2p_{i}(1-q_{i})\left(2p_{i}q_{i}-p_{i}-\frac{1}{{\tilde{r}}}\right)$
(130)
$\displaystyle=(1-p_{i})^{2}-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}+2p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}\right).$
(131)

Taking the derivative of $g$, we find that

$\displaystyle\frac{\partial g(q_{i})}{\partial q_{i}}$
$\displaystyle=-(1-p_{i})\,\frac{4p_{i}\left(2p_{i}q_{i}-p_{i}-\frac{1}{{\tilde{r}}}\right)}{2\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}-2p_{i}\left(\frac{1}{{\tilde{r}}}-p_{i}\right)$
(132)
$\displaystyle=2p_{i}\left[(1-p_{i})\,\frac{2p_{i}(1-q_{i})+\left(\frac{1}{{\tilde{r}}}-p_{i}\right)}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}-\left(\frac{1}{{\tilde{r}}}-p_{i}\right)\right].$
(133)

Note that since ${\tilde{r}}<\frac{1}{p_{i}q_{i}}$, it follows that
$\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)>0$ and
$p_{i}(1-q_{i})>p_{i}-\frac{1}{r}$. Thus,

$\displaystyle\frac{\partial g(q_{i})}{\partial q_{i}}$
$\displaystyle=2p_{i}\left[(1-p_{i})\,\frac{2p_{i}(1-q_{i})-\left(p_{i}-\frac{1}{{\tilde{r}}}\right)}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}+\left(p_{i}-\frac{1}{{\tilde{r}}}\right)\right]$
(134)
$\displaystyle>2p_{i}\left[(1-p_{i})\,\frac{\left(p_{i}-\frac{1}{{\tilde{r}}}\right)}{\sqrt{(1-p_{i})^{2}}}+\left(p_{i}-\frac{1}{{\tilde{r}}}\right)\right]$
(135) $\displaystyle=4p_{i}\left(p_{i}-\frac{1}{{\tilde{r}}}\right)$ (136)
$\displaystyle>0.$ (137)

Thus, $g(q_{i})$ is strictly increasing for ${\tilde{r}}<1/(p_{i}q_{i})$. Note
that in terms of $q_{i}$, this is equivalent to the range
$0<q_{i}<1/(p_{i}{\tilde{r}})$. Since

$\displaystyle g$ $\displaystyle\left(\frac{1}{p_{i}{\tilde{r}}}\right)$
$\displaystyle=(1-p_{i})^{2}-(1-p_{i})\sqrt{(1-p_{i})^{2}+4p_{i}(1-\frac{1}{p_{i}{\tilde{r}}})\left(\frac{1}{{\tilde{r}}}-p_{i}\frac{1}{p_{i}{\tilde{r}}}\right)}+2p_{i}\left(1-\frac{1}{p_{i}{\tilde{r}}}\right)\left(\frac{1}{{\tilde{r}}}-p_{i}\right)$
(138)
$\displaystyle=2p_{i}\left(1-\frac{1}{p_{i}{\tilde{r}}}\right)\left(\frac{1}{{\tilde{r}}}-p_{i}\right)$
(139) $\displaystyle<0,$ (140)

it follows that $g(q_{i})<0$ for $0<q_{i}<1/(p_{i}{\tilde{r}})$. Thus, as
desired, $\partial\varepsilon(p_{i},q_{i})/\partial q_{i}>0$ in this range. ∎

######  Theorem 3.

Under the conditions of Theorem 2, if $r^{*}(p_{i},q_{i})={\tilde{r}}>1$, the
solution to the minimization problem in (13) is

$\varepsilon=\frac{1}{2}\log\left({\tilde{r}}\right).$ (141)

###### Proof.

We define $\varepsilon(p_{i},q_{i})$ as follows.

$\displaystyle\varepsilon(p_{i},q_{i})=\begin{cases}\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})}\right),&\mbox{
if }0<q_{i}<1;\\\
\log\left(\frac{1-p_{i}}{\frac{1}{{\tilde{r}}}-p_{i}}\right),&\mbox{ if
}q_{i}=1.\end{cases}$ (142)

The solution to the minimization problem in (13) corresponds to the minimum of
$\varepsilon(p_{i},q_{i})$ over $(0,1]\times(0,1]$. Lemma 3 implies that
$\partial\varepsilon(p_{i},q_{i})/\partial q_{i}\neq 0$ for any $0<q_{i}<1$.
This means that this function must take its minimum value around its boundary,
i.e., when $p_{i}=1$, $q_{i}=1$, $p_{i}\to 0$, or $q_{i}\to 0$. We examine
each of these in turn.

We begin with the boundary where $p_{i}=1$. By Corollary 2, for $0<q_{i}<1$,

$\displaystyle\varepsilon(1,q_{i})=\frac{1}{2}\log\left(\frac{1-q_{i}}{\frac{1}{{\tilde{r}}}-q_{i}}\right).$
(143)

We take the partial derivative of this function with respect to $q_{i}$.

$\displaystyle\frac{\partial\varepsilon(1,q_{i})}{\partial
q_{i}}=\frac{1}{2}\left[-\frac{1}{1-q_{i}}+\frac{1}{\frac{1}{{\tilde{r}}}-q_{i}}\right].$
(144)

Since $1/{\tilde{r}}<1$, it follows that
$\partial\varepsilon(1,q_{i})/\partial q_{i}>0$ for all $0<q_{i}<1$. Thus, the
minimum occurs as $q_{i}\to 0$ and is

$\displaystyle\lim_{q_{i}\to
0}\varepsilon(1,q_{i})=\frac{1}{2}\log({\tilde{r}}).$ (145)

We next examine with the boundary where $q_{i}=1$. When $0<p_{i}<1$,

$\displaystyle\varepsilon(p_{i},1)=\log\left(\frac{1-p_{i}}{\frac{1}{{\tilde{r}}}-p_{i}}\right).$
(146)

We take the partial derivative of this function with respect to $p_{i}$.

$\displaystyle\frac{\partial\varepsilon(p_{i},1)}{\partial
p_{i}}=-\frac{1}{1-p_{i}}+\frac{1}{\frac{1}{{\tilde{r}}}-p_{i}}.$ (147)

Since $1/{\tilde{r}}<1$, it follows that
$\partial\varepsilon(p_{i},1)/\partial p_{i}>0$ for all $0<p_{i}<1$. Thus, the
minimum occurs as $p_{i}\to 0$ and is

$\displaystyle\lim_{p_{i}\to 0}\varepsilon(p_{i},1)=\log({\tilde{r}}).$ (148)

We next examine the boundary where $p_{i}\to 0$. Since the logarithm is a
continuous function, for all $0<q_{i}<1$,

$\displaystyle\lim_{p_{i}\to 0}\varepsilon(p_{i},q_{i})$
$\displaystyle=\lim_{p_{i}\to
0}\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})}\right)$
(149) $\displaystyle=\log\left(\lim_{p_{i}\to
0}\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})}\right).$
(150)

Using L’Hôpital’s Rule,

$\displaystyle\lim_{p_{i}\to 0}\varepsilon(p_{i},q_{i})$
$\displaystyle=\log\left(\lim_{p_{i}\to
0}\frac{2(1-q_{i})}{\frac{-2(1-p_{i})+4(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)-4p_{i}q_{i}(1-q_{i})}{2\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}}+1}\right)$
(151)
$\displaystyle=\log\left(\frac{2(1-q_{i})}{\frac{-1+2(1-q_{i})\left(\frac{1}{{\tilde{r}}}\right)}{\sqrt{1}}+1}\right)=\log({\tilde{r}}).$
(152)

Finally, we examine the boundary where $q_{i}\to 0$. For all $0<p_{i}\leq 1$

$\displaystyle\lim_{q_{i}\to 0}\varepsilon(p_{i},q_{i})$
$\displaystyle=\lim_{q_{i}\to
0}\log\left(\frac{2p_{i}(1-q_{i})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-q_{i})\left(\frac{1}{{\tilde{r}}}-p_{i}q_{i}\right)}-(1-p_{i})}\right)$
(153)
$\displaystyle=\log\left(\frac{2p_{i}}{\sqrt{(1-p_{i})^{2}+4p_{i}\left(\frac{1}{{\tilde{r}}}\right)}-(1-p_{i})}\right).$
(154)

We take the partial derivative with respect to $p_{i}$. From (115) in the
proof of Lemma 3, we have that

$\displaystyle\frac{\partial}{\partial p_{i}}\left(\lim_{q_{i}\to
0}\varepsilon(p_{i},q_{i})\right)$ $\displaystyle=\frac{\partial}{\partial
p_{i}}\left(\log\left(\frac{2p_{i}}{\sqrt{(1-p_{i})^{2}+4p_{i}\left(\frac{1}{{\tilde{r}}}-p_{i}\right)}-(1-p_{i})}\right)\right)$
(155)
$\displaystyle=\frac{\frac{2p_{i}\frac{1}{{\tilde{r}}}}{\sqrt{(1-p_{i})^{2}+4p_{i}\left(\frac{1}{{\tilde{r}}}\right)}-(1-p_{i})}-1}{p_{i}\sqrt{(1-p_{i})^{2}+4p_{i}\left(\frac{1}{{\tilde{r}}}\right)}}.$
(156)

By (116) with $q_{i}=0$, the ratio in the numerator of (156) is less than $1$
and so $\partial/\partial p_{i}\left(\lim_{q_{i}\to
0}\varepsilon(p_{i},q_{i})\right)$ is negative for all $0<p_{i}\leq 1$. Thus,
the minimum occurs at $p_{i}=1$ and is as in (145). The global minimum of
$\varepsilon(p_{i},q_{i})$ is thus $1/2\log({\tilde{r}})$. ∎

######  Theorem 4.

Under the conditions of Theorem 2, let ${\tilde{a}}<1$, ${\tilde{p}}\leq 1$,
and ${\tilde{r}}>1$, and $0<q_{i}\leq 1$. If the function $r^{*}$ is such that
$r^{*}({\tilde{p}},q_{i})=\max\\{{\tilde{a}}/({\tilde{p}}q_{i}),{\tilde{r}}\\}$
and $r^{*}(p_{i},q_{i})=\infty$ if $p_{i}\neq{\tilde{p}}$, then the solution
to the minimization problem in (13) is

$\varepsilon=\begin{cases}\log\left(\frac{{\tilde{a}}(1-{\tilde{p}})}{{\tilde{p}}(1-{\tilde{a}})}\right),&\mbox{
if }0<{\tilde{p}}\leq\frac{{\tilde{a}}}{{\tilde{r}}};\\\
\log\left(\frac{2({\tilde{p}}{\tilde{r}}-{\tilde{a}})}{\sqrt{{\tilde{r}}^{2}(1-{\tilde{p}})^{2}+4({\tilde{p}}{\tilde{r}}-{\tilde{a}})\left(1-{\tilde{a}}\right)}-{\tilde{r}}(1-{\tilde{p}})}\right),&\mbox{
if }\frac{{\tilde{a}}}{{\tilde{r}}}<{\tilde{p}}\leq 1.\end{cases}$ (157)

###### Proof.

We define $\varepsilon(q_{i})$ as follows.

$\displaystyle\varepsilon(q_{i})=\begin{cases}\log\left(\frac{2{\tilde{p}}(1-q_{i})}{\sqrt{(1-{\tilde{p}})^{2}+4{\tilde{p}}(1-q_{i})\left(\frac{1}{r^{*}({\tilde{p}},q_{i})}-{\tilde{p}}q_{i}\right)}-(1-{\tilde{p}})}\right),&\mbox{
if }0<q_{i}<1;\\\
\log\left(\frac{1-{\tilde{p}}}{\frac{1}{r^{*}({\tilde{p}},q_{i})}-{\tilde{p}}}\right),&\mbox{
if }q_{i}=1.\end{cases}$ (158)

The solution to the minimization problem in (13) corresponds to the minimum of
$\varepsilon(q_{i})$ over $(0,1]$.

We begin with the case where $0<{\tilde{p}}\leq{\tilde{a}}/{\tilde{r}}$. In
this setting, we have that
${\tilde{r}}\leq{\tilde{a}}/{\tilde{p}}\leq{\tilde{a}}/({\tilde{p}}q_{i})$, so
$r^{*}({\tilde{p}},q_{i})={\tilde{a}}/({\tilde{p}}q_{i})$ for all $q_{i}$. By
Lemma 2, $\varepsilon(q_{i})$ is a decreasing function of $q_{i}$, so the
minimum occurs at $q_{i}=1$ and is

$\displaystyle\varepsilon(1)=\log\left(\frac{1-{\tilde{p}}}{\frac{1}{r^{*}({\tilde{p}},1)}-{\tilde{p}}}\right)=\log\left(\frac{1-{\tilde{p}}}{\frac{{\tilde{p}}}{{\tilde{a}}}-{\tilde{p}}}\right)=\log\left(\frac{{\tilde{a}}(1-{\tilde{p}})}{{\tilde{p}}(1-{\tilde{a}})}\right).$
(159)

We now consider the case where ${\tilde{a}}/{\tilde{r}}<{\tilde{p}}\leq 1$.
Note that ${\tilde{r}}\geq{\tilde{a}}/({\tilde{p}}q_{i})$ whenever
$q_{i}\geq{\tilde{a}}/({\tilde{p}}{\tilde{r}})$. Since in this setting
${\tilde{a}}/({\tilde{p}}{\tilde{r}})<1$, the risk bound can be written in
piece-wise form

$r^{*}({\tilde{p}},q_{i})=\begin{cases}\frac{{\tilde{a}}}{{\tilde{p}}q_{i}},&\mbox{
if }0<q_{i}<\frac{{\tilde{a}}}{{\tilde{p}}{\tilde{r}}};\\\ {\tilde{r}},&\mbox{
if }\frac{{\tilde{a}}}{{\tilde{p}}{\tilde{r}}}\leq q_{i}<1.\end{cases}$ (160)

Note that if $q_{i}\geq 1/({\tilde{r}}{\tilde{p}})$, then ${\tilde{r}}\geq
1/({\tilde{p}}q_{i})$. Thus, $r^{*}({\tilde{p}},q_{i})\geq{\tilde{r}}\geq
1/({\tilde{p}}q_{i})$ and so

$\displaystyle\sqrt{(1-{\tilde{p}})^{2}+4{\tilde{p}}(1-q_{i})\left(\frac{1}{r^{*}({\tilde{p}},q_{i})}-{\tilde{p}}q_{i}\right)}-(1-{\tilde{p}})$
$\displaystyle\hskip
36.135pt\leq\sqrt{(1-{\tilde{p}})^{2}+4{\tilde{p}}(1-q_{i})\left({\tilde{p}}q_{i}-{\tilde{p}}q_{i}\right)}-(1-{\tilde{p}})$
(161) $\displaystyle\hskip
36.135pt=\sqrt{(1-{\tilde{p}})^{2}}-(1-{\tilde{p}})$ (162)
$\displaystyle\hskip 36.135pt=0.$ (163)

Thus, $\varepsilon(q_{i})=\infty$ for any $q_{i}\geq
1/({\tilde{r}}{\tilde{p}})$. We may thus restrict our attention to
$q_{i}<\min\\{1,1/({\tilde{r}}{\tilde{p}})\\}$.

Since $r^{*}({\tilde{p}},q_{i})$ is a continuous function of $q_{i}$ and
$\varepsilon(q_{i})$ is a continuous function of $r^{*}({\tilde{p}},q_{i})$,
it follows that $\varepsilon(q_{i})$ is a continuous function of $q_{i}$. By
Lemma 2, $\varepsilon(q_{i})$ is a decreasing function of $q_{i}$ for
$0<q_{i}<{\tilde{a}}/({\tilde{p}}{\tilde{r}})$ and by Lemma 3,
$\varepsilon(q_{i})$ is an increasing function of $q_{i}$ for
${\tilde{a}}/({\tilde{p}}{\tilde{r}})<q_{i}<\min\\{1,1/({\tilde{r}}{\tilde{p}})\\}$.
Thus, the minimum must occur at $q_{i}={\tilde{a}}/({\tilde{p}}{\tilde{r}})$
and is

$\displaystyle\varepsilon\left(\frac{{\tilde{a}}}{{\tilde{p}}{\tilde{r}}}\right)$
$\displaystyle=\log\left(\frac{2{\tilde{p}}\left(1-\frac{{\tilde{a}}}{{\tilde{p}}{\tilde{r}}}\right)}{\sqrt{(1-{\tilde{p}})^{2}+4{\tilde{p}}\left(1-\frac{{\tilde{a}}}{{\tilde{p}}{\tilde{r}}}\right)\left(\frac{1}{{\tilde{r}}}-{\tilde{p}}\frac{{\tilde{a}}}{{\tilde{p}}{\tilde{r}}}\right)}-(1-{\tilde{p}})}\right)$
(164)
$\displaystyle=\log\left(\frac{2\left({\tilde{p}}{\tilde{r}}-{\tilde{a}}\right)}{\sqrt{{\tilde{r}}^{2}(1-{\tilde{p}})^{2}+4\left({\tilde{p}}{\tilde{r}}-{\tilde{a}}\right)\left(1-{\tilde{a}}\right)}-{\tilde{r}}(1-{\tilde{p}})}\right).$
(165)

∎

######  Theorem 5.

Under the conditions of Theorem 2, let ${\tilde{a}}<1$, ${\tilde{q}}\leq 1$,
and ${\tilde{r}}>1$, and $0<p_{i}<1$. If the function $r^{*}$ is such that
$r^{*}(p_{i},{\tilde{q}})=\max\\{{\tilde{a}}/(p_{i}{\tilde{q}}),{\tilde{r}}\\}$
and $r^{*}(p_{i},q_{i})=\infty$ for $q_{i}\neq{\tilde{q}}$, then the solution
to the minimization problem in (13) is

$\varepsilon=\begin{cases}\frac{1}{2}\log\left(\frac{{\tilde{a}}(1-{\tilde{q}})}{{\tilde{q}}(1-{\tilde{a}})}\right),&\mbox{if
}0<{\tilde{q}}\leq\frac{{\tilde{a}}}{{\tilde{r}}};\\\
\frac{1}{2}\log\left(\frac{1-{\tilde{q}}}{\frac{1}{{\tilde{r}}}-{\tilde{q}}}\right),&\mbox{if
}0<{\tilde{q}}\leq\frac{1}{{\tilde{r}}+1}\mbox{ and
}\frac{{\tilde{a}}}{{\tilde{r}}}<{\tilde{q}}<1;\\\
\log\left(\frac{2{\tilde{a}}(1-{\tilde{q}})}{\sqrt{({\tilde{r}}{\tilde{q}}-{\tilde{a}})^{2}+4{\tilde{a}}{\tilde{q}}(1-{\tilde{q}})\left(1-{\tilde{a}}\right)}-({\tilde{r}}{\tilde{q}}-{\tilde{a}})}\right),&\mbox{if
}\frac{1}{{\tilde{r}}+1}<{\tilde{q}}<1\mbox{ and
}\frac{{\tilde{a}}}{{\tilde{r}}}<{\tilde{q}}<1;\\\
\log\left(\frac{{\tilde{r}}-{\tilde{a}}}{1-{\tilde{a}}}\right),&\mbox{if
}{\tilde{q}}=1.\end{cases}$ (166)

###### Proof.

We define $\varepsilon(p_{i})$ as follows.

$\displaystyle\varepsilon(p_{i})=\begin{cases}\log\left(\frac{2p_{i}(1-{\tilde{q}})}{\sqrt{(1-p_{i})^{2}+4p_{i}(1-{\tilde{q}})\left(\frac{1}{r^{*}(p_{i},{\tilde{q}})}-p_{i}{\tilde{q}}\right)}-(1-p_{i})}\right),&\mbox{
if }0<{\tilde{q}}<1;\\\
\log\left(\frac{1-p_{i}}{\frac{1}{r^{*}(p_{i},{\tilde{q}})}-p_{i}}\right),&\mbox{
if }{\tilde{q}}=1.\end{cases}$ (167)

The solution to the minimization problem in (13) corresponds to the minimum of
$\varepsilon(p_{i})$ over $(0,1]$.

We begin with the case where $0<{\tilde{q}}\leq{\tilde{a}}/{\tilde{r}}$. In
this setting, we have that
${\tilde{r}}\leq{\tilde{a}}/{\tilde{q}}\leq{\tilde{a}}/(p_{i}{\tilde{q}})$ so
$r^{*}(p_{i},{\tilde{q}})={\tilde{a}}/(p_{i}{\tilde{q}})$ for all $p_{i}$. By
Lemma 2, $\varepsilon(p_{i})$ is a decreasing function of $p_{i}$, so the
minimum occurs at $p_{i}=1$ and is, by Corollary 2,

$\displaystyle\varepsilon(1)=\frac{1}{2}\log\left(\frac{1-{\tilde{q}}}{\frac{{\tilde{q}}}{{\tilde{a}}}-{\tilde{q}}}\right)=\frac{1}{2}\log\left(\frac{{\tilde{a}}(1-{\tilde{q}})}{{\tilde{q}}(1-{\tilde{a}})}\right).$
(168)

We now consider the case where ${\tilde{a}}/{\tilde{r}}<{\tilde{q}}\leq 1$.
Note that ${\tilde{r}}\geq{\tilde{a}}/(p_{i}{\tilde{q}})$ whenever
$p_{i}\geq{\tilde{a}}/({\tilde{q}}{\tilde{r}})$. Since in this setting
${\tilde{a}}/({\tilde{q}}{\tilde{r}})<1$, the risk bound can be written in
piece-wise form

$r^{*}({\tilde{p}},q_{i})=\begin{cases}\frac{{\tilde{a}}}{p_{i}{\tilde{q}}},&\mbox{
if }0<p_{i}<\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}};\\\ {\tilde{r}},&\mbox{
if }\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}}\leq p_{i}<1.\end{cases}$ (169)

Note that if $p_{i}\geq 1/({\tilde{r}}{\tilde{q}})$, then ${\tilde{r}}\geq
1/(p_{i}{\tilde{q}})$. Thus, $r^{*}(p_{i},{\tilde{q}})\geq{\tilde{r}}\geq
1/(p_{i}{\tilde{q}})$ and so

$\displaystyle\sqrt{(1-p_{i})^{2}+4p_{i}(1-{\tilde{q}})\left(\frac{1}{r^{*}(p_{i},{\tilde{q}})}-p_{i}{\tilde{q}}\right)}-(1-p_{i})$
$\displaystyle\hskip
36.135pt\leq\sqrt{(1-p_{i})^{2}+4p_{i}(1-{\tilde{q}})\left(p_{i}{\tilde{q}}-p_{i}{\tilde{q}}\right)}-(1-p_{i})$
(170) $\displaystyle\hskip 36.135pt=\sqrt{(1-p_{i})^{2}}-(1-p_{i})=0.$ (171)

Thus, $\varepsilon(p_{i})=\infty$ for any $p_{i}\geq
1/({\tilde{r}}{\tilde{q}})$. We may thus restrict our attention to
$p_{i}<\min\\{1,1/({\tilde{r}}{\tilde{q}})\\}$.

Since $r^{*}(p_{i},{\tilde{q}})$ is a continuous function of $p_{i}$ and
$\varepsilon(p_{i})$ is a continuous function of $r^{*}(p_{i},{\tilde{q}})$,
it follows that $\varepsilon(p_{i})$ is a continuous function of $p_{i}$. By
Lemma 2, $\varepsilon(p_{i})$ is a decreasing function of $p_{i}$ for
$0<p_{i}<{\tilde{a}}/({\tilde{q}}{\tilde{r}})$.

When $0<{\tilde{q}}<1/({\tilde{r}}+1)$, note that
$1/({\tilde{q}}{\tilde{r}})>({\tilde{r}}+1)/{\tilde{r}}>1$ and so
$\min\\{1,1/({\tilde{r}}{\tilde{q}})\\}=1$. By Lemma 3, $\varepsilon(p_{i})$
is a decreasing function of $p_{i}$ for
${\tilde{a}}/({\tilde{q}}{\tilde{r}})<p_{i}<1$. Thus, the minimum must occur
at $p_{i}=1$ and is, by Corollary 2,

$\displaystyle\varepsilon(1)=\frac{1}{2}\log\left(\frac{1-{\tilde{q}}}{\frac{1}{{\tilde{r}}}-{\tilde{q}}}\right).$
(172)

When ${\tilde{q}}=1/({\tilde{r}}+1)$, again
$1/({\tilde{q}}{\tilde{r}})=({\tilde{r}}+1)/{\tilde{r}}>1$. By Lemma 3,
$\varepsilon(p_{i})$ is flat for
${\tilde{a}}/({\tilde{q}}{\tilde{r}})<p_{i}<\min\\{1,1/({\tilde{r}}{\tilde{q}})\\}$
= 1. Thus, the minimum is shared by all points in this range and is equal to
(172).

When $1/({\tilde{r}}+1)<{\tilde{q}}<1$, by Lemma 3, $\varepsilon(p_{i})$ is an
increasing function of $p_{i}$ for
${\tilde{a}}/({\tilde{q}}{\tilde{r}})<p_{i}<\min\\{1,1/({\tilde{r}}{\tilde{q}})\\}$.
Thus, the minimum must occur at $p_{i}={\tilde{a}}/({\tilde{q}}{\tilde{r}})$
and is

$\displaystyle\varepsilon\left(\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}}\right)$
$\displaystyle=\log\left(\frac{2\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}}(1-{\tilde{q}})}{\sqrt{(1-\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}})^{2}+4\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}}(1-{\tilde{q}})\left(\frac{1}{{\tilde{r}}}-\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}}{\tilde{q}}\right)}-(1-\frac{{\tilde{a}}}{{\tilde{q}}{\tilde{r}}})}\right)$
(173)
$\displaystyle=\log\left(\frac{2{\tilde{a}}(1-{\tilde{q}})}{\sqrt{({\tilde{q}}{\tilde{r}}-{\tilde{a}})^{2}+4{\tilde{a}}{\tilde{q}}(1-{\tilde{q}})\left(1-{\tilde{a}}\right)}-({\tilde{q}}{\tilde{r}}-{\tilde{a}})}\right).$
(174)

Finally, when ${\tilde{q}}=1$ for
${\tilde{a}}/({\tilde{q}}{\tilde{r}})<p_{i}<\min\\{1,1/({\tilde{r}}{\tilde{q}})\\}$,