# Privacy-Preserving Monotonicity of Differential Privacy Mechanisms
## 4 Differential Privacy  
In this section, we introduce preliminary to differential privacy [1]. A database \(x\) as being collections of records coming from a universe \(\mathcal{X}\) of data types. It will be convenient to represent databases by histograms, \(x\in\mathbb{N}^{|\mathcal{X}|}\), in which each \(x_{i}\) represents the number of elements in the database \(x\) of type \(i\in\mathcal{X}\). Symbol \(\mathbb{N}\) denotes the set of all nonnegative integers. In this presentation, a natural measurement of distance between two databases \(x\) and \(y\) will be \(\ell_{1}\) norm \(||x-y||_{1}\). If \(||x-y||_{1}\leq 1\), then two databases \(x\) and \(y\) is called as adjacent databases. **Definition 1** (Differential Privacy). : _A randomized algorithm \(\mathcal{M}\) with domain \(\mathbb{N}^{|\mathcal{X}|}\) is \((\varepsilon,\delta)\)-differential privacy if for all \(\mathcal{S}\subseteq Range(\mathcal{M})\) and for all \(x,y\in\mathbb{N}^{|\mathcal{X}|}\) such that \(||x-y||_{1}\leq 1\), then_  
\[P(\mathcal{M}(x)\in\mathcal{S})\leq e^{\varepsilon}P(\mathcal{M}(y)\in \mathcal{S})+\delta \tag{5}\]  
_where the probability space is over the coin flips of the mechanism \(\mathcal{M}\). If \(\delta=0\), \(\mathcal{M}\) is \(\varepsilon\)-differential privacy._  
For each record of every individual, the coin flips of the mechanism mean that \(\mathcal{M}\) inherently has only two possible and equally likely outcomes. Specifically, differential privacy ensures that any sequence of outputs in response to queries is essentially equally likely to occur, which probability spaces is the coin flips of the mechanism, independent of the presence or absence of any individual. The coin flips of the mechanism have the same mean for the following definition of local differential privacy. According to the definition of \((\varepsilon,\delta)\)-differential privacy, the mechanism \(\mathcal{M}\) is \(\varepsilon\)-differential privacy with probability at least \(1-\delta\) for all adjacent databases \(x\) and \(y\). In the follow-up section, symbol \(\mathbb{R}\) is the set of real numbers. **Definition 2** (\(\ell_{1}\)-Sensitivity). : _The \(\ell_{1}\)-sensitivity of a function \(f:\mathbb{N}^{|\mathcal{X}|}\to\mathbb{R}^{k}\) is_  
\[\Delta f=\max_{ \begin{subarray}{c}x,y\in\mathbb{N}^{|\mathcal{X}|}\\ ||x-y||_{1}=1\end{subarray} }||f(x)-f(y)||_{1} \tag{6}\]  
**Definition 3** (Laplace Mechanism). : _Given any function \(f:\mathbb{N}^{|\mathcal{X}|}\to\mathbb{R}^{k}\), the Laplace mechanism is defined as_  
\[\mathcal{M}_{L}(x,f(\cdot),\varepsilon)=f(x)+(Y_{1},\dots,Y_{k}) \tag{7}\]  
_where \(Y_{i}\) are independent identical distribution random variables drawn from Laplace distribution \(\text{Lap}(\frac{\Delta f}{\varepsilon})\)._  
**Definition 4** (\(\ell_{2}\)-Sensitivity). : _The \(\ell_{2}\)-sensitivity of a function \(f:\mathbb{N}^{|\mathcal{X}|}\to\mathbb{R}^{k}\) is_  
\[\Delta_{2}f=\max_{ \begin{subarray}{c}x,y\in\mathbb{N}^{|\mathcal{X}|}\\ ||x-y||_{1}=1\end{subarray} }||f(x)-f(y)||_{2} \tag{8}\]  
**Definition 5** (Gaussian Mechanism). : _Given any function \(f:\mathbb{N}^{|\mathcal{X}|}\to\mathbb{R}^{k}\), the Gaussian mechanism is defined as_  
\[\mathcal{M}_{G}(x,f(\cdot),\varepsilon)=f(x)+(Y_{1},\dots,Y_{k}) \tag{9}\]_where \(Y_{i}\) are independent identical distribution random variables drawn from Gaussian distribution \(N(0,\sigma^{2})\) with parameters \(\sigma\geq\frac{\Delta_{2}f\sqrt{\frac{\Delta_{2}\ln(\frac{128}{\delta})}{ \varepsilon}}}{\varepsilon}\) and \(\varepsilon\in(0,1)\)._  
While both Laplace mechanism and Gaussian mechanism are suitable for numerical data, exponential mechanism and randomized response mechanism are used for categorical data. Given some arbitrary range \(\mathcal{R}\) of exponential mechanism, the exponential mechanism is defined with respect to some utility function \(u:\mathbb{N}^{|\mathcal{X}|}\times\mathcal{R}\rightarrow\mathbb{R}\), which maps database and output pairs into utility scores.