拉普拉斯不等式
我試圖證明如果 $ r_i \sim Lap(0,1/\varepsilon) $ 在哪裡 $ \varepsilon >0 $ 然後：
$$ Pr[r_i \geq 1+r^] \geq e^{-\varepsilon}Pr[r_i \geq r^{}] $$.
我知道對於 $ r*>0 $ 它滿足平等。儘管，對於 $ r <0 $ ，我找不到如何證明這一點。
筆記 $ 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}, $$
好的，我很快就做到了。希望是正確的。
什麼時候 $ r*\geq 0, $ 正如你所觀察到的那樣，這種關係成立。什麼時候 $ r^*\leq -1, $ 您要比較的兩個機率的相同表達式可以直接證明。
讓 $ r^\in(-1,0), $ 以便 $ 1+r^ \in (0,1). $ 那麼你要展示的是 $$ \frac{1}{2} e^{-\epsilon(1+r^)}\geq e^{-\epsilon}\left(1-\frac{1}{2} e^{\epsilon r^}\right) $$ 或者 $$ \frac{1}{2} e^{-\epsilon(r^+1)}+ \frac{1}{2} e^{\epsilon (r^-1)} \geq e^{-\epsilon} $$ 或者 $$ e^{-\epsilon} \left( \frac{ e^{-\epsilon r^}+ e^{\epsilon r^}}{2} \right)\geq e^{-\epsilon} $$ 因為 cosh 函式的下界為 $ 1. $
什麼時候 $ r*<-1 $ ，再大一點，我們想找到下一個不等式：
$$ \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*} $$
我們將使用以下事實來限制這兩個不等式 $ 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*} $$
我們有同樣的方式：
$$ \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*} $$
加入這個不等式，我們可以得到
$$ \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*} $$
自那時以來不等式一直存在的地方 $ 2>1 $ 和 $ -1 \leq - e^{-\epsilon} $