Consider a function $f:(0,\infty)\rightarrow \mathbb{N}$ with argument $\epsilon$. Suppose $f$ is decreasing in $\epsilon$. Let $0<b<1$, $K>0$, $d \in \mathbb{N}$, $\delta>0$. Assume $$ 1\leq f(\epsilon* b)\leq K*\Big(\frac{2\delta}{\epsilon}\Big)^d $$ $\forall$ $0<\epsilon<2\delta$.

This implies that $$ 0 \leq \log(f(\epsilon*b))\leq \log(K)+d* \log(2)+d*\log\Big(\frac{2\delta}{\epsilon}\Big) $$ $\forall$ $0<\epsilon<2\delta$.

Is it true that $$ \exists \text{ }M>0 \text{ s.t. } \log(K)+d* \log(2)+d*\log\Big(\frac{2\delta}{\epsilon}\Big) \leq M*\log\Big(\frac{\delta}{\epsilon}\Big) $$ $\forall$ $0<\epsilon<\delta b$?

If no, could you give a counterexample? If yes, could you explain why? Maybe, it holds only for sufficiently small $\delta$?

I can see that $\log(K)+d* \log(2)+d*\log\Big(\frac{2\delta}{\epsilon}\Big)=O\Big(\log\Big(\frac{\delta}{\epsilon}\Big)\Big)$ as $\epsilon$ goes to $0$. This means that $\exists M>0, \eta>0$ s.t. $\log(K)+d* \log(2)+d*\log\Big(\frac{2\delta}{\epsilon}\Big)\leq M*\log\Big(\frac{\delta}{\epsilon}\Big) $ $\forall \epsilon<\eta$. I don't know how to show that $\eta\geq \delta b$.


1 Answer 1


The inequality is equivalent to $\log K+2 d \log 2\leq (M-d)\log \delta /\epsilon.$ Since $\epsilon\in (0,\delta b)\implies \delta /\epsilon >1/b>1\implies \log \delta /\epsilon >\log 1/b >0$ , the inequality holds for all $\epsilon \in (0,\delta b)$ if $(M-d)\log 1/b \geq \log K+2 d \log 2,$ equivalently, if $M\geq d+(\log 4^d K)/(\log 1/b).$ This is satisfied if $M>0$ and if $M$ is sufficiently large.
What does this have to do with $f$?.

  • $\begingroup$ Why do you have $2d\log(2)$? I think it should be $d\log(2)$. We want to show that for $\epsilon \in (0,\delta b)$ $\log(K)+d \log(2)\leq (M-d)\log(\frac{\delta}{\epsilon})$. Why if $\log(K)+d \log(2)\leq (M-d)\log(\frac{1}{b})$ then $\log(K)+d \log(2)\leq (M-d)\log(\frac{\delta}{\epsilon})$? $\endgroup$
    – Star
    Mar 4, 2016 at 20:27
  • $\begingroup$ Q1: ...$\log K +d \log 2 +d\log (2 \delta/\epsilon)=\log K+d \log 2 +d(\log 2 +\log \delta / \epsilon)=\log K+d \log 2 +d \log 2 +d \log \delta /\epsilon=\log K +2 d \log 2+\log \delta /\epsilon.$... Q2: Because $0<\log (1/b)<\log (\delta /\epsilon) \implies (M-d)\log (1/b)\leq (M-d)\log (\delta /\epsilon).$ $\endgroup$ Mar 4, 2016 at 21:40
  • $\begingroup$ But we don't know whether $M\geq l$ or $M<l$. And the fact that $(M-d)\log(\frac{1}{b})\geq \log(K)+2d \log(2)$ is not necessary for the result. $\endgroup$
    – Star
    Mar 8, 2016 at 11:22
  • $\begingroup$ I meant $d$ not $l$, sorry; here again the comment corrected: "But we don't know whether $M\geq d$ or $M<d$. And the fact that $(M-d)\log(\frac{1}{b})\geq \log(K)+2d\log(2)$ is not necessary for the result" $\endgroup$
    – Star
    Mar 9, 2016 at 14:23
  • $\begingroup$ I see your point. So for some $d,K$ it would be insufficient. I'll have another look at it. $\endgroup$ Mar 9, 2016 at 15:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .