THE APPROXIMATION OF CSISZÁR f–DIVERGENCE FOR MAPPINGS OF BOUNDED VARIATION

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

Abstract. We consider the approximation of the Csiszár f–divergence when f or its first derivative is a function of bounded variation. The approximants are suggested by numerical integration theory.

1. Introduction

In this article we complete a chain of ideas developed in three companion papers [5]–[7] concerning measures of the divergence between two probability measures p = (p_{1}, …, p_{n}), q = (q_{1}, …, q_{n}) defined over a common set of events. Different applications have provoked different measures. A wide spectrum of measures in use has been subsumed by Csiszár [1]–[3]: the Csiszár f–divergence between p and q is defined by the functional

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

Two important instances, which we shall invoke shortly, are the variational distance V (p, q) and the chi–squared divergence D_{χ^{2}}(p, q), for which

f(u) = |u − 1|^{m}

with m = 1, 2 respectively. We address the situation in which there exist constants r, R with

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

Our initial work [5] assumed the individual values p_{i}, q_{i} are not known. The following result was derived.

Theorem A. Suppose f : [r, R] → R is absolutely continuous and that the derivative f′ : [r, R] → R is essentially bounded, that is, f′ ∈ L_{∞}[r, R]. Then under the condition (1.1) we have

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

≤ [\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′ ∥_{∞} .

1991 Mathematics Subject Classification. 94A17, 26D15.

Key words and phrases. Csiszár f–divergence, Ostrowski’s inequality, bounded variation.

The two companion papers in this volume consider the approximation question: how closeness of f and g is reflected in closeness of I_{f} and I_{g}. Suppose

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

The following was derived in [6].

Theorem B. Suppose f : [r, R] → R with f′ absolutely continuous on [r, R] and f′′ ∈ L_{∞}[r, R]. If (1.1) holds, 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}.

Similarly define

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

The following was shown in [7].

Theorem C. Suppose f : [r, R] → R with f′ absolutely continuous on [r, R] and f′′ ∈ L_{∞}[r, R]. If (1.1) applies, then

|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},

where

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

These and further results in [6] and [7] assume the absolute continuity of f′ (or higher derivative) and essential boundedness of f′′ (or higher derivative). In this concluding contribution we weaken these assumptions to the bounded variation of f or f′ and derive analogues of Theorems A, B, C. We shall employ inter alia the following useful lemma, which is a special case of Proposition 1 of [6].

Lemma A. If (1.1) is satisfied, then

V (p, q) ≤ \frac{2(R − 1)(1 − r)}{R − r} ≤ \frac{R − r}{2} .

The first inequality is an equality if and only if 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.

In Section 2 we give a basic Ostrowski–type inequality for functions of bounded variation and use this to obtain a trapezoidal inequality for functions of bounded variation. In Section 3 we deduce analogues of Theorems A–C and in Section 4 we give two illustrative examples.

2. Preliminaries

We start with the following proposition which provides an Ostrowski–type inequality for mappings of bounded variation. This has been established by one of the present authors in the preprint [4]. We give a simple proof.

Proposition 1. Suppose g : [a, b] → R is of bounded variation on [r, R]. Then for all x ∈ [a, b],

(2.1) |∫_{a}^{b} g(t)dt − g(x)(b − a)| ≤ [\frac{b − a}{2} + |x − \frac{a + b}{2}|] ⋁_{a}^{b}(g) ≤ (b − a) ⋁_{a}^{b}(g),

where ⋁_{a}^{b}(g) denotes the total variation of g on [a, b]. The constant 1/2 is best–

possible.

Proof. Using the integration by parts formula for a Riemann–Stieltjes integral, we

have that ∫_{a}^{x}(t − a)dg(t) and ∫_{x}^{b}(t − b)dg(t) exist and that

∫_{a}^{x}(t − a)dg(t) = g(x)(x − a) − ∫_{a}^{x} g(t)dt

and

∫_{x}^{b}(t − b)dg(t) = g(x)(b − x) − ∫_{x}^{b} g(t)dt

for all x ∈ [a, b]. Addition provides

g(x)(b − a) − ∫_{a}^{b} g(t)dt = ∫_{a}^{x}(t − a)dg(t) + ∫_{x}^{b}(t − b)dg(t)

for all x ∈ [a, b].

Now if p, g : [a, b] → R with p continuous and g of bounded variation, then ∫_{a}^{b} p(t)dg(t) exists and

|∫_{a}^{b} p(t)dg(t)| = sup_{t∈[a,b]} |p(t)| ⋁_{a}^{b}(g).

Hence

|g(x)(b − a) − ∫_{a}^{b} g(t)dt| = |∫_{a}^{x}(t − a)dg(t) + ∫_{x}^{b}(t − b)dg(t)|

≤ |∫_{a}^{x}(t − a)dg(t)| + |∫_{x}^{b}(t − b)dg(t)|

≤ sup_{t∈[a,x]} |t − a| ⋁_{a}^{x}(g) + sup_{t∈[x,b]} |t − b| ⋁_{x}^{b}(g)

= (x − a) ⋁_{a}^{x}(g) + (b − x) ⋁_{x}^{b}(g)

≤ max{x − a, b − x} [⋁_{a}^{x}(g) + ⋁_{x}^{b}(g)]

= [\frac{b − a}{2} + |x − \frac{a + b}{2}|] ⋁_{a}^{b}(g),

and the first inequality in (2.1) is proved. The second follows, since |x − (a + b)/2| ≤ (b − a)/2.

Suppose that (2.1) holds with a constant c > 0, that is,

(2.2)  |∫_{a}^{b} g(t)dt − g(x)(b − a)| ≤ [c(b − a) + |x − \frac{a + b}{2}|] ⋁_{a}^{b}(g)

for all x ∈ [a, b], and define g_{1} : [a, b] → R by

g_{1}(x) = \{ \begin{matrix}1 & if x = (a + b)/2 \\ 0 & otherwise. \end{matrix}

Then g_{1} is of bounded variation on [a, b] and

⋁_{a}^{b}(g_{1}) = 2, ∫_{a}^{b} g_{1}(t)dt = 0.

Put g = g_{1} and x = (a + b)/2 in (2.2). Then we get 1 ≤ 2c, which shows that c = 1/2 is best–possible. □

Proposition 2. If g : [a, b] → R is of bounded variation, then for all x_{1}, x_{2} ∈ [a, b],

(2.3)  |∫_{a}^{b} g(t)dt − \frac{b − a}{2} ∑_{i=1}^{2} g(x_{i})| ≤ [\frac{b − a}{2} + \frac{1}{2} ∑_{i=1}^{2} |x_{i} − \frac{a + b}{2}|] ⋁_{a}^{b}(g).

Proof. This follows by putting x = x_{i} in Proposition 1, summing over i and then using the triangle inequality. □

Lemma 1. Suppose f : [r, R] → R is differentiable, so that f′ is of bounded variation on [r, R]. If r < 1 < R and x ∈ [r, R], then

(2.4)  |f(x) − f(1) − \frac{x − 1}{2} [f′(1) + f′(x)]| ≤ |x − 1| ⋁_{r}^{R}(f′).

Proof. For x ≥ 1, we set g = f′, x_{1} = a = 1 and x_{2} = b = x in (2.3) to derive

|f(x) − f(1) − \frac{x − 1}{2} [f′(1) + f′(x)]| ≤ (x − 1) ⋁_{1}^{x}(f′) ≤ (x − 1) ⋁_{r}^{R}(f′).

Similarly if x < 1, we set g = f′, x_{1} = a = x and x_{2} = b = 1 in (2.3) to derive

|f(1) − f(x) − \frac{1 − x}{2} [f′(1) + f′(x)]| ≤ (1 − x) ⋁_{x}^{1}(f′) ≤ (1 − x) ⋁_{r}^{R}(f′).

The desired result follows in both cases. □

3. Main results

Theorem 1. If f : [r, R] → R is of bounded variation and (1.1) applies, then

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

≤ [\frac{1}{2} + \frac{1}{R − r} ∑_{k=1}^{n} |p_{i} − \frac{r + R}{2} · q_{i}|] ⋁_{r}^{R}(f)

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

≤ [1 + \frac{1}{R − r} · V (p, q)] ⋁_{r}^{R}(f)

≤ \frac{3}{2} ⋁_{r}^{R}(f).

Proof. The choices g = f, x = p_{i}/q_{i} (i = 1, ..., n), a = r, b = R in (2.1) give

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

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

If we multiply by q_{i} and sum over i, we obtain via the generalized triangle inequality that

|I_{f}(p, q) − \frac{1}{R − r} ∫_{r}^{R} f(t)dt| ≤ [\frac{1}{2} + \frac{1}{R − r} ∑_{i=1}^{n} q_{i} |\frac{p_{i}}{q_{i}} − \frac{r + R}{2}|] ⋁_{r}^{R}(f),

whence we have the first inequality in (3.1).

The second follows from

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

= V (p, q) + |\frac{r + R}{2} − 1|

and the third from

|\frac{r + R}{2} − 1| ≤ \frac{R − r}{2} .

The final inequality follows by Lemma A. □

The following corollary emphasizes better the approximation aspect of the theorem. Corollary 1. Let f : [0, 2] → R be a mapping of bounded variation. If η ∈ (0, 1) and p(η) and q(η) are probability distributions satisfying

|\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 reminder term R_{f} satisfies

|R_{f}(p, q, η)| ≤ \frac{1}{2} [1 + \frac{1}{η} V (p(η), q(η))] ⋁_{1−η}^{1+η}(f).

We note that the best inequality we can get from (2.1) is

(3.2)  |∫_{a}^{b} g(t)dt − g (\frac{a + b}{2}) (b − a)| ≤ \frac{b − a}{2} ⋁_{a}^{b}(g),

which arises for x = (a + b)/2.

We now turn to a comparison theorem which encapsulates bounded–variation analogues of Theorems B and C.

Theorem 2. Suppose f : [r, R] → R is differentiable and so f′ is of bounded variation. If (1.1) applies, then

(3.3)  |I_{f}(p, q) − I_{f^{∗}}(p, q)| ≤ \frac{1}{2}V (p, q) ⋁_{r}^{R}(f′) ≤ \frac{R − 1}{4} ⋁_{r}^{R}(f′),

(3.4)  |I_{f}(p, q) − I_{f^{†}}(p, q)| ≤ V (p, q) ⋁_{r}^{R}(f′) ≤ \frac{R − 1}{2} ⋁_{r}^{R}(f′).

Proof. Taking (3.2) with g = f′, a = 1, and b = x ∈ [r, R] gives

|f (x) − f^{∗}(x)| ≤ \frac{|x − 1|}{2} ⋁_{1}^{x}(f′) ≤ \frac{|x − 1|}{2} ⋁_{r}^{R}(f′)

for all x ∈ [r, R]. The first inequality in (3.3) follows by putting x = p_{i}/q_{i}, multiplying by q_{i}, summing over i = 1, …, n and using the generalized triangle inequality. The second inequality is given by Lemma A.

The proof of (3.4) follows similarly from (2.4). □

Both parts may be viewed in terms of approximation. Thus for (3.3) we have the following.

Corollary 2. Suppose f : [0, 2] → R has its first derivative of bounded variation. If η ∈ (0, 1) and p(η), q(η) are probability distributions satisfying,

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

then

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

and the reminder R_{f} is such that

|R_{f}(p, q, η)| ≤ \frac{1}{2}V (p(η), q(η)) ⋁_{1−η}^{1+η}(f′) ≤ \frac{η}{2} ⋁_{1−η}^{1+η}(f′).

4. Examples

Suppose (1.1) holds and f : [r, R] → R is given by f(u) = u ln u, so that I_{f}(p, q) is the Kullback–Leibler distance

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

We have

∫_{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 [I (R^{2}, r^{2})] ,

where I(a, b) is the identric mean of two positive numbers a, b and is given by

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

Also

⋁_{r}^{R}(f) = ∫_{a}^{b} |f′(t)| dt = ∫_{a}^{b} |ln(et)| dt =: λ(r, R).

If 0 < r ≤ 1/e, then

λ(r, R) = ∫_{r}^{1/e}[− ln(et)] dt + ∫_{1/e}^{R} ln(et)dt

= −\frac{1}{e} ∫_{r}^{1/e}ln(et)d(et) + \frac{1}{e} ∫_{1/e}^{R} ln(et)d(et).

Since

∫_{α}^{β} ln x dx = ln I(α, β) for α, β > 0,

we have

λ(r, R) = −\frac{1}{e} ln [I (r, e^{−1})] + \frac{1}{e} ln [I(e^{−1}, R)] = ln [\frac{I(e^{−1}, R)}{I(r, e^{−1})}]^{1/e} .

If on the other hand 1/e < r < 1, then

λ(r, R) = ∫_{r}^{R} ln(et)dt = \frac{1}{e} ln I(r, R) = ln [I(r, R)]^{1/e}.

Thus (3.1) gives

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

≤ [\frac{1}{2} + \frac{1}{R − r} ∑_{i=1}^{n} |p_{i} − \frac{r + R}{2} · q_{i}|] λ(r, R)

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

≤ [1 + \frac{1}{R − r} V (p, q)] λ(r, R)

≤ \frac{3}{2}λ(r, R).

Also

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

and

⋁_{r}^{R}(f′) = ∫_{r}^{R} |f′′(t)| dt = ∫_{r}^{R} \frac{dt}{t} = ln (\frac{R}{r}) .

Hence by (3.3) we have

|D(p, q) − ∑_{i=1}^{n}(p_{i} − q_{i}) ln (\frac{p_{i} + q_{i}}{2q_{i}} )| ≤ \frac{1}{2}V (p, q) ln (\frac{R}{r})

≤ \frac{R − r}{4} (ln R − ln r)

= \frac{(R − r)^{2}}{4L(r, R)} ,

where L(a, b) is the logarithmic mean which for positive arguments a, b is given by

L(a, b) := \{ \begin{matrix}a & if b = a \\ \frac{b−a}{ln b−ln a} & otherwise. \end{matrix}

Therefore we have the inequality

|D(p, q) − ∑_{i=1}^{n}(p_{i} − q_{i}) ln (\frac{p_{i} + q_{i}}{2q_{i}} )| ≤ \frac{1}{4} · \frac{R − r}{L(r, R)}V (p, q) ≤ \frac{(R − r)^{2}}{4L(r, R)} .

Finally suppose f : [r, R] → R is given by f(u) = |u − 1|, so I_{f}(p, q) becomes the variational distance

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

We have

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

= \frac{1}{R − r} [∫_{r}^{1}(1 − u)du + \frac{1}{R − r} ∫_{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}]

and

⋁_{r}^{R}(f) = ⋁_{r}^{1}(f) + ⋁_{1}^{R}(f) = 1 − r + R − 1 = R − r.

By (3.1) we have

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

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

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

≤ [1 + \frac{1}{R − r} V (p, q)] (R − r)

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

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, On the Ostrowski’s integral inequality for mappings of bounded variation and applications, RGMIA Res. Rep. Coll. 2 (1999) No. 1, 73–80.

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

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

[7] S. S. Dragomir, V. Gluščević & C. E. M. Pearce, The approximations for Csiszár f–divergence for absolutely continuous mappings, submitted.

[8] S. S. Dragomir & 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.

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

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

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