2
$\begingroup$

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:

enter image description here

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone May 9 '16 at 2:06
  • 1
    $\begingroup$ 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)$ $\endgroup$ – Mark L. Stone May 9 '16 at 2:09
  • 1
    $\begingroup$ Examine the second derivative of $f$ with respect to $w$. $\endgroup$ – whuber May 9 '16 at 13:07
  • $\begingroup$ @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. $\endgroup$ – Adam Przedniczek May 10 '16 at 15:18
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ You're halfway there: you still can get a valley with a positive second derivative (consider a parabolic function near its vertex, for instance). But since the second derivative doesn't vanish, the first derivative cannot turn around. You still need to establish that the first derivative is everywhere negative. $\endgroup$ – whuber May 9 '16 at 15:18

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.