Why does Chebyshev's inequality yield that the probability of Laplacian noise being bigger than x is bounded like this?

Question

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.

Answer 1

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}}$