The two problems indicated in the title are studied and a connection between them established.

For an ordered set, consider the model of distributionsPfor which an element that precedes another element is considered the more significant one in the sense that the implicationa≤b⇒P(a) ≥P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible.

For an arbitrary ordered set, we consider the model of all distributions P for which an element which precedes another element is considered the more significant one in the sense that the implication a les b rArr P(a) ges P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the indicated model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of reasonably low complexity.

Truth, belief and knowledge are important aspects of the overall concept of information. Speculating over the possible connections between these entities, new concepts come up naturally and also, specific relationships among them are derived. In particular, a relatively narrow class of measures of entropy and divergence are isolated which have special interpretations related to the world of which we are a part. The classical Shannon world and the world of a black hole may be conceived as extreme examples. Emphasis is on the underlying philosophy and the resulting cognitive paradigm which allows for an interaction between truth, belief and knowledge. The specific concepts which emerge are basically known and, apart from the central concepts related to Shannon theory, they were introduced by Havrda and Charvat, by Daroczy, by Lindhard and Nielsen and by Tsallis.

General optimization techniques typically depend on analytical tools involving differentiation. However, for many problems, special intrinsic tools lead in a more natural way to insight. For information theory, instances of this phenomenon includes problems on the determination of capacity, the search for universal codes or maximum entropy distributions and the calculation of information projections. Problems from other areas may also be treated by the intrinsic methods here presented.

This paper describes the Jensen-Shannon divergence (JSD) and Hilbert space embedding. With natural definitions making these considerations precise, one finds that the general Jensen-Shannon divergence related to the mixture is the minimum redundancy, which can be achieved by the observer. The set of distributions with the metric /spl radic/JSD can even be embedded isometrically into Hilbert space and the embedding can be identified.

Entropy measures going beyond Boltsmann-Shannon entropy are important in physics. This paper demonstrates the q- and k-entropies fit into a general theory based on measures of complexity. This depends on game theoretical considerations.

Let V and D denote, respectively, total variation and divergence. We study lower bounds of D with V fixed. The theoretically best (i.e., largest) lower bound determines a function L=L(V), Vajda's (1970) tight lower bound. The main result is an exact parametrization of L. This leads to Taylor polynomials which are lower bounds for L, and thereby to extensions of the classical Pinsker (1960) inequality which has numerous applications, cf. Pinsker and followers.

Notions of block symmetry for discrete memoryless channels are introduced. The results deal with capacity and optimal distributions and appear to be simple and natural ones which somehow were overlooked or not considered in the early development of information theory.

The game which can be taken to lie behind the maximum entropy principle is studied. Refining previous techniques, new theoretical results are obtained. These results are illustrated by concrete examples pertaining to well known classical models.

Let M/sub +//sup 1/(/spl Nopf/) be the set of probability distributions over /spl Nopf/ and denote by U/sub k/ a generic uniform distribution over a k-element set. By H and IC we denote, respectively, entropy and index of coincidence, i.e. H(P) = -/spl Sigma/p/sub k/ ln p/sub k/ and IC(P) = /spl Sigma/p/sub k//sup 2/. The motivation to develop lower bounds lies in applications to certain problems of exact prediction in Bernoulli models.

The game which can be taken to lie behind the maximum-entropy principle is studied. Refining previous techniques, new theoretical results are obtained. These results are illustrated by concrete examples pertaining to well-known classical models.

To any discrete probability distribution P we can associate its entropy H(P)=-/spl Sigma/p/sub i/ ln p/sub i/ and its index of coincidence IC(P)=/spl Sigma/p/sub i//sup 2/. The main result of the paper is the determination of the precise range of the map P/spl rarr/(IC(P), H(P)). The range looks much like that of the map P/spl rarr/(P/sub max/, H(P)) where P/sub max/ is the maximal point probability, cf. research from 1965 (Kovalevskij (1965)) to 1994 (Feder and Merhav (1994)). The earlier results, which actually focus on the probability of error 1-P/sub max/ rather than P/sub max/, can be conceived as limiting cases of results obtained by methods presented here. Ranges of maps as those indicated are called information diagrams. The main result gives rise to precise lower as well as upper bounds for the entropy function. Some of these bounds are essential for the exact solution of certain problems of universal coding and prediction for Bernoulli sources. Other applications concern Shannon theory (relations between various measures of divergence), statistical decision theory, and rate distortion theory. Two methods are developed. One is topological; the other involves convex analysis and is based on a "lemma of replacement" which is of independent interest in relation to problems of optimization of mixed type (concave/convex optimization).

Inequalities which connect information divergence with other measures of discrimination or distance between probability distributions are used in information theory and its applications to mathematical statistics, ergodic theory, and other scientific fields. We suggest new inequalities of this type, often based on underlying identities. As a consequence, we obtain certain improvements of the well-known Pinsker inequality. Our study depends on two measures of discrimination, called capacitory discrimination and triangular discrimination. The discussion contains references to related research and comparison with other measures of discrimination, e.g., Ali-Silvey-Csiszar (1996, 1966) divergences and, in particular, the Hellinger distance.