The Radon-Nikodym theorem plays a significant role in the definition of Shannon entropy, f-divergences, and other basic quantities in information theory. The existence of Radon Nikodym derivates appear in many text books in measure theory but in text books on probability or information theory it is often omitted because the proof is often considered to be too difficult.

Information projections have found important applications in probability theory, statistics, and related areas. In the field of hypothesis testing in particular, the reverse information projection (RIPr) has recently been shown to lead to growth-rate optimal (GRO) e-statistics for testing simple alternatives against composite null hypotheses. However, the RIPr as well as the GRO criterion are undefined whenever the infimum information divergence between the null and alternative is infinite. We show that in such scenarios, under some assumptions, there still exists a measure in the null that is closest to the alternative in a specific sense. Whenever the information divergence is finite, this measure coincides with the usual RIPr. It therefore gives a natural extension of the RIPr to certain cases where the latter was previously not defined. This extended notion of the RIPr is shown to lead to optimal e-statistics in a sense that is a novel, but natural, extension of the GRO criterion. We also give conditions under which the (extension of the) RIPr is a strict sub-probability measure, as well as conditions under which an approximation of the RIPr leads to approximate e-statistics. For this case we provide tight relations between the corresponding approximation rates.

Information projections have found many important applications in probability theory, statistics, and related fields. In the field of hypothesis testing in particular, the reverse information projection (RIPr) has recently been shown to lead to so-called growth-rate optimal (GRO) e-statistics for testing simple alternatives against composite null hypotheses. However, the RIPr as well as the GRO criterion are only defined in cases where the infimum information divergence between the null and alternative is finite. Here, we show that under much weaker conditions there often still exists an element in the alternative that is ‘closest’ to the null: the universal reverse information projection. The universal reverse information projection and its non-universal counterpart coincide whenever the KL is finite, and the strictness of this generalization will be shown by an example. Furthermore, the universal RIPr leads to optimal e-statistics in a sense that is a novel, but natural, extension of the GRO criterion. Finally, we discuss conditions under which the universal RIPr is a strict sub-probability distributions, and conditions under which an approximation of the universal RIPr leads to approximate e-statistics.

We use techniques from rate distortion theory in testing normality. The idea is first to do optimal compression with respect to squared Euclidean distance and then use information divergence of the compressed empirical distribution from the compressed Gaussian as statistic. We can analyze how the test performs at different rates. At low rate one gets a test that is efficient against other distributions in the Gaussian location family. If the rate is fixed at a positive value or the rate increases slower than the logarithm of the sample size as the sample size tends to infinity then the rate distortion test will asymptotically as as powerful as the likelihood ratio test. The test will first get efficient against elements in the exponential families generated by moment constraints of low order.

Statistical inference may follow a frequentist approach or it may follow a Bayesian approach or it may use the minimum description length principle (MDL). Our goal is to identify situations in which these different approaches to statistical inference coincide. It is proved that for exponential families MDL and Bayesian inference coincide if and only if the renormalized saddle point approximation for the conjugated exponential family is exact. For 1-dimensional exponential families the only families with exact renormalized saddle point approximations are the Gaussian location family, the Gamma family and the inverse Gaussian family. They are conjugated families of the Gaussian location family, the Gamma family and the Poisson-exponential family. The first two families are self-conjugated implying that only for the two first families the Bayesian approach is consistent with the frequentist approach. In higher dimensions there are more examples.

For convex optimization problems Bregman divergences appear as regret functions. Such regret functions can be defined on any convex set, but if a sufficiency condition is added the regret function must be proportional to information divergence and the convex set must be spectral. Spectral sets are sets where different orthogonal decompositions of a state into pure states have unique mixing coefficients. Only on such spectral sets it is possible to define well behaved information theoretic quantities like entropy and divergence. It is only possible to perform measurements in a reversible way if the state space is spectral. The most important spectral sets can be represented as positive elements of Jordan algebras with trace 1. This means that Jordan algebras provide a natural framework for studying quantum information.

We study the existence or absence of non-Shannon inequalities for variables that are related by functional dependencies. Although the powerset on four variables is the smallest Boolean lattice with non-Shannon inequalities there exist lattices with many more variables without non-Shannon inequalities. We search for conditions that ensures that no non-Shannon inequalities exist. It is demonstrated that 3-dimensional distributive lattices cannot have non-Shannon inequalities and planar modular lattices cannot have non-Shannon inequalities. The existence of non-Shannon inequalities is related to the question of whether a lattice is isomorphic to a lattice of subgroups of a group.

For testing independence it is very popular to use either the χ2-statistic or G2-statistics (mutual information). Asymptotically both are χ2-distributed so an obvious question is which of the two statistics that has a distribution that is closest to the χ2-distribution. Surprisingly the distribution of mutual information is much better approximated by a χ2-distribution than the χ2-statistic. For technical reasons we shall focus on the simplest case with one degree of freedom. We introduce the signed log-likelihood and demonstrate that its distribution function can be related to the distribution function of a standard Gaussian by inequalities. For the hypergeometric distribution we formulate a general conjecture about how close the signed log-likelihood is to a standard Gaussian, and this conjecture gives much more accurate estimates of the tail probabilities of this type of distribution than previously published results. The conjecture has been proved numerically in all cases relevant for testing independence and further evidence of its validity is given.

Pinsker's widely used inequality upper-bounds the total variation distance ∥P - Q∥1in terms of the Kullback-Leibler divergence D(P∥Q). Although, in general, a bound in the reverse direction is impossible, in many applications the quantity of interest is actually D*(v, Q)-defined, for an arbitrary fixed Q, as the infimum of D(P∥Q) over all distributions P that are at least v-far away from Q in total variation. We show that D*(v, Q) ≤ Cv2+ O(v3), where C = C(Q) = 1/2 for balanced distributions, thereby providing a kind of reverse Pinsker inequality. Some of the structural results obtained in the course of the proof may be of independent interest. An application to large deviations is given.

Rényi divergence is related to Rényi entropy much like Kullback-Leibler divergence is related to Shannon's entropy, and comes up in many settings. It was introduced by Rényi as a measure of information that satisfies almost the same axioms as Kullback-Leibler divergence, and depends on a parameter that is called its order. In particular, the Rényi divergence of order 1 equals the Kullback-Leibler divergence. We review and extend the most important properties of Rényi divergence and Kullback-Leibler divergence, including convexity, continuity, limits of\(\sigma \)-algebras, and the relation of the special order 0 to the Gaussian dichotomy and contiguity. We also show how to generalize the Pythagorean inequality to orders different from 1, and we extend the known equivalence between channel capacity and minimax redundancy to continuous channel inputs (for all orders) and present several other minimax results.

We study online learning under logarithmic loss with regular parametric models. Hedayati and Bartlett (2012) showed that a Bayesian prediction strategy with Jeffreys prior and sequential normalized maximum likelihood (SNML) coincide and are optimal if and only if the latter is exchangeable, which occurs if and only if the optimal strategy can be calculated without knowing the time horizon in advance. They put forward the question what families have exchangeable SNML strategies. We answer this question for one-dimensional exponential families: SNML is exchangeable only for three classes of natural exponential family distributions,namely the Gaussian, the gamma, and the Tweedie exponential family of order 3/2.

In this paper we show that a combination of the minimum description length principle and an exchange-ability condition leads directly to the use of Jeffreys prior. This approach works in most cases even when Jeffreys prior cannot be normalized. Kraft's inequality links codes and distributions but a closer look at this inequality demonstrates that this link only makes sense when sequences are considered as prefixes of potential longer sequences. For technical reasons only results for exponential families are stated. Results on when Jeffreys prior can be normalized after conditioning on a initializing string are given. An exotic case where no initial string allow Jeffreys prior to be normalized is given and some way of handling such exotic cases are discussed.

For testing goodness of fit it is very popular to use either the χ2-statistic or G2-statistics (information divergence). Asymptotically both are χ2-distributed so an obvious question is which of the two statistics that has a distribution that is closest to the χ2-distribution. Surprisingly, when there is only one degree of freedom it seems like the distribution of information divergence is much better approximated by a χ2-distribution than the χ2-statistic. For random variables we introduce a new transformation that transform several important distributions into new random variables that are almost Gaussian. For the binomial distributions and the Poisson distributions we formulate a general conjecture about how close their transform are to the Gaussian. The conjecture is proved for Poisson distributions.

We compare twof-divergences and prove that their joint range is the convex hull of the joint range for distributions supported on only two points. The proofs use various methods from topology and convex analysis.

Rényi divergence is related to Rényi entropy much like information divergence (also called Kullback-Leibler divergence or relative entropy) is related to Shannon's entropy, and comes up in many settings. It was introduced by Rényi as a measure of information that satisfies almost the same axioms as information divergence. We review the most important properties of Rényi divergence, including its relation to some other distances. We show how Rényi divergence appears when the theory of majorization is generalized from the finite to the continuous setting. Finally, Rényi divergence plays a role in analyzing the number of binary questions required to guess the values of a sequence of random variables.

Many of the divergence measures used in statistics are of the f-divergence type. Often one is interested inequalities for one f-divergence in terms of another f-divergence. Such inequalities are for instance needed in order to calculate the relative efficiency of two f-divergences when used for testing goodness of fit but there are many other applications. In this paper we shall study the more general problem of determining the joint range of any pair of f-divergences. The results are useful in determining general conditions under which information divergence is a more efficient statistic for testing goodness of fit than another f-divergence, but will not be discussed in this short paper.

Rényi'sthinningoperation on a discrete random variable is a natural discrete analog of the scaling operation for continuous random variables. The properties of thinning are investigated in an information-theoretic context, especially in connection with information-theoretic inequalities related to Poisson approximation results. The classical Binomial-to-Poisson convergence (sometimes referred to as the “law of small numbers”) is seen to be a special case of a thinning limit theorem for convolutions of discrete distributions. A rate of convergence is provided for this limit, and nonasymptotic bounds are also established. This development parallels, in part, the development of Gaussian inequalities leading to the information-theoretic version of the central limit theorem. In particular, a “thinning Markov chain” is introduced, and it is shown to play a role analogous to that of the Ornstein-Uhlenbeck process in connection to the entropy power inequality.

The normalized maximum likelihood (NML) distribution plays a fundamental role in the MDL approach to statistical inference. It is only defined for statistical families with a finite Shtarkov sum. Here we characterize, for 1-dimensional exponential families, when the Shtarkov sum is finite. This turns out to be the case if and only if the minimax redundancy is finite, thus extending the reach of our results beyond the individual-sequence setting. In practice, the NML/Shtarkov distribution is often approximated by the Bayesian marginal distribution based on Jeffreys' prior. One serious problem is that in many cases Jeffreys' prior cannot be normalized. It has been conjectured that Jeffreys' prior cannot be normalized in exactly the cases where the Shtarkov sum is infinite, i.e. when the minimax redundancy and regret are infinite. We show that the conjecture is true for a large class of exponential families but that there exist examples where the conjecture is violated.

A framework is developed using techniques from rate distortion theory in statistical testing. The idea is first to do optimal compression according to a certain distortion function and then use information divergence from the compressed empirical distribution to the compressed null hypothesis as statistic. Only very special cases have been studied in more detail, but they indicate that the approach can be used under very general conditions.

The law of thin numbers is a Poisson approximation theorem related to the thinning operation. We use information projections to derive lower bounds on the information divergence from a thinned distribution to a Poisson distribution. Conditions for the existence of projections are given. If an information projection exists it must be an element of the associated exponential family. Exponential families are used to derive lower bounds on information divergence and lower bounds on the rate of convergence in the law of thin numbers. A method of translating results related to Poisson distributions into results related to Gaussian distributions is developed and used to prove a new non-trivial result related to the central limit theorem.

Recently it was shown that Shannon entropy is more Bahadur efficient than any Rényi entropy of order α ≫ 1. In this paper we shall show that relative Bahadur efficiency between any two Rényi entropies of orders α ∈ ]0; 1] is 1 when the relative Bahadur efficiency is defined according to [1]. Despite the fact that the relative Bahadur efficiency is 1 it is shown that in a certain sense Shannon entropy is more efficient than Rényi entropy for α ∈ ]0; 1]. This indicates that the definition of relative efficiency given in [1] does not fully capture the notion of efficiency.

This paper compares the power divergence statistics of orders with the information divergence statistic in the problem of testing the uniformity of a distribution. In this problem, the information divergence statistic is equivalent to the entropy statistic. Extending some previously established results about information diagrams, it is proved that the information divergence statistic in this problem is more efficient in the Bahadur sense than any power divergence statistic of order . This means that the entropy provides in this sense the most efficient way of characterizing the uniformity of a distribution.

The "thinning" operation on a discrete random variable is the natural discrete analog of scaling a continuous variable, i.e., multiplying it by a constant. We examine the role and properties of thinning in the context of information-theoretic inequalities for Poisson approximation. The classical Binomial-to-Poisson convergence, often referred to as the "law of small numbers," is seen to be a special case of a thinning limit theorem for convolutions of discrete distributions. A rate of convergence is also provided for this limit. A Nash equilibrium is established for a channel game, where Poisson noise and a Poisson input are optimal strategies. Our development partly parallels the development of Gaussian inequalities leading to the information- theoretic version of the central limit theorem.

It is well-known that the information bottleneck method and rate distortion theory are related. Here it is described how the information bottleneck can be considered as rate distortion theory for a family of probability measures where information divergence is used as distortion measure. It is shown that the information bottleneck method has some properties that are not shared with rate distortion theory based on any other divergence measure. In this sense the information bottleneck method is unique.

This paper compares the power divergence statistics of orders alpha > 1 with the information divergence statistic in the problem of testing the uniformity of a distribution. In this problem the information divergence statistic is equivalent to the entropy statistic. Extending some previously established results about information diagrams, it is proved that in this problem the information divergence statistic is more efficient in the Bahadur sense than any power divergence statistic of order alpha > 1. This means that the entropy provides in a certain sense the most efficient way of characterizing the uniformity of a distribution.

New results and simplified proofs on convergence of convolutions on compact groups are presented. Information theoretic techniques and Markov chains play a crucial role. The rate of convergence is shown to be exponential. The results are also formulated via rate distortion functions

In this paper we are interested in n-dimensional uniform distributions on a triangle and a sphere. We show that their marginal distributions are maximizers of Renyi entropy under a constraint of variance and expectation in the respective cases of the sphere and of the triangle. Moreover, using an example, we show that a distribution on a triangle with (uniform) maximum entropy marginals may have an arbitrary small entropy. As a last result, we address the asymptotic behavior of these results and provide a link to the de Finetti theorem

A new maximal inequality for non-negative martingales is proved. It strengthens a well-known maximal inequality by Doob, and it is demonstrated that the stated inequality is tight. The inequality emphasizes the relation between martingales and information divergence. It implies pointwise convergence of X log X bounded martingales. A similar inequality holds for ergodic sequences. Relations to the Shannon-McMillan-Breiman theorem and Markov chains are mentioned

For sums of i.i.d. random variables the maximum entropy distribution with respect to the first moments fixed is compared with the Edgeworth expansion. It is demonstrated that the Edgeworth expansion can and shall be considered as a linear extrapolation of the maximum entropy distribution. The coefficients in the Edgeworth expansion can be used as a first approximation for numerical calculation of the maximum entropy distribution.

Two new information-theoretic methods are introduced for establishing Poisson approximation inequalities. First, using only elementary information-theoretic techniques it is shown that, when S/sub n/=/spl Sigma//sub i=1//sup n/X/sub i/ is the sum of the (possibly dependent) binary random variables X/sub 1/,X/sub 2/,...,X/sub n/, with E(X/sub i/)=p/sub i/ and E(S/sub n/)=/spl lambda/, then D(P(S/sub n/)/spl par/Po(/spl lambda/)) /spl les//spl Sigma//sub i=1//sup n/p/sub i//sup 2/+[/spl Sigma//sub i=1//sup n/H(X/sub i/)-H(X/sub 1/,X/sub 2/,...,X/sub n/)] where D(P(S/sub n/)/spl par/Po(/spl lambda/)) is the relative entropy between the distribution of S/sub n/ and the Poisson (/spl lambda/) distribution. The first term in this bound measures the individual smallness of the X/sub i/ and the second term measures their dependence. A general method is outlined for obtaining corresponding bounds when approximating the distribution of a sum of general discrete random variables by an infinitely divisible distribution. Second, in the particular case when the X/sub i/ are independent, the following sharper bound is established: D(P(S/sub n/)/spl par/Po(/spl lambda/))/spl les/1//spl lambda/ /spl Sigma//sub i=1//sup n/ ((p/sub i//sup 3/)/(1-p/sub i/)) and it is also generalized to the case when the X/sub i/ are general integer-valued random variables. Its proof is based on the derivation of a subadditivity property for a new discrete version of the Fisher information, and uses a recent logarithmic Sobolev inequality for the Poisson distribution.

A new projection is defined via data compression. Often it equals the generalized information projection, but if the projections differ, the weak information projection has better properties.

The precise bounds on the information divergence from a binomial distribution to the accompanying Poisson law are obtained. As a corollary, an upper bound for the total variation distance between the distributions is established, which in a large range of change of the parameters of the distributions is better than those already known.

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.

The binomial and the Poisson distributions are shown to be maximum entropy distributions of suitably defined sets. Poisson's law is considered as a case of entropy maximization, and also convergence in information divergence is established.

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).