Existe una mejor forma de estimar la $(1-1/(1+e^{\epsilon/k}))^k$ desde arriba?

Question

Estoy tratando de demostrar una desigualdad que implicaría mi algoritmo satisface $\epsilon$-diferencial de privacidad para $k_i$ siendo un parámetro. La desigualdad es

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

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

He estado tratando durante semanas, y tengo una gran prueba. Primero, mostrando que los dos lados nunca es igual al $\epsilon > 0$, y utilizando el teorema del Valor Intermedio para demostrar que si en un determinado $\epsilon^\prime$ $k_i^\prime$ el lado derecho es menor que la LHS, entonces esto también se aplica para todos los $\epsilon>0$ para el mismo $k_i^\prime$. Después de que me muestre el caso base en $k_i=1$ y proceder por inducción en $k_i$ a mostrar que tiene para todos los $k_i$.

El resultado de la prueba son bastante largos (5 páginas con un montón de tangentes hiperbólicas y sus amigos). Me estaba preguntando si hay una forma más rápida y más elegante manera de probar el mismo resultado.

Answer 1

Llame a $x=\mathrm{e}^{\epsilon/k_i}$ por lo tanto $x>1$ es un número real, $n=k_i$ por lo tanto $n\ge1$ es un número entero, y $z_n=1-2^{-n}$. Quieres demostrar $$ \left(1-\frac{1}{1+x}\right)^n<1-\frac{z_n}{x^n}. $$ Esto es equivalente a $$ x^n\left(1-\left(\frac{x}{1+x}\right)^n\right)>z_n. $$ Llame a $u_n(x)$ el lado izquierdo. A continuación,$u_n(1)=z_n$, por lo tanto, si $u_n$ está aumentando, está hecho. Pero la derivada de $u_n$ es $$ 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), $$ con $$ v_n(x)=1-\left(\frac{x}{1+x}\right)^n\frac{2+x}{1+x}. $$ Desde $n\ge1$, $v_n(x)\ge v_1(x)=1/(1+x)^2>0$ y la prueba está completa.

Esto también muestra que la constante de $z_n=1-2^{-n}$ es óptimo en el sentido de que no se puede sustituir por cualquier mayor valor y todavía la esperanza de la desigualdad a todos los positivos $\epsilon$ (es decir, excepto si $\epsilon$ está restringido a $\epsilon\ge\epsilon_0$ para un determinado positivo $\epsilon_0$).

Answer 2

En primer lugar, por entero positivo $k$, escribir su desigualdad como $$ \bigg(\frac{{1+e^{\varepsilon /k} -1}}{{1 + e^{\varepsilon /k} }}\bigg)^k < \frac{{e^\varepsilon - 1 + 2^{ - k} }}{{e^\varepsilon }}, $$ o $$ e^{2\varepsilon } < (1 + e^{\varepsilon /k} )^k (e^\varepsilon - 1 + 2^{ - k} ). $$ La próxima nota de que $$ (1 + e^{\varepsilon /k} )^k \ge 1 + (e^{\varepsilon /k} )^k = 1 + e^\varepsilon . $$ Por lo tanto $$ (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 } , $$ y así hemos terminado.