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

Improve this question
$\endgroup$
4
  • 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
    Commented May 9, 2016 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
    Commented May 9, 2016 at 2:09
  • 1
    $\begingroup$ Examine the second derivative of $f$ with respect to $w$. $\endgroup$
    – whuber ♦
    Commented May 9, 2016 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
    Commented May 10, 2016 at 15:18

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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 ♦
    Commented May 9, 2016 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.