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

  • 1
    $\begingroup$ 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.$ $\endgroup$ – kodlu Jul 31 '20 at 23:08
  • $\begingroup$ 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. $\endgroup$ – Miguel Gutierrez Jul 31 '20 at 23:26
  • 1
    $\begingroup$ well i hadnt seen your full equation. by the way your $x\geq \mu$ case is still looks wrong. The distribution is negative $\endgroup$ – kodlu Aug 1 '20 at 0:19
  • $\begingroup$ 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 :( $\endgroup$ – Miguel Gutierrez Aug 1 '20 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}$

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

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.