$-\varepsilon\log(x)\overset{?}{\geq} -\log(\varepsilon x)$

Question

I'm refering to this proof: http://en.wikipedia.org/wiki/Quantum_relative_entropy#The_result

In there it's stated that "Since the matrix $(P_{ij})_{ij}$ is a doubly stochastic matrix and $-\log$ is a convex function," $$\sum_ip_i(\log p_i-\sum_j(\log q_j)P_{ij}) \geq \sum_i p_i(\log p_i - \log(\sum_j q_jP_{ij})).$$

Note that $0<P_{ij},q_j\leq 1$. For $x,y,\varepsilon<1$, I think that the correctness of this step relies on $$-\varepsilon\log x \geq -\log(\varepsilon x)$$ and $$-\log x - \log y \geq -\log(x+y).$$

The former looks terribly wrong, while the latter looks about right. Now, I don't see why this step is correct and can't think of any reason. Any ideas?

Edit: A little graph supporting that the former is wrong (copy the whole link) http://www.wolframalpha.com/input/?i=from+0.001+to+1+plot+%28-log%280.1*x%29%2C+-0.1*log%28x%29%29

Alternatively, enter

from 0.001 to 1 plot (-log(0.1*x), -0.1*log(x))

at http://www.wolframalpha.com

Answer 1

This The statement from the proof relies on the fact the $P$ is a doubly stochastic matrix (http://en.wikipedia.org/wiki/Doubly_stochastic_matrix) therefore the sum of all it's entries is 1, and the fact the $-\log$ is convex.

Since it is a doubly stochastic matrix, $\sum_j{(-\log{q_j})P_{ij}}$ is a convex expression (wighted average) - that means, since it is convex function (http://en.wikipedia.org/wiki/Convex_function), that $\sum_j{(-\log{q_j})P_{ij}}\geq-\log(\sum_j{q_jP_{ij}})$.

EDIT: I was asked to explain further. Please read in wikipedia what is a convex set and function. Perhaps the "convex expression" notation is incorrect but what I meant by this is for coeffients adding to 1, $\sum_ia_i=1$ - they are the weights! the convex expression is the weighted average $\sum_i{a_ib_i}$ for $\{b_i\}_i$ (could be numbers, vectors, functions etc.).

Now a convex function $f$ satisfies: $f(\sum_i{a_ib_i})\leq\sum_i{a_if(b_i)}$. This should make it clear why the statement from the proof is correct.

About your arguments, I think they are too strong. You can try using graphs on WolframAlpha and see what happens. I've switched letters for convenience. $-y\log x\geq-\log(yx)\iff y\log x\leq \log(yx) \iff \log x^y\leq \log(yx) \iff x^y - xy\leq 0$

EDIT2: Thanks to @Semiclassical I've found a point worth mentioning. $$\sum_i{p_i(\log p_i-\sum_j{(\log q_j)P_{ij}})}=\sum_i{p_i\log p_i-\sum_i\sum_j{(\log q_j)P_{ij}}}=\sum_i{p_i\log p_i+\sum_{i,j}{(-\log q_j)P_{ij}}}$$ and think of running on the matrix as one finite series - it doesn't matter which way you go, you end up with the same sum.

Answer 2

My analysis is that the confusion is coming in between the statement of $-\ln x$ being concave up, which is $$-t \log x_1 -(1-t) \log x_2 \geq -\log(t x_1+(1-t) x_2)$$ and the two claims you came up with: $$-\epsilon \log x\geq -\log \epsilon x,\hspace{2.6cm}(1) \\ -\log x_1 - \log x_2 \geq \log(x_1+x_2).\hspace{.2cm}(2)$$ Note that the first inequality simply expresses the fact that any line segment connecting two points on the curve $y=-\ln x$ will lie above the curve itself. As an attempt to get your first claim from it, we take $x_2=1$ to get $$-t \log x_1 \geq -\log(t x_1 +1-t)$$ in which case we see that this claim is not identical to $(1)$. Noting that $t x_1 +1-t>t x_1$, we see that this lower bound is smaller (and therefore weaker) than the one demanded by $(1)$.

What about $(2)$? We take $t=1-t=1/2$ and reorganize a little to obtain $$-\log x_1 -\log x_2 \geq -2\log\left(\frac{x_1+x_2}{2}\right)=-2\log(x_1+x_2)+2\log 2$$ which again is different than the suggested inequality. But, in this case, if $x_1+x_2<1$ then this lower bound is greater than $-\log(x_1+x_2$). Hence (2) is, in fact, implied by this concavity bound.

To sum up: Of your two claims, the first is too strong and the second too weak compared to the correct inequality.