= Laplace mechanism
{title2=$M(D)=f(D)+Y$}
The <Laplace mechanism> releases a numerical query with added <Laplace distribution> noise scaled to the query's sensitivity. For $f(D)\in\mathbb R^k$, define its sensitivity under the chosen dataset adjacency by
$$
\Delta_1f=\sup_{D\sim D'}\|f(D)-f(D')\|_1.
$$
For $\varepsilon>0$ and positive finite sensitivity, release $f(D)+(Y_1,\ldots,Y_k)$ with independent noise coordinates of density $p(y)=(2b)^{-1}e^{-|y|/b}$, where $b=\Delta_1f/\varepsilon$. The ratio of output densities for adjacent inputs is bounded by $\exp(\|f(D)-f(D')\|_1/b)\le e^\varepsilon$, by the <triangle inequality>. Integrating over any measurable output event proves $(\varepsilon,0)$ <differential privacy>.<The Algorithmic Foundations of Differential Privacy by Cynthia Dwork and Aaron Roth>[Definition 3.1 and Theorem 3.6]{ref}
For a count with add/remove sensitivity one and $\varepsilon=0.5$, the noise scale is two and its <variance> is $2b^2=8$. Smaller privacy parameters increase uncertainty in this mechanism. A fixed output when sensitivity is zero needs no noise. The adjacency convention is essential: changing what one person can contribute changes the required sensitivity bound.
Back to article page
