# Laplace Inequality

I am trying to prove that if $$r_i \sim Lap(0,1/\varepsilon)$$ where $$\varepsilon >0$$ then:

$$Pr[r_i \geq 1+r^*] \geq e^{-\varepsilon}Pr[r_i \geq r^{*}]$$.

I know that for $$r*>0$$ it satisfies with equality. Even though, for $$r <0$$, I couldn't find out how to prove it.

Note $$Lap \sim (\mu,b)$$:

$$Pr[X \geq x] = 1-F(x)=\begin{cases} 1-\frac{1}{2}\exp(\frac{x-\mu}{b}) && \text{if }x< \mu \\ \frac{1}{2}\exp(-\frac{x-\mu}{b}) &&\text{if } x\geq \mu\end{cases},$$

• Your equation is incomplete. What is $1/\epsilon$? The spread parameter? Unless the negative case is $-1\leq r* <0,$ such an inequality won't hold since the distribution is of the form $c \exp(-|r|)$ thus it is increasing for $r\leq 0.$ – kodlu Jul 31 at 23:08
• I think what its happening is the contrary. When $r* <-1$ the inequality holds. I did some calculations and works very well. When $-1\leq r* <0$, is more complex because when $1+r*>0$, the cumulative distribution may change for some values $1+r*$ and $r*$. This inequality is from proof of Report Noisy Max in differential privacy. – Miguel Gutierrez Jul 31 at 23:26
• well i hadnt seen your full equation. by the way your $x\geq \mu$ case is still looks wrong. The distribution is negative – kodlu Aug 1 at 0:19
• Yeap, it's positive. If you maybe take some time thinking about it and find a way to solve it, will help me a lot !. Yeah, I just changed it to seem more clearly in the question. I have spent like two days already :( – Miguel Gutierrez Aug 1 at 1:16

OK, I did this quickly. Hope it’s correct.

When $$r*\geq 0,$$ the relationship holds as you observed. And when $$r^*\leq -1,$$ the same expression for both probabilities you want to compare enables a direct proof.

Let $$r^*\in(-1,0),$$ so that $$1+r^* \in (0,1).$$ Then what you want to show is $$\frac{1}{2} e^{-\epsilon(1+r^*)}\geq e^{-\epsilon}\left(1-\frac{1}{2} e^{\epsilon r^*}\right)$$ or $$\frac{1}{2} e^{-\epsilon(r^*+1)}+ \frac{1}{2} e^{\epsilon (r^*-1)} \geq e^{-\epsilon}$$ or $$e^{-\epsilon} \left( \frac{ e^{-\epsilon r^*}+ e^{\epsilon r^*}}{2} \right)\geq e^{-\epsilon}$$ which holds since the cosh function is lower bounded by $$1.$$

When $$r*<-1$$, a litlle more larger, we want to find the next inequality:

$$\begin{equation*} \begin{split} e^{\epsilon} \left(1-\frac{1}{2}e^{\epsilon(x+1)} \right) \geq 1-\frac{1}{2}e^{\epsilon(x)}\\ e^{\epsilon}-\frac{1}{2}e^{\epsilon x+ 2\epsilon}\geq 1-\frac{1}{2}e^{\epsilon(x)} \end{split} \end{equation*}$$

Which we will bounded by both inequalities using the fact that $$r*\leq-1$$

$$\begin{equation*} \begin{split} r* &\leq -1\\ e^{\epsilon r*} &\leq e^{-\epsilon}\\ e^{\epsilon x + 2\epsilon} &\leq e^{\epsilon}\\ -\frac{1}{2}e^{\epsilon r*+ 2\epsilon} &\geq -\frac{1}{2}e^{\epsilon}\\ e^{\epsilon}-\frac{1}{2}e^{\epsilon r*+ 2\epsilon} &\geq e^{\epsilon}-\frac{1}{2}e^{\epsilon}\\ \end{split} \end{equation*}$$

The same way we have:

$$\begin{equation*} \begin{split} r* &\leq -1\\ 1-\frac{1}{2}e^{\epsilon x} & \geq 1-\frac{1}{2}e^{-\epsilon} \end{split} \end{equation*}$$

Joining this inequalitys, we can obtain

$$\begin{equation*} \begin{split} e^{\epsilon}-\frac{1}{2}e^{\epsilon} > 1-\frac{1}{2}e^{-\epsilon}\\ 2(e^{\epsilon}-1) > e^{\epsilon}-e^{-\epsilon} \end{split} \end{equation*}$$

Where the inequalitie holds since $$2>1$$ and $$-1 \leq - e^{-\epsilon}$$

• That proof seems correct ! But can you show also when $r* \leq -1$ ? I don't see the direct way. – Miguel Gutierrez Aug 1 at 5:39
• Already did the proof of $r*<-1$, it's not so direct. Anyway thanks, for the tip :) – Miguel Gutierrez Aug 2 at 9:21
• Been too busy with a deadline. Feel free to edit answer to include that case.. – kodlu Aug 2 at 9:56
• Perfect, done. I think its correct – Miguel Gutierrez Aug 9 at 7:57