Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to prove an inequality that would imply my algorithm satisfies $\epsilon$-differential privacy for $k_i$ being a parameter. The inequality is

$$ \left(1-\frac{1}{1+e^{\epsilon/k_i}}\right)^{k_i} < 1 - \frac{1-\frac{1}{2^{k_i}}}{e^\epsilon} , $$

for $\epsilon > 0$ and $k_i \in \{1,2,...\}$.

I've been trying for weeks, and I've got a rather large proof. First by showing that the two sides are never equal when $\epsilon > 0$, and using the Intermediate Value theorem to show that if at a given $\epsilon^\prime$ and $k_i^\prime$ the RHS is less than the LHS, then this also holds for all $\epsilon>0$ for the same $k_i^\prime$. After that I show the base case at $k_i=1$ and proceed by induction on $k_i$ to show it holds for all $k_i$.

The resulting proof are rather long (5 pages with lots of hyperbolic tangents and friends). I was just wondering if there is a faster and more elegant way to prove the same result.

share|improve this question

2 Answers 2

up vote 8 down vote accepted

Call $x=\mathrm{e}^{\epsilon/k_i}$ hence $x>1$ is a real number, $n=k_i$ hence $n\ge1$ is an integer, and $z_n=1-2^{-n}$. You want to prove $$ \left(1-\frac{1}{1+x}\right)^n<1-\frac{z_n}{x^n}. $$ This is equivalent to $$ x^n\left(1-\left(\frac{x}{1+x}\right)^n\right)>z_n. $$ Call $u_n(x)$ the LHS. Then $u_n(1)=z_n$, hence if $u_n$ is increasing, you are done. But the derivative of $u_n$ is $$ u'_n(x)=nx^{n-1}\left(1-\left(\frac{x}{1+x}\right)^n\right)-nx^n\left(\frac{x}{1+x}\right)^{n-1}\frac{1}{(1+x)^2}=nx^{n-1}v_n(x), $$ with $$ v_n(x)=1-\left(\frac{x}{1+x}\right)^n\frac{2+x}{1+x}. $$ Since $n\ge1$, $v_n(x)\ge v_1(x)=1/(1+x)^2>0$ and the proof is complete.

This also shows that the constant $z_n=1-2^{-n}$ is optimal in the sense that one cannot replace it by any greater value and still hope the inequality to hold for every positive $\epsilon$ (that is, except if $\epsilon$ is restricted to $\epsilon\ge\epsilon_0$ for a given positive $\epsilon_0$).

share|improve this answer
    
Wow, the proof is very nice. –  Sunni Jun 9 '11 at 21:41
    
@Sunni: Thanks. –  Did Jun 10 '11 at 5:20
    
Thanks for your response, I learned one possible way to work with inequalities in multiple variables (replacement of variables, and subscripted functions). Good insight too on showing the derivative is positive. Also very good notice on $z_n$ optimality, this actually showed that my assumptions are stronger than I thought. –  M. Alaggan Jun 11 '11 at 2:18

First, for positive integer $k$, write your inequality as $$ \bigg(\frac{{1+e^{\varepsilon /k} -1}}{{1 + e^{\varepsilon /k} }}\bigg)^k < \frac{{e^\varepsilon - 1 + 2^{ - k} }}{{e^\varepsilon }}, $$ or $$ e^{2\varepsilon } < (1 + e^{\varepsilon /k} )^k (e^\varepsilon - 1 + 2^{ - k} ). $$ Next note that $$ (1 + e^{\varepsilon /k} )^k \ge 1 + (e^{\varepsilon /k} )^k = 1 + e^\varepsilon . $$ Hence $$ (1 + e^{\varepsilon /k} )^k (e^\varepsilon - 1 + 2^{ - k} ) \ge (1 + e^\varepsilon )(e^\varepsilon - 1) + \bigg(\frac{{1 + e^{\varepsilon /k} }}{2}\bigg)^k > (e^{2\varepsilon } - 1) + 1 = e^{2\varepsilon } , $$ and so we are done.

share|improve this answer
    
Wow, the proof is beautiful. –  Sunni Jun 9 '11 at 21:42
    
@Sunni: Thank you! –  Shai Covo Jun 9 '11 at 21:44
    
Thanks for your proof. This was one path I've tried and failed to complete. Your "note" that we can move the "1" outside the brackets was the thing I was missing to complete it (along with the last inequality where we replace that big term with 1). –  M. Alaggan Jun 11 '11 at 2:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.