THE APPROXIMATION OF CSISZÁR f–DIVERGENCE FOR ABSOLUTELY CONTINUOUS MAPPINGS

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

Abstract. We consider the approximation of the Csiszár f–divergence of two probability distributions over a finite alphabet when the first (or second) derivative of f is absolutely continuous and the second (respectively third) essentially bounded. The approximants are suggested by results from numerical integration theory, which also provides the means of deriving error bounds. Tools are also developed for obtaining tight bounds.

1. Introduction

A common situation in information theory concerns an alphabet {a_{i}}_{i=1}^{n} on which two probability distributions p = (p_{1}, …, p_{n}), q = (q_{1}, …, q_{n}) are defined. For example, p_{i}, q_{i} may represent respectively the frequency with which the symbol a_{i} occurs before and after transmission through a noisy channel.

A variety of divergence or discrimination measures are in common use for quantifying the difference between such a pair p, q. The authors give a number of these in [4]. Two of these, that we shall invoke shortly in this introduction, are the chi–squared and (absolute) chi–cubed measures, which are given by

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

for m = 2 and m = 3 respectively. The diversity of the measures appearing in the literature is remarkable. Csiszár [1]–[3] has systematised the field by showing that a majority of these can be represented in the form

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

for a suitable choice of function f. Typically but not invariably f(1) = 0 and f is nonnegative and strictly convex. With these assumptions, I_{f} automatically carries the physically natural properties that I_{f}(p, p) = 0 and I_{f}(p, q) > 0 for p and q distinct.

A basic question is that of approximation: how closeness of f and g is reflected in closeness of I_{f} and I_{g}. As an illustrative example, the following was considered in [5].

Suppose that there exist distinct real numbers r, R with

(1.1)  0 < r ≤ p_{i}/q_{i} ≤ R < ∞ for all i ∈ {1, ..., n}.

1991 Mathematics Subject Classification. 94A17, 26D15.

Key words and phrases. Csiszár f–divergence, Iyengar inequality, trapezoid inequality, divergence measures, absolute continuity.

We suppose also that f : [r, R] → R is such that f′ is absolutely continuous on [r, R] and f′′ ∈ L_{∞}[r, R], that is,

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

Define g : [r, R] → R by

g(u) := f(1) + (u − 1)f′(1).

Then

|I_{f}(p, q) − I_{g}(p, q)| ≤ \frac{(R − r)^{2}}{8} ∥f′′ ∥_{∞} .

Similarly if f′′ is absolutely continuous on [r, R] and f′′′ ∈ L_{∞}[r, R], and we define g : [r, R] → R by

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

then

|I_{f}(p, q) − I_{g}(p, q)| ≤ \frac{(R − r)^{3}}{48} ∥f′′′ ∥_{∞} .

These examples are prompted naturally by consideration of Taylor series. However, even within the same framework of assumptions on derivatives, substantially stronger results exist. The following were established in [5] with the choice g = f^{∗}, where

f^{∗}(u) := f(1) + (u − 1)f′ (\frac{1 + u}{2}) .

Theorem A. Suppose that (1.1) holds and assume that f : [r, R] → R is such that f′ is absolutely continuous on [r, R] and f′′ ∈ L_{∞}[r, R]. Then

|I_{f}(p, q) − I_{f^{∗}}(p, q)| ≤ \frac{1}{4} ∥f′′ ∥_{∞} D_{χ^{2}}(p, q)

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

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

Theorem B. Suppose that (1.1) holds and assume that f : [r, R] → R is such that f′′ is absolutely continuous on [r, R] and f′′′ ∈ L_{∞}[r, R]. Then

|I_{f} (p, q) − I_{f^{∗}} (p, q)| ≤ \frac{1}{24} ∥f′′′ ∥_{∞} D_{|χ|}^{3}(p, q)

≤ \frac{1}{24} ∥f′′′ ∥_{∞} \frac{(R − 1)(1 − r)}{R − r} [(1 − r)^{2} + (R − 1)^{2}]

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

The constants are best–possible.

In this article, we show that these ideas can be pushed further, again without extending the raft of assumptions. We assume (1.1) throughout without further comment and keep the assumption that r, R are distinct, which is easily seen to entail that r < 1 < R. Suppose f^{†} : [r, R] → R is given by

f^{†}(u) := f(1) + \frac{u − 1}{2}f′(u).

In Section 2 we derive Theorems 1 and 2, which are versions of Theorems A and B with f^{†} in place of f^{∗}. Theorem 1 has a tighter error bound than Theorem A and Theorem B a less tight bound than Theorem B. The first bound in Theorem 1 is quite complicated. In Section 3 we introduce one– and two–point distributions and show how these may be used to clarify the bounds in Theorem 1 and indeed also to produce best–possible functional improvements of the bounds, in terms of r and R only, in both theorems. These take into account the detailed structure of the function f. In Section 4, we codify these ideas into a pair of connected geometric constructions. We conclude in Section 5 by illustrating the ideas involved by reference to some choices of f in common use.

2. Basic theorems

The analogue of Theorem A we are about to derive is based on the Iyengar inequality [7], which states the following.

Theorem C. Suppose g : [a, b] → R is absolutely continuous on [a, b] and g′ : [a, b] → R is essentially bounded, that is, g′ ∈ L_{∞}[a, b]. Then

|∫_{a}^{b} g(t)dt − \frac{1}{2}(b − a)[g(a) + g(b)]|

≤ \frac{1}{4} ∥g′ ∥_{∞} (b − a)^{2} − \frac{1}{4 ∥g′∥_{∞}} [g(b) − g(a)]^{2}.

We shall also make use of Proposition 1 of [5], which provides the following.

Proposition A. Suppose that (1.1) is satisfied with r < R and that m ≥ 1. Then

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

The first inequality is an equality if and only if p, q form a boundary pair with respect to r and R, that is, for each i either p_{i}/q_{i} = r or p_{i}/q_{i} = R. The second inequality is an equality if and only if R + r = 2, that is, r and R are equidistant from unity.

We now proceed to our first basic result. We shall make use of f_{0} : [r, R] → R given by

f_{0}(u) := [f′(u) − f′(1)]^{2} .

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

(2.1) |I_{f}(p, q) − I_{f^{†}}(p, q)| ≤ \frac{1}{4} ∥f′′ ∥_{∞} D_{χ^{2}}(p, q) − \frac{1}{4 ∥f′′∥_{∞}} I_{f_{0}}(p, q)
≤ \frac{1}{4} ∥f′′ ∥_{∞} D_{χ^{2}}(p, q)
≤ \frac{1}{4} ∥f′′ ∥_{∞} (R − 1)(1 − r)
≤ \frac{1}{16} ∥f′′ ∥_{∞} (R − r)^{2}.

Proof. We choose a = 1, b = x and g = f′ in Theorem C to obtain

|∫_{1}^{x} f′(t)dt − \frac{1}{2}(x − 1) [f′(1) + f′(x)]|

≤ \frac{1}{4} ∥f′′ ∥_{∞} (x − 1)^{2} − \frac{1}{4 ∥f′′∥_{∞}} f_{0}(x),

or equivalently

|f(x) − f(1) − \frac{1}{2}f′(1)(x − 1) − \frac{1}{2}f′(x)(x − 1)|

≤ \frac{1}{4} ∥f′′ ∥_{∞} (x − 1)^{2} − \frac{1}{4 ∥f′′∥_{∞}} f_{0}(x)

for all x ∈ [r, R].

If we choose x = p_{i}/q_{i}, multiply by q_{i} and sum over i from 1 to n, we derive the first inequality in (2.1) via the extended triangle inequality. The second inequality is immediate, since f_{0} and so also I_{f_{0}} is nonnegative. The remaining inequalities are given by Proposition A with m = 2. □

Corollary 1. Suppose the assumptions of Theorem 1 hold. If ε > 0 and

0 ≤ R − r ≤ 4 · \sqrt{ε/ ∥f′′∥_{∞}},

then

|I_{f}(p, q) − I_{f^{†}}(p, q)| ≤ ε.

The following corollary emphasizes the approximation aspect of Theorem 1 for distributions p and q which are close.

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

(2.2)  |\frac{p_{i}(η)}{q_{i}(η)} − 1| ≤ η for all i ∈ \{1, ..., n\} ,

then

(2.3)  I_{f} (p(η), q(η)) = I_{f^{†}} (p(η), q(η)) + R_{f}(p, q, η)

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

R_{f}(p, q, η) ≤ \frac{1}{4} ∥f′′ ∥_{∞} η^{2}.

Proof. Choose r = 1 − η, R = 1 + η in Theorem 1. □

Our other basic theorem makes use of the trapezoid inequality

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

from numerical integration, which holds provided g′′ ∈ L_{∞}[a, b].

Theorem 2. If f : [r, R] → R with f′′ absolutely continuous on [r, R] and f′′′ ∈ L_{∞}[r, R], then

(2.5) |I_{f} (p, q) − I_{f^{†}}(p, q)| ≤ \frac{1}{12} ∥f′′′ ∥_{∞} D_{|χ|}^{3}(p, q)

≤ \frac{1}{24} ∥f′′′ ∥_{∞} \frac{(R − 1)(1 − r)}{R − r} [(1 − r)^{2} + (R − 1)^{2}]

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

The constants on the right are best–possible.

Proof. The first inequality is derived from (2.4) along the same lines as the first inequality in Theorem 1. The remaing inequalities follow from Proposition A with m = 3.

For f(u) = |u − 1|^{3} we have I_{f}(p, q) = D_{|χ|^{3}}(p, q). Also f^{†}(u) = (3/2)f(u), so as I is linear in f we have

|I_{f}(p, q) − I_{f^{†}}(p, q)| = \frac{1}{2}D_{|χ|^{3}}(p, q).

Since ∥f′′′ ∥ = 6, the first inequality in (2.5) is thus an equality for this choice of f and the corresponding constant is best–possible. That the following constants are best–possible is inherited from Proposition A. □

Corollary 3. Let f be as in Theorem 2. If ε > 0 and

0 ≤ R − r ≤ 2 · \sqrt[3]{12ε/ ∥f′′′∥_{∞}},

then

|I_{f} (p, q) − I_{f^{†}}(p, q)| ≤ ε.

Also, the following approximation result holds.

Corollary 4. Let f : [0, 2] → R with f′′ absolutely continuous on [0, 2] and f′′′ ∈ L_{∞}[0, 2]. If η ∈ (0, 1) and p(η), q(η) are such that (2.2) holds, then we have the representation (2.3) and the remainder R_{f}(p, q, η) satisfies

|R_{f}(p, q, η)| ≤ \frac{1}{12} ∥f′′′ ∥_{∞} η^{3}.

Remark 1. The last bound in Theorem 2 is tighter than that of Theorem 1 if

\frac{6 ∥f′′ ∥_{∞}}{∥f′′′∥_{∞}} > R − r,

while the reverse is true if

\frac{6 ∥f′′ ∥_{∞}}{∥f′′′∥_{∞}} < R − r.

As we shall see in Section 5, both possibilities can arise in practice. In the examples we consider, Theorem 2 gives the better bound when r/R is large and Theorem 1 when it is small.

3. One– and two–point distributions

Suppose we wish to obtain the error bound involved in estimating I_{f}(p, q) by I_{g}(p, q) for some function g. Since

I_{f}(p, q) − I_{g}(p, q) = I_{f−g}(p, q),

we wish to find sup |I_{h}(p, q)|, where h = f − g and the supremum is taken over all n–point probability distribution pairs (p, q) satisfying (1.1). In this section we approach this question directly and establish some basic results. We shall find it convenient for clarity and succinctness to adopt the notation I_{h,n}(p, q) and to write u_{i} := p_{i}/q_{i} for i ∈ {1, 2, …, n} in this and the following section. Proposition 1. Let n ≥ 1 and assume p, q are n–point distributions all of whose components are nonzero.

(a) There exist k–point distributions p^{U}, q^{U}, where k takes one of the values 1 or 2 and p^{U}, q^{U} depend on p and q, such that

p_{i}^{U}/q_{i}^{U} ∈ {u_{1}, …, u_{n}} for i = 1, …, k

and

I_{h,k}(p^{U}, q^{U}) ≥ I_{h,n}(p, q).

(b) There exist k–point distributions p^{L}, q^{L}, where k takes one of the values 1 or 2 and p^{L}, q^{L} depend on p and q, such that

p_{i}^{L}/q_{i}^{L} ∈ {u_{1}, …, u_{n}} for i = 1, …, k

and

I_{h,k}(p^{L}, q^{L}) ≤ I_{h,n}(p, q).

Proof. Consider the first half of the enunciation. If there are j distinct values u_{(1)}, u_{(2)}, …, u_{(j)} (1 ≤ j ≤ n), then for each such we may sum the associated values q_{i} to obtain q_{1}^{(j)}, q_{2}^{(j)}, …, q_{j}^{(j)}. Likewise we derive p_{ℓ}^{(j)} associated with u_{(ℓ)} (1 ≤ ℓ ≤ j). We have at once that p_{ℓ}^{(j)}/q_{ℓ}^{(j)} = u_{(ℓ)}, and that p^{(j)} = (p_{1}^{(j)}, …, p_{j}^{(j)}) and q^{(j)} = (q_{1}^{(j)}, …, q_{j}^{(j)}) are j–point probability distributions for which I_{h,j}(p^{(j)}, q^{(j)}) has the same value as I_{h,n}(p, q).

To derive the desired result (a) by mathematical induction, we need to show that if m is such that 3 ≤ m ≤ j then there exist (m − t)–point probability distributions p^{(m−t)}, q^{(m−t)} (with t equal to 1 or 2) depending on p^{(m)} and q^{(m)} with

p_{ℓ}^{(m−t)}/q_{ℓ}^{(m−t)} = u_{(ℓ)} (1 ≤ ℓ ≤ m − t)

and

I_{h,m−t}(p^{(m−t)}, q^{(m−t)}) ≥ I_{h,j}(p^{(m)}, q^{(m)}).

We may without loss of generality assume that there are at least three distinct values u_{i}, for otherwise there is nothing to prove.

To achieve the induction, we shall show that such a reduction from m–point support to (m − t)–point support can be brought about by replacing the last three components of p^{(m)} by two suitably chosen components and a zero or one suitably chosen component and two zeros, with a corresponding replacement in q^{(m)}, the zeros being in the same position or positions.

For notational convenience, put v_{1} := u_{(m−2)}, v_{2} := u_{(m−1)}, v_{3} := u_{(m)}. With relabelling if necessary, we may assume v_{1} < v_{2} < v_{3}. Likewise we put p_{m−2}^{(m)} = ρ_{1}, p_{m−1}^{(m)} = ρ_{2}, p_{m}^{(m)} = ρ_{3} and q_{m−2}^{(m)} = σ_{1}, q_{m−1}^{(m)} = σ_{2}, q_{m}^{(m)} = σ_{3}, so that ρ_{i}/σ_{i} = v_{i} for i = 1, 2, 3. Define

λ := \frac{v_{3} − v_{2}}{v_{3} − v_{1}} ,

so that 0 < λ, 1−λ < 1 and v_{2} = λv_{1} +(1−λ)v_{3}. We address in turn three possible cases.

(i) If h(v_{2}) ≤ λh(v_{1}) + (1 − λ)h(v_{3}), then

∑_{i=1}^{3} σ_{i}h(v_{i}) ≤ ∑_{i=1,3} σ′_{i}h(v_{i}),

where σ′_{1} = σ_{1} + λσ_{2} and σ′_{3} = σ_{3} + (1 − λ)σ_{2}. Note that ∑_{i=1}^{3} σ_{i} = ∑_{i=1,3} σ′_{i}. If we define ρ′_{i} = σ′_{i}v_{i} for i = 1, 3, then ρ′_{i}/σ′_{i} = v_{i} (i = 1, 3) and

∑_{i=1,3} ρ′_{i} = ∑_{i=1,3} σ_{i}v_{i} + σ_{2}[λ_{1}v_{1} + (1 − λ)v_{3}] = ∑_{i=1}^{3} σ_{i}v_{i} = ∑_{i=1}^{3} ρ_{i}.

This shows that the reduction can be effected in this case with t = 1.

(ii) Next we suppose

(3.1)  h(v_{2}) > λh(v_{1}) + (1 − λ)h(v_{3})

with

(3.2)  σ_{1}/λ ≤ σ_{3}/(1 − λ).

Put

σ′_{2} := σ_{2} + σ_{1}/λ, σ′_{3} := σ_{3} − \frac{1 − λ}{λ}σ_{1}.

Then σ′_{2} > 0 and by (3.2) σ′_{3} ≥ 0. Further ∑_{i=2,3} σ′_{i} = ∑_{i=1}^{3} σ_{i}. Also by (3.1),

∑_{i=2,3} σ′_{i}h(v_{i}) > \frac{σ_{1}}{λ} [λh(v_{1}) + (1 − λ)h(v_{3})] + σ_{2}h(v_{2}) + [σ_{3} − \frac{1 − λ}{λ}σ_{1}] h(v_{3})

= ∑_{i=1}^{3} σ_{i}h(v_{i}).

If we define ρ′_{i} = σ′_{i}v_{i} for i = 2, 3, then ρ′_{i}/σ′_{i} = v_{i} (i = 2, 3) and much as above

∑_{i=2,3} ρ′_{i} = ∑_{i=1}^{3} ρ_{i}.

If (3.2) holds with equality, then σ′_{3} = 0 and the reduction holds with t = 2. Otherwise it holds with t = 1.

(iii) Finally we have the possibility that (3.1) holds with

(3.3)  σ_{1}/λ > σ_{3}/(1 − λ).

We may argue as in (ii), this time starting with

σ′_{1} := σ_{1} − \frac{λ}{1 − λ}σ_{3}, σ′_{2} := σ_{2} + \frac{1}{1 − λ}σ_{3}.

Then σ′_{1}, σ′_{2} are positive and

∑_{i=1,2} σ′_{i} = ∑_{i=1^{3}} σ_{i}.

By (3.1),

∑_{i=1,2} σ′_{i}h(v_{i}) = ∑_{i=1,2} σ_{i}h(v_{i}) + \frac{σ_{3}}{1 − λ} [h(v_{2}) − λh(v_{1})]

> ∑_{i=1}^{3} σ_{i}h)v_{i}).

If ρ′_{i} = σ′_{i}v_{i} for i = 1, 2, then ρ′_{i}/σ′_{i} = v_{i} (i = 1, 2) and

∑_{i=1,2} ρ′_{i} = ∑_{i=1,2} σ′_{i}v_{i} = ∑_{i=1,2} σ_{i}v_{i} + \frac{σ_{3}}{1 − λ} [v_{2} − λv_{1}] = ∑_{i=1}^{3} σ_{i}v_{i} = ∑_{i=1}^{3} ρ_{i}.

Thus we have a reduction with t = 1.

This completes the proof of part (a). Part (b) follows by applying part (a) to the function −h. □

Suppose h is bounded on [r, R]. By letting p_{i}, q_{i} tend to zero for different choices of i successively while keeping p_{ℓ}/q_{ℓ} ∈ [r, R] for all ℓ ∈ {1, 2, …, n}, we can obtain one– and two–point distributions satisfying (1.1) as limiting cases of n–point distributions. With this convention, the following result is natural. Proposition 2. Suppose h is continuous and bounded on [r, R]. Then I_{h,n} achieves its supremum and infimum over n–point distributions p, q satisfying (1.1). These are realised by one– or two–point distributions.

Proof. The first part is immediate. The second follows via Proposition 1, by relating extremum–achieving distributions to I_{h} evaluated at one– or two–point distributions at which I_{h} is dominating (in the supremum case) or dominated (in the infimum case). □

Corollary 5. The supremum and infimum of I_{h} subject to (1.1) take one of the forms

(3.4)  qh(u) + (1 − q)h (\frac{1 − qu}{1 − q}) , h(1),

where u ∈ [r, R].

Proof. The first form in (3.4) is immediate, since if p/q = u, then

\frac{1 − p}{1 − q} = \frac{1 − qu}{1 − q}.

The second is trivial, since p/q = 1 when p and q are one–point distributions. □

The ideas of this section provide the means for obtaining tight bounds on |I_{h}| in terms of r, R. This we pursue in the following section. In practice the calculations can be quite intricate even when h has a relatively simple functional form, although they are suited to efficient numerical implementation, such as by bifurcation search. For this reason, it is very convenient to have even the largest and second largest bounds on the right–hand sides of (2.1) and (2.5).

Finite–point distributions have a special role in extremal theory. For a general discussion, the reader is referred to [6].

4. Evaluating extrema

We now draw together the ideas of the preceding section to codify the treatment of some broad classes of function h. For notational convenience we introduce

F (x, y) := \frac{y − 1}{y − x}h(x) + \frac{1 − x}{y − x}h(y),

which gives the value of I_{h} for two–point distributions p, q with support at u = x, y. We assume throughout that (1.1) applies and that x, y ∈ [r, R]. Theorem 3. Suppose r_{T}, R_{T} satisfy r ≤ r_{T} < 1 < R_{T} ≤ R and the line joining (r_{T} , h(r_{T})) to (R_{T} , h(R_{T})) lies strictly above the graph of h(u) for u ∈ [r, R] \ {r_{T} , R_{T} }. Then

sup I_{h}(p, q) = F (r_{T} , R_{T}).

Proof. Put v_{1} = r_{T}, v_{3} = R_{T} and suppose if possible u = v_{2} ∈ (r_{T} , R_{T}) is in the support of one– or two–point distributions p_{0}, q_{0} for which I_{f} realises its supremum. By assumption

h(v_{2}) < λh(v_{1}) + (1 − λ)h(v_{3})

in the notation of Proposition 1(a) case (i). The argument of case (i) shows that I_{f}(p_{0}, q_{0}) experiences a strict increase if p_{0}, q_{0} are modified by a suitable redistribution of probability mass from v_{2} to v_{1} and v_{3}, a contradiction to the extremality of I_{f}(p_{0}, q_{0}). Thus the support of p_{0} and q_{0} must have empty intersection with (r_{T} , R_{T}). There is nothing more to prove if r_{T} = r and R_{T} = R. In any case, we see that since 1 ∈ (r_{T} , R_{T}), p_{0} and q_{0} must have two–point support.

If R_{T} < R, suppose if possible p_{0} and q_{0} have a point of support r_{0} ∈ (R_{T} , R]. Then (R_{T} , h(R_{T})) lies above the chord joining (r_{T} , h(r_{T})) to (r_{0}, h(r_{0})), so we may derive a contradiction by the construction of case (ii) or case (iii) of Proposition 1 (a). Since p_{0} and q_{0} must have a point of support greater than unity, that point must therefore be u = R_{T}. A similar argument show that the support point less than unity must be at u = r_{T}. □

By taking −h in place of h in the preceding theorem, we derive the following corresponding theorem for infima.

Theorem 4. Suppose r_{S}, R_{S} satisfy r ≤ r_{S} < 1 < R_{S} ≤ R and the line joining (r_{S}, h(r_{S})) to (R_{S}, h(R_{S})) lies strictly below the graph of h(u) for u ∈ [r, R] \ {r_{S}, R_{S}}. Then

inf I_{h}(p, q) = F (r_{S}, R_{S}).

Whenever the above theorems are applicable, we may derive sup |I_{f}(p, q)| from

sup |I_{f}(p, q)| = max [sup I_{f}(p, q), − inf I_{f}(p, q)] .

Some modification to Theorem 3 is necessary if r_{T} < 1 < R_{T} is violated. This has not been found to occur in the examples we have looked at but could be dealt with on an ad hoc basis. For this reason we have not seen fit to strive for further generality in Theorem 3 at the cost of complicating it. The same comment applies to Theorem 4.

5. Examples

For the mapping f : (0, ∞) → R given by f(u) = u ln u, I_{f}(p, q) becomes the Kulback–Leibler distance

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

We have

I_{f}(p, q) = \frac{1}{2} ∑_{i=1}^{n} [ln (\frac{p_{i}}{q_{i}} ) + 1] (p_{i} − q_{i})

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

= \frac{1}{2}[D(p, q) + D(q, p)],

∑_{i=1}^{n} q_{i}f_{0}(u_{i}) = ∑_{i=1}^{n} q_{i} [ln (u_{i})]^{2}

and

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

Consequently Theorem 1 provides

(5.1)  0 ≤ |D(p, q) − D(q, p)|

≤ \frac{1}{2r} D_{χ^{2}}(p, q) − \frac{r}{2} ∑_{i=1}^{n} q_{i} [ln (\frac{p_{i}}{q_{i}} )]^{2}

≤ \frac{1}{2r} D_{χ^{2}}(p, q)

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

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

which measures the asymmetry of the Kullback–Leibler distance.

A simple calculation gives

∥f′′′ ∥_{∞} = 1/r^{2},

so that Theorem 2 gives the bounds

0 ≤ |D(p, q) − D(q, p)| ≤ \frac{1}{6r^{2}} D_{|χ|}^{3}(p, q) ≤ \frac{1}{48r^{2}} (R − r)^{3}.

The last bound here can be seen to be strictly better than that in (5.1) if r > R/7.

Tight bounds for \frac{1}{2}|D(p, q) − D(q, p)| involving only r, R can be derived using the ideas of the previous section. We have

h(u) = \frac{u + 1}{2} [ln u − (u − 1)] ,

so that

h′(u) = \frac{1}{2} [ln u + \frac{1}{u}] and h′′(u) = \frac{u − 1}{2u^{2}}.

Thus h′(u) > 0 for u ≥ 1. By the elementary inequality

\frac{1}{u} + ln u > 1 for 0 < u < 1,

we have that h′(u) > 0 holds for 0 < u < 1 as well and so h is strictly increasing for all u < 0. Also h is strictly concave for 0 < u < 1 and strictly convex for u > 1.

This falls within the scope of Theorems 3 and 4. If r_{1} is the demonstrably unique value of u less than unity at which the tangent to the graph of h passes through (R, h(R)), then we may choose r_{T} = max(r, r_{1}). If R_{1} is the demonstrably unique value of u greater than unity at which the tangent to the graph of h passes through (r, h(r)), then we may choose R_{T} = min(R, R_{1}).

Now consider the mapping f : (0, ∞) → R given by f(u) = ln u. We have

I_{f}(p, q) = ∑_{i=1}^{n} q_{i} ln (u_{i}) = −D(q, p),

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

∑_{i=1}^{n} q_{i}f_{0}(u_{i}) = ∑_{i=1}^{n} q_{i} (\frac{q_{i}}{p_{i}} − 1)^{2} = ∑_{i=1}^{n} \frac{q_{i}(q_{i} − p_{i})}{p_{i}^{2}}^{2}

and ∥f′′ ∥_{∞} = 1/r^{2}.

Consequently, by (2.1), we have

(5.2)  0 ≤ |D(q, p) + \frac{1}{2}D_{χ^{2}}(q, p)|

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

≤ \frac{1}{4r^{2}} D_{χ^{2}}(p, q)

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

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

A simple calculation shows that ∥f′′′ ∥_{∞} = 2/r^{3}, so that by Theorem 2

0 ≤ [D(q, p) + \frac{1}{2}D_{χ^{2}}(q, p)] ≤ \frac{1}{6r^{3}} D_{|χ|}^{3}(p, q) ≤ \frac{1}{48} (\frac{R}{r} − 1)^{3} .

The last bound here can be seen to be better than that in (5.2) if r > R/4.

Again we may obtain a tight bound for |D(q, p) − \frac{1}{2}D_{χ^{2}}(q, p)| in terms of r, R alone by use of Theorems 3 and 4. We have

h(u) = ln u − \frac{u − 1}{2u},

so that

h′(u) = \frac{2u − 1}{2u^{2}} and h′′(u) = \frac{1 − u}{u^{3}}.

Thus h is decreasing for 0 < u < 1/2 and increasing for u > 1/2. Further it is strictly convex for 0 < u < 1 and strictly concave for u > 1, and so is quasiconvex. We may define r_{T} and R_{T} exactly as in the previous example.

Finally suppose f : (0, ∞) → R is given by f(u) = \frac{1}{2} (\sqrt{u} − 1)^{2} . Then I_{f}(p, q) becomes the Hellinger discrimination

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

We have

∑_{i=1}^{n} f′ (\frac{p_{i}}{q_{i}} ) (p_{i} − q_{i}) = \frac{1}{2} ∑_{i=1}^{n} (q_{i} − p_{i}) \begin{matrix}√ & \overline{q_{i}} \\ √ & \overline{p_{i}} \end{matrix} ,

∑_{i=1}^{n} q_{i}f_{0}(u_{i}) = ∑_{i=1}^{n} \frac{q_{i}}{p_{i}} (\sqrt{p_{i}} − \sqrt{q_{i}})^{2}

and

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

Consequently Theorem 1 provides

|h^{2}(p, q) − \frac{1}{4} ∑_{i=1}^{n} (q_{i} − p_{i}) \sqrt{\frac{q_{i}}{p_{i}}} | ≤ \frac{1}{16r^{3/2}} D_{χ^{2}}(p, q) − r^{3/2} ∑_{i=1}^{n} \frac{q_{i}}{p_{i}} (\sqrt{p_{i}} − \sqrt{q_{i}})^{2}

≤ \frac{1}{16r^{3/2}} D_{χ^{2}}(p, q)

≤ \frac{1}{16r^{3/2}} (R − 1)(1 − r)

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

Also, as f′′′(u) = −\frac{3}{8}u^{−5/2}, we have ∥f′′′ ∥_{∞} = sup_{u∈[r,R]} |f′′′(u)| = \frac{3}{8}r^{−5/2}, and

Theorem 2 gives

(5.3) |h^{2}(p, q) − \frac{1}{4} ∑_{i=1}^{n} (q_{i} − p_{i}) \sqrt{\frac{q_{i}}{p_{i}}} | ≤ \frac{1}{32r^{5/2}} D_{|χ|3}(p, q) ≤ \frac{1}{256r^{5/2}} (R − r)^{3}.

The largest bound here is better than the largest provided by Theorem 1 provided r > R/5.

The use of Theorems 3 and 4 to obtain an absolute upper bound for the left– hand side of the first inequality in (5.3) is more complicated than in the previous examples. We have

h(u) = \frac{(\sqrt{u} − 1)^{3}}{4\sqrt{u}} .

Hence

h′(u) = \frac{(\sqrt{u} − 1)^{2}}{8u^{3/2}} [2\sqrt{u} + 1] and h′′(u) = \frac{\sqrt{u} − 1}{16u^{3}} [2 + 3u^{1/2} + 3u − 6u^{3/2}] .

Thus h is strictly increasing for u > 0. It is strictly concave for 0 < u < 1, strictly convex for 1 < u < u_{0} and strictly concave for u > u_{0}, where u_{0} is the unique zero exceeding unity of the cubic polynomial 2 + 3x + 3x^{2} − 6x^{3}.

There exist a unique pair of points (r_{1}, h(r_{1})), (R_{1}, h(R_{1})) with r_{1} < 1 < R_{1} at which the graph of h has a common tangent which lies above the graph for all u > 0 except at the two osculating points. If r ≤ r_{1} < R_{1} ≤ R, we may take r_{T} = r_{1} and R_{T} = R_{1}. Suppose r_{1} < r. Then there exists a unique u = R_{2} > 1 such that the tangent to the graph at (R_{2}, h(R_{2})) passes through (r, h(r)) and lies above the graph for r < u < R_{2}. We may choose r_{T} = r, R_{T} = min(R_{2}, R).

If the join of (r, h(r)) to (R, h(R)) lies below the graph for r < u < R, or is tangential to the graph at an intermediate point, we may take r_{S} = r, R_{S} = R. Otherwise, (r, h(r)) lies on the tangent to the graph at a unique point (r_{2}, h(r_{2})) with 1 < r_{2} < u_{0} and this tangent meets the graph again at (r_{3}, h(r_{3})) with r_{3} > R. Similarly (R, h(R)) lies on the tangent to the graph at a unique point (R_{2}, h(R_{2})) with 1 < R_{2} < u_{0} and this tangent meets the graph again at (R_{3}, h(R_{3})) with R_{3} < r. At least one of r_{2}, R_{2} is not unity. If r_{2} ≠ 1, we may take r_{S} = r, R_{T} = r_{2}. If R_{2} ≠ 1, we may take r_{S} = R_{2}, R_{S} = R.

References

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

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

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

[4] S. S. Dragomir, V. Gluščević and C. E. M. Pearce, Csiszár f–divergence, Ostrowski’s inequality and mutual information, to appear in J. Nonlin. Anal. Ser. A.

[5] S. S. Dragomir, V. Gluščević and C. E. M. Pearce, Approximations for Csiszár f–divergence via midpoint inequalities, submitted.

[6] M. G. Kreǐn and A. A. Nudel’man, The Markov moment problem and extremal problems, Transl. Math. Monographs 50, Amer. Math. Soc., 1977.

[7] D. S. Mitrinović, J. E. Pečarić and A. M. Fink, Inequalities for functions and their integrals and derivatives, Kluwer Academic, Dordrecht, 1994.

School of Communications and Informatics, Victoria University, PO Box 14428, MCMC, Melbourne, Victoria 8001, Australia

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

Royal Australian Air Force, ARDU, PO Box 1500, Salisbury SA 5108, Australia

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

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

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