# Interaction anisotropy and random impurities effects on the critical
behaviour of ferromagnets

H Chamati 1 and S Romano 2 1 Institute of Solid State Physics, Bulgarian
Academy of Sciences, 72 Tzarigradsko Chaussée, 1784 Sofia, Bulgaria
<EMAIL_ADDRESS>2 Dipartimento di Fisica “A. Volta“, Università di Pavia,
Via A. Bassi 6, I-27100 Pavia, Italy<EMAIL_ADDRESS>
###### Abstract

The theory of phase transitions is based on the consideration of "idealized"
models, such as the Ising model: a system of magnetic moments living on a
cubic lattice and having only two accessible states. For simplicity the
interaction is supposed to be restricted to nearest–neighbour sites only. For
these models, statistical physics gives a detailed description of the
behaviour of various thermodynamic quantities in the vicinity of the
transition temperature. These findings are confirmed by the most precise
experiments. On the other hand, there exist other cases, where one must
account for additional features, such as anisotropy, defects, dilution or any
effect that may affect the nature and/or the range of the interaction. These
features may have impact on the order of the phase transition in the ideal
model or smear it out. Here we address two classes of models where the nature
of the transition is altered by the presence of anisotropy or dilution.

To appear in Journal of Physics: Conference Series

##  1 Introduction

Materials in Nature can be found in qualitatively different phases having
distinct properties. The change from one phase to another is the consequence
of a variation of an intensive thermodynamic quantity, e.g., the temperature
$T$, the pressure $P$, external electric or magnetic fields $E$ or $H$. Phase
transitions are accompanied by abrupt changes in a number of macroscopic
thermodynamic quantities. Some familiar examples of phase transitions include
the gas–liquid transition (condensation), the liquid–solid transition
(freezing), the normal–superconducting transition in conductors, the
paramagnet–ferromagnet transition in magnetic materials, and the superfluid
transition in liquid helium. Further examples are transitions involving
amorphous or glassy structures, spin glasses, liquid crystals, charge–density
waves, and spin–density waves.

In many cases, the two phases above and below the transition point, say
$T_{c}$ for a temperature driven phase transition, may be discerned from each
other in terms of some ordering that occurs in the phase below $T_{c}$. For
example in the liquid–solid transition the molecules of the liquid get
“ordered” in space when they form the solid phase. In a paramagnet, the
magnetic moments of each atom can point in any random direction (in the
absence of an external magnetic field), but in the ferromagnetic phase the
moments are lined up in a particular direction of ordering. Thus in the high
temperature phase (above $T_{c}$), the degree of ordering is smaller than in
the low temperature phase (below $T_{c}$). To quantify the amount of ordering
in a system one uses the so called order parameter, which is usually a
vanishing quantity in the high temperature (disordered) phase.

The phase diagram shows regions within which homogeneous equilibrium states
exist as a function of temperature and other thermodynamic variables like $P$,
$E$, $H$. For some physical systems the chemical potential $\mu$ or
composition variables are also involved. The different regions of the phase
diagram are delimited by phase boundaries that mark conditions under which
multiple phases can coexist at equilibrium. Phase transitions take place along
phase boundaries marked by lines of equilibrium.

The theoretical framework that aims at describing phase transitions and
related phenomena as a result from cooperative effects over macroscopic scales
is a part of the realm of equilibrium statistical physics [1, 2, 3].
Statistical physics is based on probabilistic models of the interactions of
microscopic entities forming large assemblages (macroscopic bodies). The
probability a macroscopic system of volume $V$, having $N$ particles, in a
state $\mathfrak{S}$ with energy $E$ at a temperature $T$, is given by

$\mathscr{P}(\mathfrak{S})=\frac{e^{-E(\mathfrak{S})/(k_{B}T)}}{\mathscr{Z}(T)},$
(1)

where $k_{B}$ is the Boltzmann constant, and $\mathscr{Z}(T)$ is the partition
function

$\mathscr{Z}(T)=\sum_{\mathfrak{S}}e^{-E(\mathfrak{S})/(k_{B}T)},$ (2)

relating microscopic degrees of freedom to macroscopic thermodynamic
quantities. The function $\mathscr{Z}(T)$ depends upon any parameters that
might affect the value of $E(\mathfrak{S})$. The expectation value of any
statistical operator $\mathfrak{O}$ is defined via

$\langle\mathfrak{O}(\mathfrak{S})\rangle=\sum_{\mathfrak{S}}\mathfrak{O}(\mathfrak{S})\mathscr{P}(\mathfrak{S}).$
(3)

For example the internal energy $U$ is obtained by averaging $E(\mathfrak{S})$
over all the accessible states of the system. This is given by

$U=\langle E(\mathfrak{S})\rangle.$

A fundamental thermodynamic quantity related to the partition function is the
free energy

$f(T)=-k_{B}T\ln\mathscr{Z}(T),$ (4)

which contains all the information on the thermodynamics of the considered
system.

According to the Ehrenfest classification scheme there are different kinds of
phase transitions depending on the nature of the singularities of the
thermodynamic quantities at the transition. Such transitions are categorized
as first–, second–, or higher order transitions if the lowest derivative of
the free energy that exhibit nonanalytic behaviour with a finite jump is the
first, second or higher one. Within this classification the
Berezinskiǐ–Kosterlitz–Thouless (BKT) [4, 5] may be considered as being of
infinite order.

To describe universal features of phase transitions one uses relatively
“simple” microscopic models such as the magnetic model involving interaction
between magnetic degrees of freedom. In a classical model for a magnet, the
spins (magnetic moments) may be represented by $n$–component unit vectors
$\bm{s}_{i}$ located at sites $i$, with coordinates $\bm{x}_{i}$, belonging to
a finite subset of a generic $d$–dimensional lattice $\Lambda_{d}$, i.e.
$\mathfrak{L}\subset\Lambda_{d}$, with $|\mathfrak{L}|=N$. We are considering
here saturated lattice models, where each lattice site hosts one spin. The
simplest and probably most extensively studied cases considered in the
literature assume a hypercubic lattice $\Lambda_{d}=\mathbb{Z}^{d}$ and
isotropically interacting spins, thus the (nearest–neighbour) Hamiltonian

$\mathscr{H}_{\mathfrak{L}}=-\frac{J}{2}\sum_{\langle
i,j\rangle}\bm{s}_{i}\cdot\bm{s}_{j}-\bm{H}\sum_{i}\bm{s}_{i},$ (5)

where the coupling $J$ is restricted to nearest–neighbouring sites $i$ and
$j$, with each distinct pair being counted once. $\bm{H}$ stands for an
uniform magnetic field.

In the absence of the magnetic field, i.e. $\bm{H}=\bm{0}$, a ferromagnetic
coupling, $J>0$, favours a parallel orientation of the spins in the ground
state, whereas thermal fluctuations tend to create an orientational disorder.
On the other hand an interaction, $J<0$, would be the precursor of an
antiferromagnetic order at low temperatures. Actually, in the specific case
considered here, i.e. nearest–neighbour coupling and bipartite lattice, and
with $\bm{H}=\bm{0}$, the sign of the coupling constant is immaterial, i.e.
models defined by $+J$ and $-J$ yield the same partition function, whereas the
two correlation functions are connected by suitable sign factors.

For $n=1,2,3$, the model corresponds to the Ising, planar rotator (PR) and
Heisenberg (He), respectively. The Ising model is known to have a $Z_{2}$
discrete symmetry, while systems with $n\geq 2$, like PR and He, are said to
possess a continuous $O(n)$ symmetry. It has become customary to refer to the
number of component $n$ of the order parameter as symmetry index. The
interaction with an external field breaks this symmetry and establishes a
preferred direction for spin alignment. By reducing the external field to zero
in the thermodynamic limit, the system may exhibit spontaneous magnetization
pointing in the initial direction of the field. It has been shown [6] that the
limit $n\to\infty$ leads to the spherical model [7] obtained by requiring the
spins to be continuous variables subject to a global relaxed constraint
($\sum_{i=1}^{N}\bm{s}_{i}^{2}=N$) rather than forcing them to take unit
lengths i.e. $|\bm{s}_{i}|^{2}=1$. The formal limit $n\to 0$ is relevant to
the study of self–avoiding walk problem, which can be applied to polymers.

By now a number of rigorous results, assuming translational invariance, have
been worked out, entailing existence or absence of a phase transition in the
thermodynamic limit, depending on lattice dimensionality $d$ and number of
spins components $n$ [8, 9].

Model (5) with different values of $n$ and $d$ is extensively studied in the
literature via different methods and its behaviour as a function of the
temperature is very well known. For a review with a rich list of references
see [10]. At $H=0$, it exhibits a second order phase transition,111Here and
below the temperature will be measured in units of $J/k_{B}$. for any $d>1$
and with discrete spin variables, i.e. $n=1$. Such a transition is
characterized by a significant growth of the nearest–neighbour correlations
for orientational fluctuations, and also the onset for long–range
orientational correlations. On the other hand, according to the Mermin–Wegner
theorem [11] in $O(n)$ symmetric models ($n\geq 2$) there can be no
spontaneous symmetry breaking at finite temperatures for $d\leq 2$ meaning
that the system remains orientationally disordered at any finite temperature.
For $d>2$ and $n\geq 2$ a second order phase transition takes place in the
system. In the two–dimensional case $d=2$ and $n=2$ the system exhibits a BKT
transition from a high temperature disordered phase to a low temperature phase
with slow decay of the correlation function and an infinite magnetic
susceptibility [12].

In the vicinity of a continuous phase transition, such as second order or BKT
transition, there is only one dominating length scale related to the growth of
fluctuations: The correlation length. Because of the diverging nature of the
correlation length as the critical point is approached the microscopic details
of the system becomes irrelevant. Thus the description of the singular
behaviour of many thermodynamic observables requires a small number of
universal variables: critical exponents, amplitudes and functions. This allows
the arrangement of a great variety of different microscopic systems in
universality classes of equivalent critical behaviour. A universality class
depends upon the number of components of the order parameter and the
dimensionality of the system. For more details the reader is invited to
consult references [13, 14].

The model (5) can describe the properties of a wide variety of physical
situations in the vicinity of their transition point, however, it may happen
that the very experimental situation at hand requests the interaction model to
be complicated (made physically richer and theoretically more challenging) in
various ways. On the one hand, there exist different possible lattice types
$\Lambda_{d}$, in addition to $\mathbb{Z}^{d}$. On the other hand, as for the
orientational dependence, more elaborate potential models involve (in some
combination or other) isotropic or anisotropic linear couplings between spin
components, sometimes higher powers of scalar products among the interacting
spins, multipolar (usually dipolar) interactions, Dzyaloshinski–Moriya terms,
single–site anisotropy fields. Notice also that more distant neighbours are
sometimes involved, or even, in principle, all neighbours may be coupled by
long–range interactions. In some specific favourable cases one has even been
able to match the model and its potential parameters to a specific
experimental system [15]. The ferromagnetic ordering transition observed
experimentally in the absence of an external field is more frequently second
order, but first–order transitions are also known. They might, for example,
result from doping by nonmagnetic impurities, anisotropy of interactions in
spin space, or coupling to the lattice [16]. Other interaction models for
different physical systems can be found in [17].

This review is devoted to the description and analysis of effects related to
the nature of the interaction. This aims at gaining insights in the
thermodynamics of some specific systems. The models considered here are some
of the most popular models in the theory of phase transitions. They involve
different kind of interactions that hopefully might be adapted to the
characteristics of a given material. They describe ferromagnetism with
anisotropic coupling, systems with random dilution and may to some extent be
used to investigate fluids. Special attention is paid to the construction of
the phase diagrams of these models that are determined from the investigation
of different thermodynamic quantities such as: the free energy, the
susceptibility, specific heat etc.

The review is organised as follows: In Section 2 we discuss the transitional
behaviour of generalised XY models introduced in reference [18]. These are
generalization of the XY model with a nontrivial coupling along the $z$
components of the spins. We construct the phase diagrams of the models in two
and three dimensions and determine the effect of the nontrivial coupling on
the nature and location of transition temperature. In Section 3 we review the
effect of dilution of ferromagnets by the introduction of random impurities
and present the phase diagram of the diluted Heisenberg in three dimensions
and the diluted plane rotator in two dimensions. We conclude with Section 4,
where we discuss the results and comment on other models sharing similar
transitional behaviour.

##  2 Generalised XY models

Let us first consider interactions being anisotropic in spin space with
nonvanishing and equal ferromagnetic couplings involving $m<n$ components of
the partner spins only, while still keeping the interaction restricted to
nearest neighbours. In this case the model reads

$\mathscr{H}_{\mathrm{anis.}}=-\frac{J}{2}\sum_{\langle
i,j\rangle}\sum_{\alpha,\beta\leq
m}\delta_{\alpha,\beta}s_{i}^{\alpha}s_{j}^{\beta}.$ (6)

Among these models we may mention the continuous Ising ($m=1$ and $n$
arbitrary) and the various versions of XY models ($m=2$ and $n$ arbitrary),
where the interaction is restricted to only one component and two components
of the magnetic moments, respectively

In general the transitional behaviour of such models is analogous to that of
their $O(m)$ isotropic counterparts: On the one hand, the universal critical
behaviour of these models in the vicinity of their corresponding transition
temperature is equivalent to their isotropic $O(m)$ counterparts i.e. the
models share the same universal features (critical exponents and amplitudes).
on the other hand, the transition temperature is a typical non–universal
quantity, and is recognizably affected by the anisotropy.

A more general class of anisotropic spin models may be constructed by
introducing some kind of extreme anisotropy coupling only a part of the spin
components in some nontrivial manner in addition to the anisotropic
interaction in the spin space. A model that will be discussed in this study is
the so called “generalised” XY model introduced in reference [18]. This model
involves $3-$component unit vectors, and is defined by

$\mathscr{H}_{XY}^{p}=-\frac{J}{2}\sum_{\langle
i,j\rangle}(\sin\theta_{i}\sin\theta_{j})^{p}\cos(\phi_{i}-\phi_{j}),$ (7)

where $p\in\mathbb{N}$ is a parameter controlling the strength of anisotropy
along the $z$–spin direction, and the spins are expressed in terms of the
usual spherical coordinates $\theta_{i}$ and $\phi_{i}$ i.e.
$\bm{s}_{i}=(\sin\theta_{i}\cos\phi_{i},\sin\theta_{i}\sin\phi_{i},\cos\theta_{i})$.
Notice that by setting $p=1$ ($p=0$) we recover the familiar XY model (planar
rotator). In this case of the planar rotator model, the $\theta$–dependence
only survives in the free–spin measure. The Hamiltonian (7) can also be
written in terms of spin components, in the more complicated form

$\mathscr{H}_{XY}^{p}=-\frac{J}{2}\sum_{\langle
i,j\rangle}\left[1-(s_{i}^{z})^{2}-(s_{j}^{z})^{2}+(s_{i}^{z}s_{j}^{z})^{2}\right]^{(p-1)/2}\left(s_{i}^{x}s_{j}^{x}+s_{i}^{y}s_{j}^{y}\right).$
(8)

As for the role of $p$ in Eq. (7), notice that it could be taken to be a real
positive number, say ranging between $0$ and $1$ (and hence continuously
interpolating between planar rotator and XY models). On the other hand, larger
values of $p$ reinforce the out–of–plane fluctuations. This makes it possible
to widely vary the anchoring of spins with respect to the horizontal plane
which might have direct experimental relevance. As for the present model, this
change of anchoring is ultimately reflected by the significant changes in
transition behaviour.

The transitional behaviour of the model in two and three dimensions has been
investigated by different approaches. First, it was proven rigorously [18], on
the basis of the known behaviour of PR, that when $d=2$ and for all values of
$p$, the named potential models produce orientational disorder at all finite
temperatures, and support a BKT–like transition. On the other hand, when
$d=3$, these models support ordering transitions taking place at finite
temperatures. In both cases, the transition temperatures are bounded from
above by the corresponding values for the PR counterpart. It was later proven
[19], again rigorously, that the transition turns first–order for sufficiently
large $p$. Notice that the threshold values had to be estimated by other
means.

###  2.1 Two dimensions

Using Monte Carlo simulations, the thermodynamics of model (7) has been
investigated in details in reference [20] for $d=2$ and values of $p$ ranging
from 2 to 5. Analysis of Monte Carlo data, showed that the model produces a
BKT–(like) transition, possibly changing to a first–order transition for
larger $p$, due to the large number of vortices and strong out–of–plane
fluctuations. It has been found that the transition temperature is indeed
decreasing with increasing $p$.

To gain insight into the transitional behaviour of the model for large values
of $p$ we performed further Monte Carlo simulations at $p=6$. Our analysis
shows that the transition is most likely to have a weak first order nature.
Unfortunately more simulations are required and different approaches are
needed to be more conclusive.

Figure 1: ($p,T$) phase diagram of the two–dimensional generalised XY model.
Full circles indicate a Berezinskiǐ–Kosterlitz–Thouless like phase transition,
while the square is believed to corresponds to a weak first order phase
transition.

In figure 1 we show the phase diagram of the two dimensional generalised XY
model in the $(p,T)$ plane. It is seen that the model exhibits a phase
transition from a paramagnetic phase to a BKT–like phase as the temperature
decreases. The transition temperature is evaluated using Monte Carlo
simulations according to reference [20]. The value of the transition
temperature corresponding to $p=1$ is taken from reference [21].

###  2.2 Three dimensions

For $d=3$, different analytical approximations, such as a Mean Field (MF)
approach, as well as its Two–Site Cluster (TSC) refinement have been used in
reference [18] to estimate transition temperatures for $p=2,3,4$, and then for
higher values of $p$ in subsequent papers (see below). Notice also that
$(\sin\theta)^{p}$, and hence the absolute value of the interaction potential,
decreases with increasing $p$, and this aspect is reflected by the
$p$–dependence of the estimated transition temperature. Transition
temperatures have been estimated in reference [22] by self–consistent harmonic
approximation, both for $d=2$ and $d=3$, and it was found that the transition
temperature is decreasing against $p$. A study of the model in its continuum
limit, carried out in reference [22] also showed that out–of–plane
fluctuations, and consequently the magnon density, decrease with increasing
$p$.

We have also addressed the three dimensional generalised XY models for various
values of $p$, by means of Monte Carlo (MC) simulation. We have investigated
the transitional behaviour of various thermodynamic functions, such as the
susceptibility and the specific heat, and made comparisons with MF and TSC
predictions. MF yielded a tricritical behaviour with tricritical points having
real (non–integer) values of the parameter $p$. As for simulation results,
transitional behaviour characetristic of the XY model was found for
$p=2,3,4,8$, the case $p=12$ suggested tricritical behaviour, whereas evidence
of first–order transitions was obtained for $p=16,20$.

In Figure 2 we present the $(p,T)$ phase diagram, where we can read off the
behaviour of the transition temperature as a function of $p$ for $1\leq p\leq
20$. MF and TSC data can be found in references [18, 23, 24, 19], while Monte
carlo data are taken from references [25, 23, 24]. Notice that, for $p\leq 4$,
TSC gives better estimates of $T_{c}$ than MF, then the two roles are
exchanged for $p=8,12$, and finally the three methods give very similar
answers when $p\geq 16$, i.e. where the transition has a pronounced
first–order character.

Figure 2:  Phase diagram of the three dimensional generalised XY model. The
solid and dashed lines stand for transition temperatures estimated via
mean–field and two–site–cluster treatments, respectively. Full circles and
squares indicate second and first order phase transitions temperatures
evaluated via Monte Carlo simulations, respectively. Full diamonds shows the
locations of tricritical points.

##  3 Annealed dilution in ferromagnets

Another class of systems that has been extensively studied in the literature
spans those with random impurities (disorder). For a review on diluted
magnetism see reference [26]. The interest in these systems stems from the
fact that in nature no system is really pure. Indeed, the presence of
cavities, grain boundaries, lattice defects, chemical impurities (i.e. of
other chemical individuals) or some other kind of disorder may affect the
properties of the pure system, and result in different effects. To consider a
simple but rather important example, in a system of magnetically coupled
spins, some lattice sites may be occupied by nonmagnetic constituents
(site–dilution). Both in experimental and theoretical terms, one can
distinguish between annealed and quenched disorder.

In quenched systems, impurities are held frozen in randomly distributed fixed
positions, without the possibility of overcoming potential barriers for
diffusing into the host material: in this case the relaxation time is very
long and thermal equilibrium between impurities and the constituents of the
host is never reached. In annealed materials, impurities are allowed to
diffuse randomly and to reach thermal equilibrium with the other constituents
of the host material. One can also think of a two–component solution being
very dilute with respect to one of the components. When the system is in the
liquid phase, molecules of the two types can exchange their positions, and
diffuse throughout the sample. Let then the system crystallize, at
sufficiently low temperature. In the resulting solid, particles of the
minority component are fixed in certain lattice sites only.

The simplest extension of equation (5) taking these situations into account
reads

$\mathscr{H}_{\mathrm{dis.}}=-\frac{J}{2}\sum_{\langle
i,j\rangle}\nu_{i}\nu_{j}\ \bm{s}_{i}\cdot\bm{s}_{j}.$ (9)

where the occupation numbers $\nu_{i}$ equal “zero” for a site $i$ hosting a
nonmagnetic impurity and “one” for a magnetic particle. The density of
magnetic particles in the system is defined via

$\rho=\frac{1}{N}\sum_{i}^{N}\langle\nu_{i}\rangle.$

Within this notation the pure system, i.e. without impurities, corresponds to
$\rho=1$.

In the annealed case, Hamiltonian (9) can be interpreted as describing a
two–component system consisting of interconverting “real” ($\nu_{i}=1$) and
“ghost”, “virtual” or ideal–gas particles ($\nu_{i}=0$). Both kinds of
particles have the same kinetic energy, and the total number of particles
equals the number of available lattice sites. In this case one works in the
Grand–Canonical Ensemble where the probability (1) for a configuration, now
involving the occupation numbers $\\{\nu_{i}\\}$, as well as the spins
$\\{\bm{s}_{i}\\}$, is defined by

$\mathscr{P}\propto\exp\left[-\beta\left(\mathscr{H}_{\mathrm{dis.}}-\mu\sum_{i}\nu_{i}\right)\right],$
(10)

where $\mu$ denotes the excess chemical potential of “real” particles over
“ideal” ones. Of course, the interaction may be anisotropic in spin space, as
in the cases outlined above, or involve more distant neighbours. The system
remains translationally invariant on average. This model bears some similarity
with the Blume–Emery–Griffiths model [27] for 3He impurities in superfluid
4He. More precisely, notice also that, starting from an assigned model, its
lattice gas extensions can be written in general as

$\mathscr{H}_{LG}=-\frac{J}{2}\sum_{\langle i,j\rangle}\nu_{i}\nu_{j}\
\bm{s}_{i}\cdot\bm{s}_{j}+\frac{\lambda}{2}\sum_{\langle
i,j\rangle}\nu_{i}\nu_{j}\ ,$ (11)

where the purely positional $\lambda$ term only becomes immaterial in the pure
limit $\mu\rightarrow+\infty$. In equation (9) we have chosen the simplest
case $\lambda=0$. Lattice gas models can be used to model adsorption, and, in
general, the variable occupation numbers produce some fluidity of the system.
One can also set the coupling $J$ term to zero, so that the resulting model
becomes isomorph with an Ising model in external field. In general, the
interplay between $J$ and $\lambda$ can produce a richer phase diagram: for
example, when $\lambda>0$ and $\mu$ is sufficiently large, the ground state
may exhibit checkerboard positional order but no orientational one.

It is very well known that a small amount of annealed disorder does not affect
the way the singularities take place in pure systems i.e. the phase transition
remains a second order one. The $\rho$–dependent critical temperature is
shifted towards $T_{c}(\rho)<T_{c}(1)$. If the chemical potential $\mu$ is
held fixed, the properties of the phase transition are the same as those known
for the pure system, corresponding to $\mu\to\infty$ and $\rho=1$. If,
however, the concentration $\rho$ is kept fixed during the transition, care
must taken in characterising the transition. For details see reference [28].

A significant amount of impurities may alter the order of the phase transition
or make it disappear. Investigations of the XY model, as a protype for He3 –
He4 mixtures, in three dimensions, via high temperature series expansion of
the partition function, show that by increasing the density of randomness the
transition temperature decreases. At a certain value of $\rho$ the transition
changes its nature and turns into a first order one [29]. The second order
phase transition line ends at a tricritical point, which marks the begining of
a line of fisrt–oder phase transition temperature that keeps decreasing as the
concentration of impurities increases.

In the three–dimensional case, the topology of the phase diagram of model (9)
had been investigated by MF and TSC approximations for the Ising [30], as well
as PR cases [31] in the presence of a magnetic field, and for He at zero
magnetic field [32]. These investigations were later extended [33] to the
extremely anisotropic (Ising–like) two–dimensional model, and in the absence
of a magnetic field, as well. The studied models were found to exhibit a
tricritical behaviour i.e. the ordering transition turned out to be of first
order for $\mu$ below an appropriate threshold, and of second order above it.
When the transition is of first order, the orientationally ordered phase is
also denser than the disordered one.

To check the predictions of the molecular–field–like treatments used to
construct the phase diagrams, extensive Monte Carlo simulations has been
performed [31, 32, 33] for particular values of the chemical potential. A
number of thermodynamic and structural properties had been investigated. It
had been found that there is a second order ferromagnetic phase transition
manifested by a significant growth of magnetic and density fluctuations. The
transition temperatures were found to be smaller than those of the
corresponding values for the pure systems and the critical behaviour of the
investigated models to be consistent with that of their pure counterparts.
Furthermore it had been found that MF yields a qualitatively correct picture,
and the quantitative agreement with simulation could be improved by TSC, which
has the advantage of predicting two–site correlations. In general we found
that simulations results are consistent with the molecular–field like
treatments.

Figure 3: Phase diagrams of the three–dimensional Heisenberg model in the
chemical potential – temperature and density – temperature planes. Solid and
dashed lines correspond to mean–field and two–site–cluster results,
respectively. Circles and squares stand, respectively, for estimates of the
second and first order transition temperatures using Monte Carlo simulations.
Diamonds mark the locations of tricritical points. The dotted line marks the
transition temperature of the model in the absence of impurities.

In figure 3 we report the phase diagrams in the chemical potential –
temperature and density – temperature planes. We show the behaviour of the
transition temperature $T_{c}$ versus chemical potential $\mu$. The plot also
shows a fast, approximately linear, increase of $T_{c}$ with $\mu$ up to
$\mu\approx 0$, and a slower one above this value. Moreover, MF and TSC
results essentially coincide up to $\mu\approx 0$. In the phase diagram in the
($\rho,T$) plane the existence of a first–order transition is reflected by a
biphasic region. We found that the system exhibits a first–order phase
transition from a dense BKT phase to a paramagnetic one. In the
temperature–density phase diagram, both phases are expected to coexist over
some range of densities and temperatures.

Two–dimensional annealed lattice models were investigated [34, 35] as well,
and the obtained results for $\mu=0$ or a moderately negative $\mu$ were found
to support a BKT phase transition with a transition temperature lower than
that of the pure parent due to the presence of impurities. For negative and
sufficiently large in magnitude $\mu$ we found evidence of a first order phase
transition in agreement with renormalization group treatments [36, 37].

Figure 4: Phase diagrams of the two–dimensional planar rotator. Circles and
squares stand, respectively, for estimates of the second and first order
transition temperatures using Monte Carlo simulations. Diamonds mark the
locations of tricritical points. The dotted line marks the transition
temperature of the model in the absence of impurities.

In figure 4 we show the phase diagram in the $(\rho,T)$ plane. The existence
of a first–order transition is reflected here by a biphasic (binodal) region.
The phase diagram obtained here is similar to the one resulting from the study
of the diluted planar rotator model [31].

So far, we have discussed isotropic models. As we have mentioned, in addition
to dilution one can consider anisotropic interactions as well. In reference
[33] we have investigated two–dimensional continuous Ising spin models with
two and tree component spins. The phase diagrams of these models were found to
be topologically similar to those found for the Heisenberg model shown in
figure 3. The main differences come from the locations of the phase
boundaries.

##  4 Conclusion

The Statistical Mechanics of lattice systems is essentially based on the study
of a number of relatively “simple” models which are gradually made more
complicated. We have shown here some examples, involving generalized XY models
and annealed magnetic systems, where rigorous results have been produced to
prove existence and type of transition, supplemented by a variety of
techniques (MF or TSC approximation and Monte Carlo simulation) for
elucidating the resulting physical behaviour and estimating numerical values.

We obtained the phase diagram in two and three dimensions of a generalized
version of the lattice XY model, where the out–of–plane fluctuations of the
spins are controlled by a parameter $p$. Our investigation shows that the
nature of the transition is highly affected by the strength of the
out–of–plane fluctuations. For $p\geq 12$ at three dimensions and $p\gtrsim 6$
at two dimensions, it is first order, whereas for small values its
transitional behaviour coincides with that of the original XY model. The
transition temperature is found to decrease as $p$ increases at any dimension.

We constructed the phase diagrams of the annealed lattice plane rotator in two
dimensions and the Heisenberg model in three dimensions. It is found that the
transition changes from a second order at three dimensions and
Berezinskiǐ–Kosterlitz–Thouless at two dimensions into a first order
transition as the concentration of impurities is increased. In turn the
transition temperature is found to decrease with increasing impurity density.

This work was supported by the Ministry of Education and Science of Bulgaria
under Grant No $\Phi$–1517.

## References

  * [1] Yeomans J M 1992 Statistical Mechanics of Phase Transitions (New York: Oxford University Press)
  * [2] Pathria R K 1996 Statistical mechanics 2nd ed (Oxford, England: Butterworth–Heinemmann)
  * [3] Mazenko G F 2003 Fluctuations, Order and Defects (Hoboken: Wiley)
  * [4] Berezinskiǐ V L 1971 Sov. Phys. JETP 32 493–500 [Zh. Eksp. Teor. Fiz. 59, 907–920]
  * [5] Kosterlitz J M and Thouless D J 1973 J. Phys. C: Solid State Phys. 6 1181–1203
  * [6] Stanley H E 1968 Phys. Rev. 176 718–722
  * [7] Berlin T H and Kac M 1952 Phys. Rev. 86 821–835
  * [8] Georgii H O 1988 Gibbs Measures and Phase Transitions (de Gruyter Studies in Mathematics vol 9) (Berlin: Walter de Gruyter)
  * [9] Sinai Y G 1982 Theory of Phase Transitions: Rigorous Results (Oxford: Pergamon)
  * [10] Pelissetto A and Vicari E 2002 Phys. Rep. 368 549–727
  * [11] Mermin N D and Wagner H 1966 Phys. Rev. Lett. 17 1133–1136
  * [12] Gulácsi Z and Gulácsi M 1998 Adv. Phys. 47 1–89
  * [13] Fisher M E 1998 Rev. Mod. Phys. 70 653–681
  * [14] Stanley H E 1999 Rev. Mod. Phys. 71 S358–S366
  * [15] de Jongh L J and Miedema A R 2001 Adv. Phys. 50 947–1170
  * [16] Binder K 1987 Rep. Prog. Phys. 50 783–859
  * [17] Cardy J 1996 Scaling and Renormalization in Statistical Physics (Cambridge Lecture Notes in Physics vol 5) (Cambridge, England: Cambridge University Press)
  * [18] Romano S and Zagrebnov V 2002 Phys. Lett. A 301 402–407
  * [19] van Enter A C D, Romano S and Zagrebnov V A 2006 J. Phys. A: Math. Gen. 39 L439–L445
  * [20] Mól L, Pereira A R, Chamati H and Romano S 2006 Eur. Phys. J. B 50 541–548
  * [21] Evertz H G and Landau D P 1996 Phys. Rev. B 54 12302–12317
  * [22] Mól L A S, Pereira A R and Moura-Melo W A 2003 Phys. Lett. A 319 114–121
  * [23] Chamati H, Romano S, Mól L and Pereira A R 2005 Eur. Phys. Lett. 72 62–68
  * [24] Chamati H and Romano S 2006 Eur. Phys. J B 54 249–254
  * [25] Costa B V, Pereira A R and Pires A S T 1996 Phys. Rev. B 54 3019–3021
  * [26] Stinchcombe R B 1983 Dilute Magnetism Phase Transitions and Critical Phenomena vol 7 ed Domb C and Lebowitz J L (London: Academic Press) chap 3, pp 151–280
  * [27] Blume M, Emery V J and Griffiths R B 1971 Phys. Rev. A 4 1071–1077
  * [28] Fisher M E 1968 Phys. Rev. 176 257–272
  * [29] Reeve J S 1976 J. Phys. C: Solid State Phys. 9 2575–2587
  * [30] Sokolovskii R O 2000 Phys. Rev. B 61 36–39
  * [31] Romano S and Sokolovskii R O 2000 Phys. Rev. B 61 11379–11390
  * [32] Chamati H and Romano S 2005 Phys. Rev. B 72 064424
  * [33] Chamati H and Romano S 2005 Phys. Rev. B 72 064444
  * [34] Chamati H and Romano S 2006 Phys. Rev. B 73 184424
  * [35] Chamati H and Romano S 2007 Phys. Rev. B 75 184413
  * [36] Cardy J L and Scalapino D J 1979 Phys. Rev. B 19 1428–1436
  * [37] Berker A N and Nelson D R 1979 Phys. Rev. B 19 2488–2503


$W_{\gamma}^{\infty}(F_{f},G)\leq\beta\quad\Longleftrightarrow\quad\Pr_{g\leftarrow
G}[\mathfrak{d}(f,g)>\beta]\leq\gamma.$

Proof:  We show both the directions below.

  * •

Only if part ($\Rightarrow$): Suppose $W_{\gamma}^{\infty}(F_{f},G)\leq\beta$.
It follows from Lemma 3 that there exists a distribution $G^{\prime}$ such
that $\Delta(G^{\prime},G)\leq\gamma$ and
$W^{\infty}(F_{f},G^{\prime})\leq\beta$. Since $F_{f}$ is a point
distribution, all couplings $\phi\in\Phi^{0}(F_{f},G^{\prime})$ will be such
that $\phi_{1}=F_{f}$ and $\phi_{2}=G^{\prime}$, which implies that
$W^{\infty}(F_{f},G^{\prime})=\sup_{g^{\prime}\leftarrow
G^{\prime}}\mathfrak{d}(f,g^{\prime})\leq\beta$. Now we show that, together
with $\Delta(G^{\prime},G)\leq\gamma$, this implies $\Pr_{g\leftarrow
G}[\mathfrak{d}(f,g)>\beta]\leq\gamma$:

$\displaystyle\Pr_{g\leftarrow G}[\mathfrak{d}(f,g)>\beta]$
$\displaystyle=\underbrace{\Pr_{g\leftarrow G}[\mathfrak{d}(f,g)>\beta\ |\
g\in\mathrm{support}(G^{\prime})]}_{=\ 0}\Pr_{g\leftarrow
G}[g\in\mathrm{support}(G^{\prime})]$ $\displaystyle\hskip
56.9055pt+\underbrace{\Pr_{g\leftarrow G}[\mathfrak{d}(f,g)>\beta\ |\
g\notin\mathrm{support}(G^{\prime})]}_{\leq\ 1}\Pr_{g\leftarrow
G}[g\notin\mathrm{support}(G^{\prime})]$ $\displaystyle\leq\Pr_{g\leftarrow
G}[g\notin\mathrm{support}(G^{\prime})]$ $\displaystyle=\int_{g\in\Omega:\
p_{G}(g)>0\ \&\ p_{G^{\prime}}(g)=0}p_{G}(g)dg$
$\displaystyle=\int_{g\in\Omega:\ p_{G}(g)>0\ \&\
p_{G^{\prime}}(g)=0}(p_{G}(g)-p_{G^{\prime}}(g))dg$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}\int_{g\in\Omega:\
p_{G}(g)>p_{G^{\prime}}(g)}(p_{G}(g)-p_{G^{\prime}}(g))dg$
$\displaystyle\stackrel{{\scriptstyle\text{(b)}}}{{=}}\Delta(G,G^{\prime})\leq\gamma,$

where (a) follows because $\\{g\in\Omega:p_{G}(g)>0\ \&\
p_{G^{\prime}}(g)=0\\}\subseteq\\{g\in\Omega:p_{G}(g)>p_{G^{\prime}}(g)\\}$,
and (b) follows from the reasoning given below.

Define $\Omega_{G}^{+}:=\\{g\in\Omega:p_{G}(g)>p_{G^{\prime}}(g)\\}$ and
$\Omega_{G}^{-}:=\\{g\in\Omega:p_{G}(g)<p_{G^{\prime}}(g)\\}$. Since
$\int_{g\in\Omega}p_{G}(g)dg=\int_{g\in\Omega}p_{G^{\prime}}(g)dg$, it follows
that
$\int_{g\in\Omega_{G}^{+}}(p_{G}(g)-p_{G^{\prime}}(g))dg=\int_{g\in\Omega_{G}^{-}}(p_{G^{\prime}}(g)-p_{G}(g))dg$.
Substituting this in the definition of $\Delta(G,G^{\prime})$, we get
$\Delta(G,G^{\prime})=\int_{g\in\Omega_{G}^{+}}(p_{G}(g)-p_{G^{\prime}}(g))dg$.

  * •

If part ($\Leftarrow$): Suppose $\Pr_{g\leftarrow
G}[\mathfrak{d}(f,g)>\beta]\leq\gamma$. Let
$\Omega^{\prime}=\\{g\in\Omega:\mathfrak{d}(f,g)\leq\beta\\}$ and $G^{\prime}$
be a distribution supported on $\Omega^{\prime}$ such that
$p_{G^{\prime}}(g)=\frac{1}{\eta}p_{G}(g)$ when $g\in\Omega^{\prime}$,
otherwise $p_{G^{\prime}}(g)=0$. Here
$\eta=\int_{g\in\Omega^{\prime}}p_{G}(g)dg\geq(1-\gamma)$ is the normalizing
constant. First we show that $\Delta(G,G^{\prime})\leq\gamma$.

$\displaystyle\Delta(G,G^{\prime})$
$\displaystyle=\frac{1}{2}\int_{g\in\Omega}|p_{G^{\prime}}(g)-p_{G}(g)|dg$
$\displaystyle=\frac{1}{2}\int_{g\in\Omega^{\prime}}|p_{G^{\prime}}(g)-p_{G}(g)|dg+\frac{1}{2}\int_{g\in\Omega\setminus\Omega^{\prime}}p_{G}(g)dg$
(Since $p_{G^{\prime}}(g)=0$ when $g\in\Omega\setminus\Omega^{\prime}$)
$\displaystyle=\frac{1}{2}\int_{g\in\Omega^{\prime}}p_{G}(g)(\frac{1}{\eta}-1)dg+\frac{1}{2}\int_{g\in\Omega\setminus\Omega^{\prime}}p_{G}(g)dg$
$\displaystyle=\frac{1}{2}(\frac{1}{\eta}-1)\eta+\frac{1}{2}(1-\eta)$ (Since
$\int_{g\in\Omega^{\prime}}p_{G}(g)dg=\eta$) $\displaystyle=1-\eta\leq\gamma.$
(31)

Now define a joint distribution $\phi$, whose first marginal is the point
distribution $F_{f}$ and the second marginal is $G^{\prime}$, which implies
that
$\sup_{(x,y)\leftarrow\phi}\mathfrak{d}(x,y)=\sup_{g^{\prime}\in\Omega^{\prime}}\mathfrak{d}(f,g^{\prime})$.
It follows from the argument above that $\phi\in\Phi^{\gamma}(F_{f},G)$, which
implies that
$W_{\gamma}^{\infty}(F_{f},G)\leq\sup_{(x,y)\leftarrow\phi}\mathfrak{d}(x,y)=\sup_{g^{\prime}\in\Omega^{\prime}}\mathfrak{d}(f,g^{\prime})\leq\beta$,
where the last inequality is by definition of $\Omega^{\prime}$. Hence, we get
$W_{\gamma}^{\infty}(F_{f},G)\leq\beta$.

This completes the proof of Lemma 9. $\Box$

######  Lemma 10.

For any two distributions $P,Q$ over a metric space $(\Omega,\mathfrak{d})$
and $\gamma\in[0,1]$, we have

$W_{\gamma}^{\infty}(P,Q)=0\quad\Longleftrightarrow\quad\Delta(P,Q)\leq\gamma.$

Proof:  We show both the directions below.

  * •

Only if part ($\Rightarrow$): Suppose $W_{\gamma}^{\infty}(P,Q)=0$. This
implies that there exists a joint distribution $\phi\in\Phi^{\gamma}(P,Q)$
such that $\sup_{(x,y)\leftarrow\phi}\mathfrak{d}(x,y)=0$. Since
$\mathfrak{d}$ is a metric, this implies that for all $(x,y)\leftarrow\phi$,
we have $x=y$. Hence, the first marginal $\phi_{1}$ and the second marginal
$\phi_{2}$ of $\phi$ are equal, which implies that
$\Delta(\phi_{1},P)+\Delta(\phi_{2},Q)\leq\gamma$. Then, by triangle
inequality and that $\phi_{1}=\phi_{2}$, we get $\Delta(P,Q)\leq\gamma$.

  * •

If part ($\Leftarrow$): Suppose $\Delta(P,Q)\leq\gamma$. Define a joint
distribution $\phi:=P\times P$. Since $\phi_{1}=\phi_{2}=P$, we have
$\phi\in\Phi^{\gamma}(P,Q)$. This, by definition, implies
$W_{\gamma}^{\infty}(P,Q)\leq\sup_{(x,y)\leftarrow\phi}\mathfrak{d}(x,y)$.
Since both the marginals of $\phi$ are the same, we have $\mathfrak{d}(x,y)=0$
for every $(x,y)\leftarrow\phi$. This, by the non-negativity of
$W_{\gamma}^{\infty}(P,Q)$, gives $W_{\gamma}^{\infty}(P,Q)=0$.

$\Box$

##  Appendix B Details Omitted from Section 3.2 – Usefulness [BLR13] vs.
Flexible Accuracy

To express accuracy guarantees of their mechanisms, Blum et al. [BLR13]
introduced a notion of _$(\beta,\gamma,\psi)$ -usefulness_ that parallels
$(\alpha,\beta,\gamma)$-accuracy, except that $\psi$ measures perturbation of
the function rather than input distortion. Note that this is a reasonable
notion for the function classes they considered (half-space queries, range
queries etc.), but it is not applicable to queries like maximum.

Flexible accuracy generalizes the notion of usefulness. Firstly, mechanisms
which are $(\beta,\gamma,0)$-useful are $(0,\beta,\gamma)$-accurate (in
[BLR13], such mechanisms were given for interval queries). But even general
usefulness can be translated to flexible accuracy generically, by redefining
the function to have an extra input parameter that specifies perturbation.
Further, the specific $(\beta,\gamma,\psi)$-useful DP mechanism of [BLR13] for
half-space counting queries – with data points on a unit sphere, and the
perturbation of the function corresponded to rotating the half-space by $\psi$
radians – is $(\psi,\beta,\gamma)$-accurate for the same functions, w.r.t. the
distortion $\mathsf{\partial}_{\mathrm{move}}$. This is because, the rotation
of the half-space can be modeled as moving all the points on the unit sphere
by a distance of at most $\psi$.

##  Appendix C Details Omitted from Section 4.1.3 – Proof of Lemma 2

For convenience, we write the lemma statement below.

######  Lemma (Restating Lemma 2).

Let $\mathcal{M}:\mathcal{B}\to\mathcal{C}$ be a deterministic mechanism for a
deterministic function $f:\mathcal{B}\to\mathcal{C}$. Then, for any
$\beta_{1}\geq 0$, we have

$\displaystyle\tau_{\mathcal{M},f}^{0,0}(\beta_{1},0)\quad=\sup_{\begin{subarray}{c}X,X^{\prime}:\\\
W^{\infty}(\mathfrak{p}_{{}_{X}},\mathfrak{p}_{{}_{X^{\prime}}})\leq\beta_{1}\end{subarray}}W^{\infty}(\mathcal{M}(X),f(X^{\prime}))\quad=\sup_{\begin{subarray}{c}x,x^{\prime}\in\mathcal{A}:\\\
\mathfrak{d}_{\mathrm{\mathcal{B}}}(x,x^{\prime})\leq\beta_{1}\end{subarray}}\mathfrak{d}_{\mathrm{\mathcal{C}}}(\mathcal{M}(x),f(x^{\prime})).$

Proof:  The first equality follows from the definition of error sensitivity.
We only need to prove the second equality.

  * •

LHS $\geq$ RHS: This is the easy part.

$\displaystyle\sup_{\begin{subarray}{c}X,X^{\prime}:\\\
W^{\infty}(\mathfrak{p}_{{}_{X}},\mathfrak{p}_{{}_{X^{\prime}}})\leq\beta_{1}\end{subarray}}W^{\infty}(\mathcal{M}(X),f(X^{\prime}))\
\ \geq\sup_{\begin{subarray}{c}x,x^{\prime}\in\mathcal{B}:\\\
W^{\infty}(\mathfrak{p}_{{}_{x}},\mathfrak{p}_{{}_{x^{\prime}}})\leq\beta_{1}\end{subarray}}W^{\infty}(\mathcal{M}(x),f(x^{\prime}))\
\ =\sup_{\begin{subarray}{c}x,x^{\prime}\in\mathcal{B}:\\\
\mathfrak{d}_{\mathrm{\mathcal{B}}}(\mathfrak{p}_{{}_{x}},\mathfrak{p}_{{}_{x^{\prime}}})\leq\beta_{1}\end{subarray}}\mathfrak{d}_{\mathrm{\mathcal{C}}}(\mathcal{M}(x),f(x^{\prime})),$

where the inequality holds because considering only point distributions
restricts the set over which we take supremum and the equality holds because
the $\infty$-Wasserstein distance between any two point distributions in any
metric is just the distance between the points on which the distributions are
supported in that metric.

  * •

LHS $\leq$ RHS: Consider any two distributions
$\mathfrak{p}_{{}_{X}},\mathfrak{p}_{{}_{X^{\prime}}}$ over $\mathcal{B}$ s.t.
$W^{\infty}(\mathfrak{p}_{{}_{X}},\mathfrak{p}_{{}_{X^{\prime}}})\leq\beta$.
Let $\phi_{1}$ be the optimal coupling between
$\mathfrak{p}_{{}_{X}},\mathfrak{p}_{{}_{X^{\prime}}}$ such that

$W^{\infty}(\mathfrak{p}_{{}_{X}},\mathfrak{p}_{{}_{X^{\prime}}})\quad=\sup_{(\mathbf{x},\mathbf{x}^{\prime})\leftarrow\phi_{1}}\mathfrak{d}_{\mathrm{\mathcal{B}}}(\mathbf{x},\mathbf{x}^{\prime})\leq\beta_{1}.$

Using $\phi_{1},\mathcal{M},f$, we define a joint distribution $\phi_{2}$ over
$\mathcal{C}\times\mathcal{C}$ as follows: For any ${\bf a,b}\in\mathcal{C}$,
define

$\phi_{2}({\bf a},{\bf
b})\quad:=\sum_{\begin{subarray}{c}\mathbf{x},\mathbf{x}^{\prime}:\\\
\mathcal{M}(\mathbf{x})={\bf a},f(\mathbf{x}^{\prime})={\bf
b}\end{subarray}}\phi_{1}(\mathbf{x},\mathbf{x}^{\prime}).$

It can be verified that $\phi_{2}\in\Phi(\mathcal{M}(X),f(X^{\prime}))$, i.e.,
$\phi_{2}$ is a valid coupling between $\mathcal{M}(X),f(X^{\prime})$. Now

$\displaystyle W^{\infty}(\mathcal{M}(X),f(X^{\prime}))\ \ \leq\sup_{({\bf
a},{\bf b})\leftarrow\phi_{2}}\mathfrak{d}_{\mathrm{\mathcal{C}}}(\bf a,\bf
b)\ \
=\sup_{(\mathbf{x},\mathbf{x}^{\prime})\leftarrow\phi_{1}}\mathfrak{d}_{\mathrm{\mathcal{C}}}(\mathcal{M}(\mathbf{x}),f(\mathbf{x}^{\prime}))\
\
\leq\sup_{\begin{subarray}{c}\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{B}:\\\
\mathfrak{d}_{\mathrm{\mathcal{B}}}(\mathbf{x},\mathbf{x}^{\prime})\leq\beta_{1}\end{subarray}}\mathfrak{d}_{\mathrm{\mathcal{C}}}(\mathcal{M}(\mathbf{x}),f(\mathbf{x}^{\prime})),$

where the last inequality holds because
$\\{(\mathbf{x},\mathbf{x}^{\prime}):(\mathbf{x},\mathbf{x}^{\prime})\leftarrow\phi_{1}\\}\subseteq\\{(\mathbf{x},\mathbf{x}^{\prime}):\mathfrak{d}_{\mathrm{\mathcal{B}}}(\mathbf{x},\mathbf{x}^{\prime})\leq\beta_{1}\\}$.

Note that the RHS of the last inequality does not depend on $X,X^{\prime}$.
So, taking supremum over all distributions $X,X^{\prime}$ such that
$W^{\infty}(\mathfrak{p}_{{}_{X}},\mathfrak{p}_{{}_{X^{\prime}}})\leq\beta_{1}$
gives the required result.

This completes the proof of Lemma 2. $\Box$

##  Appendix D Omitted Details from Section 6.2 – Flexible Accuracy Under
Composition

In this section, we prove Lemma 4.

######  Lemma (Restating Lemma 4).

Suppose $f:A\to B$ has distortion sensitivity $\sigma_{f}$ w.r.t.
$(\mathsf{\partial}_{1},\mathsf{\partial}_{2})$. For all r.v.s $X_{0}$ over
$A$ and $Y$ over $B$ such that
${\widehat{}\mathsf{\partial}}_{2}(f(X_{0}),\mathfrak{p}_{{}_{Y}})\leq\alpha$
for some $\alpha\geq 0$, there must exist a r.v. $X$ over $A$ such that
$Y=f(X)$ and
${\widehat{}\mathsf{\partial}}_{1}(\mathfrak{p}_{{}_{X_{0}}},\mathfrak{p}_{{}_{X}})\leq\sigma_{f}(\alpha)$,
provided $\sigma_{f}(\alpha)$ is finite.

Proof:  Fix random variables $X_{0}$ over $A$ and $Y$ over $B$ such that
${\widehat{}\mathsf{\partial}}_{2}(f(X_{0}),\mathfrak{p}_{{}_{Y}})\leq\alpha$.
Let $\phi$ be an optimal coupling that achieves the infimum in the definition
of ${\widehat{}\mathsf{\partial}}_{2}(f(X_{0}),\mathfrak{p}_{{}_{Y}})$, i.e.,

${\widehat{}\mathsf{\partial}}_{2}(f(X_{0}),\mathfrak{p}_{{}_{Y}})=\sup_{(u,y)\leftarrow\phi}\mathsf{\partial}_{2}(u,y)\leq\alpha.$
(32)

For each $x_{0}\in\mathrm{support}(X_{0})$, consider the conditional
distribution $\phi_{x_{0}}=\phi|\\{X_{0}=x_{0}\\}$. Clearly, the first
marginal of $\phi_{x_{0}}$ is a point distribution supported at $f(x_{0})$.
Let its second marginal be denoted by $\mathfrak{p}_{{}_{Y_{x_{0}}}}$. First
we show that for each $x_{0}\in\mathrm{support}(X_{0})$, we have
${\widehat{}\mathsf{\partial}}_{2}(f(x_{0}),\mathfrak{p}_{{}_{Y_{x_{0}}}})\leq\alpha$.

$\displaystyle{\widehat{}\mathsf{\partial}}_{2}(f(x_{0}),\mathfrak{p}_{{}_{Y_{x_{0}}}})=\inf_{\phi\in\Phi^{0}(f(x_{0}),\mathfrak{p}_{{}_{Y_{x_{0}}}})}\sup_{(u,y)\leftarrow\phi}\mathsf{\partial}_{2}(u,y)\leq\sup_{(u,y)\leftarrow\phi_{x_{0}}}\mathsf{\partial}_{2}(u,y)\overset{\text{(a)}}{\leq}\sup_{(u,y)\leftarrow\phi}\mathsf{\partial}_{2}(u,y)\overset{\text{(b)}}{\leq}\alpha.$

Here $(a)$ follows from the fact that
$\mathrm{support}(\phi_{x_{0}})\subseteq\mathrm{support}(\phi)$ and (b)
follows from (32). Thus for each $x_{0}\in\mathrm{support}(X_{0})$, we have
${\widehat{}\mathsf{\partial}}_{2}(f(x_{0}),\mathfrak{p}_{{}_{Y_{x_{0}}}})\leq\alpha$.
Since $\sigma_{f}(\alpha)$ is finite, by the definition of $\sigma_{f}$, there
exist a r.v. $X_{x_{0}}$ such that

$\displaystyle Y_{x_{0}}$ $\displaystyle=f(X_{x_{0}}),$ (33)
$\displaystyle{\widehat{}\mathsf{\partial}}_{1}(x_{0},\mathfrak{p}_{{}_{X_{x_{0}}}})$
$\displaystyle\leq\sigma_{f}(\alpha).$ (34)

Define
$X=\sum_{x_{0}\in\mathrm{support}(X_{0})}\mathfrak{p}_{{}_{X_{0}}}(x_{0})X_{x_{0}}$.
Now we show that $Y=f(X)$ and
${\widehat{}\mathsf{\partial}}_{1}(\mathfrak{p}_{{}_{X_{0}}},\mathfrak{p}_{{}_{X}})\leq\sigma_{f}(\alpha)$.

  * •

Showing $Y=f(X)$: Note that
$Y=\sum_{x_{0}\in\mathrm{support}(X_{0})}\mathfrak{p}_{{}_{X_{0}}}(x_{0})Y_{x_{0}}$
and
$f(X)=\sum_{x_{0}\in\mathrm{support}(X_{0})}\mathfrak{p}_{{}_{X_{0}}}(x_{0})f(X_{x_{0}})$.
Now the claim follows because because $Y_{x_{0}}=f(X_{x_{0}})$ for each
$x_{0}\in\mathrm{support}(X_{0})$ (from (33)).

  * •

Showing
${\widehat{}\mathsf{\partial}}_{1}(\mathfrak{p}_{{}_{X_{0}}},\mathfrak{p}_{{}_{X}})\leq\sigma_{f}(\alpha)$:
For each $x_{0}\in\mathrm{support}(X_{0})$, let $\psi_{x_{0}}$ be the optimal
coupling that achieves the infimum in the definition of
${\widehat{}\mathsf{\partial}}_{1}(x_{0},\mathfrak{p}_{{}_{X_{x_{0}}}})$. That
is, for each $x_{0}$,
$\psi_{x_{0}}\in\Phi^{0}(x_{0},\mathfrak{p}_{{}_{X_{x_{0}}}})$ and
${\widehat{}\mathsf{\partial}}_{1}(x_{0},\mathfrak{p}_{{}_{X_{x_{0}}}})=\sup_{(a,b)\leftarrow\psi_{x_{0}}}\mathsf{\partial}_{1}(a,b)$.
Let $\psi$ be defined by
$\psi(a,b)=\mathfrak{p}_{{}_{X_{0}}}(x_{0})\psi_{x_{0}}(a,b)$. It is easy to
verify that
$\psi\in\Phi^{0}(\mathfrak{p}_{{}_{X_{0}}},\mathfrak{p}_{{}_{X}})$. Further,

$\displaystyle{\widehat{}\mathsf{\partial}}_{1}(\mathfrak{p}_{{}_{X_{0}}},\mathfrak{p}_{{}_{X}})$
$\displaystyle\leq\sup_{(a,b)\leftarrow\psi}\mathsf{\partial}_{1}(a,b)=\sup_{x_{0}\leftarrow\mathfrak{p}_{{}_{X_{0}}}}\sup_{(a,b)\leftarrow\psi_{x_{0}}}\mathsf{\partial}_{1}(a,b)=\sup_{x_{0}\leftarrow\mathfrak{p}_{{}_{X_{0}}}}{\widehat{}\mathsf{\partial}}_{1}(x_{0},\mathfrak{p}_{{}_{X_{x_{0}}}})\leq\sigma_{f}(\alpha),$

where the last inequality follows from (34).

This completes the proof of Lemma 4. $\Box$

##  Appendix E Proof of Theorem 2 – Differential Privacy Under Composition

######  Theorem (Restating Theorem 2).

Let $\mathcal{M}_{1}:A\to B$ and $\mathcal{M}_{2}:B\to C$ be any two
mechanisms. If $\mathcal{M}_{1}$ is neighborhood-preserving w.r.t.
neighborhood relations $\sim_{A}$ and $\sim_{B}$ over $A$ and $B$,
respectively, and $\mathcal{M}_{2}$ is $(\epsilon,\delta)$-DP w.r.t.
$\sim_{B}$, then $\mathcal{M}_{2}\circ\mathcal{M}_{1}:A\to C$ is
$(\epsilon,\delta)$-DP w.r.t. $\sim_{A}$.

Proof:  For simplicity, we consider the case when $B$ is discrete. The proof
can be generalized to the continuous setting.

Since the mechanism $\mathcal{M}_{1}$ is neighborhood preserving, for
$x,x^{\prime}\in A$ s.t. $x_{1}\sim_{A}x_{2}$, there exists a pair of jointly
distributed random variables $(X_{1},X_{2})$ over $B\times B$ s.t,
$\mathfrak{p}_{{}_{X_{1}}}=\mathcal{M}_{1}(x)$,
$\mathfrak{p}_{{}_{X_{2}}}=\mathcal{M}_{1}(x^{\prime})$ and
$\Pr[X_{1}\sim_{B}X_{2}]=1$. So, for all $(x_{1},x_{2})$ such that
$\mathfrak{p}_{{}_{X_{1},X_{2}}}(x_{1},x_{2})>0$, we have $x_{1}\sim_{B}x_{2}$
and hence, by the $(\epsilon,\delta)$-differential privacy of the mechanism
$\mathcal{M}_{2}$, for all subsets $S\subseteq C$, we have,

$\displaystyle\Pr(\mathcal{M}_{2}(x_{1})\in S)$ $\displaystyle\leq
e^{\epsilon}\Pr(\mathcal{M}_{2}(x_{2})\in S)+\delta.$

Thus, if $x\sim_{A}x^{\prime}$, then for any subset $S\subseteq C$, we have,

$\displaystyle\Pr[\mathcal{M}_{2}(\mathcal{M}_{1}(x))\in S]$
$\displaystyle=\sum_{x_{1}}\mathfrak{p}_{{}_{X_{1}}}(x_{1})\Pr[\mathcal{M}_{2}(x_{1})\in
S]$
$\displaystyle=\sum_{(x_{1},x_{2})}\mathfrak{p}_{{}_{X_{1},X_{2}}}(x_{1},x_{2})\Pr[\mathcal{M}_{2}(x_{1})\in
S]$
$\displaystyle\leq\sum_{(x_{1},x_{2})}\mathfrak{p}_{{}_{X_{1},X_{2}}}(x_{1},x_{2})\left(e^{\epsilon}\Pr[\mathcal{M}_{2}(x_{2})\in
S]+\delta\right)$
$\displaystyle=e^{\epsilon}\left(\sum_{(x_{1},x_{2})}\mathfrak{p}_{{}_{X_{1},X_{2}}}(x_{1},x_{2})\Pr[\mathcal{M}_{2}(x_{2})\in
S]\right)+\delta$
$\displaystyle=e^{\epsilon}\left(\sum_{x_{2}}\mathfrak{p}_{{}_{X_{2}}}(x_{2})\Pr[\mathcal{M}_{2}(x_{2})\in
S]\right)+\delta$
$\displaystyle=e^{\epsilon}\Pr[\mathcal{M}_{2}(\mathcal{M}_{1}(x^{\prime}))\in
S]+\delta$

This completes the proof of Theorem 2. $\Box$

##  Appendix F Details Omitted from Section 6.3 – Shifted-Truncated Laplace
Mechanism

######  Claim (Restating Claim 2).

$\Pr[\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x}^{\prime})\in
S_{0}\cup S_{2}]\leq
e^{(1+\nu)\epsilon}\Pr[\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})\in
S_{0}\cup S_{2}]$, provided
$n\geq\frac{2}{\epsilon\tau}\ln\left(1+\frac{1-e^{-\frac{\epsilon\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}\right)$.

Proof:  First we show that for $\mathbf{s}\in S_{0}\cup S_{2}$, we have,
$\pi_{q^{\prime}}(s_{i^{*}}-x_{i^{*}}^{\prime})\leq
e^{(1+\nu)\epsilon}\pi_{q}(s_{i^{*}}-x_{i^{*}})$, provided
$n\geq\frac{2}{\epsilon\tau}\ln\left(1+\frac{1-e^{-\frac{\epsilon\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}\right)$,
and then we show how this implies the result.

For $\mathbf{s}\in S_{0}$, $\pi_{q^{\prime}}(s_{i^{*}}-x_{i^{*}}^{\prime})=0$
so the inequality trivially holds. For $\mathbf{s}\in S_{2}$, both
$\pi_{q^{\prime}}(s_{i^{*}}-x_{i^{*}}^{\prime})>0$ and
$\pi_{q}(s_{i^{*}}-x_{i^{*}})>0$; hence, we will be done if we show that
$\frac{\pi_{q^{\prime}}(s_{i^{*}}-x_{i^{*}}^{\prime})}{\pi_{q}(s_{i^{*}}-x_{i^{*}})}\leq
e^{(1+\nu)\epsilon}$. Note that we are given the following inequality:

$\displaystyle n$
$\displaystyle\geq\frac{2}{\epsilon\tau}\ln\left(1+\frac{1-e^{-\epsilon\frac{\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}\right),$

which can be rewritten as (which we show in Claim 9 after this proof):

$\displaystyle\ln\left(\frac{1-e^{-\epsilon\frac{\tau(n+1)}{2}}}{1-e^{-\epsilon\frac{\tau
n}{2}}}\right)$ $\displaystyle\leq\epsilon(\nu+\frac{\tau}{2}).$ (35)

By substituting $q=\tau(n+1)$ and $q^{\prime}=\tau n$, (35) is equivalent to

$\frac{1}{\epsilon}\ln\left(\frac{1-e^{-\epsilon\frac{q}{2}}}{1-e^{-\epsilon\frac{q^{\prime}}{2}}}\right)+(1-\frac{\tau}{2})\leq
1+\nu.$

This, using the triangle inequality, implies that

$\frac{1}{\epsilon}\ln\left(\frac{1-e^{-\epsilon\frac{q}{2}}}{1-e^{-\epsilon\frac{q^{\prime}}{2}}}\right)+\left|s_{i^{*}}-x_{i^{*}}+\frac{q}{2}\right|-\left|s_{i^{*}}-x_{i^{*}}+\frac{q}{2}+(1-\frac{\tau}{2})\right|\leq
1+\nu.$

Putting $q^{\prime}=q-\tau$ and $x_{i^{*}}^{\prime}=x_{i^{*}}-1$, we get

$\frac{1}{\epsilon}\ln\left(\frac{1-e^{-\epsilon\frac{q}{2}}}{1-e^{-\epsilon\frac{q^{\prime}}{2}}}\right)+\left|s_{i^{*}}-x_{i^{*}}+\frac{q}{2}\right|-\left|s_{i^{*}}-x_{i^{*}}^{\prime}+\frac{q^{\prime}}{2}\right|\leq
1+\nu.$

By taking exponents of both sides, this is equivalent to showing

$\frac{(1-e^{-\epsilon\frac{q}{2}})}{(1-e^{-\epsilon\frac{q^{\prime}}{2}})}\frac{e^{-\epsilon|s_{i^{*}}-x_{i^{*}}^{\prime}+\frac{q^{\prime}}{2}|}}{e^{-\epsilon|s_{i^{*}}-x_{i^{*}}+\frac{q}{2}|}}\leq
e^{(1+\nu)\epsilon}$

By substituting the values of $\pi_{q}(s_{i^{*}}-x_{i^{*}})$ and
$\pi_{q^{\prime}}(s_{i^{*}}-x_{i^{*}}^{\prime})$, this can be equivalently
written as

$\frac{\pi_{q^{\prime}}(s_{i^{*}}-x_{i^{*}}^{\prime})}{\pi_{q}(s_{i^{*}}-x_{i^{*}})}\leq
e^{(1+\nu)\epsilon}.$ (36)

Now we show
$\Pr[\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x}^{\prime})\in
S_{0}\cup S_{2}]\leq
e^{(1+\nu)\epsilon}\Pr[\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})\in
S_{0}\cup S_{2}]$. Recall that
$\mathcal{G}_{\mathbf{x}}=\mathrm{support}(\mathbf{x})$ for any histogram
$\mathbf{x}\in\mathcal{H}_{\mathcal{G}}$.

$\displaystyle\Pr[\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x}^{\prime})\in
S_{0}\cup S_{2}]$ $\displaystyle=\int_{S_{0}\cup
S_{2}}\big{[}\prod_{i\in\mathcal{G}_{\mathbf{x}^{\prime}}}\pi_{q^{\prime}}(s_{i}-x_{i}^{\prime})\big{]}\,\mathrm{d}\mathbf{s}$
$\displaystyle=\int_{S_{0}\cup
S_{2}}\big{[}\prod_{\begin{subarray}{c}i\in\mathcal{G}_{\mathbf{x}^{\prime}}:i\neq
i^{*}\end{subarray}}\pi_{q^{\prime}}(s_{i}-x_{i}^{\prime})\big{]}\pi_{q^{\prime}}(s_{i^{*}}-x_{i^{*}}^{\prime})\,\mathrm{d}\mathbf{s}$
$\displaystyle\leq\int_{S_{0}\cup
S_{2}}\big{[}\prod_{\begin{subarray}{c}i\in\mathcal{G}_{\mathbf{x}}:i\neq
i^{*}\end{subarray}}\pi_{q}(s_{i}-x_{i})\big{]}e^{(1+\nu)\epsilon}\pi_{q}(s_{i^{*}}-x_{i^{*}})\,\mathrm{d}\mathbf{s}$
(Using (36) and that $x_{i}=x_{i}^{\prime},\forall i\neq i^{*}$)
$\displaystyle=e^{(1+\nu)\epsilon}\int_{S_{0}\cup
S_{2}}\big{[}\prod_{i\in\mathcal{G}_{\mathbf{x}}}\pi_{q}(s_{i}-x_{i})\big{]}\,\mathrm{d}\mathbf{s}$
$\displaystyle=e^{(1+\nu)\epsilon}\Pr[\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})\in
S_{0}\cup S_{2}]$

This completes the proof of Claim 2. $\Box$

######  Claim 9.

$n\geq\frac{2}{\epsilon\tau}\ln\left(1+\frac{1-e^{-\epsilon\frac{\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}\right)\quad\Longleftrightarrow\quad\ln\left(\frac{1-e^{-\epsilon\frac{\tau(n+1)}{2}}}{1-e^{-\epsilon\frac{\tau
n}{2}}}\right)\leq\epsilon(\nu+\frac{\tau}{2}).$

Proof:  We will start with the RHS and show that it is equivalent to the LHS.

$\displaystyle\frac{1-e^{-\epsilon\frac{\tau(n+1)}{2}}}{1-e^{-\epsilon\frac{\tau
n}{2}}}$ $\displaystyle\leq e^{\epsilon(\nu+\frac{\tau}{2})}$
$\displaystyle\Longleftrightarrow 1-e^{-\epsilon\frac{\tau(n+1)}{2}}$
$\displaystyle\leq
e^{\epsilon(\nu+\frac{\tau}{2})}-e^{\epsilon(\nu+\frac{\tau}{2})}e^{-\epsilon\frac{\tau
n}{2}}$ $\displaystyle\Longleftrightarrow 1-e^{-\epsilon\frac{\tau
n}{2}}e^{-\epsilon\frac{\tau}{2}}$ $\displaystyle\leq
e^{\epsilon(\nu+\frac{\tau}{2})}-e^{\epsilon(\nu+\frac{\tau}{2})}e^{-\epsilon\frac{\tau
n}{2}}$ $\displaystyle\Longleftrightarrow e^{-\epsilon\frac{\tau
n}{2}}\left(e^{\epsilon(\nu+\frac{\tau}{2})}-e^{-\epsilon\frac{\tau}{2}}\right)$
$\displaystyle\leq e^{\epsilon(\nu+\frac{\tau}{2})}-1$
$\displaystyle\Longleftrightarrow e^{\epsilon\frac{\tau n}{2}}$
$\displaystyle\geq\frac{e^{\epsilon(\nu+\frac{\tau}{2})}-e^{-\epsilon\frac{\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}$
$\displaystyle\Longleftrightarrow e^{\epsilon\frac{\tau n}{2}}$
$\displaystyle\geq
1+\frac{1-e^{-\epsilon\frac{\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}$
$\displaystyle\Longleftrightarrow n$
$\displaystyle\geq\frac{2}{\epsilon\tau}\ln\left(1+\frac{1-e^{-\epsilon\frac{\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}\right).$

$\Box$

######  Claim (Restating Claim 3).

$\Pr[\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x}^{\prime})\in
S_{1}]\leq\frac{e^{\epsilon}-1}{2(e^{\nicefrac{{\epsilon q}}{{2}}}-1)}$.

Proof:  Observe that, for every $\mathbf{s}\in S_{1}$, we have
$-q^{\prime}\leq s_{i^{*}}-x_{i^{*}}^{\prime}<-q^{\prime}+(1-\tau)$. Recall
that $\mathcal{G}_{\mathbf{x}^{\prime}}=\mathrm{support}(\mathbf{x}^{\prime})$
and $|\mathbf{x}^{\prime}|=n$. Let $|\mathcal{G}_{\mathbf{x}^{\prime}}|=t$ for
some $t\leq n$, and, for simplicity, assume that
$\mathcal{G}_{\mathbf{x}^{\prime}}=\\{1,2,\ldots,t\\}$. For $i\in[t]$, define
$S_{1}(i):=\\{\hat{s}_{i}:\exists\mathbf{s}\in S_{1}\text{ s.t.
}\hat{s}_{i}=s_{i}\\}$, which is equal to the collection of the multiplicity
of $i$ in the histograms in $S_{1}$.

$\displaystyle\Pr[\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x}^{\prime})\in
S_{1}]$
$\displaystyle=\int_{S_{1}}\big{[}\prod_{i=1}^{t}\pi_{q^{\prime}}(s_{i}-x_{i}^{\prime})\big{]}\,\mathrm{d}\mathbf{s}$
$\displaystyle=\int_{S_{1}(1)}\ldots\int_{S_{1}(i^{*})}\ldots\int_{S_{1}(t)}\big{[}\prod_{i=1}^{t}\pi_{q^{\prime}}(s_{i}-x_{i}^{\prime})\big{]}\,\mathrm{d}s_{t}\ldots\,\mathrm{d}s_{i^{*}}\ldots\,\mathrm{d}s_{1}$
$\displaystyle=\int_{S_{1}(i^{*})}\pi_{q^{\prime}}(s_{i^{*}}-x_{i^{*}}^{\prime})\underbrace{\bigg{(}\int_{S_{1}(1)}\ldots\int_{S_{1}(t)}\big{[}\prod_{\begin{subarray}{c}i=1:i\neq
i^{*}\end{subarray}}^{t}\pi_{q^{\prime}}(s_{i}-x_{i}^{\prime})\big{]}\,\mathrm{d}s_{t}\ldots\,\mathrm{d}s_{1}\bigg{)}}_{\leq\
1}\,\mathrm{d}s_{i^{*}}$
$\displaystyle\leq\int_{S_{1}(i^{*})}\pi_{q^{\prime}}(s_{i^{*}}-x_{i^{*}}^{\prime})\,\mathrm{d}s_{i^{*}}$
$\displaystyle=\int_{q^{\prime}}^{q^{\prime}+(1-\tau)}\pi_{q^{\prime}}(z)\,\mathrm{d}z$
$\displaystyle=\frac{e^{(1-\tau)\epsilon}-1}{2(1-e^{-\epsilon
q/2})}e^{-\epsilon\nicefrac{{q}}{{2}}}$
$\displaystyle\leq\frac{e^{\epsilon}-1}{2(e^{\epsilon\nicefrac{{q}}{{2}}}-1)}.$
(Since $\tau>0$)

This proves Claim 3. $\Box$

######  Lemma 11.

For any $\nu,\epsilon>0$ and $\mathbf{x}$ such that
$\epsilon\nu>\ln\left(1+\frac{1}{|\mathbf{x}|}\right)$,
$\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}$ is
$\left((1+\nu)\epsilon,\frac{e^{\epsilon}-1}{2(e^{\nicefrac{{\epsilon
q}}{{2}}}-1)}\right)$-DP w.r.t. $\sim_{\mathrm{hist}}$, where
$q=\tau|\mathbf{x}|$.

Proof:  We use Lemma 5 and put a restriction that $\nu$ should be $>0$. We
will analyze the effect of this restriction on the bound of $|\mathbf{x}|$. We
restate the bound on $|\mathbf{x}|$ here again for convenience:

$|\mathbf{x}|\geq\frac{2}{\epsilon\tau}\ln\left(1+\frac{1-e^{-\epsilon\frac{\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}\right)$

It can be easily checked that for any fixed $\epsilon,\nu>0$, the RHS is a
decreasing function of $\tau$. Hence, if we set $\tau$ to its minimum value,
we get a lower bound on $|\mathbf{x}|$ which is independent of $\tau$. Since
this expression is not defined at $\tau=0$, we will take its one-sided limit
as $\tau\rightarrow 0^{+}$, i.e.,

$\displaystyle\lim_{\tau\rightarrow
0^{+}}\frac{2}{\epsilon\tau}\ln\left(1+\frac{1-e^{-\epsilon\frac{\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}\right)$

We will replace $\frac{\epsilon\tau}{2}$ with $l$. As $\tau\rightarrow 0^{+}$,
$l\rightarrow 0^{+}$, and we get

$\displaystyle\lim_{\tau\rightarrow
0^{+}}\frac{2}{\epsilon\tau}\ln\left(1+\frac{1-e^{-\epsilon\frac{\tau}{2}}}{e^{\epsilon(\nu+\frac{\tau}{2})}-1}\right)$
$\displaystyle=\lim_{l\rightarrow
0^{+}}\frac{1}{l}\ln\left(1+\frac{1-e^{-l}}{e^{\epsilon\nu+l}-1}\right)$
$\displaystyle=\lim_{l\rightarrow
0^{+}}\frac{1}{l}\ln\left(1+\frac{1-e^{-l}}{e^{\epsilon\nu+l}-1}\right)\left(\frac{1-e^{-l}}{e^{\epsilon\nu+l}-1}\right)\left(\frac{e^{\epsilon\nu+l}-1}{1-e^{-l}}\right)$
$\displaystyle=\lim_{l\rightarrow
0^{+}}\left(\frac{1}{e^{\epsilon\nu+l}-1}\right)\left(\frac{1-e^{-l}}{l}\right)\left(\frac{\ln\left(1+\frac{1-e^{-l}}{e^{\epsilon\nu+l}-1}\right)}{\frac{1-e^{-l}}{e^{\epsilon\nu+l}-1}}\right)$
$\displaystyle=\frac{1}{e^{\epsilon\nu}-1}$ ($\lim_{x\rightarrow
0^{+}}\frac{1-e^{-x}}{x}=1$; $\lim_{x\rightarrow 0^{+}}\frac{\ln(1+x)}{x}=1$)

We have proved that on inputs $\mathbf{x}$ s.t.
$|\mathbf{x}|>\frac{1}{e^{\epsilon\nu}-1}$, which is equivalent to the
condition that $\epsilon\nu>\ln\left(1+\frac{1}{|\mathbf{x}|}\right)$,
$\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}$ is
$\left((1+\nu)\epsilon,\frac{e^{\epsilon}-1}{2(e^{\nicefrac{{\epsilon
q}}{{2}}}-1)}\right)$-DP w.r.t. $\sim_{\mathrm{hist}}$, where
$q=\tau|\mathbf{x}|$. $\Box$

##  Appendix G Details Omitted from Section 6.4 – Bucketed Histogram Mechanism

######  Claim (Restating Claim 4).

$\mathcal{M}_{\mathrm{buc}}^{w,[0,B)}$ is
$\left(0,\frac{w}{2},0\right)$-accurate for the identity function
$f_{\emph{id}}$ over $\mathcal{H}_{[0,B)}$ w.r.t the metric
$\mathfrak{d}_{\mathrm{hist}}$.

Proof:  Since both $f_{\text{id}}$ and $\mathcal{M}_{\mathrm{buc}}^{w,[0,B)}$
are deterministic maps, on any input $\mathbf{x}\in\mathcal{H}_{[0,B)}$, we
denote $\mathbf{x}$ (as the output of $f_{\text{id}}(\mathbf{x})$) and
$\mathcal{M}_{\mathrm{buc}}^{w,[0,B)}$ as point distributions over
$\mathcal{H}_{[0,B)}$. Now, in order to prove the claim, we need to show that
$W^{\infty}(\mathcal{M}_{\mathrm{buc}}^{w,[0,B)}(\mathbf{x}),\mathbf{x})\leq\frac{w}{2}$
holds for any $\mathbf{x}\in\mathcal{H}_{[0,B)}$.

Fix any $\mathbf{x}\in\mathcal{H}_{[0,B)}$ and define
$\mathbf{y}:=\mathcal{M}_{\mathrm{buc}}^{w,[0,B)}(\mathbf{x})$. Since
$\mathbf{x},\mathbf{y}$ are point distributions and the underlying metric is
$\mathfrak{d}_{\mathrm{hist}}$, we have
$W^{\infty}(\mathbf{y},\mathbf{x})=\mathfrak{d}_{\mathrm{hist}}(\mathbf{y},\mathbf{x})$,
where $\mathfrak{d}_{\mathrm{hist}}$ is defined as
$\mathfrak{d}_{\mathrm{hist}}(\mathbf{y},\mathbf{x})=W^{\infty}(\frac{\mathbf{y}}{|\mathbf{y}|},\frac{\mathbf{x}}{|\mathbf{x}|})$.
Since $\mathbf{y}$ is a deterministic function of $\mathbf{x}$,
$W^{\infty}(\frac{\mathbf{y}}{|\mathbf{y}|},\frac{\mathbf{x}}{|\mathbf{x}|})$
is upper bounded by the maximum distance any point in $\mathbf{x}$ moves to
form $\mathbf{y}$, which is equal to the the maximum distance of the center of
a bucket from any point in that bucket, which is $\frac{w}{2}$. $\Box$

######  Claim (Restating Claim 5).

For any $\mathbf{x}\in\mathcal{H}_{\mathcal{G}}$, if $\mathbf{z}$ is
$\alpha$-distorted from $\mathbf{x}$, then $f_{\phi}(\mathbf{z})$ is
$\alpha$-distorted from $\mathbf{x}^{\prime}$.

Proof:  We need to show two things: (i)
$f_{\phi}(\mathbf{z})(b)\leq\mathbf{x}^{\prime}(b)$ holds for every
$b\in\mathcal{G}$, and (ii)
$\sum_{b\in\mathcal{G}}f_{\phi}(\mathbf{z})(b)\geq(1-\alpha)\sum_{b\in\mathcal{G}}\mathbf{x}^{\prime}(b)$.
The first condition holds because $\mathbf{z}(a)\leq\mathbf{x}(a),\forall
a\in\mathcal{G}$ (since $\mathbf{z}$ is $\alpha$-distorted from $\mathbf{x}$)
and that
$\sum_{a\in\mathcal{G}}\phi(a,b)=\frac{\mathbf{x}^{\prime}(b)}{|\mathbf{x}^{\prime}|}$.
For the second condition,

$\displaystyle\sum_{b\in\mathcal{G}}f_{\phi}(\mathbf{z})(b)$
$\displaystyle=\sum_{b\in\mathcal{G}}|\mathbf{x}^{\prime}|\sum_{a\in\mathcal{G}}\frac{\mathbf{z}(a)\phi(a,b)}{\mathbf{x}(a)}=|\mathbf{x}^{\prime}|\sum_{a\in\mathcal{G}}\frac{\mathbf{z}(a)}{\mathbf{x}(a)}\sum_{b\in\mathcal{G}}\phi(a,b)\stackrel{{\scriptstyle\text{(a)}}}{{=}}\frac{|\mathbf{x}^{\prime}|}{|\mathbf{x}|}\sum_{a\in\mathcal{G}}\mathbf{z}(a)\stackrel{{\scriptstyle\text{(b)}}}{{\geq}}(1-\alpha)|\mathbf{x}^{\prime}|,$
(37)

where (a) follows from
$\sum_{b\in\mathcal{G}}\phi(a,b)=\frac{\mathbf{x}(a)}{|\mathbf{x}|}$ and (b)
follows because $\mathbf{z}$ is $\alpha$-distorted from $\mathbf{x}$, which
implies that
$\sum_{a\in\mathcal{G}}\mathbf{z}(a)=|\mathbf{z}|\geq(1-\alpha)|\mathbf{x}|$.
Therefore, $f_{\phi}(\mathbf{z})$ is $\alpha$-distorted from
$\mathbf{x}^{\prime}$. $\Box$

######  Claim (Restating Claim 6).

$\widehat{\partial}_{\emph{drop}}(\mathbf{x}^{\prime},\mathfrak{p}_{{}_{Y}})\leq\alpha$.

Proof:  Note that the support of
$\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})$ is the
set of all $\alpha$-distorted histograms from $\mathbf{x}$. We have shown in
Claim 5 that for any $\mathbf{z}\in\mathcal{H}_{\mathcal{G}}$ such that
$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{z})\leq\alpha$, we have
$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x}^{\prime},f_{\phi}(\mathbf{z}))\leq\alpha$.
This implies that
$\sup_{\mathbf{y}\in\mathrm{support}(f_{\phi}(\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})))}\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x}^{\prime},\mathbf{y})\leq\alpha$,
which in turn implies that
$\widehat{\partial}_{\text{drop}}(\mathbf{x}^{\prime},\mathfrak{p}_{{}_{Y}})\leq\alpha$.
$\Box$

######  Claim (Restating Claim 7).

$W^{\infty}(\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x}),\mathfrak{p}_{{}_{Y}})\leq\beta$.

Proof:  Define a coupling $\phi_{\mathbf{x}}$ of
$\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})$ and
$\mathfrak{p}_{{}_{Y}}$ over
$\mathcal{H}_{\mathcal{G}}\times\mathcal{H}_{\mathcal{G}}$ as follows:

$\phi_{\mathbf{x}}(\mathbf{z},\mathbf{y}):=\begin{cases}\Pr[\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})=\mathbf{z}]&\text{
if }\mathbf{y}=f_{\phi}(\mathbf{z}),\\\ 0&\text{ otherwise}.\end{cases}$

It is easy to verify that the above defined $\phi_{\mathbf{x}}$ is a valid
coupling of
$\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})$ and
$\mathfrak{p}_{{}_{Y}}$, i.e., its first marginal is equal to
$\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})$ and the
second marginal is equal to $\mathfrak{p}_{{}_{Y}}$. Note that
$\phi_{\mathbf{x}}(\mathbf{z},\mathbf{y})$ is non-zero only when
$\mathbf{y}=f_{\phi}(\mathbf{z})$. This implies that

$W^{\infty}(\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x}),\mathfrak{p}_{{}_{Y}})\leq\sup_{(\mathbf{z},\mathbf{y})\leftarrow\phi_{\mathbf{x}}}\mathfrak{d}_{\mathrm{hist}}(\mathbf{z},\mathbf{y})=\sup_{(\mathbf{z},f_{\phi}(\mathbf{z}))\leftarrow\phi_{\mathbf{x}}}\mathfrak{d}_{\mathrm{hist}}(\mathbf{z},f_{\phi}(\mathbf{z}))\leq\beta,$

where the last inequality follows from Claim 10 (stated and proven below) and
using the fact that
$\mathbf{z}\sim\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,\mathcal{G}}(\mathbf{x})$
is $\alpha$-distorted from $\mathbf{x}$. $\Box$

######  Claim 10.

Let $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{H}_{\mathcal{G}}$ be such that
$\mathfrak{d}_{\mathrm{hist}}(\mathbf{x},\mathbf{x}^{\prime})\leq\beta$. Then,
for any $\mathbf{z}$ that is $\alpha$-distorted from $\mathbf{x}$, we have
$\mathfrak{d}_{\mathrm{hist}}(\mathbf{z},f_{\phi}(\mathbf{z}))\leq\mathfrak{d}_{\mathrm{hist}}(\mathbf{x},\mathbf{x}^{\prime})\leq\beta$.

Proof:  Define
$\phi^{\prime}(a,b)=\frac{\mathbf{z}(a)|\mathbf{x}|\phi(a,b)}{\mathbf{x}(a)|\mathbf{z}|}$.
For any $a\in\mathcal{G}$, its first marginal is equal to
$\sum_{b\in\mathcal{G}}\phi^{\prime}(a,b)=\frac{\mathbf{z}(a)}{|\mathbf{z}|}$.
For any $b\in\mathcal{G}$, its second marginal is equal to
$\sum_{a\in\mathcal{G}}\phi^{\prime}(a,b)=\frac{|\mathbf{x}|}{|\mathbf{z}|}\sum_{a\in\mathcal{G}}\frac{\mathbf{z}(a)}{\mathbf{x}(a)}\phi(a,b)=\frac{|\mathbf{x}|}{|\mathbf{x}^{\prime}||\mathbf{z}|}f_{\phi}(\mathbf{z})(b)$.
We would like to say that the quantity on the RHS is equal to
$\frac{f_{\phi}(\mathbf{z})(b)}{|f_{\phi}(\mathbf{z})|}$. We show this as
follows: Since $|\mathbf{z}|\geq(1-\alpha)|\mathbf{x}|$, there exists $c\geq
0$ such that $|\mathbf{z}|=(1-\alpha+c)|\mathbf{x}|$. If we put this instead
of $|\mathbf{z}|\geq(1-\alpha)|\mathbf{x}|$ in (37), we would get
$\sum_{b\in\mathcal{G}}f_{\phi}(\mathbf{z})(b)=(1-\alpha+c)|\mathbf{x}^{\prime}|$.
With these substitutions, we get
$\frac{|\mathbf{x}|}{|\mathbf{x}^{\prime}||\mathbf{z}|}f_{\phi}(\mathbf{z})(b)=\frac{f_{\phi}(\mathbf{z})(b)}{\sum_{b\in\mathcal{G}}f_{\phi}(\mathbf{z})(b)}$,
which implies that the second marginal of $\phi^{\prime}$ is equal to
$\sum_{a\in\mathcal{G}}\phi^{\prime}(a,b)=\frac{f_{\phi}(\mathbf{z})(b)}{|f_{\phi}(\mathbf{z})|}$
for any $b\in\mathcal{G}$.

This means that $\phi^{\prime}(a,b)$ is a valid coupling of
$\mathbf{z},f_{\phi}(\mathbf{z})$. This implies that

$\displaystyle\mathfrak{d}_{\mathrm{hist}}(\mathbf{z},f_{\phi}(\mathbf{z}))=W^{\infty}(\mathbf{z},f_{\phi}(\mathbf{z}))\leq\sup_{\begin{subarray}{c}(a^{\prime},b^{\prime})\leftarrow\phi^{\prime}\end{subarray}}\mathfrak{d}_{\mathrm{\mathcal{G}}}(a^{\prime},b^{\prime})\stackrel{{\scriptstyle\text{(c)}}}{{\leq}}\sup_{\begin{subarray}{c}(a^{\prime},b^{\prime})\leftarrow\phi\end{subarray}}\mathfrak{d}_{\mathrm{\mathcal{G}}}(a^{\prime},b^{\prime})=\mathfrak{d}_{\mathrm{hist}}(\mathbf{x},\mathbf{x}^{\prime})\leq\beta,$

where (c) holds because
$\text{support}(\phi^{\prime})\subseteq\text{support}(\phi)$ (by the
definition of $\phi^{\prime}$). $\Box$

##  Appendix H $d$-Dimensional Analogues of our Mechanisms/Results

In our $d$-dimensional bucketing mechanism for $\mathcal{G}=[0,B)^{d}$, we
divide $[0,B)^{d}$ into $t=\lceil\frac{B}{w}\rceil^{d}$ $d$-dimensional cubes
(buckets), each of side length $w$, and map each input point to the center of
the nearest cube (bucket). Note that the distance between any point in
$[0,B)^{d}$ to the center of the nearest bucket is $\frac{w}{2}\sqrt{d}$. In
the following, we will ignore the ceil/floor for simplicity.

Algorithm 4 Bucketing Mechanism over $[0,B)^{d}$,
$\mathcal{M}_{\mathrm{buc}}^{w,[0,B)^{d}}$

Parameter: Bucket (which is $d$-dimensional cube) side length $w$, ground set
$[0,B)^{d}$.
Input: A histogram $\mathbf{x}$ over $[0,B)$.
Output: A histogram $\mathbf{y}$ over $S=T^{d}$ where
$T=\\{w(i-\frac{1}{2}):i\in[t],t=\lceil\frac{B}{w}\rceil\\}$, and
$|\mathbf{y}|=|\mathbf{x}|$.

1:for all $s\in S$ do

2:
$\mathbf{y}(s):=\sum_{g:g-s\in[\frac{-w}{2},\frac{w}{2})^{d}}\;\mathbf{x}(g)$

3:end for

4:Return $\mathbf{y}$

Algorithm 5 BucketHist Mechanism over $[0,B)^{d}$,
$\mathcal{M}_{\mathrm{BucHist}}^{\alpha,\beta,[0,B)^{d}}$

Parameter: Accuracy parameters $\alpha,\beta$; ground set $[0,B)^{d}$.
Input: A histogram $\mathbf{x}$ over $[0,B)^{d}$.
Output: A histogram $\mathbf{y}$ over $[0,B)^{d}$.

1:$w:=2\beta$, $t:=\lceil\frac{B}{w}\rceil^{d}$, $\tau:=\alpha/t$

2:Return
$\mathcal{M}_{\mathrm{STLap}}^{\tau,\epsilon,[0,B)^{d}}\circ\mathcal{M}_{\mathrm{buc}}^{w,[0,B)^{d}}(\mathbf{x})$
$\triangleright$ where $\mathcal{M}_{\mathrm{buc}}^{w,[0,B)}$ is in Algorithm
4

Our $d$-dimensional bucketing mechanism
$\mathcal{M}_{\mathrm{buc}}^{w,[0,B)^{d}}$ and the final $d$-dimensional
bucketed-histogram mechanism
$\mathcal{M}_{\mathrm{BucHist}}^{\alpha,\beta,[0,B)^{d}}$ are presented in
Algorithm 4 and Algorithm 5, respectively.

As mentioned in Remark 5 in Section 5.3, with these modified mechanisms, all
our results in Theorem 4, Theorem 5, and Theorem 6 will hold verbatim, except
for the value of $\tau$, which will be replaced by
$\tau=\alpha(\frac{2\beta}{B\sqrt{d}})^{d}$. Note that for the one dimensional
case, we have $\tau=\frac{\alpha}{t}=\alpha(\frac{w}{B})$, where $w=2\beta$,
which comes from the $(0,\frac{w}{2},0)$-accuracy of the bucketing mechanism
$\mathcal{M}_{\mathrm{buc}}^{w,[0,B)}$ (see Claim 4 in Section 6.4). The
$d$-dimensional analogue of that result is stated in the following claim which
can be proven along the lines of the proof of Claim 4..

######  Claim 11.

$\mathcal{M}_{\mathrm{buc}}^{w,[0,B)^{d}}$ is
$\left(0,\frac{w}{2}\sqrt{d},0\right)$-accurate for the identity function
$f_{\emph{id}}$ over $\mathcal{H}_{[0,B)^{d}}$ w.r.t the metric
$\mathfrak{d}_{\mathrm{hist}}$.

It follows from Claim 11 that the output error of
$\mathcal{M}_{\mathrm{buc}}^{w,[0,B)^{d}}$ is $\beta=\frac{w}{2}\sqrt{d}$.
This implies
$\tau=\frac{\alpha}{t}=\alpha(\frac{w}{B})^{d}=\alpha(\frac{2\beta}{B\sqrt{d}})^{d}$.

##  Appendix I Details Omitted from Section 3.1

In this section, first we prove that ${\widehat{}\mathsf{\partial}}$ is a
quasi-metric (assuming that $\mathsf{\partial}$ is a quasi-metric), and then
prove that our two distortions $\mathsf{\partial}_{\mathrm{move}}$ and
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}$ (defined in (4) and (5),
respectively) are metric and quasi-metric, respectively.

######  Lemma 12.

If $\mathsf{\partial}$ is a quasi-metric, then ${\widehat{}\mathsf{\partial}}$
is a quasi-metric.

Proof:  We need to show that for any three distributions $P$, $Q$, and $R$
over the same space $A$, we have (i) ${\widehat{}\mathsf{\partial}}(P,Q)\geq
0$, where the equality holds if and only if $P=Q$, and (ii)
${\widehat{}\mathsf{\partial}}$ satisfies the triangle inequality:
${\widehat{}\mathsf{\partial}}(P,Q)\leq{\widehat{}\mathsf{\partial}}(P,R)+{\widehat{}\mathsf{\partial}}(R,Q)$.
We show them one by one below:

  1. 1.

The first property follows from the definition of
${\widehat{}\mathsf{\partial}}$ (see Definition 2): If
${\widehat{}\mathsf{\partial}}(P,Q)=0$, then the optimal $\phi\in\Phi(P,Q)$ is
a diagonal distribution, which means that $P=Q$. On the other hand, if $P=Q$,
then there exists a coupling $\phi$ in $\Phi(P,Q)$, which is a diagonal
distribution and hence ${\widehat{}\mathsf{\partial}}(P,Q)=0$.

  2. 2.

Since the definition of ${\widehat{}\mathsf{\partial}}$ is the same as that of
$W^{\infty}$, except for that the former is defined w.r.t. a quasi-metric,
whereas, the latter is defined w.r.t. a metric, we can show the triangle
inequality for ${\widehat{}\mathsf{\partial}}$ along the lines of the proof of
Lemma 7. Note that we did not use the symmetric property of $W^{\infty}$ while
proving Lemma 7; we only used that the underlying metric $\mathfrak{d}$
satisfies the triangle inequality, which also holds for
${\widehat{}\mathsf{\partial}}$ which is a quasi-metric.

This completes the proof of Lemma 12. $\Box$

In Section 3.1, we introduced two new distortions:
$\mathsf{\partial}_{\mathrm{move}}(\mathbf{x},\mathbf{y})$ in (4) and
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{y})$ in (5). We
prove that $\mathsf{\partial}_{\mathrm{move}}$ is a metric in Claim 12 and
that $\mathsf{\partial}_{\mathrm{drmv}}^{\eta}$ is a metric in Claim 13. We
present the definitions of these distortions here again for convenience:

$\displaystyle\mathsf{\partial}_{\mathrm{move}}(\mathbf{x},\mathbf{y})$
$\displaystyle=\begin{cases}W^{\infty}(\frac{\mathbf{x}}{|\mathbf{x}|},\frac{\mathbf{y}}{|\mathbf{y}|})&\text{
if }|\mathbf{x}|=|\mathbf{y}|\\\ \infty&\text{ otherwise}\end{cases}$
$\displaystyle\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{y})=\inf_{\mathbf{z}}\left(\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{z})+\eta\cdot\mathsf{\partial}_{\mathrm{move}}(\mathbf{z},\mathbf{y})\right).$

Note that in the definition of $\mathsf{\partial}_{\mathrm{move}}$, when
$|\mathbf{x}|=|\mathbf{y}|=0$, we define
$\mathsf{\partial}_{\mathrm{move}}(\mathbf{x},\mathbf{y})=0$.

######  Claim 12.

$\mathsf{\partial}_{\mathrm{move}}(\cdot,\cdot)$ is a metric.

Proof:  Since $\mathsf{\partial}_{\mathrm{move}}(\cdot,\cdot)$ is defined as
the $\infty$-Wasserstein distance between normalized histograms, it suffices
to show that the $\infty$-Wasserstein distance is a metric. We need to show
three things for any triple of distributions $P,Q,R$ over a metric space
$(\Omega,\mathfrak{d})$: (i) $W^{\infty}(P,Q)\geq 0$ and equality holds if and
only if $P=Q$, (ii) $W^{\infty}(P,Q)=W^{\infty}(Q,P)$, and (iii)
$W^{\infty}(P,R)\leq W^{\infty}(P,Q)+W^{\infty}(Q,R)$.

By definition, $W^{\infty}(P,R)=\inf_{\phi\in\Phi(P,R)}\sup_{(x,z):\\\
\phi(x,z)\neq 0}\mathfrak{d}(x,z)$. Now, the first two conditions follow
because $\mathfrak{d}$ is a metric, and the last condition (triangle
inequality) we show in Lemma 7 in Appendix A.1.

Note that when $|\mathbf{x}|=|\mathbf{y}|=0$, the Wasserstein distance is
undefined, but we have defined
$\mathsf{\partial}_{\mathrm{move}}(\mathbf{x},\mathbf{y})$ in this case
separately as $0$ which is consistent with the properties of a metric. $\Box$

We first give an intermediate result (Lemma 13 below) which will be used in
proving that $\mathsf{\partial}_{\mathrm{drmv}}^{\eta}$ is a quasi-metric. The
result of this lemma is also used in the proof of Theorem 6.

######  Lemma 13.

Let $\mathbf{x}$, $\mathbf{y}$ and $\mathbf{z}$ be any three histograms over a
ground set $\mathcal{G}$ ,associated with a metric $\mathfrak{d}$, such that
$\mathsf{\partial}_{\mathrm{move}}(\mathbf{x},\mathbf{z})=\alpha_{1}$ and
$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{z},\mathbf{y})=\alpha_{2}$ with
$\alpha_{1}\geq 0$ and $\alpha_{2}<1$. Then there exists a histogram
$\mathbf{s}$ such that
$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{s})=\alpha_{2}$ and
$\mathsf{\partial}_{\mathrm{move}}(\mathbf{s},\mathbf{y})\leq\alpha_{1}$.

Proof:  Using the definitions of $\mathsf{\partial}_{\mathrm{drop}}$ and
$\mathsf{\partial}_{\mathrm{move}}$, we have the following:

  1. Z.1

$|\mathbf{x}|=|\mathbf{z}|$

  2. Z.2

$W^{\infty}(\frac{\mathbf{x}}{|\mathbf{x}|},\frac{\mathbf{z}}{|\mathbf{z}|})\leq\alpha_{1}$.
We will use $\phi_{z}$ to denote the optimal joint distribution which achieves
the infimum in the definition of
$W^{\infty}(\frac{\mathbf{x}}{|\mathbf{x}|},\frac{\mathbf{z}}{|\mathbf{z}|})$.

  3. Z.3

$|\mathbf{y}|=(1-\alpha_{2})|\mathbf{z}|$

  4. Z.4

For all $g\in\mathcal{G}$, $0\leq\mathbf{y}(g)\leq\mathbf{z}(g)$

Now we want to prove the existence of a histogram $\mathbf{s}$ with the
following property:

  1. S.1

$|\mathbf{s}|=(1-\alpha_{2})|\mathbf{x}|$

  2. S.2

For all $g\in\mathcal{G}$, $0\leq\mathbf{s}(g)\leq\mathbf{x}(g)$

  3. S.3

$|\mathbf{s}|=|\mathbf{y}|$

  4. S.4

$W^{\infty}(\frac{\mathbf{s}}{|\mathbf{s}|},\frac{\mathbf{y}}{|\mathbf{y}|})\leq\alpha_{1}$.

Consider the following joint distribution $\phi_{s}$:

$\phi_{s}(g_{x},g_{y})=\begin{cases}\frac{1}{1-\alpha_{2}}\phi_{z}(g_{x},g_{y})\frac{\mathbf{y}(g_{y})}{\mathbf{z}(g_{y})}&\text{if
}\mathbf{z}(g_{y})>0\\\ 0&\text{otherwise}\end{cases}$ (38)

We denote the first marginal of $\phi_{s}$ by
$\frac{\mathbf{s}}{|\mathbf{s}|}$, where $\mathbf{s}$ corresponds to the
histogram that we want to show exists.

By definition, for all $g_{x},g_{y}\in\mathcal{G}$, we have
$\phi_{s}(g_{x},g_{y})\geq 0$. Also note that, if $\mathbf{z}(g_{y})=0$, then
for all $g_{x}\in\mathcal{G}$, we have $\phi_{z}(g_{x},g_{y})=0$; this is
because $\frac{\mathbf{z}}{|\mathbf{z}|}$ is the second marginal of
$\phi_{z}$. Now we show that the above-defined $\phi_{s}$ satisfies properties
S.1-S.4 – we show these in the sequence of S.4, S.3, S.1, S.2.

  * •

Proof of S.4. Note that the first marginal of $\phi_{s}$ is assumed to be
$\frac{\mathbf{s}}{|\mathbf{s}|}$. Now we show that its second marginal is
$\frac{\mathbf{y}}{|\mathbf{y}|}$ and that
$\max_{(g_{x},g_{y})\leftarrow\phi_{s}}\mathfrak{d}(g_{x},g_{y})\leq\alpha_{1}$.
Note that these together imply that
$W^{\infty}(\frac{\mathbf{s}}{|\mathbf{s}|},\frac{\mathbf{y}}{|\mathbf{y}|})\leq\alpha_{1}$.

    * –

Second marginal of $\phi_{s}$ is $\frac{\mathbf{y}}{|\mathbf{y}|}$: We show it
in two parts, first for $g_{y}\in\mathcal{G}$ for which $\mathbf{z}(g_{y})=0$
and then for the rest of the $g_{y}\in\mathcal{G}$. Note that when
$\mathbf{z}(g_{y})=0$, we have from Z.4 that $\mathbf{y}(g_{y})=0$. Now we
show that $\int_{\mathcal{G}}\phi_{s}(g_{x},g_{y})\,\mathrm{d}g_{x}=0$. It
follows from (38) that for all $g_{y}$ such that $\mathbf{z}(g_{y})=0$, we
have $\phi_{s}(g_{x},g_{y})=0,\forall g_{x}\in\mathcal{G}$, which implies that
$\int_{\mathcal{G}}\phi_{s}(g_{x},g_{y})\,\mathrm{d}g_{x}=0$. Now we analyze
the case when $\mathbf{z}(g_{y})>0$.

$\displaystyle\int_{\mathcal{G}}\phi_{s}(g_{x},g_{y})\,\mathrm{d}g_{x}$
$\displaystyle=\int_{\mathcal{G}}\frac{1}{1-\alpha_{2}}\phi_{z}(g_{x},g_{y})\frac{\mathbf{y}(g_{y})}{\mathbf{z}(g_{y})}\,\mathrm{d}g_{x}$
(using (38))
$\displaystyle=\frac{1}{1-\alpha_{2}}\frac{\mathbf{y}(g_{y})}{\mathbf{z}(g_{y})}\int_{\mathcal{G}}\phi_{z}(g_{x},g_{y})\,\mathrm{d}g_{x}$
$\displaystyle=\frac{1}{1-\alpha_{2}}\frac{\mathbf{y}(g_{y})}{\mathbf{z}(g_{y})}\frac{\mathbf{z}(g_{y})}{|\mathbf{z}|}$
(using Z.2)
$\displaystyle=\frac{\mathbf{y}(g_{y})}{(1-\alpha_{2})|\mathbf{z}|}$
$\displaystyle=\frac{\mathbf{y}(g_{y})}{|\mathbf{y}|}.$ (Using Z.3)

    * –

$W^{\infty}(\frac{\mathbf{s}}{|\mathbf{s}|},\frac{\mathbf{y}}{|\mathbf{y}|})\leq\alpha_{1}$:
We have shown that the first and the second marginals of $\phi_{s}$ are
$\frac{\mathbf{s}}{|\mathbf{s}|}$ and $\frac{\mathbf{y}}{|\mathbf{y}|}$,
respectively. So, it suffices to show that
$\max_{(g_{x},g_{y})\leftarrow\phi_{s}}\mathfrak{d}(g_{x},g_{y})\leq\alpha_{1}$.
Consider any pair $(g_{x},g_{y})\in\mathcal{G}^{2}$ s.t.
$\phi_{s}(g_{x},g_{y})>0$. This is possible only if $\phi_{z}(g_{x},g_{y})>0$
(see (38)), which, when combined with Z.2, gives
$\mathfrak{d}(g_{x},g_{y})\leq\alpha_{1}$. Hence, for any pair
$(g_{x},g_{y})\in\mathcal{G}^{2}$ s.t. $\phi_{s}(g_{x},g_{y})>0$, we have
$\mathfrak{d}(g_{x},g_{y})\leq\alpha_{1}$.

  * •

Proof of S.3. Note that (38) gives the normalized $\mathbf{s}$, but we still
have the freedom to choose $|\mathbf{s}|$. To satisfy S.3, we set
$|\mathbf{s}|=|\mathbf{y}|$.

  * •

Proof of S.1. Note that S.1 is already satisfied using Z.1, Z.3, and S.3.

  * •

Proof of S.2. Let us denote $\\{g\in\mathcal{G}\ |\ \mathbf{z}(g)>0\\}$ by
$\mathcal{G}_{z}$. We will show that for any $g\in\mathcal{G}$, we have
$\mathbf{x}(g)-\mathbf{s}(g)\geq 0$:

$\displaystyle\mathbf{x}(g)-\mathbf{s}(g)$
$\displaystyle=|\mathbf{x}|\int_{\mathcal{G}}\phi_{z}(g,g_{y})\,\mathrm{d}g_{y}-|\mathbf{s}|\int_{\mathcal{G}}\phi_{s}(g,g_{y})\,\mathrm{d}g_{y}$
(using Z.2 and S.4)
$\displaystyle=|\mathbf{x}|\int_{\mathcal{G}_{z}}\phi_{z}(g,g_{y})\,\mathrm{d}g_{y}-|\mathbf{s}|\int_{\mathcal{G}}\phi_{s}(g,g_{y})\,\mathrm{d}g_{y}$
(Since $\mathbf{z}(g_{y})=0\Rightarrow\phi_{z}(g,g_{y})=0,\forall
g\in\mathcal{G}$; Z.2)
$\displaystyle=|\mathbf{x}|\int_{\mathcal{G}_{z}}\phi_{z}(g,g_{y})\,\mathrm{d}g_{y}-|\mathbf{s}|\int_{\mathcal{G}_{z}}\frac{1}{1-\alpha_{2}}\phi_{z}(g,g_{y})\frac{\mathbf{y}(g_{y})}{\mathbf{z}(g_{y})}\,\mathrm{d}g_{y}$
(using (38))
$\displaystyle=|\mathbf{x}|\int_{\mathcal{G}_{z}}\phi_{z}(g,g_{y})\,\mathrm{d}g_{y}-\frac{(1-\alpha_{2})|\mathbf{x}|}{1-\alpha_{2}}\int_{\mathcal{G}_{z}}\phi_{z}(g,g_{y})\frac{\mathbf{y}(g_{y})}{\mathbf{z}(g_{y})}\,\mathrm{d}g_{y}$
(using S.1)
$\displaystyle=|\mathbf{x}|\int_{\mathcal{G}_{z}}\phi_{z}(g,g_{y})\,\mathrm{d}g_{y}-|\mathbf{x}|\int_{\mathcal{G}_{z}}\phi_{z}(g,g_{y})\frac{\mathbf{y}(g_{y})}{\mathbf{z}(g_{y})}\,\mathrm{d}g_{y}$
$\displaystyle=|\mathbf{x}|\int_{\mathcal{G}_{z}}\phi_{z}(g,g_{y})\left(1-\frac{\mathbf{y}(g_{y})}{\mathbf{z}(g_{y})}\right)\,\mathrm{d}g_{y}$
$\displaystyle\geq 0$ (using Z.4,
$\frac{\mathbf{y}(g_{y})}{\mathbf{z}(g_{y})}\leq 1$)

Thus, we have shown that the joint distribution $\phi_{s}$ defined in (38)
satisfies all four properties S.1-S.4. This completes the proof of Lemma 13.
$\Box$

######  Claim 13.

For all $\eta\in{\mathbb{R}}_{\geq 0}$,
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\cdot,\cdot)$ is a quasi metric.

Proof:  Note that both $\mathsf{\partial}_{\mathrm{drop}}$ and
$\mathsf{\partial}_{\mathrm{move}}$ are quasi-metrics. Hence, for any
$\mathbf{x},\mathbf{y}$,
$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{y})\geq 0$ and
$\mathsf{\partial}_{\mathrm{move}}(\mathbf{x},\mathbf{y})\geq 0$. This implies
that for every $\mathbf{x},\mathbf{y}$,
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{y})\geq 0$. Now
we one by one prove that $\mathsf{\partial}_{\mathrm{drmv}}^{\eta}$ satisfies
the properties of quasi-metric:

Property #1: For all $\mathbf{x}$ and $\mathbf{y}$,
$\mathbf{x}=\mathbf{y}\Leftrightarrow\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{y})=0$.

  1. 1.

For all $\mathbf{x}$,
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{x})=0$:

$\displaystyle\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{x})$
$\displaystyle=\inf_{\mathbf{z}}\left(\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{z})+\eta\cdot\mathsf{\partial}_{\mathrm{move}}(\mathbf{z},\mathbf{x})\right)$
$\displaystyle\leq\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{x})+\eta\cdot\mathsf{\partial}_{\mathrm{move}}(\mathbf{x},\mathbf{x})$
(infimum over a set is $\leq$ the value at any fixed point in set)
$\displaystyle=0$

Since $\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{x})\geq 0$
as well as $\leq 0$,
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{x})=0$.

  2. 2.

For all $\mathbf{x},\mathbf{y}$,
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{y})=0\Rightarrow\mathbf{x}=\mathbf{y}$:
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{y})=0$ implies
that
$\inf_{\mathbf{z}}\left(\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{z})+\eta\cdot\mathsf{\partial}_{\mathrm{move}}(\mathbf{z},\mathbf{y})\right)=0$.
As both $\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{z})$ and
$\mathsf{\partial}_{\mathrm{move}}(\mathbf{z},\mathbf{y})$ are $\geq 0$ for
any value of $\mathbf{x},\mathbf{y},\mathbf{z}$, this is possible only if
$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{z})=\mathsf{\partial}_{\mathrm{move}}(\mathbf{z},\mathbf{y})=0$
which means that $\mathbf{x}=\mathbf{z}=\mathbf{y}$. Hence
$\mathbf{x}=\mathbf{y}$.

Property #2: For all $\mathbf{x}$, $\mathbf{y}$ and $\mathbf{z}$,
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{z})\leq\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{y})+\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{y},\mathbf{z})$.

We assume that the infimum in both
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{y})$ and
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{y},\mathbf{z})$ is achieved
by $\mathbf{s}_{1}$ and $\mathbf{s}_{2}$, respectively (the proof can be
easily extended to the case when the infimum is not achieved). This means that
there exists $a,b,c,d\geq 0$, such that

$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{s}_{1})=a;\
\mathsf{\partial}_{\mathrm{move}}(\mathbf{s}_{1},\mathbf{y})=b;\
\mathsf{\partial}_{\mathrm{drop}}(\mathbf{y},\mathbf{s}_{2})=c;\
\mathsf{\partial}_{\mathrm{move}}(\mathbf{s}_{2},\mathbf{z})=d,$

which implies
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{y})=a+\eta b$ and
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{y},\mathbf{z})=c+\eta d$. We
need to show that
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{z})\leq(a+c)+\eta(b+d)$.

Using Lemma 13 with
$\mathsf{\partial}_{\mathrm{move}}(\mathbf{s}_{1},\mathbf{y})=b$ and
$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{y},\mathbf{s}_{2})=c$, we get that
there is a $\mathbf{y}^{\prime}$ such that
$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{s}_{1},\mathbf{y}^{\prime})=c$ and
$\mathsf{\partial}_{\mathrm{move}}(\mathbf{y}^{\prime},s_{2})\leq b$. This
gives the following:

$\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{s}_{1})=a;\
\mathsf{\partial}_{\mathrm{drop}}(\mathbf{s}_{1},\mathbf{y}^{\prime})=c;\
\mathsf{\partial}_{\mathrm{move}}(\mathbf{y}^{\prime},\mathbf{s}_{2})\leq b;\
\mathsf{\partial}_{\mathrm{move}}(\mathbf{s}_{2},\mathbf{z})=d.$

Now we prove that
$\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{z})\leq(a+c)+\eta(b+d)$:

$\displaystyle\mathsf{\partial}_{\mathrm{drmv}}^{\eta}(\mathbf{x},\mathbf{z})$
$\displaystyle=\inf_{\mathbf{z}}\left(\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{y})+\eta\cdot\mathsf{\partial}_{\mathrm{move}}(\mathbf{y},\mathbf{z})\right)$
$\displaystyle\leq\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{y}^{\prime})+\eta\cdot\mathsf{\partial}_{\mathrm{move}}(\mathbf{y}^{\prime},\mathbf{z})$
$\displaystyle\leq\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{s}_{1})+\mathsf{\partial}_{\mathrm{drop}}(\mathbf{s}_{1},\mathbf{y}^{\prime})+\eta\cdot\mathsf{\partial}_{\mathrm{move}}(\mathbf{y}^{\prime},\mathbf{z})$
($\mathsf{\partial}_{\mathrm{drop}}$ is a quasi-metric)
$\displaystyle\leq\mathsf{\partial}_{\mathrm{drop}}(\mathbf{x},\mathbf{s}_{1})+\mathsf{\partial}_{\mathrm{drop}}(\mathbf{s}_{1},\mathbf{y}^{\prime})+\eta\cdot(\mathsf{\partial}_{\mathrm{move}}(\mathbf{y}^{\prime},\mathbf{s}_{2})+\mathsf{\partial}_{\mathrm{move}}(\mathbf{s}_{2},\mathbf{z}))$
($\mathsf{\partial}_{\mathrm{move}}$ is a metric)
$\displaystyle\leq(a+c)+\eta(b+d).$

This concludes the proof of Claim 13 $\Box$