1
$\begingroup$

I saw this in a technical paper which made a leap I can't follow, it tries to solve an inequality $(cx)^{-x} \leq y$, which it then says it is satisfied when $x \geq -\ln {y}$. I can't make the leap, any ideas? I can also provide the link to the paper if needed. Thanks!

EDIT: Hi, thanks for the replies! Here is the paper http://supertech.csail.mit.edu/papers/steal.pdf It's the last a bit of math on Page 16. It says that: $(\frac{em}{\Delta})^\Delta \leq \frac{\epsilon}{P}$ holds as long as $\Delta \geq \max\{2em, \lg P + \lg \frac{1}{\epsilon} \}$ holds. Here e is the base of natural logarithm, m is a non-negative integer, P is a positive integer, $\Delta$ is a positive integer, and $\epsilon$ is a positive real number.

Frankly speaking, I'm confused about all of these I just described, I can't figure out why the solution to this inequality is a max of two terms, and why the first term does not depend on $\epsilon$ at all. I guess the second term is probably the important part so I asked it in the first place.

Thanks so much!

Resoulution: $\lg$ means logarithm with base 2 in the paper. So $\Delta \geq \max\{2em, \lg P + \lg \frac{1}{\epsilon} \}$ means that $(\frac{em}{\Delta})^\Delta \leq (\frac12)^\Delta \leq (\frac12)^{\lg P + \lg \frac{1}{\epsilon}} = \frac{\epsilon}{P}$. Also thanks Tim for the explanation.

$\endgroup$
  • $\begingroup$ Please provide the link to the paper. $\endgroup$ – user230734 Jun 17 '15 at 1:50
  • 1
    $\begingroup$ There is additionnal information needed, because for $x>0$ fixed, $cx^{−x}$ can take any value in $]0,+\infty[$ (depending on the value of $c$). But $x \geq −\ln(y)$ doesn't depend of $c$ : there will probably be a problem $\endgroup$ – Tryss Jun 17 '15 at 2:39
  • $\begingroup$ Hi BolzWeir and Tryss, thanks for the reply! I've added the link to the paper and pointed out the location. I apologize if my original description was a little off from the paper. Thanks! $\endgroup$ – ios learner Jun 17 '15 at 6:10
  • $\begingroup$ What does lg mean? $\endgroup$ – Gerry Myerson Jun 17 '15 at 7:00
  • 1
    $\begingroup$ Hi @GerryMyerson, you are right, apparently lg means logarithm with base 2 in the original literature and I understand it now, thanks! $\endgroup$ – ios learner Jun 17 '15 at 21:44
0
$\begingroup$

Suppose $\Delta=2em$, $P=e^{em}$, $1/\epsilon=e^{em}$. Then $\log P+\log(1/\epsilon)=2em$, so the condition on $\Delta$ is met. We have $$\left({em\over\Delta}\right)^{\Delta}=2^{-2em}>e^{-2em}={\epsilon\over P}$$ so the conclusion is false.

EDIT: I'm assuming "lg" is an abbreviation for natural logarithm. If I'm wrong about that, then all bets are off.

$\endgroup$
  • $\begingroup$ Shouldn't the left hand side have base $\frac{1}{2}$? $\endgroup$ – Linus S. Jun 17 '15 at 7:28
  • $\begingroup$ The left side of what? $em/\Delta=1/2$, $(1/2)^Q=2^{-Q}$. $\endgroup$ – Gerry Myerson Jun 17 '15 at 7:30
  • $\begingroup$ You are correct, my bad. $\endgroup$ – Linus S. Jun 17 '15 at 7:32
  • $\begingroup$ Hi, thanks for the observation, that's so weird. $\endgroup$ – ios learner Jun 17 '15 at 18:23

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.