1
$\begingroup$

I am trying to understand this proof of the bounds of Laplacian noise used in a paper on differential privacy.

Given a random variable $Lap\left ( \frac{\Delta f}{\varepsilon } \right )$, apparently the probability that the Laplacian noise is bigger than $x$ is bounded by:

$\mathbb{P}\left [ \left | Lap\left ( \frac{\Delta f}{\epsilon } \right ) \right | > x \right ]= e^{-\frac{x \cdot \epsilon}{\Delta f}}$

The proof for this is that the variant below of Chebyshev's inequality "directly" yields this result:

$\mathbb{P}\left [ \left | X - E\left [ X \right ] \right | \geq k^{2}\right ]\leq \frac{\sigma^{2}}{k^{2}}$

The paper doesn't explain this, since it should be very obvious. It is not obvious to me. This is what I did so far:

$E\left [ X \right ]$ denotes expected value.

If I understand it correctly $E\left [ X \right ] = 0$ for

I also think I understand that $\sigma^{2} = \frac{2\cdot \left ( \Delta f \right )^{2}}{ \epsilon^{2}}$ for $Lap\left ( \frac{\Delta f}{\varepsilon } \right )$

But how do you get from that to this: $e^{-\frac{x \cdot \epsilon}{\Delta f}}$??

My first (and only step):

$\mathbb{P}\left [ \left | Lap\left ( \frac{\Delta f}{\varepsilon } \right ) \right | \geq x\right ]\leq \frac{\frac{2\cdot \left ( \Delta f \right )^{2}}{ \epsilon^{2}}}{x}$

Apparently the rest should be completely obvious, but I am completely stumped.

$\endgroup$
2
$\begingroup$

This can be shown without Chebyshev's inequality. The pdf of a Laplace distribution with scale parameter $b$ and mean $0$ is $f(x) = \frac{1}{2b}e^{-\frac{|x|}{b}}$. Using the symmetry of the distribution about $0$:

$\mathbb{P}(|Lap(b)| > c) = 2\mathbb{P}(Lap(b) > c) = 2\int_c^\infty\frac{e^{-\frac{x}{b}}}{2b}dx = e^{-\frac{c}{b}}$

$\endgroup$
2
  • $\begingroup$ Your approach makes complete sense to me. Reading it I started doubting whether you can even use Chebyshev's inequality to come to the same result. You would have to use the pdf anyway, at wich point using Chebyshev seems moot. What do you think? $\endgroup$ – gijswijs Dec 18 '20 at 2:42
  • 1
    $\begingroup$ It does seem unlikely that you would be able to prove an equality from an inequality. $\endgroup$ – fblundun Dec 18 '20 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.