CSISZÁR f–DIVERGENCE, OSTROWSKI’S INEQUALITY AND MUTUAL INFORMATION

S. S. DRAGOMIR, V. GLUŠČEVIĆ, AND C. E. M. PEARCE

Abstract. The Ostrowski integral inequality for an absolutely continuous function is used to provide a simple approximation to Csiszár’s f–divergence measure for the difference between two probability distributions defined on a finite set. Concrete examples are given and some applications made to mutual information.

1. Introduction

The difference between two probability measures p, q on a set A = {α_{i}|1 ≤ i ≤ n} is commonly measured in a variety of ways. Denote by p_{i}, q_{i} the associated point probabilities for the event α_{i} ∈ A. To avoid triviality we assume that p_{i} + q_{i} > 0 for each i. The variational distance (ℓ_{1}–distance) and information divergence (Kullback–Leibler divergence) between the distributions p and q are defined respectively by

V (p, q) := ∑_{i=1}^{n} |p_{i} − q_{i}|,

D(p, q) := ∑_{i=1}^{n} p_{i} ln \frac{p_{i}}{q_{i}} .

Another measure, which proves a useful benchmark in our analysis, is the chi– squared divergence of p, q, which is defined by

D_{χ^{2}}(p, q) := ∑_{i=1}^{n} \frac{p_{i}^{2}}{q_{i}} − 1 = ∑_{i=1}^{n} \frac{(p_{i} − q_{i})^{2}}{q_{i}} .

The last two measures are unfortunately infinite if p_{i} > 0 but q_{i} = 0 for some i. This complication is obviated in the triangular discrimination between p and q, which is defined as in [10] by

Δ(p, q) := ∑_{i=1}^{n} \frac{|p_{i} − q_{i}|^{2}}{p_{i} + q_{i}} .

A generalization of this measure, parameterized by a natural number υ, is

Δ_{υ}(p, q) := ∑_{i=1}^{n} \begin{matrix}|p_{i} − q_{i}| & 2υ \\ (p_{i} + q_{i}) & 2υ−1 \end{matrix} ,

1991 Mathematics Subject Classification. 94A17, 26D15.

Key words and phrases. Csiszár f–divergence, Ostrowski’s inequality, divergence measure, mutual information.

which we refer to as triangular discrimination of order υ (see [10]). Another common choice is the Hellinger discrimination

h^{2}(p, q) := \frac{1}{2} ∑_{i=1}^{n} (\sqrt{p_{i}} − \sqrt{q_{i}})^{2} .

For applications it is important to know how these divergences compare with one another. The basic relations between V, Δ and h^{2} are

\frac{1}{2}V^{2}(p, q) ≤ Δ(p, q) ≤ V (p, q)

and

2h^{2}(p, q) ≤ Δ(p, q) ≤ 4h^{2}(p, q)

(see LeCam [8] and Dacunha–Castelle [5]). From these we may deduce that

\frac{1}{8}V^{2}(p, q) ≤ h^{2}(p, q) ≤ \frac{1}{2}V (p, q).

The coefficients in these inequalities are best possible (cf. [10]).

The first half of this result has been improved by Kraft [7], who showed that

\frac{1}{8}V^{2}(p, q) ≤ h^{2}(p, q) (1 − \frac{1}{2}h^{2}(p, q)) .

We note also the important inequality

D(p, q) ≥ −2 ln (1 − h^{2}(p, q))

(see Dacunha–Castelle [5]). It follows from this that

D(p, q) ≥ 2h^{2}(p, q).

Again the coefficient 2 is best–possible (see [10]).

The key to unity in this diversity is that all the discrepancy measures considered above are particular instances of Csiszár f–divergences. If f : [0, ∞) → R is convex, the Csiszár f-divergence between p and q is defined by

(1.1)  I_{f}(p, q) := ∑_{i=1}^{n} q_{i}f (p_{i}/q_{i})

(see Csiszár [2]–[4]). Thus the family (f_{s})_{s≥1} of functions with

f_{s}(u) = |u − 1|^{s}(u + 1)^{1−s}

gives rise to variational distance when s = 1, triangular discrimination when s = 2 and triangular discrimination of order υ when s = 2υ (see [10]). The choice f(u) = \frac{1}{2}(\sqrt{u} − 1)^{2} gives rise to Hellinger discrimination and f(u) = u ln u to Kullback-Leibler divergence. The chi–squared divergence is given by f(u) = (u − 1)^{2}.

For all of the above choices f(1) = 0, so that I_{f}(p, p) = 0. The convexity of f then ensures that I_{f}(p, q) is nonnegative.

In Section 2 we derive, by the use of Ostrowski’s integral inequality for absolutely continuous mappings with essentially bounded first derivative, an approximation for the Csiszár f–divergence in terms of an integral mean. With many concrete examples this provides very simple approximations. Section 3 considers some of the examples noted above and Section 4 the case when each pair p_{i}, q_{i} are very close. Finally, in Section 5, we look at applications to mutual information.

It needs to be stressed that as these estimates lose most of the detailed information involved in the values p_{i}, q_{i}, the approximations, while very simple, can also be very crude.

2. An inequality for Csiszár f–divergence

In some applications it is convenient to make use of definition (1.1) for functions f : [0, ∞) → R which are continuous but not necessarily convex. An illustrative example is given in Section 3. Accordingly our main result, Theorem 1 below, does not assume convexity.

We assume in what follows that there exist real numbers r, R with

0 < r ≤ p_{i}/q_{i} ≤ R < ∞

for all i ∈ {1, ..., n}. Note that if r > 1, then p_{i} > q_{i} for each i, which gives 1 = ∑_{i} p_{i} > ∑_{i} q_{i} = 1, a contradiction. Hence r ≤ 1. A similar argument gives R ≥ 1.

Further suppose that the restriction of f to the compact interval [r, R] is absolutely continuous. We derive an approximation to the Csiszár f–divergence in terms of the integral mean of f over [r, R]. We shall show in Theorem 1 below that if p and q are close in the sense that R − r is small, then the integral mean

\frac{1}{R − r} ∫_{r}^{R} f(t)dt

approximates the Csiszár f–divergence to first order.

We make use of Ostrowski’s integral inequality, which states the following. See [6] for a short proof and some applications to numerical integration and special means.

Theorem A. Assume that g : [a, b] → R is absolutely continuous with g′ ∈ L_{∞}[a, b], that is, that

∥g′ ∥_{∞} := ess sup_{t∈[a,b]} |g′(t)| < ∞.

Then

|g(x) − \frac{1}{b − a} ∫_{a}^{b} g(t)dt| ≤ [\frac{1}{4} + (\frac{x − \frac{a+b}{2}}{b − a} )^{2}] (b − a) ∥g′ ∥_{∞}

for all x ∈ [a, b].

A further key result is due to Diaz and Metcalf (see [9, p. 61]).

Theorem B. Suppose a_{k}(≠ 0) and b_{k} (k = 1, ..., n) are real numbers satisfying m ≤ b_{k}/a_{k} ≤ M. Then

∑_{k=1}^{n} b_{k}^{2} + mM ∑_{k=1}^{n} a_{k}^{2} ≤ (M + m) ∑_{k=1}^{n} a_{k}b_{k}.

Equality holds if and only if for each k either b_{k} = ma_{k} or b_{k} = Ma_{k}.

We shall make use of a slight extension of this.

Proposition 1. Suppose the conditions of the Diaz–Metcalf result hold and t_{k} > 0 for k = 1, ..., n. Then

∑_{k=1}^{n} t_{k}b_{k}^{2} + mM ∑_{k=1}^{n} t_{k}a_{k}^{2} ≤ (M + m) ∑_{k=1}^{n} t_{k}a_{k}b_{k}.

Equality holds if and only if for each k either b_{k} = ma_{k} or b_{k} = Ma_{k}.

Proof. We have for k = 1, 2, …, n that

(b_{k}/a_{k} − m)(M − b_{k}/a_{k})t_{k}a_{k}^{2} ≥ 0.

The desired result follows on summation over k. □

Theorem 1. Assume that f : [r, R] → R is absolutely continuous on [r, R] and f′ ∈ L_{∞}[r, R]. Then

|I_{f}(p, q) − \frac{1}{R − r} ∫_{r}^{R} f(t)dt| (2.1)

≤ [\frac{1}{4} + \frac{1}{(R − r)^{2}} \{D_{χ^{2}}(p, q) + (\frac{R + r}{2} − 1)^{2}\}] (R − r) ∥f′ ∥_{∞}

≤ \frac{1}{2}(R − r) ∥f′ ∥_{∞} .

Proof. By Ostrowski’s integral inequality, we have

|f (\frac{p_{i}}{q_{i}} ) − \frac{1}{R − r} ∫_{r}^{R} f(t)dt| ≤ [\frac{1}{4} + ( \frac{\frac{p_{i}}{q_{i}} − \frac{R+r}{2}}{R − r} )^{2}] (R − r) ∥f′ ∥_{∞}

for each i ∈ {1, ..., n}.

We may multiply by q_{i}, sum the resultant inequalities and use the generalized triangle inequality to obtain

|I_{f}(p, q) − \frac{1}{R − r} ∫_{r}^{R} f(t)dt|

≤ ∑_{i=1}^{n} q_{i} |f (\frac{p_{i}}{q_{i}} ) − \frac{1}{R − r} ∫_{r}^{R} f(t)dt|

≤ [\frac{1}{4} + \frac{1}{(R − r)^{2}} ∑_{i=1}^{n} q_{i} (\frac{p_{i}}{q_{i}} − \frac{R + r}{2} )^{2}] (R − r) ∥f′ ∥_{∞} .

Since

∑_{i=1}^{n} q_{i} (\frac{p_{i}}{q_{i}} − \frac{R + r}{2} )^{2} = ∑_{i=1}^{n} \frac{p_{i}^{2}}{q_{i}} − (R + r) + (\frac{R + r}{2} )^{2}

≤ ∑_{i=1}^{n} \frac{p_{i}^{2}}{q_{i}} − 1 + (\frac{R + r}{2} − 1)^{2}

= D_{χ^{2}}(p, q) + (\frac{R + r}{2} − 1)^{2} ,

this yields the first inequality in (2.1).

For the second, set b_{k} = \sqrt{p_{k}/q_{k}} and a_{k} = \sqrt{q_{k}/p_{k}} (k = 1, ..., n). Then a_{k}/b_{k} = p_{k}/q_{k} ∈ [r, R] (k ∈ {1, ..., n}). On applying Proposition 1 for t_{k} = p_{k} (k = 1, ..., n), we get

∑_{k=1}^{n} p_{k} (\sqrt{\frac{p_{k}}{q_{k}}} )^{2} + rR ∑_{k=1}^{n} p_{k} (\sqrt{\frac{q_{k}}{p_{k}}} )^{2} ≤ (r + R) ∑_{k=1}^{n} p_{k}\sqrt{\frac{p_{k}}{q_{k}}} · \sqrt{\frac{q_{k}}{p_{k}}} ,

or equivalently

∑_{k=1}^{n} \frac{p_{k}^{2}}{q_{k}} + rR ≤ R + r.

Thus

D_{χ^{2}}(p, q) ≤ r + R − rR − 1 = (1 − r)(R − 1)

and so

\frac{1}{4} + \frac{1}{(R − r)^{2}} [D_{χ^{2}}(p, q) + \frac{1}{4}(R + r − 2)^{2}] ≤ \frac{1}{2}

and the theorem is proved. □

Corollary 1. Let f satisfy the conditions of Theorem 1. If ε > 0 and

0 ≤ R − r ≤ 2ϵ/ ∥f′ ∥_{∞} ,

then

|I_{f}(p, q) − \frac{1}{R − r} ∫_{r}^{R} f(t)dt| ≤ ϵ.

Theorem 1 can be reformulated to emphasize the approximation aspect.

Corollary 2. Let f : [0, 2] → R be absolutely continuous with f′ ∈ L_{∞}[0, 2]. If η ∈ (0, 1) and p(η), q(η) are such that

|\frac{p_{i}(η)}{q_{i}(η)} − 1| ≤ η

for all i ∈ {1, ..., n}, then

I_{f}(p(η), q(η)) = \frac{1}{2η} ∫_{1−η}^{1+η}f(t)dt + R_{f}(p, q, η)

and the remainder R_{f}(p, q, η) satisfies

|R_{f}(p, q, η)| ≤ \frac{η}{2} [1 + \frac{1}{η^{2}} D_{χ^{2}} (p(η), q(η))] ∥f′ ∥_{∞} ≤ η ∥f′ ∥_{∞} .

This follows by Theorem 1 with the choices R = 1 + η and r = 1 − η (η ∈ (0, 1)).

6 S. S. DRAGOMIR, V. GLUŠČEVIĆ, AND C. E. M. PEARCE

3. Particular cases

For Kullback–Leibler distance, we take f(u) = u ln u. With this choice we have ∥f′ ∥_{∞} = ln(eR) and

∫_{r}^{R} f(t)dt = \frac{1}{4} [R^{2} ln R^{2} − r^{2} ln r^{2} − (R^{2} − r^{2})]

= \frac{R^{2} − r^{2}}{4} ln [(\frac{(R^{2})^{(R^{2})}}{(r^{2})^{(r^{2})}} )^{1/(R^{2}−r^{2})} · \frac{1}{e}]

= \frac{R^{2} − r^{2}}{4} I [(R^{2}, r^{2})] ,

where the identric mean I(a, b) for positive arguments is given by

I(a, b) := \{ \begin{matrix}a & if b = a \\ \frac{1}{e} (\frac{b^{b}}{a^{a}} )1/(b−a) & if b ≠ a. \end{matrix}

The conclusion of Theorem 1 reads

|D(p, q) − \frac{R + r}{4} ln [I (R^{2}, r^{2})]| (3.1)

≤ [\frac{1}{4} + \frac{1}{(R − r)^{2}} [D_{χ^{2}}(p, q) + (\frac{R + r}{2} − 1)^{2}]] (R − r) ln(eR)

≤ \frac{1}{2}(R − r) ln(eR).

If we take the concave map f : (0, ∞) → R given by f(u) = ln u, then we have

I_{f}(p, q) = ∑_{k=1}^{n} q_{i} ln \frac{p_{i}}{q_{i}} = −D(q, p).

With this choice ∥f′ ∥_{∞} = 1/r and the identric mean reappears through

\frac{1}{R − r} ∫_{r}^{R} f(t)dt = ln [I(r, R)] .

Theorem 1 provides

|D(q, p) − ln [\frac{1}{I(r, R)}]| (3.2)

≤ [\frac{1}{4} + \frac{1}{(R − r)^{2}} [D_{χ^{2}}(p, q) + (\frac{R + r}{2} − 1)^{2}]] (\frac{R}{r} − 1)

≤ \frac{1}{2} (\frac{R}{r} − 1) .

For Hellinger discrimination f(u) = (\sqrt{u} − 1)^{2} /2, so

f′(u) = \frac{\sqrt{u} − 1}{2\sqrt{u}}, f′′(u) = \frac{1}{4u}

for u ∈ (0, ∞) and

∥f′ ∥_{∞} = sup_{u∈[r,R]} |f′(u)| = |f′(R)| = \frac{\sqrt{R} − 1}{2\sqrt{R}}.

Also

\frac{1}{R − r} ∫_{r}^{R} f(t)dt = \frac{R + r}{4} − \frac{2}{3} · \frac{R + \sqrt{rR} + r}{\sqrt{r} + \sqrt{R}} + \frac{1}{2},

and inequality (2.1) becomes

|h^{2}(p, q) − [\frac{R + r}{4} − \frac{2}{3} · \frac{R + \sqrt{rR} + r}{\sqrt{r} + \sqrt{R}} + \frac{1}{2}]|

≤ [\frac{1}{4} + \frac{1}{(R − r)^{2}} \{D_{χ^{2}}(p, q) + (\frac{R + r}{2} − 1)^{2}\}] (R − r) [\frac{\sqrt{R} − 1}{2\sqrt{R}}]

≤ \frac{1}{4\sqrt{R}}(R − r)(\sqrt{R} − 1).

For variational distance, f(u) = |u − 1|, which is absolutely continuous on [r, R]. We have

f′(u) := \{ \begin{matrix}−1 & if u ∈ (r, 1) \\ 1 & if u ∈ (1, R), \end{matrix}

so that

∥f′ ∥_{∞} = sup_{t∈[r,R]} |f′(t)| = 1.

Further

\frac{1}{R − r} ∫_{r}^{R} f(t)dt = \frac{1}{R − r} [∫_{r}^{1}(1 − u)du + ∫_{1}^{R}(u − 1)du]

= \frac{1}{R − r} [\frac{(r − 1)^{2}}{2} + \frac{(R − 1)^{2}}{2} ]

= \frac{1}{R − r} [\frac{(R − r)^{2}}{4} + (\frac{r + R}{2} − 1)^{2}] .

Theorem 1 provides

|V (p, q) − \frac{1}{R − r} [\frac{(R − r)^{2}}{4} + (\frac{r + R}{2} − 1)^{2}]|

≤ [\frac{1}{4} + \frac{1}{(R − r)^{2}} \{D_{χ^{2}}(p, q) + (\frac{R + r}{2} − 1)^{2}\}] (R − r)

≤ \frac{1}{2}(R − r).

Our final example relates to triangular discrimination, which arises with f(u) = (u − 1)^{2}/(u + 1). We have

f(u) = u + 1 − \frac{4u}{u + 1}, f′(u) = 1 − \frac{4}{(u + 1)^{2}}

for u ∈ [0, ∞), so that

∥f′ ∥_{∞} = sup_{u∈[r,R]} |f′(u)| = |f′(R)| = \frac{(R − 1)(R + 1)}{(R + 1)^{2}}.

Also

\frac{1}{R − r} ∫_{r}^{R} f(u)du = \frac{R + r}{2} + ln (\frac{R + 1}{r + 1})^{4/(R−r)} − 3

and Theorem 1 provides

|Δ(p, q) − [\frac{R + r}{2} + ln (\frac{R + 1}{r + 1})^{4/(R−r)} − 3]|

≤ [\frac{1}{4} + \frac{1}{(R − r)^{2}} \{D_{χ^{2}}(p, q) + (\frac{R + r}{2} − 1)^{2}\}] \frac{(R − r)(R − 1)(R + 3)}{(R + 1)^{2}}

≤ \frac{1}{2} \frac{(R − r)(R − 1)(R + 3)}{(R + 1)^{2}}.

4. Some numerical examples

One situation of practical interest is where p_{i} and q_{i} are close, so that we have p_{i} = p_{i}(ε), q_{i} = q_{i}(ε) and

(4.1)  |\frac{p_{i}(ε)}{q_{i}(ε)} − 1| ≤ ε ε ∈ (0, 1)

for all i ∈ {1, ..., n}. With R = ε + 1 and r = 1 − ε, we obtain from (3.1) that

|D(p(ε), q(ε)) − \frac{1}{2} ln [I ((1 + ε)^{2} , (1 − ε)^{2})]|

≤ \frac{ε}{2} [1 + \frac{1}{ε^{2}} D_{χ^{2}}(p(ε), q(ε))] ln [e(1 + ε)]

≤ ε ln [e(1 + ε)] .

Consequently if p(ε), q(ε) are in the sense of (4.1), we can approximate the Kullback-Leibler distance D(p(ε), q(ε)) by (1/2) ln [I ((1 + ε)^{2} , (1 − ε)^{2})] and the error of the approximation is less than

E(ε) := ε ln[e(1 + ε)].

From (3.2), we derive

|D(q(ε), p(ε)) − ln [\frac{1}{I(1 − ε, 1 + ε)}]| ≤ \frac{1}{2} \frac{ε}{1 − ε} [1 + \frac{1}{ε^{2}} D_{χ^{2}}(p(ε), q(ε))]

≤ \frac{ε}{1 − ε}

for ε ∈ (0, 1).

Consequently for p(ε), q(ε) satisfying (4.1), we can approximate the Kullback– Leibler distance D(p(ε), q(ε)) by ln [I^{−1}(1 − ε, 1 + ε)] and the error of the approximation is less than ε/(1 − ε) for ε ∈ (0, 1).

5. Application to mutual information

We consider mutual information, which is a measure of the amount of information that one random variable provides about another. It is the reduction of uncertainty about one variable due to knowledge of the other (see, for example, [1]). Definition 1. Consider two discrete–valued random variables X and Y with a joint probability mass function t(x, y) and marginal probability mass functions p(x) (x ∈ X) and q(y) (y ∈ Y). The mutual information is the relative entropy between the joint distribution and the product distribution, that is,

I(X; Y) = ∑_{x∈X} ∑_{y∈Y} t(x, y) ln [\frac{t(x, y)}{p(x)q(y)}] = D (t(x, y), p(x)q(y)) ,

where as before D(·, ·) denotes Kullback–Leibler distance.

We assume that

(5.1)  s ≤ \frac{t(x, y)}{p(x)q(y)} ≤ S for all (x, y) ∈ X × Y.

Much as with r, R we have s ≤ 1 ≤ S.

We also may consider mutual information in a chi–squared sense, that is,

I_{χ^{2}} (X; Y) := ∑_{(x,y)∈X ×Y} \frac{t^{2}(x, y)}{p(x)q(y)} − 1.

Inequality (3.1) yields the following proposition. Proposition 2. If t, p and q satisfy (5.1), then

|I(X; Y) − \frac{s + S}{4} ln [I (s^{2}, S^{2})]|

≤ [\frac{1}{4} + \frac{1}{(S − s)^{2}} [I_{χ^{2}} (X; Y) + (\frac{s + S}{2} − 1)^{2}]] (S − s) ln[eS]

≤ \frac{1}{2}(S − s) ln(eS).

Remark 1. The condition t(x, y) = p(x)p(y) for all (x, y) ∈ X × Y means that the random variables X and Y are independent. We may refer to them as “quasi– independent” if

|\frac{t(x, y)}{p(x)q(y)} − 1| ≤ δ (δ ∈ (0, 1))

for all (x, y) ∈ X × Y. When this occurs, we can approximate the mutual information I(X; Y) by

\frac{1}{2} [\frac{(1 + δ)^{2} ln(1 + δ)^{2} − (1 − δ)^{2} ln(1 − δ)^{2}}{4δ} − 1] (δ ∈ (0, 1))

with an error less than E(δ) for t ∈ (0, 1).

References

[1] T. M. Cover and J. A. Thomas, Elements of information theory, Wiley, 1991.

[2] I. Csiszár, A note on Jensen’s inequality, Studia Sci. Math. Hung., 1 (1966) 185–188.

[3] I. Csiszár, Information–type measures of differences of probability distributions and indirect observation, Studia Sci. Math. Hung., 2 (1967) 299–318.

[4] I. Csiszár, On topological properties of f–divergence, Studia Sci. Math. Hung., 2 (1967) 329–339.

[5] D. Dacunha–Castelle, Ecole d’été de probabilités de Saint–Fleur, VII-1977, Berlin, Heidelberg, New York: Springer, 1978.

[6] S. S. Dragomir and S. Wang, Application of Ostrowski’s inequality to the estimation of error bounds for some special means and for some numerical quadrature rules, Appl. Math. Lett., 11 (1998), 105–109.

[7] C. Kraft, Some conditions of consistency and uniform consistency of statistical procedure, Univ. of California Publ. in Statistics, Ph.D. Thesis, 1 (1955), 125–142.

[8] L. LeCam, Asymptotic methods in statistical decision theory, New York: Springer, 1986.

[9] D. S. Mitrinović, Analytic inequalities, Springer Verlag, 1970.

[10] F. Topsoe, Some inequalities for information divergence and related measures of discrimination, RGMIA Res. Rep. Coll. 2 (1999) No. 1, 85–98.

Department of Computer and Mathematical Sciences, Victoria University of Technology, PO Box 14428, MCMC, Melbourne, Victoria 8001, Australia

  E-mail address: sever@matilda.vu.edu.au

Royal Australian Air Force, ARDU, P.O. Box 1500, Salisbury SA 5108, Australia

  E-mail address: vgluscev@maths.adelaide.edu.au

Applied Mathematics Department, The University of Adelaide, Adelaide, SA 5005, Australia

  E-mail address: cpearce@maths.adelaide.edu.au