The Refinement Integral

by

Isidore Fleischer

C.R.M., Université de Montréal, C.P.6128 Succ. Centre-Ville, Montréal, P.Q. H3C 3J7, Canada

Abstract

The refinement integral already surfaces in implicit form in Darboux’s reformulation of the Riemann(-Stieltjes) integral, although the recognition that the upper and lower integrals are refinement depends on the subsequent convergence theory of E.H. Moore, who also observed that the Lebesgue integral could be construed as refinement. For a sub- (or super-) additive integrand, the refinement integral exists as the sup (or inf) over the approximating sums; it can sometimes be evaluated as a standard integral (e.g. for BV functions of quotients of measures by replacing the quotient with the derivative and integrating this point function). Shannon’s definitions of information theory notions for continuous distributions can be corrected, and the statisticians’ formal integrals made sense of, as refinement integrals. A substantial study of the refinement integral was carried out by Kolmogorov in Math. Ann. 103 (1930) 654–696 — he integrates real-valued integrands of a subset argument on a domain of subsets closed only for intersection. Some extension and application of this basic source will be presented.

Leibniz’s conception of integration was as addition of infinitely many infinitely small quantities: To each x he imagined assigned an “infinitesimal” dy whose “sum” for all the x’s between a and b was to be the integral ∫_{a}^{b} dy. Eighteenth century mathematicians were unable to make head or tail of this and it was not until Cauchy, who “translated the definition from the language of metaphysics into that of mathematics” that it became usable. Cauchy approximated the “infinitesimal” f(x)dx (for a continuous function f) by the finite f(ξ_{i})(x_{i} − x_{i−1}) for any ξ_{i} between x_{i−1} and x_{i}; took the finite sum of these for any partition of the interval by finitely many x_{i}’s; and then defined ∫_{a}^{b} f(x)dx as the limit of these finite sums as the maximum length of the partitioning subintervals goes to zero. By the (uniform) continuity of f the result is independent of the choice of the ξ_{i} in the subintervals: indeed, the approach to the limit is uniform in these choices—a uniformity which must be postulated when defining the integral for discontinuous f. The approximation to dy on a subinterval Δ is thus the subset f(Δ)ℓ(Δ) of products of all values of f on it by its length; this multi-valued function of an interval, the diameter of whose value goes to zero as the interval shrinks to a point, represents the infinitesimal; and the limit of its sum over the partition, the result of the infinite summation.

The multi-valued functions can be avoided by recourse to the Darboux definition: this encompasses the totalities f(Δ) in terms of their bounds, the sup, \overline{f(Δ)} and inf, \underline{f(Δ)} of f on Δ; the upper/lower Darboux sums for a given partition are Σ\overline{f(Δ_{i})}ℓ(Δ_{i})/Σ(\underline{fΔ_{i}})ℓ(Δ_{i}) and the upper/lower integrals, inf Σ\overline{f(Δ_{i})}ℓ(Δ_{i})/ sup Σ(\underline{fΔ_{i}})ℓ(Δ_{i}) over all partitions. These quantities are actually (refinement) limits: for by adding an additional point to a partition— i.e. by splitting one of the Δ_{i} into a pair of contiguous subintervals—the upper sum can at most decrease and the lower at most increase. For any ϵ > 0 there is a partition whose upper/lower sum is within ϵ of the inf/sup—consequently so is every finer partition. The formulation as a refinement integral permits generalizing the setting from interval functions to set functions defined for subsets of an abstract set; it is also no longer needed to have these of the particular form of products—the additive “length function” ℓ can be absorbed by the set function.

Fix a system M of subsets of some set X; a partition, DE, of an E ∈ M is a representation of E as a finite disjoint union of sets E_{n} ∈ M, written E = ΣE_{n}. Partition D′E refines DE, D′E > DE, if every E′_{n} ∈ D′E is contained in some E_{m} ∈ DE—this is transitive: indeed, a partial order on the partitions of E.

We’ll postulate M closed for (finite) intersection: Then every DE induces on every E′ ∈ M contained in E a DE′ : E′ = ΣE_{n} ∩ E′; every pair of partitions DE, D′E have a common (actually a least fine) refinement (D ∩D′)E := ΣE_{m} ∩E′_{n}. This makes the partition partial order directed, which is what is needed for the usual properties of limit to hold: see Hildebrandt.

Let F be a real-valued function of a set argument (not taking −∞ as value) differentially defined i.e. (at least) on the sets making up sufficiently fine partitions: e.g. on all those which refine some given DE. Extend F to a partition function as F (DE) = ΣF (E_{j}). Thus F becomes a “net” and if it converges as DE is refined, F is called (refinement) integrable, its limit being denoted ∫_{E} F (dE).

To obtain the standard integral, say of a bounded measurable function f on a finite measure space X with its field M of subsets measurable for a finitely additive measure μ, take for F the function which assigns E ∈ M the product f(ξ)μE for some ξ ∈ E. One will require the convergence to ∫ f(x)μ(dx) (of Σf(ξ_{i})μE_{i}) to occur for all choices of the ξ_{i}—and even uniformly in the chosen ξ_{i}: thus convergence of the multi-valued ΣfE_{i} · μE_{i}. This can be modeled by an F which assigns each E ∈ M a subset of reals rather than a singleton (equivalently, to have uniform convergence for all the single-valued F ’s sending E into this subset). The convergence of the F extended to partitions is the same as that for the smallest intervals enclosing these image subsets, hence one could restrict to interval-image F ’s.

Convergence of (a net of) intervals comes to convergence of the left and right endpoints to the same limit. Every interval-valued function F on M yields two such functions on the partitions D′E > DE: an upper Σ\overline{F} E′_{m} and a lower Σ\underline{F} E′_{m}: the former is ≥ the latter on the same partition, but nothing further can be asserted in this general setting. The existence of the integral must thus require explicitly the existence of the refinement limits of the partition functions Σ\overline{F} E′_{m} and Σ\underline{F} E′_{m}—these limits could be called the upper and lower integral; (their ≥ is still maintained)—as well as their equality, the common value being by definition the integral ∫_{E} F (dE). What this comes to is that the intervals [Σ\underline{F} E′_{m}, Σ\overline{F} E′_{m}] refinement converge to this limit.

Corresponding to this three-part requirement is a three-part Cauchy condition: For ∀ϵ > 0 there should exist a DE such that for all D′E > DE, |Σ\overline{F} E′_{i} − Σ\overline{F} E_{j}| < ϵ; the same with \underline{F} replacing \overline{F}; and finally Σ\overline{F} E′_{i} − Σ\underline{F} E′_{i} < ϵ. (These could be combined into a single condition: |Σ\overline{F} E′_{i} − Σ\underline{F} E′′_{j}| < ϵ for all D′, D′′ > D. Proof: First deduce the last inequality.)

Kolmogorov’s take on the Leibniz paradigm is thus to realize the “infinitesimal” at a point as the set function F on the filter of subsets in the domain of F containing the point, the diameter of whose value converges to zero as the subsets shrink to the point, and their “infinite sum” over E as the refinement limit of the values of F as evaluated on the partitions of E.

The integral is additive in the domain of integration: The subsets over which it exists are closed under disjoint union and its value is the sum of its values on the summands. Proof: Sufficiently fine partitions of the union are obtained by combining partitions of the summands; and the limit of a sum is the sum of the limits (if they exist).

Integrability is inherited by every E′ ⊂ E which occurs in some DE. Proof: The Cauchy condition holds also with D replaced by any refinement, e.g. by D ∩ D′, which induces a partition of E′. Complete any refinement of the latter to a partition of E by leaving D ∩ D′ unchanged on the complement of E′. The first two Cauchy conditions then follow from their holding for partitions of E; the last from the positivity of the difference. By additivity, this may be construed as the integral of the function made zero on the complement.

As a function of E, ∫_{E} F (dE) is appropriately designated indefinite integral (on the real line this construes ∫ f(x) dx as an additive interval function rather than as a function of its upper limit): it is a single-valued additive set function defined on the subsets of the domain occurring in one of its partitions.

We will now characterize this set function and so obtain an alternate “descriptive” definition of the refinement integral.

To this end, declare two differentially defined functions f and g to be differentially equivalent if for every ϵ > 0 there is a DE such that for every finer D′E, Σ|fE′_{n} −gE′_{n}| < ϵ. What this comes to is that the set function |f − g|(E′) := |fE′ − gE′| integrates to 0 over E. Since it is non-negative, its indefinite integral is identically zero on ME, the subsets occurring in partitions of E (reducing the integrand to 0 on the complement of its domain results in an integrand dominated by |f − g|) a situation which could be called “zero almost everywhere.” Since the absolute value of h := f − g integrates identically to zero, it follows (e.g. from −|h| ≤ h ≤ |h|) that so does h.

We show the converse: If ∫_{G} h(dG) = 0 for all G ∈ ME then also ∫_{G} |h|(dG) = 0 — specifically, if |Σ\overline{h}(E′_{m})|, |Σ\underline{h}E′_{m}| < ϵ for all D′E > DE then Σ|h(E′_{m})| ≤ 4ϵ for sufficiently fine D′E — if not: i.e. if lim_{D′E>DE} sup Σ|\underline{h}E_{n}′| > 4ϵ, one of these D′E would have the sum of its like-signed terms, say the positive ones, > 2ϵ; the integral over each of the E′ sent by \underline{h} to a negative being zero, one can decompose each of these so that the sum of \underline{h} over all these subpartitions is > −ϵ, resulting in a global decomposition of E finer than DE over which \underline{h} sums to > ϵ.

Thus differential equivalence of f and g comes to ∫_{G} f(dG)−g(dG) = 0 for all G ∈ ME: If one of f, g is integrable, so is the other and the integrals are equal — and conversely. In particular, since the integral is a single-valued additive function on ME, its integral exists and equals its value, so that every integrable function is differentially equivalent to its indefinite integral. Conversely, if f is differentially equivalent to a single-valued additive function, it is integrable with indefinite integral that function. The indefinite integral is thus the unique additive function differentially equivalent to the integrand.

A (single-valued) additive function was seen to be integrable (to its value on the domain E); more generally, a subadditive function, i.e. f(E) ≤ Σf(E_{m}) on the partitions of every E, is integrable to the sup Σf(E_{m}) over all partitions of an E (one needs to require the Σf(E_{m}) to be bounded if one is unwilling to accept infinite values for the integral). If f is additive |f| is subadditive (since | | is): ∫_{E} |f(dE)| is then the (total) variation of f on E: e.g. if F is the interval function F (b) − F (a) then this yields the familiar sup Σ|F (x_{i}) − F (x_{i−1})|. A BV additive F can be written as a difference of nonnegatives: \frac{1}{2} [∫_{G} |f(dG)| + f(G)] − \frac{1}{2} [∫_{G} |f(dG)| − f(G)] (∫ ≥ ±f(G) by subadditivity)— however without the extremal property of Jordan’s.

If f is integrable over E, its differential equivalence with its indefinite integral F entails that of |f| with |F |. Thus an absolutely integrable f has a BV indefinite integral (in the Lebesgue theory, it is even absolutely continuous).

From every (possibly multi-valued) point function f(x) one can create a set function f(E) := ∪_{x∈E}f(x). This is a (complete) ∪–morphism. For just a subset–preserving interval– valued set map, define its “measurability” to mean convergence (under refinement) to zero of max_{i} \overline{f}E_{i} −\underline{f}E_{i} for partitions E = ΣE_{i}. Then a product fμ, with f measurable and μ BV, is integrable. If μ is non-negative and additive, the upper/lower sums are non-increasing/- decreasing under refinement and one obtains the upper/lower integral as an inf / sup as on the real line.

The following convergence theorem can be extracted from [Fl].

Let f be bounded on a BV set E containing an increasing sequence E_{n} of subsets converging in measure to E; for f_{n}μ integrable on E_{n}, let sup_{E_{n}} |fx − f_{n}x| converge to zero. Then fμ is integrable to lim ∫_{E_{n}} f_{n}μ.

Call an interval-valued set function g differentially contained (on E) in f if on sufficiently fine partitions of E = ΣE_{m}, Σ\underline{f}E_{m} ≤ Σ\underline{g}E_{m} ≤ Σ\overline{g}E_{m} ≤ Σ\overline{f}E_{m}. Then if f is integrable over E, so is g, and to the same value. The condition is certainly satisfied if the values of g on every subset E′ (in sufficiently fine partitions of E) lie between \underline{f}E′ and \overline{f}E′—i.e. if values of g are straddled by values of f on every such subset. Values of g are straddled by values of a product fμ , of which the second factor μ is single-valued, if and only if values of g/μ are by those of f— this entails that integrability of fμ yields that of g to the same value.

This justifies the additivity of the integral for integrands which are products: i.e. the integrability of fg and fg′ entails that of f(g + g′) and its value as the sum of their values: In view of the set identity F (G + G′) ⊂ F G + F G′, the values of f(g + g′) are contained in those of fg + fg′; the latter’s integrability to the sum ∫ fg + ∫ fg′ follows because the extrema of a sum are straddled by the sum of the extrema.

Finally, there is the possibility of evaluating certain refinement integrals as classical Lebesgue or Stieltjes integrals of related integrands. As seen above, the refinement integral of g will exist and equal that of the productfμ with single-valued μ if values of g/μ are straddled by those of f on subsets of sufficiently fine partitions. When μ is also additive and f derives from a point-function as the image function on subsets, this “Stieltjes-type integral” coincides with the Lebesgue integral when the set-system is that of the measurable sets (due to E.H. Moore)—indeed, a bounded measurable function on a set of finite measure refinement integrates to its Lebesgue integral, since there are partitions on whose sets the oscillation of f is arbitrarily small.

Since the indefinite refinement integral is finitely additive, it can be evaluated as a classical Lebesgue-Stieltjes integral of a given σ-additive measure μ for a suitable point integrand, just when it is μ absolutely continuous. If λ is additive and bounded by μ, then \frac{dλ}{dμ} is a bounded measurable function whose values on measurable E straddle \frac{λ(E)}{μ(E)}. This is preserved by postcomposition with piecewise monotone (increasing or decreasing) m’s—which would serve to reduce also refinement integrals of m [\frac{λ(E)}{μ(E)}] · μ (even for BV m by linearity) to ordinary integrals ∫ m [\frac{dλ}{dμ}] dμ.

One encounters this form with m = − ln in Information Theory; the form m[\frac{λ}{μ}] is, even for any convex m, subadditive so this refinement integral is also the sup over the approximating sums. Indeed, for any convex function f, vf(\frac{u}{v}) is a convex function of u and v > 0 [V, p. 260]:

f (\frac{αu + ⋯}{αv + ⋯}) = f (\frac{av}{αv + ⋯} · \frac{u}{v} + ⋯) ≤ \frac{αv}{αv + ⋯}f (\frac{u}{v}) + ⋯;

a quotient of additive functions λ/μ sends disjoint unions to convex combinations: \frac{λ+···}{μ+···} = \frac{μ}{μ+···} · \frac{λ}{μ} + ⋯, and a convex function of these is dominated by the convex combination of its values, hence by the sum of its values—thus a convex function of λ/μ is subadditive.

The basic quantity in Information Theory is the “average self-information” or “uncertainty” of a finite probability distribution

H\{p_{i}\} := Σp_{i} ln \frac{1}{p_{i}} = −Σp_{i} ln p_{i}.

In extending this to infinite distributions, Shannon proposed by analogy, for a distribution with density p

H\{p\} := ∫ p(x) ln \frac{1}{p(x)}dx = − ∫ p(x) ln p(x)dx.

But this is wrong, e.g., it could be negative, which would not be interpretable; more seriously it is not invariant under change of variable.

The correct definition is as a refinement integral

∫ P (dX) ln \frac{1}{P (dX)} = − ∫ P (dX) ln P (dX);

that is, one divides the interval into finitely many disjoint measurable sets {E_{i}} and approximates with finite sums −Σ_{i} ∫_{E_{i}} pdx ln ∫_{E_{i}} pdx. Since ln (\frac{1}{v}) is convex, the form is subadditive, whence the integral exists as the sup. It was calculated in [F] and gives ∞ except (possibly) for a discrete distribution, for which it refinement integrates to

Σp_{i} ln \frac{1}{p_{i}} .

Of fundamental significance in communication theory is the average decrease in uncertainty in one marginal (of a joint) distribution due to knowledge of the other. The quantity to be averaged (over the joint distribution) is the difference of the negative ln of the “a priori” (marginal) distribution {p_{i}} and that of the “a posteriori” (conditional—on the other marginal) distribution p_{i|j} :

Σp_{ij} ln \frac{p_{i|j}}{p_{i}} = Σp_{ij} ln \frac{p_{ij}}{p_{i}p_{j}} .

This is seen to be symmetric in the marginals and so is called their “mutual information.” It is subadditive under refinement (considering p_{i}p_{j} as a product distribution): hence for infinite distributions its refinement integral is the sup over the finite partitions of this expression— also a standard integral of the expression with the quotient of the joint over the product distribution replaced by their derivative [GY, Theorem 1.1].

Renyi’s “information gain of order α ≠ 1” for discrete distributions [R, p. 587] is (except for a constant factor)

I_{α}(Q∥P) = ln Σ\frac{q_{k}^{α}}{p_{k}^{α−1}} = ln Σ (\frac{q}{p})^{α} p.

On refinement, this goes over (x^{α} is convex for α > 1, concave for α < 1) to

ln ∫ (\frac{dQ}{dP})^{α} dP.

In particular, with P and Q distributions a.c. with respect to Lebesgue measure, the above yields [R, Theorem 2, p. 595].

The paradigm in Statistics is a family F (x; θ) of cumulative distribution functions indexed by an interval of θ’s; on the basis of an “observed” n-tuple one forms an “estimate” θ̃(x_{1}, …, x_{n}). [W] proposes to differentiate the identity ∫_{−∞}^{∞} dF (x; θ) = 1 and finds

\frac{d}{dθ} ∫_{−∞}^{∞} dF (x; θ) = ∫_{−∞}^{∞} [\frac{∂}{∂θ} log dF (x; θ)] dF (x; θ) = 0.

The bracket is obviously trying to be

[ ] = \frac{\frac{∂}{∂θ}dF (x; θ)}{dF (x; θ)};

and on the next page he explains the bracket as

[ ] = lim_{y↑x} \frac{\frac{∂}{∂θ}[F (x; θ) − F (y; θ)]}{F (x; θ) − F (y; θ)} = lim_{y↑x} \frac{\frac{∂}{∂θ}P ((y, x] | θ)}{P ((y, x] | θ)}.

However, independent of the existence of this limit or of its expectation, the refinement integral

∫ d\frac{∂F (x; θ)}{∂θ} = ∫ \frac{∂F}{∂θ} (dx; θ)

exists for differentiable F over every bounded interval since \frac{∂F}{∂θ} is, like F, additive; only the existence of the limit of \frac{∂F}{∂θ} at ±∞ is needed for the existence of the integral, and its vanishing to justify the passage of differentiation under ∫_{−∞}^{∞} .

Similarly, his

H(θ, θ′) := ∫_{−∞}^{∞}[log dF (x; θ′)]dF (x; θ)

could be interpreted as a refinement integral

∫ [log P (dx | θ′)]P (dx | θ).

An “unbiased estimator” θ̃ is one for which E(θ̃ | θ) = θ, i.e. ∫ (θ̃−θ)dF (x_{1}, …, x_{n}; θ) = 0. Since θ̃ does not involve θ, differentiation yields 1 = ∫ (θ̃ − θ)\frac{∂}{∂θ}dF = ∫ (θ̃ − θ)d\frac{∂F}{∂θ} . Let’s require d\frac{∂F}{∂θ} to have an L_{2} quotient with respect to dF, i.e. to have \frac{∂}{∂θ} log dF, the “derivative” d\frac{∂F}{∂θ} /dF, ∈ L_{2}(dF); then by Schwartz, 1 ≤ σ^{2}θ̃ · E (\frac{d \frac{∂F}{∂θ}}{dF} )^{2} and we obtain a lower bound for the variance of the estimator

σ^{2}θ̃ ≥ \frac{1}{E [(\frac{d \frac{∂F}{∂θ}}{dF} )^{2}]}.

That this “derivative” may be obtained pointwise from left differentiation with respect to F to justify d\frac{∂F}{∂θ} = [\frac{∂}{∂θ}dF/dF ] dF, follows because an everywhere left differentiable function is (dF) a.e. differentiable [S, p. 236].

It is worth noting that in the usual settings the two derivatives actually coincide. For discrete distributions F has jumps p_{i} and \frac{∂F}{∂θ} (if it exists) will have jumps \frac{dp_{i}}{dθ} at the same place; in the (absolutely) continuous case, dF = p(x; θ)dx and, with passage of \frac{∂}{∂θ} into ∫ p(x, θ)dx permitted, one has d\frac{∂F}{∂θ} /dF = \frac{1}{p(x;θ)} \frac{∂p(x;θ)}{∂θ} by the Chain Rule, both pointwise and for the measures.

An integral ∫ (\frac{df}{dF} )^{2} dF is the value of a refinement (called a “Hellinger”) integral ∫ \frac{f^{2}(dI)}{F (dI)}, since the value of \frac{(Δf)^{2}}{(ΔF)^{2}} (F nondecreasing) at intervals I not including 0 is straddled by values of (\frac{df}{dF} )^{2} at points of I. Since x^{2} is convex, this refinement integral is a sup, which is the form conceived by Hellinger in his 1907 Göttingen dissertation.

References [Arb] I.M. Gelfand et al., Arbeiten zur informationstheorie. II. Deutscher Verlag der Wis-

senschaften, Berlin, 1961.

[Cr] H. Cramér, Mathematical Methods of Statistics, Princeton Mathematical Series, vol. 9, Princeton University Press, Princeton, 1946.

[F] I. Fleischer, The central concepts of communication theory for infinite alphabets, J. Math. Phys. 37 (1958), pp. 223–228.

[Fl] I. Fleischer, Ein Integrallimesaustauschsatz Math. Annalen 148 (1962) pp. 367-371.

[G] R.G. Gallager, Information theory and reliable communication, Wiley, New York, 1968.

[GKY] I.M. Gelfand, A.N. Kolmogorov and A.M. Yaglom, On the general definition of the amount of information (Russian), Doklady Akad. Nauk, SSSR 111 (1956), pp. 745– 748. German translation in [Arb].

[GY] I.M. Gelfand and A.M. Yaglom, Calculation of the amount of information about a random function contained in another such function, Amer. Math. Soc. Transl. (2) 12 (1959), 199–246.

[H] T.H. Hildebrandt, Introduction to the Theory of Integration, Academic Press, New York, 1963.

[Ho] E.W. Hobson, The theory of functions of a real variable and the theory of Fourier’s series, Vol. I, Dover Publications, Inc., New York, 1958.

[K] A.N. Kolmogoroff, Untersuchungen über den Integralbegriff, Math. Ann. 103 (1930), 654–696.

[P] M.S. Pinsker, Information and information stability of random variables and processes, Translated and edited by Amiel Feinstein, Holden-Day, Inc., San Francisco, 1964.

[R] A. Rényi, Probability theory, North-Holland, 1970.

[S] S. Saks, Theory of the Integral, Dover, New York, 1964.

[V] I. Vajda, Theory of statistical inference and information, Kluwer Academic Publishers, Dordrecht, 1989.

[W] S.S. Wilks, Mathematical Statistics, Princeton University Press, Princeton, N.J., 1943.