3
$\begingroup$

For nonnegative $x \in \mathbb{R}_+^n$, $p \geq 1$ I want to find $\epsilon_{n,p}$ such that

$$ \frac{n^{1/p}}{||1/x||_p} \geq \min (x) \geq \frac{n^{1/p}}{||1/x||_p} - \epsilon_{p,n} ||x||_\infty $$

Here is how far I got. Without loss of generality, take $||x||_\infty=1$, furthermore, let $x$ be the vector $(m,1,...,1)$, where $m$ is the minimum element of $x$. Then our goal is to find the maximum value of

$$\epsilon_{n,p}(m) = \left(\frac{n}{p - 1 + m^{-p}}\right)^{1/p} - m$$

What is an upper bound on $\epsilon_{n,p}(m)$ on $m \in [0,1]$?

See this plot for n=3, p=3

$\endgroup$

1 Answer 1

3
$\begingroup$

[Edit to answer the modified question:]

For $p=1$, $\epsilon_{n,p}(m)=(n-1)m$ and there is no upper bound on $\epsilon$, so I will assume $p>1$.

The derivative of this new version of $\epsilon$ with respect to $m$ is

$$\epsilon'_{n,p}(m) = n^{1/p}m^{-(p+1)}\left(p - 1 + m^{-p}\right)^{-(p+1)/p} - 1\;.$$

Setting this to zero yields

$$n^{1/p}m^{-(p+1)}\left(p - 1 + m^{-p}\right)^{-(p+1)/p}=1\;,$$

$$n^{-1/(p+1)}m^{p}\left(p - 1 + m^{-p}\right)=1\;,\tag{1}$$

$$(p - 1)m^p + 1=n^{1/(p+1)}\;,$$

$$m=\left(\frac{n^{1/(p+1)}-1}{p-1}\right)^{1/p}\;.\tag{2}$$

Then using (1) to substitute $p - 1 + m^{-p}$ and (2) to substitute $m$ yields

$$ \begin{eqnarray} \epsilon_{n,p}(m) &=& \left(n^{1/p}n^{-1/(p(p+1))}-1\right)m \\ &=& \left(n^{1/(p+1)}-1\right)\left(\frac{n^{1/(p+1)}-1}{p-1}\right)^{1/p} \\ &=& \left(\frac{\left(n^{1/(p+1)}-1\right)^{p+1}}{p-1}\right)^{1/p}\;. \end{eqnarray} $$

For $n=3$, $p=3$, this is about $0.171$, in agreement with your plot. To show that this is always a global maximum, note that $\epsilon_{n,p}(m)$ goes to $0$ for $m\to0$ and to $-\infty$ for $m\to\infty$, so if the derivative vanishes at a single point, it must be a global maximum.

$\endgroup$
5
  • $\begingroup$ I am pretty sure there is another solution, though. If you plot $\epsilon_p(m)$ over $[0,1]$ there is definitely a maximum. $\endgroup$ Apr 28, 2011 at 21:35
  • $\begingroup$ @charles.y.zheng: I don't see how that could be. What $p$ are you using? Here's a plot for $p=3$ that has no maximum: wolframalpha.com/input/… $\endgroup$
    – joriki
    Apr 28, 2011 at 21:50
  • $\begingroup$ Ah, sorry about that, there was a typo in the original post. $\endgroup$ Apr 29, 2011 at 0:49
  • $\begingroup$ @charles.y.zheng: When you edit your question such that correct answers become incorrect, it's good practice to make such edits visible (e.g. by adding "Edit" in bold or prepending "This is a corrected version of the question" or whatever) so that people won't be led to think the error is in the answer. I've edited my post to answer the modified question. $\endgroup$
    – joriki
    Apr 29, 2011 at 6:34
  • $\begingroup$ Noted, and thanks for the answer. $\endgroup$ Apr 29, 2011 at 10:26

You must log in to answer this question.

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