# Proof that $-\log \Big(\sum_y(\sum_{x}P(x)Q(y\mid x)^{\frac{1}{1+r}})^{r+1}\Big)$ is increasing

I want to prove that the following is increasing:

$-\log \Big(\sum_y \sum_{x_1}P_1(x_1)Q_1(y\mid x_1)^{\frac{1}{1+r}}(\sum_{x_2}P_2(x_2)Q_2(y\mid x_2)^{\frac{1}{1+r}})^r\Big)$

Here $P_1, P_2$ are probability mass functions, $Q_1,Q_2$ are transition matrices.

I know for a fact that I had something like the following

$-\log \Big((\sum_{x} P(x)Q(y\mid x)^{\frac{1}{1+r}})^{r+1}\Big)$

then it would have been increasing. The proof follows Holder's inequality. since for $r\leq s$ $(\sum_j q_j b_j^{\frac{1}{r+1}})^{r+1} \geq (\sum_j q_j b_j^{\frac{1}{s+1}})^{s+1}$

Note1:I don't think taking the derivative is going to help, the expression is extremely ugly.

First, this is not true. Consider $a_i=a, b_i=b, \forall i$ for some $a, b>0$. When $a<b$ the function strictly increases. Second, in the case the inequality is true, it is not necessary that $a_i,b_i\le 1$.

The answer to the modified question is again in the negative. Try the simplest case, where $x$'s are of only $1$ element and $y$ of only $2$ elements, $Q_1(Y|X_1)=[0.6\quad 0.4],\, Q_2(Y|X_2)=[0.1\quad 0.9]$. The function first increases then decreases with respect to positive $r$.

A good question to ask is whether the function of $r$ inside the logarithm is convex. It is not. Neither is it in $[0,1]$, e.g., when $Q_1(Y|X_1)=[0.3075,0.3388,0.3538]^T,\, Q_2(Y|X_2)=[0.4781,0.0001,0.5218]^T$. It is also not convex as a function of $u:=\frac{1}{1+r}$ either. $f\big(\frac{1}{u}-1\big),\, u\in[0,1]$ as defined below can have an inflection point. $f(r=\infty)=\sum_i\prod_kb_{ik}^{q_k}\le \sum_i\sum_kq_kb_{ik}=1$ by Jensen's inequality on the logarithm.

For my own benefit and possibly others, I would like to show the simple fact that $$f(r):= \sum_i\Big(\sum_j p_ja_{ij}^\frac{1}{1+r}\Big)\Big(\sum_k q_kb_{ik}^\frac{1}{1+r}\Big)^r\le 1$$ where all variables are nonnegative and $\sum_i a_{ij}=\sum_i b_{ij}=1$ and $\sum_j p_j=\sum_k q_k=1$.

To this end, we have $$\sum_jp_ja_{ij}^\frac{1}{1+r}\le \Big(\sum_jp_ja_{ij}\Big)^\frac{1}{1+r}=:x_i^\frac{1}{1+r},\quad \sum_k q_kb_{ik}^\frac{1}{1+r}\le \Big(\sum_jq_kb_{ik}\Big)^\frac{1}{1+r}=:y_i^\frac{1}{1+r}$$ by Jensen's inequality. \begin{align} f(r)&\le \sum_i x_i^\frac{1}{1+r}y_i^\frac{r}{1+r} \\ &\le \Big(\sum_i x_i\Big)^\frac{1}{1+r}\Big(\sum_i y_i\Big)^\frac{r}{1+r} \\ &=1 \end{align} by Holder's inequality and $$\sum_i x_i =\sum_jp_j\sum_ia_{ij}=1=\sum_jq_j\sum_ib_{ij}=\sum_iy_i.$$ The desired upper bound is established.

• Oh you are right. I did not think of that, so I omitted some parts of the problem to make it simpler. My problem is actually the following: – s.sh Nov 20 '15 at 2:10
• I changed the question, do you think it is correct now? – s.sh Nov 20 '15 at 2:19
• You should plot the graph with my parameters on $[0, 2]$ and look really carefully at it probably with a straight ruler. Let me know if you still do not see it being concave at $r=1$. I have not looked at the problem with $s$ yet. Maybe you can pose it as another question here. Please provide the link here if you do. – Hans Nov 24 '15 at 7:57
• $f(u)=\log \sum_i a_i^u b_i^{1-u}=\log \sum_i a_i^{\theta x+\bar{\theta}y}b_i^{\theta(1-x)+\bar{\theta}(1-y)}\leq \log[ \Big( \sum_i a_i^x b_i^{1-x} \Big)^\theta \Big(\sum_i a_i^y b_i^{1-y}\Big)^\bar{\theta}]=\theta f(x)+\bar{\theta}f(y)$ So the logarithm is also convex. Right? Chain rule was correct I guess. – s.sh Nov 25 '15 at 4:54
• Sorry, I missed that. You are right about the convexity of your $f$. Your reasoning about $g(u(r))$ is still wrong due to the sign of $g'(u)$ in the chain rule. – Hans Nov 25 '15 at 5:05