An example where the Kullback-Leibler divergence breaks the triangle inequality

This is an example where the Kullback-Leibler divergence of probability distributions breaks the triangle inequality. This example uses three binary distributions to illustrate. The example program is written in the Go programming language.

/*

This is an example of where the divergence between probability
distributions does not obey the triangular inequality.

*/

package main

import (
        "fmt"
        "math"
)

var logtwo float64

func log2(x float64) float64 {
        return math.Log(x) / logtwo
}

func divergence(x, y []float64) float64 {
        if len(y) < len(x) {
                return math.Inf(1)
        }
        d := 0.0
        for i, x_i := range x {
                y_i := y[i]
                if y_i == 0.0 {
                        return math.Inf(1)
                }
                quotient := x_i / y_i
                d += x_i * log2(quotient)
        }
        return d
}

func main() {
        logtwo = math.Log(2)
        p := []float64{0.5, 0.5}
        q := []float64{0.25, 0.75}
        r := []float64{0.1, 0.9}
        dpq := divergence([]float64(p), []float64(q))
        dqr := divergence([]float64(q), []float64(r))
        dpr := divergence([]float64(p), []float64(r))
        fmt.Println(dpq, dqr, dpr)
}

(download)

The output looks like this:

0.20751874963942185 0.13320621934649512 0.7369655941662061


Copyright © Ben Bullock 2009-2017. All rights reserved. For comments, questions, and corrections, please email Ben Bullock (benkasminbullock@gmail.com). / Privacy / Disclaimer