2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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: $\endgroup$ – s.sh Nov 20 '15 at 2:10
  • $\begingroup$ I changed the question, do you think it is correct now? $\endgroup$ – s.sh Nov 20 '15 at 2:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Hans Nov 24 '15 at 7:57
  • 1
    $\begingroup$ $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. $\endgroup$ – s.sh Nov 25 '15 at 4:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Hans Nov 25 '15 at 5:05

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.