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)=\int\limits_{-\infty}^x f(u)du=\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},$$
First of all, there's a typo in your last expression. The correct expression is $$ \begin{align} P(X \ge x) & = \begin{cases} 1 - \frac{1}{2} \exp\left( \frac{x - \mu}{b} \right), & \text{ if } x < \mu \\ \frac{1}{2} \exp\left( - \frac{x - \mu}{b} \right), & \text{ if } x \ge \mu \end{cases} \\ & = \begin{cases} 1 - \frac{1}{2} \exp\left( \epsilon x \right), & \text{ if } x < 0 \\ \frac{1}{2} \exp\left( - \epsilon x \right), & \text{ if } x \ge 0 \end{cases} \end{align} $$ with $\mu = 0$ and $b = 1/\epsilon$. And you in fact have equality for $x \ge 0$, not just for $x > 0$. If you first think of $\epsilon$ as a fixed parameter, we can plot both sides of the inequality as a function of $x = r^*$. Here I've used $\epsilon = 1$:
Notice that the gap between them appears to be monotonically decreasing. This suggests that we can use the derivative to prove the inequality. With this hypothesis in mind, let's assume that $x \le -1$, so that the expressions on both sides of the inequality are given by the same part of the piecewise function. Now denote the difference by $$ \begin{align} g(x) & = P(r_i \ge x + 1) - e^{-\epsilon}P(r_i \ge x) \\ & = 1 - \frac{1}{2} e^{\epsilon (x + 1)} - \left[e^{-\epsilon}\left(1 - \frac{1}{2} e^{\epsilon x}\right)\right] \\ & = 1 - e^{-\epsilon} + \frac{1}{2} \left[e^{\epsilon (x - 1)} - e^{\epsilon (x + 1)}\right] \end{align} $$ and hence $g'(x) = \frac{1}{2} \epsilon \left(e^{\epsilon (x - 1)} - e^{\epsilon (x + 1)} \right)$. Because $\epsilon > 0$, the function $\exp(\epsilon x)$ is an increasing function, and therefore $g'(x) < 0$, so $g$ is a decreasing function. Therefore it achieves a minimum on $(-\infty, -1]$ at the point $x = -1$. That means that $g(x) \ge g(-1) = \frac{1}{2} (e^{-\epsilon})^2 - (e^{-\epsilon}) + \frac{1}{2}$. You might recognize that this is a quadratic function in the new variable $y = e^{-\epsilon}$, so factor $\frac{1}{2} y^2 - y + \frac{1}{2} = \frac{1}{2} (y - 1)^2$ to see that this is non-negative. Therefore, $g(x) \ge g(-1) \ge 0$ which proves the inequality for the case when $x \le -1$.
Now we can prove the inequality for the case when $-1 < x < 0$ in much the same way. Denote the difference by $$ \begin{align} h(x) & = P(r_i \ge x + 1) - e^{-\epsilon}P(r_i \ge x) \\ & = \frac{1}{2} e^{-\epsilon (x + 1)} - \left[e^{-\epsilon}\left(1 - \frac{1}{2} e^{\epsilon x}\right)\right] \\ & = - e^{-\epsilon} + \frac{1}{2} \left[e^{\epsilon (x - 1)} + e^{-\epsilon (x + 1)}\right] \\ h'(x) & = \frac{1}{2} \epsilon \left[ e^{\epsilon (x - 1)} - e^{-\epsilon (x + 1)}\right] \\ & \le 0 \end{align} $$ where the last inequality is true because $e^{-\epsilon (x + 1)} > e^{\epsilon (x - 1)}$ for $x < 0$. And hence $h$ is decreasing on the interval $(-1, 0)$, and therefore $h(x) \ge h(0) = 0$. So the inequality it proved for this case as well, and we have finished proving the result.
