# Monotonicity of special case of Kullback-Leibler divergence

I have two discrete distributions $\tau$ and $\rho$ with the same support $\Omega$. I'm considering a weighted mixture of these distributions described by the following function: $$f(w) = (1-w) \cdot \tau + w \cdot \rho, ~~ \text{where} ~~ w \in [0,1]$$

I'm particulary interested in very special case of Kullback-Leibler divergence / relative entropy: $$KL(f(w), \rho) = \sum\limits_{i \in \Omega} ((1-w) \cdot \tau_i + w \cdot \rho_i) \cdot \ln (\frac{(1-w) \cdot \tau_i + w \cdot \rho_i}{\rho_i})$$

Generally, $KL(f(0), \rho) \geq 0$ and decreases towards $KL(f(1), \rho) = 0$ as $w$ goes from $0$ to $1$.

I would like to formally assure that this very specific case of Kullback-Leibler divergence is MONOTONICALLY decreasing, because I wonder if there's a possibility of such phenomenon that I would call "cannot escape from the valley", which is depicted below:

• It is continuous and I think it is monotonically decreasing as w goes from 0 to 1, but haven't proved it. I think, but with less confidence, it's a convex function of w over that range. Anyhow, unless you're really worried about execution speed, just throw it in any descent pre-canned nonlinear equation solver which allows the 0 <= w <= 1 bound constraints, or alternatively, nonlinear optimizer with bound constraints using $(KL-C)^2$ as objective function. If KL(0) >= C >= 0, and is strictly monotonic, there should be unique solution. Bisection would also work. Maybe try Math board for proof. Commented May 9, 2016 at 2:06
• None of these methods require monotonicity. If you don't have it, there could be a possibility of multiple solutions to KL(w) = C, but you should still find at least one of them. Note that in this comment and previous comment, I used abbreviation of KL(w) meaning what you wrote as $KL(f(w),\rho)$ Commented May 9, 2016 at 2:09
• Examine the second derivative of $f$ with respect to $w$.
– whuber
Commented May 9, 2016 at 13:07
• @gung I hope this reworked form of my question is sufficient, especially that with some hits by whuber I solved my problem. So, if you find it as still irrelevant, I would delete it completly. Commented May 10, 2016 at 15:18

According William A. Huber comment, which solves the problem and proves that this function is monotonically decreasing: The second derivative is always non-negative. $$h_i''(w) = \frac{(\rho_i - \tau_i)^2}{\rho_i} \cdot \frac{1}{(1 - w) \cdot \frac{\tau_i}{\rho_i} + w}$$ $$(1 - w) \cdot \frac{\tau_i}{\rho_i} + w = (1 - \frac{\tau_i}{\rho_i}) \cdot w + \frac{\tau_i}{\rho_i} ~~\text{this is linear function of w}$$ This linear function from denominator takes values from $[\frac{\tau_i}{\rho_i}, 1]$ or $[1, \frac{\tau_i}{\rho_i}]$, thus the whole second derivative is non-negative, hence convex and I won't get such "valley".
As William cleverly pointed out, that's no the end, because I still must prove that this function is decreasing. I can accomplish that by using $h_i$ convexity and Jensen's inequality: $$\forall_{t \in [0,1]}~ h(t \cdot w_1 + (1-w) \cdot w_2) \leq t \cdot h(w_1) + (1-t) \cdot h(w_2)$$ Let's fix $w_2 = 1$ for which $h(w_2) = h(1) = 0$. Now, $w_3 = t \cdot w_1 + (1-w)$ denotes some point to the right of $w_1$ (between $w_1$ and $1$): $$\forall_{t \in [0,1]}~ h(t \cdot w_1 + (1-w) \cdot 1) \leq t \cdot h(w_1)$$ So, we have $w_1 \leq w_3$ and thankfully $h(w_1) \geq h(w_3)$, thus this function is monotonically decreasing.