We all know the well known upper bound: $$ \min(a,b) \leq a^s b^{1-s}$$ for $$a,b \geq 0, 0 < s < 1$$ I am looking for a lower bound on $\min(a,b)$.

  • $\begingroup$ What have you tried so far? What are you willing to sacrifice? $\min$ itself is a very good (perfect) lower bound for $\min$, but I expect this is not what you want, so what properties should your lower bound have? $\endgroup$ – flawr Dec 4 '15 at 17:06
  • $\begingroup$ Specificlly I need to lower bound:$$\sum_x \min(p(x),\lambda q(x))$$. where $p,q$ are probability measure. For the upper bound $$\sum_x \min(p(x),\lambda q(x)) \leq \lambda^{1-s} \sum_x p(x)^s q(x)^{1-s} $$ which is close related to renyi divergence $\endgroup$ – nir Dec 4 '15 at 17:17
  • $\begingroup$ What is $p,q,\lambda$ and what values can $x$ take? $\endgroup$ – flawr Dec 4 '15 at 17:19
  • $\begingroup$ also $\lambda > 0$ $\endgroup$ – nir Dec 4 '15 at 17:24
  • $\begingroup$ I do not know any solution, but I am trying some ideas for one, but perhaps I can only post them tomorrow. Seems like an interesting problem=) $\endgroup$ – flawr Dec 4 '15 at 17:46

You did not specify this, but I assumed you wanted a differentiable lower bound.

If you consider the $f(x,y)=\min(x,y)$ as a function $\mathbb R^2 \to \mathbb R$ and you consider the slice $x+y = const = c$, then my idea was to fit a parabola under that 'triangle' that matches the gradients of $f$ at the zeros. With this idea you end up with following result:

$$\min(x,y) \geq \frac{xy}{x+y} \qquad \forall x\geq0 \forall y\geq 0 \text{ (and $xy\neq 0$)}$$

Proof: WLOG we can assume $y \geq x$. It is obvious that $x(x+y) = x^2+xy \geq xy$. Dividing by $(x+y)$ results in

$$\min(x,y) = x \geq \frac{xy}{x+y}$$

Here a plot of this, the upper surface is $\min$ and the lower is my suggested lower bound.

enter image description here

  • $\begingroup$ Why the downvotes? $\endgroup$ – flawr Dec 15 '15 at 13:09

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.