Maximum Entropy Fundamentals

Abstract

In its modern formulation, the Maximum Entropy Principle was promoted by E.T. Jaynes, starting in the mid-fifties The principle dictates that one should look for a distribution, consistent with available information, which maximizes the entropy. However, this principle focuses only on distributions and it appears advantageous to bring information theoretical thinking more prominently into play by also focusing on the “observer” and on coding. This view was brought forward by the second named author in the late seventies and is the view we will follow-up on here. It leads to the consideration of a certain game, the Code Length Game and, via standard game theoretical thinking, to a principle of Game Theoretical Equilibrium. This principle is more basic than the Maximum Entropy Principle in the sense that the search for one type of optimal strategies in the Code Length Game translates directly into the search for distributions with maximum entropy.

In the present paper we offer a self-contained and comprehensive treatment of fundamentals of both principles mentioned, based on a study of the Code Length Game. Though new concepts and results are presented, the reading should be instructional and accessible to a rather wide audience, at least if certain mathematical details are left aside at a first reading.

The most frequently studied instance of entropy maximization pertains to the Mean Energy Model which involves a moment constraint related to a given function, here taken to represent “energy” . This type of application is very well known from the literature with hundreds of applications pertaining to several different fields and will also here serve as important illustration of the theory. But our approach reaches further, especially regarding the study of continuity properties of the entropy function, and this leads to new results which allow a discussion of models with so-called entropy loss. These results have tempted us to speculate over the development of natural languages. In fact, we are able to relate our theoretical findings to the empirically found Zipf’s law which involves statistical aspects of words in a language. The apparent irregularity inherent in models with entropy loss turns out to imply desirable stability properties of languages.

1 The Maximum Entropy Principle – overview and a generic example

The Maximum Entropy Principle as conceived in its modern form by Jaynes, cf. [11], [12] and [13], is easy to formulate: “Given a model of probability distributions, choose the distribution with highest entropy.” With this choice you single out the most significant distribution, the least biased one, the one which best represents the “true” distribution. The sensibility of this principle in a number of situations is well understood and discussed at length by Jaynes, in particular.

The principle is by now well established and has numerous applications in physics, biology, demography, economy etc. For practically all applications, the key example which is taken as point of departure – and often the only example discussed – is that of models prescribed by moment conditions. We refer to Kapur, [14] for a large collection of examples as well as a long list of references.

In this section we present models defined by just one moment condition. These special models will later be used to illustrate theoretical points of more technical sections to follow.

Our approach will be based on the introduction of a two-person zero-sum game. The principle which this leads to, called the principle of Game Theoretical Equilibrium is taken to be even more basic than the Maximum Entropy Principle. In fact, from this principle you are led directly to the Maximum Entropy Principle and, besides, new interesting features emerge naturally by focusing on the interplay between a system and the observer of the system. As such the new principle is in conformity with views of quantum physics, e.g. we can view the principle of Game Theoretical Equilibrium as one way of expressing certain sides of the notion of complementarity as advocated by Niels Bohr in a precise mathematical way.

To be more specific, let us choose the language of physics and assume that on the set of natural numbers ℕ we have given a function E, the energy function. This function is assumed to be bounded below. Typically, E will be non-negative. Further, we specify a certain finite energy level, λ, and take as our model all probability distributions with mean energy λ. We assume that the energy E_i in “state” i ∈ ℕ goes fast enough to infinity that the entropies of distributions in the model remain bounded. In particular, this condition is fulfilled if E_i = ∞ for all i sufficiently large – the corresponding states are then “forbidden states” – and in this case the study reduces to a study of models with finite support.

Once you have accepted the Maximum Entropy Principle, this leads to a search for a maximum entropy distribution in the model. It is then tempting to introduce Lagrange multipliers and to solve the constrained optimization problem you are faced with in the standard manner. In fact, this is what practically all authors do and we shall briefly indicate this approach

We want to maximize entropy $H=-{\displaystyle {\sum }_1^{\infty }{p}_i}\log p_i$ subject to the moment condition ${\displaystyle {\sum }_1^{\infty }{p}_i}{E}_i=\lambda$ and subject to the usual constraints p_i ≥ 0; i ∈ ℕ and ${\displaystyle {\sum }_1^{\infty }{p}_i}=1$. Introducing Lagrange multipliers –β and μ, we are led to search for a solution for which all partial derivatives of the function $H-\beta {\displaystyle {\sum }_1^{\infty }{p}_i}{E}_i+\mu {\displaystyle {\sum }_1^{\infty }{p}_i}{E}_i$ vanish. This leads to the suggestion that the solution is of the form

$$p_i=\frac{\exp \left(-\beta E_i\right)}{Z\left(\beta \right)} ;i\ge 1$$

(1.1)

for some value of β for which the partition function Z defined by

$$Z\left(\beta \right)={\displaystyle \sum _{i=1}^{\beta }\exp \left(-\beta E_i\right)}$$

(1.2)

is finite.

The approach is indeed very expedient. But there are difficulties connected with it. Theoretically, we have to elaborate on the method to be absolutely certain that it leads to the solution, even in the finite case when E_i = ∞ for i sufficiently large. Worse than this, in the infinite case there may not be any solution at all. This is connected with the fact that there may be no distribution of the form (1.1) which satisfies the required moment condition. In such cases it is not clear what to do.

Another concern is connected with the observation that the method of Lagrange multipliers is a completely general tool, and this very fact indicates that in any particular situation there may possibly be other ways forward which better reflect the special structure of the problem at hand. Thus one could hope to discover new basic features by appealing to more intrinsic methods.

Finally we note that the method of Lagrange multipliers cannot handle all models of interest. If the model is refined by just adding more moment constraints, this is no great obstacle. Then the distributions and partition functions that will occur instead of (1.1) and (1.2) will work with inner products of the form ${\beta }^{\prime }{E^{\prime }}_i+{\beta }^{″}{E^{″}}_i+\cdots$ in place of the simple product βE_i. In fact, we shall look into this later. Also other cases can be handled based on the above analysis, e.g. if we specify the geometric mean, this really corresponds to a linear constraint by taking logarithms, and the maximum entropy problem can be solved as above (and leads to interesting distributions in this case, socalled power laws). But for some problems it may be difficult or even impossible to use natural extensions of the standard method or to use suitable transformations which will reduce the study to the standard set-up. In such cases, new techniques are required in the search for a maximum entropy distribution. As examples of this difficulty we point to models involving binomial or empirical distributions, cf. [8] and [22].

After presentation of preliminary material, we introduce in Section 3 the basic concepts related to the game we shall study. Then follows a section which quickly leads to familiar key results. The method depends on the information- and game-theoretical point of view. This does not lead to complete clarification. For the proper understanding of certain phenomena, a more thorough theoretical discussion is required and this is taken up in the remaining sections.

New results are related to so-called entropy loss – situations where a maximum entropy distribution does not exist. In the last section, these type of models are related to Zipf’s law regarding statistical aspects of the semantics of natural languages.

Mathematical justification of all results is provided. Some technical results which we shall need involve special analytical tools regarding Dirichlet series and are delegated to an appendix.

2 Information theoretical preliminaries

Let $\mathbb{A}$, the alphabet, be a discrete set, either finite or countably infinite and denote by ^∼$M_{+}^1\left(\mathbb{A}\right)$, respectively $M_{+}^1\left(\mathbb{A}\right)$ the set of non-negative measures P on $\mathbb{A}$ (with the discrete Borel structure) such that P ($\mathbb{A}$) ≤ 1, respectively P ($\mathbb{A}$) = 1. The elements in $\mathbb{A}$ can be thought of in many ways, e.g. as letters (for purely information theoretical or computer science oriented studies), as pure states (for applications to quantum physics) or as outcomes (for models of probability theory and statistics).

For convenience, $\mathbb{A}$ will always be taken to be the set ℕ of natural numbers or a finite section thereof, and elements in $\mathbb{A}$ are typically referred to by indices like i, j, ⋯.

Measures in $M_{+}^1\left(\mathbb{A}\right)$ are probability distributions, or just distributions, measures in ^~$M_{+}^1\left(\mathbb{A}\right)$ are general distributions and measures in ^~$M_{+}^1\left(\mathbb{A}\right)\backslash M_{+}^1\left(\mathbb{A}\right)$ are incomplete distributions. For P, Q, ⋯ ∈ ^∼$M_{+}^1\left(\mathbb{A}\right)$, the point masses are, typically, denoted by p_i, q_i, ⋯.

By ^∼K($\mathbb{A}$), we denote the set of all mappings κ : $\mathbb{A}$ → [0; ∞] which satisfy Kraft’s inequality

$${\displaystyle \sum _{i\in \mathbb{A}}\exp \left(-{\kappa }_i\right)}\le 1.$$

(2.3)

Elements in ^∼K($\mathbb{A}$) are general codes. The values of a general code κ are denoted κ_i. The terminology is motivated by the fact that if κ ∈ ^∼K($\mathbb{A}$) and if the base for the exponential in (2.3) is 2, then there exists a binary prefix-free code such that the i’th code word consists of approximately κ_i binary digits.

By K($\mathbb{A}$) we denote the set of mappings κ : $\mathbb{A}$ → [0; ∞] which satisfy Kraft’s equality

$${\displaystyle \sum _{i\in \mathbb{A}}\exp \left(-{\kappa }_i\right)}=1.$$

(2.4)

This case corresponds to codes without superfluous digits. For further motivation, the reader may wish to consult [23] or standard textbooks such as [3] and [6].

Elements in K($\mathbb{A}$) are compact codes, for short just codes.

For mathematical convenience, we shall work with exponentials and logarithms to the base e.

For κ ∈ ^∼K($\mathbb{A}$) and i ∈ $\mathbb{A}$, κ_i is the code length associated with i or, closer to the intended interpretation, we may think of κ_i as the code length of the code word which we imagine κ associates with i. There is a natural bijective correspondance between ^∼$M_{+}^1\left(\mathbb{A}\right)$ and ^∼K($\mathbb{A}$), expressed notationally by writing P ↔ κ or κ ↔ P , and defined by the formulas

κ_i = −log p_i, p_i = exp(−κ_i).

Here the values κ_i = ∞ and p_i = 0 correspond to eachother. When the above formulas hold, we call (κ, P) a matching pair and we say that κ is adapted to P or that P is the general distribution which matches κ. If $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$ and κ ∈ K($\mathbb{A}$), we say that κ is $\mathcal{P}$-adapted if κ is adapted to one of the distributions in $\mathcal{P}$. Note that the correspondance κ ↔ P also defines a bijection between $M_{+}^1\left(\mathbb{A}\right)$ and k($\mathbb{A}$)

The support of κ is the set of i ∈ $\mathbb{A}$ with κ_i < ∞. Thus, with obvious notation, supp (κ) = supp (P) where P is the distribution matching κ and supp (P) is the usual support of P .

For expectations – always w.r.t. genuine probability distributions – we use the bracket notation. Thus, for $P\in M_{+}^1\left(\mathbb{A}\right)$ and f : $\mathbb{A}$ → [−∞; ∞], we put

$$\langle f,P\rangle ={\displaystyle \sum _{i\in \mathbb{A}}f\left(i\right)}{p}_i$$

whenever this is a well-defined extended real number. Mostly, our functions will be non-negative and then 〈f, P〉 will of course be a well defined number in [0; ∞]. In particular this is the case for average code length defined for κ ∈ ^∼K($\mathbb{A}$ ) and $P\in M_{+}^1\left(\mathbb{A}\right)$ by

$$\langle \kappa ,P\rangle ={\displaystyle \sum _{i\in \mathbb{A}}f\left(i\right)}{p}_i.$$

Entropy and divergence are defined as usual, i.e., for $P\in M_{+}^1\left(\mathbb{A}\right)$, the entropy of P is given by

$$H\left(P\right)=-{\displaystyle \sum _{i\in \mathbb{A}}{p}_i}\log p_i$$

(2.5)

or, equivalently, by H(P) = 〈κ, P〉 where κ is the code adapted to P. And for $P\in M_{+}^1\left(\mathbb{A}\right)$ and $Q\in {}^{\sim }{M}_{+}^1\left(\mathbb{A}\right)$ we define the divergence (or relative entropy) between P and Q by

$$D\left(P\left|\right|Q\right)={\displaystyle \sum _{i\in \mathbb{A}}{p}_i}\log \frac{p_i}{q_i}.$$

(2.6)

Divergence is well defined with 0 ≤ D(P‖Q) ≤ ∞ and D(P‖Q) = 0 if and only if P = Q.

The topological properties which we shall find useful for codes and for distributions do not quite go in parallel. On the coding side we consider the space ^∼K($\mathbb{A}$) of all general codes and remark that this space is a metrizable, compact and convex Hausdorff space. This may be seen by embedding ^∼K($\mathbb{A}$) in the space [0; ∞]${}^{\mathbb{A}}$ of all functions on $\mathbb{A}$ taking values in the compact space [0; ∞]. The topology on ^∼K($\mathbb{A}$) then is the topology of pointwise convergence. This is the only topology we shall need on ^∼K($\mathbb{A}$).

On the distribution side we shall primarily consider probability distributions but on the corresponding space, $M_{+}^1\left(\mathbb{A}\right)$, we find it useful to consider two topologies, the usual, pointwise topology and then a certain stronger non-metrizable topology, the information topology.

As to the usual topology on $M_{+}^1\left(\mathbb{A}\right)$ we remind the reader that this is a metrizable topology, indeed it is metrized by total variation defined by

$$V\left(P,Q\right)={\displaystyle \sum _i\left|p_i-q_i\right|}.$$

We write $P_n\stackrel{V}{\to }P$ for convergence and ${\overline{\mathcal{P}}}^V$, ${\overline{\text{co}}}^V\mathcal{P}$ etc. for closure in this topology (the examples show the closure of $𝒫$ and of the convex hull of $𝒫$, respectively).

As to the information topology – the second topology which we need on the space $M_{+}^1\left(\mathbb{A}\right)$–this can be described as the strongest topology such that, for (P_n)_n≥1 ⊆ $M_{+}^1\left(\mathbb{A}\right)$ and P ∈ $M_{+}^1\left(\mathbb{A}\right)$, lim_n→∞ D(P_n‖P) = 0 implies that the sequence (P_n)_n≥1 converges to P. Convergence in this topology is denoted $P_n\stackrel{D}{\to }P$. We only need convergence in this topology for sequences, not for generalized sequences or nets. Likewise, we only need sequential closure and ${\overline{\mathcal{P}}}^{D_{\sigma }}$, ${\overline{\text{co}}}^{D_{\sigma }}\mathcal{P}$ or what the case may be denotes sequential closure. Thus ${\overline{\mathcal{P}}}^{D_{\sigma }}$ denotes the set of distributions P for which there exists a sequence (P_n)_n≥1 of distributions in $\mathcal{P}$ with $P_n\stackrel{D}{\to }P$. The necessary and sufficient condition that $P_n\stackrel{D}{\to }P$ holds is that D(P_n‖P) → 0 as n → ∞. We warn the reader that the corresponding statement for nets (generalized sequences) is wrong – only the sufficiency part holds generally. For the purposes of this paper, the reader needs only worry about sequences but it is comforting to know that the sequential notion $P_n\stackrel{D}{\to }P$ is indeed a topological notion of convergence. Further details will be in [9].

An important connection between total variation and divergence is expressed by Pinsker’s inequality:

$$D\left(P\left|\right|Q\right)\ge \frac{1}{2}V{\left(P,Q\right)}^2,$$

(2.7)

which shows that convergence in the information topology is stronger than convergence in total variation.

The functions of relevance to us, entropy and divergence, have important continuity properties: P ↷ H(P) is lower semi-continuous on $M_{+}^1\left(\mathbb{A}\right)$ and (P, Q) ↷ D(P‖Q) is jointly lower semicontinuous on $M_{+}^1\left(\mathbb{A}\right){\times }^{\sim }{M}_{+}^1\left(\mathbb{A}\right)$. These continuity properties even hold w.r.t. the usual, pointwise topology. Details may be found in [23].

3 The Code Length Game, introduction

In this section $\mathcal{P}$ is a non-empty subset of $M_{+}^1\left(\mathbb{A}\right)$, neutrally referred to as the model. In specific applications it may be more appropriate with other terminology, e.g. the preparation space or the statistical model. Distributions in $\mathcal{P}$ are called consistent distributions.

With $\mathcal{P}$we associate a two-person zero-sum game, called the Code Length Game over$\mathcal{P}$. In this game, Player I chooses a consistent distribution, and Player II chooses a general code. The cost-function, seen from the point of view of Player II, is the $P\times {}^{\sim }K\left(\mathbb{A}\right)\to \left[0,\infty \right]$ given by the average code length:

(P, κ) ↷ (κ, P).

This game was introduced in [20], see also [15], [21], [10], [8] and [22]. Player I may be taken to represent “the system”, “Nature”, “God” or ⋯ , whereas Player II represents “the observer”, “the statistician” or ⋯ .

We can motivate the game introduced in various ways. The personification of the two participants in the game is natural as far as Player II is concerned since, in many situations, we can identify ourselves with that person. Also, the objective of Player II appears well motivated. To comment on this in more detail, we first remind the reader that we imagine that there is associated a real code consisting of binary sequences to κ ∈ ^∼K($\mathbb{A}$) and that κ merely tells us what the code lengths of the various code words are.

We can think of a specific code in at least three different ways: as a representation of the letters in $\mathbb{A}$, as a means for identification of these letters and – the view we find most fruitful – as a strategy for making observations from a source generating letters from $\mathbb{A}$. The two last views are interrelated. In fact, for the strategy of observation which we have in mind, we use the code to identify the actual outcome by posing a succession of questions, starting with the question “is the first binary digit in the code word corresponding to the outcome a 1?” , then we ask for the second binary digit and so on until it is clear to us which letter is the actual outcome from the source. The number of questions asked is the number of binary digits in the corresponding code word.

The cost function can be interpretated as mean representation time, mean identification time or mean observation time and it is natural for Player II to attempt to minimize this quantity. The sense in assuming that Player I has the opposite aim, namely to maximize the cost function is more dubious. The arguments one can suggest to justify this, thereby motivating the zero-sum character of the Code Length Game, are partly natural to game theory in general, partly can be borrowed from Jaynes’ reasoning behind his Maximum Entropy Principle. Without going into lengthy discussions we give some indications: Though we do not seriously imagine that Player I is a “real” person with rational behaviour, such thoughts regarding the fictive Player I reflect back on our own conceptions. With our fictitious assumptions we express our own modelling. If all we know is the model $𝒫$ and if, as is natural, all we strive for is minimization of the cost function, we cannot do better than imagining that Player I is a real person behaving rationally in a way which is least favourable to us. Any other assumption would, typically, lead to non-sensical results which would reveal that we actually knew more than first expressed and therefore, as a consequence, we should change the model in order better to reflect our level of knowledge.

To sum up, we have argued that the observer should be allowed freely to choose the means of observation, that codes offer an appropriate technical tool for this purpose and that the choice of a specific code should be dictated by the wish to minimize mean observation time, modelled adequately by the chosen cost function. Further, the more fictitious views regarding Player I and the behaviour of that player, really reflect on the adequacy and completeness of our modelling. If our modelling is precise, the assumptions regarding Player I are sensible and general theory of two-person zero-sum games can be expected to lead to relevant and useful results.

The overall principle we shall apply, we call the principle of Game Theoretical Equilibrium. It is obtained from general game theoretical considerations applied to the Code Length Game. No very rigid formulation of this principle is necessary. It simply dictates that in the study of a model, we shall investigate standard game theoretical notions such as equilibrium and optimal strategies.

According to our basic principle, Player I should consider, for each possible strategy P ∈ $𝒫$, the infimum of 〈κ, P〉 over κ ∈ ^∼K($\mathbb{A}$). This corresponds to the optimal response of Player II to the chosen strategy. The infimum in question can easily be identified by appealing to an important identity which we shall use frequently in the following. The identity connects average code length, entropy and divergence and states that

〈κ, P〉 = H(P) + D(P‖Q),

(3.8)

valid for any κ ∈ ^∼K($\mathbb{A}$) and $P\in M_{+}^1\left(\mathbb{A}\right)$ with Q the (possibly incomplete) distribution matching κ. The identity is called the linking identity. As D(P‖Q) ≥ 0 with equality if and only if P = Q, an immediate consequence of the linking identity is that entropy can be conceived as minimal average code length:

$$H\left(P\right)=\underset{\kappa {\in }^{\sim }K\left(\mathbb{A}\right)}{\min }\langle \kappa ,P\rangle .$$

(3.9)

The minimum is attained for the code adapted to P and, provided H(P) < ∞, for no other code.

Seen from the point of view of Player I, the optimal performance is therefore achieved by maximizing entropy. The maximum value to strive for is called the maximum entropy value (H_max-value) and is given by

$$H_{\max }\left(\mathcal{P}\right)=\underset{P\in \mathcal{P}}{\sup }H\left(P\right).$$

(3.10)

On the side of Player II – the “coding side” – we consider, analogously, for each κ ∈ ^∼K($\mathbb{A}$) the associated risk given by

$$R\left(\kappa |\mathcal{P}\right)=\underset{P\in \mathcal{P}}{\sup }\langle \kappa ,P\rangle$$

(3.11)

and then the minimum risk value (R_min-value)

$$R_{\min }\left(\mathcal{P}\right)=\underset{\kappa {\in }^{\sim }K\left(\mathbb{A}\right)}{\inf }R\left(\kappa |\mathcal{P}\right).$$

(3.12)

This is the value to strive for for Player II.

We have now looked at each side of the game separately. Combining the two sides, we are led to the usual concepts, well known from the theory of two-person zero-sum games. Thus, the model $\mathcal{P}$ is in equilibrium if H_max($\mathcal{P}$) = R_min($\mathcal{P}$) < ∞, and in this case, H_max($\mathcal{P}$) = R_min($\mathcal{P}$) is the value of the game. Note that as a “supinf” is bounded by the corresponding “infsup”, the inequality

$$H_{\max }\left(\mathcal{P}\right)\le R_{\min }\left(\mathcal{P}\right)$$

(3.13)

always holds.

The concept of optimal strategies also follows from general considerations. For Player I, this is a consistent distribution with maximal entropy, i.e. a distribution P ∈ $\mathcal{P}$ with H(P) = H_max($\mathcal{P}$). And for Player II, an optimal strategy is a code κ^∗ ∈ ^∼K($\mathbb{A}$) such that R(κ^∗|$\mathcal{P}$) = R_min($\mathcal{P}$). Such a code is also called a minimum risk code (R_min-code).

4 Cost-stable codes, partition functions and exponential families

The purpose of this section is to establish a certain sufficient condition for equilibrium and to identify the optimal strategies for each of the players in the Code Length Game. This cannot always be done but the simple result presented here already covers most applications. Furthermore, the approach leads to familiar concepts and results. This will enable the reader to judge the merits of the game theoretical method as compared to a more standard approach via the introduction of Lagrange multipliers.

As in the previous section, we consider a model $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$. Let κ^∗ ∈ K($\mathbb{A}$) together with its matching distribution P^∗ be given and assume that P^∗ is consistent. Then we call κ^∗ a Nash equilibrium code for the model $\mathcal{P}$ if

〈κ^∗, P 〉 ≤ 〈κ^∗, P^∗〉; P ∈ $𝒫$

(4.14)

and if H(P^∗) < ∞. The terminology is adapted from mathematical economy, cf. e.g. Aubin [2]. The requirement can be written R(κ^∗|$\mathcal{P}$) ≤ H(P^∗) < ∞. Note that here we insist that a Nash equilibrium code be $\mathcal{P}$-adapted. This condition will later be relaxed.

Theorem 4.1. 

Let $\mathcal{P}$ be a model and assume that there exists a $\mathcal{P}$-adapted Nash equilibrium code κ^∗, say, with matching distribution P^∗. Then $\mathcal{P}$ is in equilibrium and both players have optimal strategies. Indeed, P^∗ is the unique optimal strategy for Player I and κ^∗ the unique optimal strategy for Player II.

Proof. 

Since R(κ^∗|$\mathcal{P}$) ≤ H(P^∗), R_min($\mathcal{P}$) ≤ H_max($\mathcal{P}$). As the opposite inequality always holds by (3.13), $\mathcal{P}$ is in equilibrium, the value of the Code Length Game associated with $\mathcal{P}$ is H(P^∗) and κ^∗ and P^∗ are optimal strategies.

To establish the uniqueness of κ^∗, let κ be any code distinct from κ. Let P be the distribution matching κ. Then, by the linking identity,

R(κ|$𝒫$) ≥ 〈κ, P^∗〉 = H(P^∗) + D(P^∗‖P) > H(P^∗) ,

hence κ is not optimal.

For the uniqueness proof of P^∗, let P be a consistent distribution distinct from P^∗. Then, again by the linking identity,

H(P) < H(P) + D(P‖P^∗) = (κ^∗, P) ≤ H(P^∗),

and P cannot be optimal.      ☐

As we shall see later, the existence of a Nash equilibrium code is, essentially, also necessary for the conclusion of the theorem. 1 This does not remove the differenty of actually finding the Nash equilibrium code in concrete cases of interest. In many cases it turns out to be helpful to search for codes with stronger properties. A code κ^∗ is a cost-stable code for $\mathcal{P}$ if there exists h < ∞ such that 〈κ^∗, P〉 = h for all P ∈ $\mathcal{P}$. Clearly, a cost-stable code with a consistent matching distribution is a Nash equilibrium code. Therefore, we obtain the following corollary from Theorem 4.1:

Corollary 4.2. 

If κ^∗ is a cost-stable code for $\mathcal{P}$ and if the matching distribution P^∗ is consistent, then $\mathcal{P}$ is in equilibrium and κ^∗ and P^∗ are the unique optimal strategies pertaining to the Code Length Game.

In order to illustrate the usefulness of this result, consider the case of a model $𝒫$ given by finitely many linear constraints, say

$$\mathcal{P}=\left\{P\in M_{+}^1\left(\mathbb{A}\right)|\langle E_1,P\rangle ={\lambda }_1,\dots ,\langle E_n,P\rangle ={\lambda }_n\right\}$$

(4.15)

with E₁, . . . , E_n real-valued functions bounded from below and λ₁, . . . , λ_n real-valued constants.

Let us search for cost-stable codes κ for$\mathcal{P}$. Clearly, any code of the form

$$\kappa =\alpha +{\beta }_1{E}_1+\cdots +{\beta }_n{E}_n=\alpha +\overline{\beta }\cdot \overline{E}$$

(4.16)

is cost-stable. Here, α and the β’s denote constants, $\overline{\beta }$ and $\overline{E}$ vectors and a dot signifies scalar products of vectors. For κ defined by (4.16) to define a code we must require that κ ≥ 0 and, more importantly, that Kraft’s equality (2.4) holds. We are thus forced to assume that the partition function evaluated at $\overline{\beta }=\left({\beta }_1,\dots ,{\beta }_n\right)$ is finite, i.e. that

$$Z\left(\overline{\beta }\right)={\displaystyle \sum _{i\in \mathbb{A}}\text{exp}}\left(-\overline{\beta }\cdot \overline{E_i}\right)$$

(4.17)

is finite, and that $\alpha =\log Z\left(\overline{\beta }\right)$. When these conditions are fulfilled, $\kappa ={\kappa }^{\overline{\beta }}$ defined by

$${\kappa }^{\overline{\beta }}=\log Z\left(\overline{\beta }\right)+\overline{\beta }·\overline{E}$$

(4.18)

defines a cost-stable code with individual code lengths given by

$${\kappa }_i^{\overline{\beta }}=\log Z\left(\overline{\beta }\right)+\overline{\beta }·\overline{E_i}.$$

(4.19)

The matching distribution $P^{\overline{\beta }}$ is given by the point probabilities

$$P_i^{\overline{\beta }}=\frac{\exp \left(\overline{\beta }\cdot \overline{E_i}\right)}{Z\left(\overline{\beta }\right)}.$$

(4.20)

In most cases where linear models occur in the applications, one will be able to adjust the parameters in $\overline{\beta }$ such that $P^{\overline{\beta }}$ is consistent. By Corollary 4.2, the entropy maximization problem will then be solved. However, not all cases can be settled in this way as there may not exist a consistent maximum entropy distribution.

We have seen that the search for cost-stable codes led us to consider the well-known partition function and also the well-known exponential family consisting of distributions ($P^{\overline{\beta }}$) with $\overline{\beta }$ ranging over all vectors $\overline{\beta }\in {ℝ}^n$ for which $Z\left(\overline{\beta }\right)<\infty$.

From our game theoretical point of view, the family of codes (${\kappa }^{\overline{\beta }}$) with $Z\left(\overline{\beta }\right)<\infty$ has at least as striking features as the corresponding family of distributions. We shall therefore focus on both types of objects and shall call the family of matching pairs $({\kappa }^{\overline{\beta }},P^{\overline{\beta }})$ with $\overline{\beta }$ ranging over vectors with $Z\left(\overline{\beta }\right)<\infty$ for the exponential family associated with the set $\overline{E}=\left(E_1,\dots ,E_n\right)$ of functions on $\mathbb{A}$ or associated with the family of models one can define from E by choosing $\overline{\lambda }=\left({\lambda }_1,\dots ,{\lambda }_n\right)$ and considering $\mathcal{P}$ given by (4.15).

We stress that the huge literature on exponential families displays other families of discrete distributions than those that can be derived from the above definition. In spite of this we maintain the view that an information theoretical definition in terms of codes (or related objects) is more natural than the usual structural definitions. We shall not pursue this point vigorously here as it will require the consideration of further games than the simple Code Length Game.

In order to further stress the significance of the class of cost stable codes we mention a simple continuity result:

Theorem 4.3. 

If a model $\mathcal{P}$ has a cost-stable code, the entropy function H is continuous when restricted to $\mathcal{P}$.

Proof. 

Assume that 〈κ^∗, P〉 = h < ∞ for all P ∈ $\mathcal{P}$. Then H(P) + D(P‖P^∗) = h for P ∈ $\mathcal{P}$ with P^∗ the distribution matching κ^∗. As the sum of the two lower semi-contimuous functions in this identity is a constant function, each of the functions, in particular the entropy function, must be continuous.

     ☐

As we have already seen, the notion of cost-stable codes is especially well suited to handle models defined by linear constraints. In section 6 we shall take this up in more detail.

The following sections will be more technical and mathematically abstract. This appears necessary in order to give a comprehensive treatment of all basic aspects related to the Cost Length Game and to the Maximum Entropy Principle.

5 The Code Length Game, further preparations

In section 3 we introduced a minimum of concepts that enabled us to derive the useful results of section 4. With that behind us as motivation and background material, we are ready to embark on a more thorough investigation which will lead to a clarification of certain obscure points, especially related to the possibility that a consistent distribution with maximal entropy may not exist. In this section we point out certain results and concepts which will later be useful.

In view of our focus on codes it is natural to look upon divergence in a different way, as redundancy. Given is a code κ ∈ ^∼K($\mathbb{A}$) and a distribution $P\in M_{+}^1\left(\mathbb{A}\right)$. We imagine that we use κ to code letters from $\mathbb{A}$ generated by a “source” and that P is the “true” distribution of the letters. The optimal performance is, according to (3.9), represented by the entropy H(P) whereas the actual performance is represented by the number 〈κ, P〉. The difference 〈κ, P 〉 − H(P) is then taken as the redundancy. This is well defined if H(P) < ∞ and then coincides with D(P‖Q) where Q denotes the distribution matching κ. As D(P‖Q) is always well defined, we use this quantity for our technical definition: The redundancy of κ ∈ ^∼K($\mathbb{A}$) against $P\in M_{+}^1\left(\mathbb{A}\right)$ is denoted D(P‖κ) and defined by

D(P‖κ) = D(P‖Q) with κ ↔ Q.

Thus D(P‖κ) and D(P‖Q) can be used synonymously and reflect different ways of thinking. Using redundancy rather than divergence, the linking identity takes the following form:

〈κ, P 〉 = H(P) + D(P‖κ).

(5.21)

We shall often appeal to basic concavity and convexity properties. Clearly, the entropy function is concave as a minimum of affine functions, cf. (3.9). However, we need a more detailed result which also implies strict concavity. The desired result is the following identity

$$H({\displaystyle \sum _v{\alpha }_v{P}_v})={\displaystyle \sum _v{\alpha }_{v}H\left(P_v\right)}+{\displaystyle \sum _v{\alpha }_{v}H\left(P_v\left|\right|\overline{P}\right)},$$

(5.22)

where $\overline{P}={\displaystyle \sum _v{\alpha }_v{P}_v}$ is any finite or countably infinite convex combination of probability distributions. This follows by the linking identity.

A closely related identity involves divergence and states that, with notation as above and with Q denoting an arbitrary general distribution,

$${\displaystyle \sum _v{\alpha }_{v}D\left(P_v\left|\right|Q\right)}=D\left({\displaystyle \sum _v{\alpha }_v{P}_v\left|\right|Q}\right)+{\displaystyle \sum _v{\alpha }_{v}D\left(P_v\left|\right|\overline{P}\right)}.$$

(5.23)

The identity shows that divergence D(·‖Q) is strictly convex. A proof can be found in [23].

For the remainder of the section we consider a model $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$ and the associated Code Length Game.

By supp ($\mathcal{P}$) we denote the support of $\mathcal{P}$, i.e. the set of i ∈ $\mathbb{A}$ for which there exists P ∈ $\mathcal{P}$ with p_i > 0. Thus, supp ($\mathcal{P}$) = ${\cup }_{P\in \mathcal{P}}$supp (P), the union of the usual supports of all consistent distributions. Often one may restrict attention to models with full support, i.e. to models with supp $\left(\mathcal{P}\right)=\mathbb{A}$. However, we shall not make this assumption unless pointed out specifically.

Recall that distributions in $\mathcal{P}$ are said to be consistent. Often, it is more appropriate to consider distributions in ${\overline{\mathcal{P}}}^{\sigma }$. These distributions are called essentially consistent distributions. Using these distributions we relax the requirements to a distribution with maximum entropy, previously only considered for consistent distributions. Accordingly, a distribution P^∗ is called a maximum entropy distribution (H_max-distribution) if P^∗ is essentially consistent and H(P^∗) = H_max($\mathcal{P}$). We warn the reader that the usual definition in the literature insists on the requirement of consistency. Nevertheless, we find the relaxed requirement of essential consistency more adequate. For one thing, lower semi-continuity of the entropy function implies that

$$H_{\max }\left(\mathcal{P}\right)=H_{\max }({\overline{\mathcal{P}}}^{\sigma })=H_{\max }({\overline{\mathcal{P}}}^V)$$

(5.24)

and this points to the fact that the models ${\overline{\mathcal{P}}}^{\sigma }$ and ${\overline{\mathcal{P}}}^V$ behave in the same way as $\mathcal{P}$. This view is further supported by the observation that for any κ ∈ ^∼K($\mathbb{A}$),

$$R\left(\kappa |\mathcal{P}\right)=R\left(\kappa |{\overline{\text{co}}}^V\mathcal{P}\right).$$

(5.25)

This follows as the map P ↷ 〈κ, P〉 is lower semi-continuous and affine. As a consequence,

$$R_{\min }\left(\mathcal{P}\right)=R_{\min }\left({\overline{\text{co}}}^V\right).$$

(5.26)

It follows that all models with $\mathcal{P}\subseteq {\mathcal{P}}^{\prime }\subseteq {\overline{\mathcal{P}}}^V$ behave similarly as far as the Code Length Game is concerned. The reason why we do not relax further the requirement of a H_max-distribution from $P*\in {\overline{\mathcal{P}}}^{\sigma }$ to $P*\in {\overline{\mathcal{P}}}^V$ is firstly, that we hold the information topology for more relevant for our investigations than the usual topology. Secondly, we shall see that the property $P*\in {\overline{\mathcal{P}}}^{\sigma }$ whichis stronger than $P*\in {\overline{\mathcal{P}}}^V$ can in fact be verified in the situations we have in mind (see Theorem 6.2).

The fact that a consistent H_max-distribution may not exist leads to further important notions. Firstly, a sequence (P_n)_n≥1 of distributions is said to be asymptotically optimal if all the P_n are consistent and if H(P_n) → H_max($\mathcal{P}$) for n → ∞. And, secondly, a distribution P^∗ is the maximum entropy attractor (H_max-attractor) if P^∗ is essentially consistent and if $P_n\stackrel{D}{\to }P*$ for every asymptotically optimal sequence (P_n)_n≥1.

As an example, consider the (uninteresting!) model of all deterministic distributions. For this model, the H_max-attractor does not exist and there is no unique H_max-distribution. For more sensible models, the H_max-attractor P^∗ will exist, but it may not be the H_max-distribution as lower semi-continuity only quarantees the inequality H(P^∗) ≤ H_max($\mathcal{P}$), not the corresponding equality.

Having by now refined the concepts related to the distribution side of the Code Length Game, we turn to the coding side.

It turns out that we need a localized variant of the risk associated with certain codes. The codes we shall consider are, intuitively, all codes which the observer (Player II) off-hand finds it worth while to consider. If P ∈ $\mathcal{P}$ is the “true” distribution, and the observer knows this, he will choose the code adapted to P in order to minimize the average code length. As nature (Player I) could from time to time change the choice of P ∈ $\mathcal{P}$, essentially any strategy in the closure of $\mathcal{P}$ could be approached. With these remarks in mind we find it natural for the observer only to consider ${\overline{\mathcal{P}}}^{D\sigma }$-adapted codes in the search for reasonable strategies.

Assume now that the observer decides to choose a ${\overline{\mathcal{P}}}^{D\sigma }$-adapted code κ. Let P ∈ ${\overline{\mathcal{P}}}^{D\sigma }$ be the distribution which matches κ. Imagine that the choice of κ is dictated by a strong belief that the true distribution is P or some distribution very close to P (in the information topology!). Then the observer can evaluate the associated risk by calculating the localized risk associated with κ which is defined by the equation:

$$R_{\mathrm{loc}}\left(\kappa |\mathcal{P}\right)=\underset{\left(P_n\right)\subseteq \mathcal{P},P_n\stackrel{D}{\to }P}{\sup }\underset{n\to \infty }{\lim \sup }\langle \kappa ,P_n\rangle ,$$

(5.27)

where the supremum is over the class of all sequences of consistent distributions which converge in the information topology to P. Note that we insist on a definition which operates with sequences.

Clearly, the normal “global” risk must be at least as large as localized risk, therefore, for any ${\overline{\mathcal{P}}}^{D\sigma }$-adapted code,

R_loc(κ|$𝒫$) ≤ R(κ|$𝒫$) .

(5.28)

A further and quite important inequality is the following:

R_loc(κ|$𝒫$) ≤ H_max($𝒫$).

(5.29)

This inequality is easily derived from the defining relation (5.27) by writing 〈κ, P_n〉 in the form H(P_n) + D(P_n‖P) with κ ↔ P, noting also that $P_n\stackrel{D}{\to }P$ implies that D(Pn ‖P) → 0. We note that had we allowed nets in the defining relation (5.27), a different and sometimes strictly larger quantity would result and (5.29) would not necessarily hold.

As the last preparatory result, we establish pretty obvious properties of an eventual optimal strategy for the observer, i.e. of an eventual R_min-code.

Lemma 5.1.  

Let $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$ with R_min ($\mathcal{P}$) < ∞ be given. Then the R_min-code is unique and if it exists, say R(κ^∗|$\mathcal{P}$) = R_min($\mathcal{P}$), then κ^∗ is compact with supp (κ^∗) = supp ($\mathcal{P}$).

Proof. 

Assume that κ^∗∈ ^∼K($\mathbb{A}$) is a R_min-code. As R(κ^∗|$\mathcal{P}$) < ∞, supp ($\mathcal{P}$) ⊆ supp (κ^∗). Then consider an a₀ ∈ supp (κ^∗) and assume, for the purpose of an indirect proof, that a₀ ∈ $\mathbb{A}$\supp ($\mathcal{P}$). Then the code κ obtained from κ^∗ by putting κ(a₀) = ∞ and keeping all other values fixed, is a general non-compact code which is not identically +∞. Therefore, there exists ε > 0 such that κ − ε is a compact code. For any P ∈ $\mathcal{P}$, we use the fact that a₀ ∉ supp (P)) to conclude that 〈κ − ε, P 〉 = 〈κ^∗ − ε, P〉, hence R(κ − ε|$\mathcal{P}$) = R(κ^∗|$\mathcal{P}$) − ε, contradicting the minimality property of κ^∗. Thus we conclude that supp (κ^∗) = supp ($\mathcal{P}$). Similarly, it is clear that κ^∗ must be compact – since otherwise, κ^∗− ε would be more efficient than κ^∗ for some ε > 0.

In order to prove uniqueness, assume that both κ₁ and κ₂ are R_min-codes for $\mathcal{P}$. If we assume that κ₁ ≠ κ₂, then κ₁(a) ≠ κ₂(a) holds for some a in the common support of the codes κ₁ and κ₂ and then, by the geometric/arithmetic inequality, we see that $\frac{1}{2}\left({\kappa }_1+{\kappa }_2\right)$ is a general non-compact code. For some ε > 0, $\frac{1}{2}\left({\kappa }_1+{\kappa }_2\right)$ − ε will then also be a code and as this code is seen to be more efficient than κ₁ and κ₂, we have arrived at a contradiction. Thus κ₁ = κ₂, proving the uniqueness assertion. ☐

6 Models in equilibrium

Let $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$. By definition the requirement of equilibrium is one which involves the relationship between both sides of the Code Length Game. The main result of this section shows that the requirement can be expressed in terms involving only one of the sides of the game, either distributions or codes.

Theorem 6.1 (conditions for equilibrium). 

Let $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$ be a model and assume that H_max($\mathcal{P}$) < ∞. Then the following conditions are equivalent:

(i) 

$\mathcal{P}$ is in equilibrium,

(ii) 

H_max(co $\mathcal{P}$) = H_max($\mathcal{P}$),

(iii) 

there exists a${\overline{\mathcal{P}}}^D$-adapted code κ^∗ such that

R(κ^∗|$𝒫$) = R_loc(κ^∗|$𝒫$).

Proof. 

(i) ⇒ (iii): Here we assume that H_max($P$) = R_min($\mathcal{P}$). In particular, R_min($\mathcal{P}$) < ∞. As the map κ ↷R(κ|$\mathcal{P}$) is lower semi-continuous on ^∼K($\mathbb{A}$) (as the supremum of the maps κ ↷ 〈κ, $\mathcal{P}$〉; P ∈ $\mathcal{P}$), and as ^∼K($\mathbb{A}$) is compact, the minimum of κ ↷ R(κ|$\mathcal{P}$) is attained. Thus, there exists κ^∗ ∈ ^∼K($\mathbb{A}$) such that R(κ^∗|$\mathcal{P}$) = R_min($\mathcal{P}$). As observed in Lemma 5.1, κ^∗ is a compact code and κ^∗ is the unique R_min-code.

For P ∈ $\mathcal{P}$,

H(P) + D(P‖κ^∗) = 〈κ^∗, P〉 ≤ R_min($𝒫$) = H_max($𝒫$) .

It follows that D(P_n‖κ^∗) → 0 for any asymptotically optimal sequence (P_n)_n≥1. In other words, the distribution $P*\in M_{+}^1\left(\mathbb{A}\right)$ which matches κ^∗ is the H_max- attractor of the model.

We can now consider any asymptotically optimal sequence (P_n)_n≥1 in order to conclude that

By (5.28), the assertion of (iii) follows.

(iii) ⇒ (ii): Assuming that (iii) holds, we find from (5.25), (3.13) and (5.29) that

and the equality of (ii) must hold.

(ii) ⇒ (i): For this part of the proof we fix a specific asymptotically optimal sequence (P_n)_n≥1 ⊆ $\mathcal{P}$. We assume that (ii) holds. For each n and m we observe that by (5.22) and (2.7), with $M=\frac{1}{2}\left(P_n+P_m\right)$

It follows that (P_n)_n≥1 is a Cauchy sequence with respect to total variation, hence there exists $P*\in M_{+}^1\left(\mathbb{A}\right)$ such that $P_n\stackrel{V}{\to }P*$.

Let κ^∗ be the code adapted to P^∗. In order to evaluate R(κ^∗|$\mathcal{P}$) we consider any P ∈ $\mathcal{P}$. For a suitable sequence (ε_n)_n≥1 of positive numbers converging to zero, we consider the sequence (Q_n)_n≥1 ⊆ $\mathcal{P}$ given by

$$Q_n=\left(1-{\epsilon }_n\right)P_n+{\epsilon }_n{P}_n ;n\ge 1.$$

By (5.22) we find that

H_max($𝒫$) = H_max(co $𝒫$) ≥ H(Q_n) ≥ (1 − ε_n)H(P_n) + ε_nH(P) + ε_nD(P‖Q_n),

hence

$$H\left(P\right)+D\left(P\left|\right|Q_n\right)\le H\left(P_n\right)+\frac{1}{{\epsilon }_n}\left(H_{\max }\left(\mathcal{P}\right)-H\left(P_n\right)\right).$$

As Q ↷ D(P‖Q) is lower semi-continuous, we conclude from this that

$$H\left(P\right)+D\left(P\left|\right|P*\right)\le H_{\max }\left(\mathcal{P}\right)+\underset{n\to \infty }{\text{lim inf}}\left(H_{\max }\left(\mathcal{P}\right)-H\left(P_n\right)\right).$$

Choosing the ε_n’s appropriately, e.g. ${\epsilon }_n={\left(H_{\max }\left(\mathcal{P}\right)-H\left(P_n\right)\right)}^{\frac{1}{2}}$, it follows that H(P)+D(P‖P^∗) ≤H_max($\mathcal{P}$), i.e. that 〈κ^∗, P〉 ≤ H_max($\mathcal{P}$). As this holds for all P ∈ $\mathcal{P}$, R(κ^∗|$\mathcal{P}$) ≤ H_max($\mathcal{P}$) follows. Thus R_min($\mathcal{P}$) ≤ H_max($\mathcal{P}$), hence equality must hold here, and we have proved that $\mathcal{P}$ is in equilibrium, as desired.

It is now easy to derive the basic properties which hold for a system in equilibrium.

Theorem 6.2 (models in equilibrium). 

Assume that $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$ is a model in equilibrium. Then the following properties hold:

(i) 

There exists a unique H_max-attractor and for this distribution, say P^∗, the inequality

R_min($𝒫$) + D(P^∗‖κ) ≤ R(κ|$𝒫$)

(6.30)

holds for all κ ∈ ^∼K($\mathbb{A}$).

(ii) 

There exists a unique R_min-code and for this code, say κ^∗, the inequality

H(P) + D(P‖κ^∗) ≤ H_max($𝒫$)

(6.31)

holds for every P ∈ $\mathcal{P}$, even for every $P\in {\overline{\text{co}}}^V\mathcal{P}$ . The R_min-code is compact.

Proof. 

The existence of the R_min-code was established by the compactness argument in the beginning of the proof of Theorem 6.1. The inequality (6.31) for P ∈ $\mathcal{P}$ is nothing but an equivalent form of the inequality R(κ^∗|$\mathcal{P}$) ≤ H_max($\mathcal{P}$) and this inequality immediately implies that the distribution P^∗ matching κ^∗ is the H_max-attractor. The extension of the validity of (6.31) to $P\in {\overline{\text{co}}}^V\mathcal{P}$ follows from (5.26).

To prove (6.30), let (P_n)_n≥1 ⊆ $\mathcal{P}$ be asymptotically optimal. Then

which is the desired conclusion as H_max($\mathcal{P}$) = R_min($\mathcal{P}$). ☐

If $\mathcal{P}$ is a model in equilibrium, we refer to the pair (κ^∗, P^∗) from Theorem 6.2 as the optimal matching pair pair. Thus κ^∗ denotes the R_min-code and P^∗ the H_max-attractor.

Combining Theorem 6.2 and Theorem 6.1 we realize that, unless R(κ|$\mathcal{P}$) = ∞ for every κ ∈^∼K($\mathbb{A}$), there exists a unique R_min-code. The matching distribution is the H_max-attractor for the model co ($\mathcal{P}$). We also note that simple examples (even with $\mathbb{A}$ a two-element set) show that $\mathcal{P}$ may have a H_max-attractor without $\mathcal{P}$ being in equilibrium and this attractor may be far away from the H_max-attractor for co ($\mathcal{P}$).

Corollary 6.3. 

For a model $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$ in equilibrium, the R_min-code and the H_max-attractor form a matching pair: κ^∗ ↔ P^∗, and for any matching pair (κ, P) with $P\in {\overline{\text{co}}}^V\mathcal{P}$,

$$V\left(P,P*\right)\le {\left(R\left(\kappa |\mathcal{P}\right)-H\left(P\right)\right)}^{\frac{1}{2}}.$$

Proof. 

Combining (6.30) with (6.31) it folows that for κ ↔P with $P\in {\overline{\text{co}}}^V\mathcal{P}$,

D(P‖P^∗) + D(P^∗‖P) ≤ R(κ|$𝒫$) − H(P)

and the result follows from Pinskers inequality, (2.7). ☐

Corollary 6.3 may help us to judge the approximate position of the H_max-attractor P^∗ even without knowing the value of H_max($\mathcal{P}$). Note also that the proof gave the more precise bound J (P, P^∗) ≤ R(κ|$\mathcal{P}$) − H(P) with assumptions as in the theorem and with J (·, ·) denoting Jeffrey’s measure of discrimination, cf. [3] or [16].

Corollary 6.4. 

Assume that the model $\mathcal{P}$ has a cost-stable code κ^∗ and let P^∗ be the matching distribution. Then $\mathcal{P}$ is in equilibrium and has (κ^∗, P^∗) as optimal matching pair if and only if P^∗ is essentially consistent.

Proof. 

By definition an H_max-attractor is essentially consistent. Therefore, the necessity of the condition $P*\in {\overline{\mathcal{P}}}^{D\sigma }$ is trivial. For the proof of sufficiency, assume that 〈κ^∗, P〉 = h for all P ∈ $\mathcal{P}$ with h a finite constant. Clearly then, H_max($\mathcal{P}$) ≤ h. Now, let (P_n)_n≥1 be a sequence of consistent distributions with $P_n\stackrel{D}{\to }P$. By the linking identity, H(P_n) + D(P_n‖P^∗) = h for all n, and we see that H_max($\mathcal{P}$) ≥ h. Thus H_max($\mathcal{P}$) = h and (P_n) is asymptotically optimal. By Theorem 6.2, the sequence converges in the information topology to the H_max-attractor which must then be P^∗. The result follows.     ☐

Note that this result is a natural further development of Corollary 4.2.

Corollary 6.5. 

Assume that $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$ is a model in equilibrium. Then all models ${\mathcal{P}}^{\prime }$ with $\mathcal{P}\subseteq {\mathcal{P}}^{\prime }\subseteq {\overline{\text{co}}}^V\mathcal{P}$ are in equilibrium too and they all have the same optimal matching pair.

Proof. 

If $\mathcal{P}\subseteq {\mathcal{P}}^{\prime }\subseteq {\overline{\text{co}}}^V\mathcal{P}$ then

$$H_{\max }\left(\text{co} {\mathcal{P}}^{\prime }\right)\le H_{\max }\left({\overline{\text{co}}}^V\mathcal{P}\right)=H_{\max }\left(\text{co} \mathcal{P}\right)=H_{\max }\left(\mathcal{P}\right)\le H_{\max }\left(P^{\prime }\right)$$

and we see that ${\mathcal{P}}^{\prime }$ is in equilibrium. As an asymptotically optimal sequence for $\mathcal{P}$ is also asymp- totically optimal for ${\mathcal{P}}^{\prime }$, it follows that ${\mathcal{P}}^{\prime }$ has the same H_max-attractor, hence also the same optimal matching pair, as $\mathcal{P}$.

Another corollary is the following result which can be used as a basis for proving certain limit theorems, cf. [22].

Corollary 6.6. 

Let ${\left(\mathbb{A},P_n\right)}_{n\ge 1}$ be a sequence of models and assume that they are all in equilibrium with ${\sup }_{n\ge 1}{H}_{\max }\left({\mathcal{P}}_n\right)<\infty$ and that they are nested in the sense that $co\left({\mathcal{P}}_1\right)\subseteq co\left({\mathcal{P}}_2\right)\subseteq \cdots$. Let there further be given a model $\mathcal{P}$ such that

$$\bigcup _{n\ge 1}{\mathcal{P}}_n\subseteq \mathcal{P}\subseteq {\overline{\text{co}}}^V(\bigcup _{n\ge 1}{\mathcal{P}}_n).$$

Then $\mathcal{P}$ is in equilibrium too, and the sequence of H_max-attractors of the${\mathcal{P}}_n$ ’s converges in diver-gence to the H_max-attractor of $\mathcal{P}$.

Clearly, the corollaries are related and we leave it to the reader to extend the argument in the proof of Corollary 6.5 so that it also covers the case of Corollary 6.6.

We end this section by developing some results on models given by linear conditions, thereby continuing the preliminary results from section 1 and section 4. We start with a general result which uses the following notion: A distribution P^∗ is algebraically inner in the model $\mathcal{P}$ if, for every P ∈ $\mathcal{P}$ there exists Q ∈ $\mathcal{P}$ such that P^∗ is a convex combination of P and Q.

Lemma 6.7. 

If the model $P$ is in equilibrium and has a H_max-distribution P^∗ which is algebraically inner in $\mathcal{P}$, then P^∗ is cost-stable.

Proof. 

Let κ^∗ be the code adapted to P^∗. To any P ∈ $\mathcal{P}$ we determine Q ∈ $\mathcal{P}$ such that P^∗ is a convex combination of these two distributions. Then, as 〈κ^∗, P〉 ≤ H_max($\mathcal{P}$) and 〈κ^∗, Q〉 ≤ H_max($\mathcal{P}$) and as a convex combination gives 〈κ^∗, P^∗〉 ≤ H_max($\mathcal{P}$) we must conclude that 〈κ^∗, P〉 = 〈κ^∗, Q〉 since 〈κ^∗, P^∗〉 is in fact equal to H_max($\mathcal{P}$). Therefore, κ^∗ is cost-stable.

Theorem 6.8. 

If the alphabet $\mathbb{A}$ is finite and the model $\mathcal{P}$ affine, then the model is in equilibrium and the R_min-code is cost-stable.

Proof. 

We may assume that $\mathcal{P}$ is closed. By Theorem 6.1, the model is in equilibrium and by continuity of the entropy function, the H_max-attractor is a H_max-distribution. For the R_min-code κ^∗, supp (P^∗) = supp ($\mathcal{P}$) by Lemma 5.1. As $\mathbb{A}$ is finite we can then conclude that P^∗ is algebraically inner and Lemma 6.7 applies. ☐

We can now prove the following result:

Theorem 6.9. 

Let $\mathcal{P}$ be a non-empty model given by finitely many linear constraints as in (4.15):

$$\mathcal{P}=\left\{P\in M_{+}^1\left(\mathbb{A}\right)|\langle E_1,P\rangle ={\lambda }_1,\dots ,\langle E_n,P\rangle ={\lambda }_n\right\}.$$

Assume that the functions E₁, ⋯ , E_n, 1 are linearly independent and that H_max($\mathcal{P}$) < ∞. Then the model is in equilibrium and the optimal matching pair (κ^∗, P^∗) belongs to the exponential family defined by (4.18) and (4.20). In particular, κ^∗ is cost-stable.

Proof. 

The model is in equilibrium by Theorem 6.1. Let (κ^∗, P ^∗) be the corresponding optimal matching pair. If $\mathbb{A}$ is finite the result follows by Theorem 6.8 and some standard linear algebra.

Assume now that $\mathbb{A}$ is infinite Choose an asymptotically optimal sequence (P_n)_n≥1. Let ${\mathbb{A}}_0$ be a finite subset of $\mathbb{A}$, chosen sufficiently large (see below), and denote by ${\mathcal{P}}_n$ the convex model of all P ∈ $\mathcal{P}$ for which p_i = P_n,i for all $i\in \mathbb{A}{\mathbb{A}}_0$. Let $P_n^{*}$ be the H_max-attractor for $𝒫$_n and ${\kappa }_n^{*}$ the adapted code. Then this code is cost-stable for $𝒫$_n and of the form

$${\kappa }_{n,i}^{*}={\alpha }_n+{\displaystyle \sum _{v=1}^n{\beta }_{n,v}}\cdot E_v\left(i\right);i\in {\mathbb{A}}_0.$$

If the set ${\mathbb{A}}_0$ is sufficiently large, the constants appearing here are uniquely determined. We find that ${\left(P_n^{*}\right)}_{n\ge 1}$ is asymptotically optimal for $\mathcal{P}$, and therefore,$P_n^{*}\stackrel{D}{\to }{P}^{*}$. It follows that the constants β_n,ν and α_n converge to some constants β_ν and α and that

$${\kappa }_i^{*}=\alpha +{\displaystyle \sum _{v=1}^n{\beta }_v}\cdot E_v\left(i\right);i\in {\mathbb{A}}_0$$

As ${\mathbb{A}}_0$ can be chosen arbitrarily large, the constants α and β_ν must be independent of ${\mathbb{A}}_0$ with i ∈ ${\mathbb{A}}_0$ and the above equation must hold for all i ∈ $\mathbb{A}$.   ☐

Remark. 

Extensions of the result just proved may well be possible, but care has to be taken. For instance, if we consider models obtained by infinitely many linear constraints, the result does not hold. As a simple instance of this, the reader may consider the case where the model is a “line” , viz. the affine hull generated by the two distributions P, Q on $\mathbb{A}=\mathbb{N}$ given by p_i = 2⁻ⁱ; i ≥ 1 and q_i = (ζ(3) i³)⁻¹; i ≥ 1. This model is in equilibrium with P as H_max-distribution, but the adapted code is not cost-stable. These facts can be established quite easily via the results quoted in the footnote following the proof of Theorem 4.1.

7 Entropy-continuous models

In the sequel we shall only discuss models in equilibrium. Such models can be quite different regarding the behaviour of the entropy function near the maximum. We start with a simple observation.

Lemma 7.1. 

If $\mathcal{P}$ is in equilibrium and the H_max-value H_max($\mathcal{P}$) is attained on ${\overline{\mathcal{P}}}^V$, it is only attained for the H_max-attractor.

Proof. 

Assume that $P\in {\overline{\mathcal{P}}}^V$ and that H(P) = H_max($\mathcal{P}$). Choose a sequence (P_n)_n≥1 ⊆ $\mathcal{P}$ which converges to P in total variation. By lower semi-continuity and as H(P) = H_max($\mathcal{P}$) we see that (P_n) is asymptotically optimal. Therefore, for the H_max-attractor P^∗, $P_n\stackrel{D}{\to }P*$, hence also $P_n\stackrel{V}{\to }P*$ . It follows that P = P^∗.

Lemma 7.2. 

For a model $\mathcal{P}$ in equilibrium and with H_max-attractor P^∗ the following conditions are equivalent:

(i) 

$H:{\overline{\mathcal{P}}}^V\to {\mathbb{R}}_{+}$ is continuous at P^∗ in the topology of total variation,

(ii) 

$H:{\overline{\mathcal{P}}}^{\sigma }\to {\mathbb{R}}_{+}$ is sequentially continuous at P^∗ in the information topology,

(iii) 

H(P^∗) = H_max($𝒫$).

Proof. 

Clearly, (i) implies (ii).

Assume that (ii) holds and let (P_n)_n≥1⊆ $\mathcal{P}$ be asymptotically optimal. Then $P_n\stackrel{D}{\to }P*$. By assumption, H(P_n) → H(P^∗) and (iii) follows since H(P_n) → H_max($\mathcal{P}$) also holds.

Finally, assume that (iii) holds and let ${\left(P_n\right)}_{n\ge 1}\subseteq {\overline{\mathcal{P}}}^V$ satisfy $P_n\stackrel{V}{\to }P*$. By lower semi-continuity,

$$H_{\max }\left(\mathcal{P}\right)=H\left(P*\right)\le \underset{n\to \infty }{\lim \inf } H\left(P_n\right)\le \underset{n\to \infty }{\text{lim sup}} H\left(P_n\right)\le H_{\max }({\overline{\mathcal{P}}}^V)=H_{\max }\left(\mathcal{P}\right)$$

and H(P_n) → H(P^∗) follows. Thus (i) holds.

A model $\mathcal{P}$ in equilibrium is entropy-continuous if H(P^∗) = H_max($\mathcal{P}$) with P^∗ the H_max-attractor. In the opposite case we say that there is an entropy loss.

We now discuss entropy-continuous models. As we shall see, the previously introduced notion of Nash equilibrium code, cf. Section 4, is of central importance in this connection. We need this concept for any ${\overline{\mathcal{P}}}^{D\sigma }$-adapted code. Thus, by definition a code κ^∗ is a Nash equilibrium code if κ^∗ is ${\overline{\mathcal{P}}}^{D\sigma }$-adapted and if

R(κ^∗|$𝒫$) ≤ H(P^∗) < ∞ .

(7.32)

We stress that the definition is used for any model $\mathcal{P}$ (whether or not it is known beforehand that the model is in equilibrium). We shall see below that a Nash equilibrium code is unique.

Theorem 7.3 (entropy-continuous models).  

Let $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$ be a model. The following conditions are equivalent:

(i) 

$\mathcal{P}$ is in equilibrium and entropy-continuous,

(ii) 

$\mathcal{P}$ is in equilibrium and has a maximum entropy distribution,

(iii) 

$\mathcal{P}$ has a Nash equilibrium code.

If these conditions are fulfilled, the H_max-distribution is unique and coincides with the H_max-attractor. Likewise, the Nash equilibrium code is unique and it coincides with the R_min-code.

Proof. 

(i) ⇒ (ii): This is clear since, assuming that (i) holds, the H_max-attractor must be a H_max-distribution.

(ii) ⇒ (iii): Assume that $\mathcal{P}$ is in equilibrium and that $P_0\in {\overline{\mathcal{P}}}^{D\sigma }$ is a H_max-distribution. Let (κ^∗, P^∗) be the optimal matching pair pair. Applying Theorem 6.2, (6.31) with P = P₀, we conclude that D(P₀ ‖P^∗) = 0, hence P₀ = P^∗. Then we find that

R(κ^∗|$𝒫$) = R_min($𝒫$) = H_max($𝒫$) = H(P₀) = H(P^∗)

and we see that κ^∗ is a Nash equilibrium code.

(iii) ⇒ (i): If κ^∗ is a Nash equilibrium code for $\mathcal{P}$, then

R_min($𝒫$) ≤ R(κ^∗|$𝒫$) ≤ H(P^∗) ≤ H_max($𝒫$) ≤ R_min($𝒫$)

and we conclude that $\mathcal{P}$ is in equilibrium and that κ^∗ is the minimum risk code.

In establishing the equivalence of (i)–(iii) we also established the uniqueness assertions claimed. ☐

The theorem generalizes the previous result, Theorem 4.1. We refer to section 4 for results which point to the great applicability of results like Theorem 7.3.

8 Loss of entropy

We shall study a model $\mathcal{P}$ in equilibrium. By previous results we realize that for many purposes we may assume that $\mathcal{P}$ is a closed, convex subset of $M_{+}^1\left(\mathbb{A}\right)$ with H_max($\mathcal{P}$) < ∞. Henceforth, these assumptions are in force.

Denote by (κ^∗, P^∗) the optimal matching pair associated with $\mathcal{P}$. By the disection of $\mathcal{P}$ we understand the decomposition of $\mathcal{P}$ consisting of all non-empty sets of the form

$${\mathcal{P}}_x=\left\{P\in \mathcal{P}|\langle \kappa *,P\rangle =x\right\}.$$

Let ∆ denote the set of $x\in \mathbb{R}$ with ${\mathcal{P}}_x\ne \varnothing$. As R(κ^∗|$\mathcal{P}$) = R_min($\mathcal{P}$) = H_max($\mathcal{P}$), and as $\mathcal{P}$ is convex with P^∗ ∈ $\mathcal{P}$, ∆ is a subinterval of [0; H_max($\mathcal{P}$)] which contains the interval [H(P^∗), H_max($\mathcal{P}$)[.

Clearly, κ^∗ is a cost-stable code for all models ${\mathcal{P}}_x$; x ∈ ∆. Hence, by Theorem 4.3 the entropy function is continuous on each of the sets ${\mathcal{P}}_x$; x ∈ ∆.

Each set ${\mathcal{P}}_x$; x ∈ ∆ is a sub-model of $\mathcal{P}$ and as each ${\mathcal{P}}_x$ is convex with H_max(${\mathcal{P}}_x$) < ∞, these sub-models are all in equilibrium. The linking identity shows that for all P ∈ ${\mathcal{P}}_x$,

H(P) + D(P‖P^∗) = x .

(8.34)

This implies that H_max(${\mathcal{P}}_x$) ≤ x, a sharpening of the trivial inequality H_max(${\mathcal{P}}_x$) ≤ H_max($\mathcal{P}$). From (8.34) it also follows that maximizing entropy H(·) over ${\mathcal{P}}_x$ amounts to the same thing as minimizing divergence D(·‖P^∗) over ${\mathcal{P}}_x$. In other words, the H_max-attractor of ${\mathcal{P}}_x$ may, alterna-tively, be characterized as the I-projection of P^∗ on ${\mathcal{P}}_x$, i.e. as the unique distribution $P_x$ for which $Q_n\stackrel{D}{\to }{P}_x$ for every sequence (Q_n) ⊆ ${\mathcal{P}}_x$ for which D(Q_n‖P^∗) converges to the infimum of D(Q‖P^∗) with Q ∈ ${\mathcal{P}}_x$.*

Further basic results are collected below:

Theorem 8.1 (disection of models). 

Let $\mathcal{P}$ be a convex model in equilibrium with optimal matching pair (κ^∗, P^∗) and assume that P^∗ ∈ $\mathcal{P}$. Then the following properties hold for the disection ${\left({\mathcal{P}}_x\right)}_{x\in \Delta }$ defined by (8.33):

(i) 

The set ∆ is an interval with sup ∆ = H_max($\mathcal{P}$). A necessary and sufficient condition that H_max($\mathcal{P}$) ∈ ∆ is that $\mathcal{P}$ is entropy-continuous. If $\mathcal{P}$ has entropy loss, ∆ contains the non-degenerate interval [H(P^∗), H_max($\mathcal{P}$)[.

(ii) 

The entropy function is continuous on each sub-model ${\mathcal{P}}_x$; x ∈ ∆,

(iii) 

Each sub-model ${\mathcal{P}}_x$; x ∈ ∆ is in equilibrium and the H_max-attractor for $𝒫$_x is the I-projection of P^∗ on ${\mathcal{P}}_x$,

(iv) 

For x ∈ ∆, H_max(${\mathcal{P}}_x$) ≤ x and the following bi-implications hold, where $P_x^{*}$ denotes the H_max-attractor of ${\mathcal{P}}_x$:

$$H_{\max }\left({\mathcal{P}}_x\right)=x\iff P_x^{*}=P^{*}\iff x\ge H\left(P^{*}\right).$$

(8.35)

Proof. 

(i)–(ii) as well as the inequality H_max(${\mathcal{P}}_x$) ≤ x of (iii) were proved above.

For the proof of (iv) we consider an x ∈ ∆ and let $\left(P_n\right)\subseteq {\mathcal{P}}_x$ be an asymptotically optimal sequence for ${\mathcal{P}}_x$. Then the condition H_max(${\mathcal{P}}_x$) = x is equivalent with the condition H(P_n) → x, and the condition $P_x^{*}$ = P^∗ is equivalent with the condition$P_n\stackrel{D}{\to }{P}^{*}$. In view of the equality x = H(_n)+ D(P_n‖P^∗) we now realize that the first bi-implication of (8.35) holds. For the second bi-implication we first remark that as x ≥ H($P_x^{*}$) holds generally, if $P_x^{*}=P^{*}$ then x ≥ H(P^∗) must hold.

For the final part of the proof of (iv), we assume that x ≥ H(P^∗). The equality H_max(${\mathcal{P}}_x$) = x is evident if x = H(P^∗). We may therefore assume that H(P^∗) < x < H_max($\mathcal{P}$). We now let (P_n) denote an asymptotically optimal sequence for the full model $\mathcal{P}$ such that H(P_n) ≥ x; n ≥ 1. As 〈κ^∗, P^∗〉 ≤ x ≤ 〈κ^∗, P_n〉 for all n, we can find a sequence (Q_n)_n≥1 of distributions in P_x such that each Q_n is a convex combination of the form Q_n = α_nP^∗ + β_nP_n. By (5.23), D(Q_n‖P^∗) ≤ β_nD(P_n‖P^∗) → 0. Thus P^∗ is essentially consistent for ${\mathcal{P}}_x$ and as the code adapted to P^∗ is cost-stable for this model, Corollary 6.4 implies that the model has P^∗ as its H_max-attractor.     ☐

A distribution P^∗ is said to have potential entropy loss if the distribution is the H_max-attractor of a model in equilibrium with entropy loss. As we shall see, this amounts to a very special behaviour of the point probabilities. The definition we need at this point we first formulate quite generally for an arbitrary distribution P . With P we consider the density function Ω associated with the adapted code, cf. the appendix. In terms of P this function is given by:

$$\Omega \left(t\right)=\#\left\{i\in \mathbb{A}|p_i\ge \exp \left(-t\right)\right\}$$

(8.36)

(# = “number of elements in”). We can now define a hyperbolic distribution as a distribution P such that

$$\underset{t\to \infty }{\lim \sup }\frac{\log \Omega \left(t\right)}{t}=1.$$

(8.37)

Clearly, Ω(t) ≤ exp(t) for each t so that the equality in the defining relation may just as well be replaced by the inequality “≥” .

We note that zero point probabilities do not really enter into the definition, therefore we may assume without any essential loss of generality that all point probabilities are positive. And then, we may as well assume that the point probabilities are ordered: $p_1^{*}\ge p_2^{*}\ge \cdots$. In this case, it is easy to see that (8.37) is equivalent with the requirement

$$\underset{i\to \infty }{\lim \inf }\frac{\log p_i^{*}}{\log \frac{1}{i}}=1.$$

(8.38)

In the sequel we shall typically work with distributions which are ordered in the above sense. The terminology regarding hyperbolic distributions is inspired by [19] but goes back further, cf. [24]. In these references the reader will find remarks and results pertaining to this and related types of distributions and their discovery from empirical studies which we will also comment on in the next section.

We note that in (8.38) the inequality “≤” is trivial as $p_i\le \frac{1}{i}$ for every $i\in \mathbb{A}$. Therefore, in more detail, a distribution with ordered point probabilities is hyperbolic if and only if, for every a > 1,

$$p_i^{*}\ge \frac{1}{i^a}$$

(8.39)

for infinitely many indices.

Theorem 8.2. 

Every distribution with infinite entropy is hyperbolic.

Proof. 

Assume that P is not hyperbolic and that the point probabilities are ordered. Then there exists a > 1 such that p_i ≥ i^−a for all sufficiently large i. As the distribution with point probabilities equal to i^−a, properly normalized, has finite entropy, the result follows. ☐

With every model $\mathcal{P}$ in equilibrium we associate a partition function and an exponential family, simply by considering the corresponding objects associated with the R_min-code for the model in question. This then follows the definition given in Section 4, but for the simple case where there is only one “energy function” with the R_min-code playing the role of the energy function.

Theorem 8.3 (maximal models). 

Let $\mathcal{P}\subseteq M_{+}^1\left(\mathbb{A}\right)$ be given and assume that there exists a model ${\mathcal{P}}^{\prime }$ such that ${\mathcal{P}}^{\prime }\supseteq \mathcal{P}$ , ${\mathcal{P}}^{\prime }$ is in equilibrium and H_max(${\mathcal{P}}^{\prime }$) = H_max($\mathcal{P}$). Then $𝒫$ itself must be in equilibrium. Furthermore, there exists a largest model ${\mathcal{P}}_{\max }$ with the stated properties, namely the model

$${\mathcal{P}}_{\max }=\left\{P\in M_{+}^1\left(\mathbb{A}\right)|\langle {\kappa }^{*},P\rangle \le H_{\max }\left(\mathcal{P}\right)\right\},$$

(8.40)

where κ^∗ denotes the minimum risk code of $\mathcal{P}$. Finally, any model ${\mathcal{P}}^{\prime }$ with $\mathcal{P}\subseteq {\mathcal{P}}^{\prime }\subseteq {\mathcal{P}}_{\max }$ is in equilibrium and has the same optimal matching pair as $\mathcal{P}$.

Proof. 

Choose ${\mathcal{P}}^{\prime }$ with the stated properties. By Theorem 6.1,

$$H_{\max }\left(\text{co} \mathcal{P}\right)\le H_{\max }\left(\text{co} {\mathcal{P}}^{\prime }\right)=H_{\max }\left({\mathcal{P}}^{\prime }\right)=H_{\max }\left(\mathcal{P}\right),$$

hence $\mathcal{P}$ is in equilibrium. Let κ^∗ be the R_min-code of $\mathcal{P}$ in accordance with Theorem 6.2 and consider ${\mathcal{P}}_{\max }$ defined by (8.40).

Now let ${\mathcal{P}}^{\prime }\supseteq \mathcal{P}$ be an equilibrium model with $H_{\max }\left({\mathcal{P}}^{\prime }\right)=H_{\max }\left(\mathcal{P}\right)$. As an asymptotically optimal sequence for $\mathcal{P}$ is also asymptotically optimal for ${\mathcal{P}}^{\prime }$, we realize that ${\mathcal{P}}^{\prime }$ has the same H_max-attractor, hence also the same R_min-code as $\mathcal{P}$. Thus R(κ^∗|${\mathcal{P}}^{\prime }$) = R_min(${\mathcal{P}}^{\prime }$) = H_max(${\mathcal{P}}^{\prime }$) = H_max($\mathcal{P}$) and it follows that ${\mathcal{P}}^{\prime }\subseteq {\mathcal{P}}_{\max }$.

Clearly, ${\mathcal{P}}_{\max }$ is convex and $H_{\max }\left({\mathcal{P}}_{\max }\right)=H_{\max }\left(\mathcal{P}\right)<\infty$, hence ${\mathcal{P}}_{\max }$ is in equilibrium by Theorem 6.1.

The final assertion of the theorem follows by one more application of Theorem 6.1. ☐

The models which can arise as in Theorem 8.3 via (8.40) are called maximal models.

Let κ^∗ ∈ K($\mathbb{A}$) and 0 ≤ h < ∞. Put

$${\mathcal{P}}_{{\kappa }^{*},h}=\left\{P\in M_{+}^1\left(\mathbb{A}\right)|\langle {\kappa }^{*},P\rangle \le h\right\}.$$

We know that any maximal model must be of this form. Naturally, the converse does not hold. An obvious necessary condition is that the entropy of the matching distribution be finite. But we must require more. Clearly, the models in (8.41) are in equilibrium but it is not clear that they have κ^∗ as R_min-code and h as H_max-value.

Theorem 8.4. 

A distribution $P^{*}\in M_{+}^1\left(\mathbb{N}\right)$ with finite entropy has potential entropy loss if and only if it is hyperbolic.

Proof. 

We may assume that the point probabilities of P are ordered.

Assume first that P^∗ is not hyperbolic and that P^∗ is the attractor for some model. Consider the corresponding maximal models ${\mathcal{P}}_{{\kappa }^{*},h}$ and consider a value of h with H(P^∗) ≤ h ≤ H_max($\mathcal{P}$). Let γ be the abscissa of convergence associated with κ^∗ and let Φ be defined as in the appendix. As γ < 1, we can choose β > γ such that Φ(β) = h. Now both P^∗ and Q_β given by

$$Q_{\beta }=\frac{\exp \left(-\beta {\kappa }_i\right)}{Z\left(\beta \right)}$$

are attractors for ${\mathcal{P}}_{{\kappa }^{*},h}$ and hence equal. It follows that h = H(P^∗). Next we show that a hyperbolic distribution has potential entropy loss.

Consider the maximal models ${\mathcal{P}}_{{\kappa }^{*},h}$. Each one of these models is given by a single linear constraint. Therefore, the attractor is element in the corresponding exponential family. The abscissa of convergence is 1 and, therefore, the range of the map $\Phi :\left[1;\infty \left[\to ℝ \text{is}\right]{\kappa }_1^{*};H\left(P^{*}\right)\right]$. For $h\in ]{\kappa }_1^{*};H\left(P^{*}\right)]$, there exists a consistent maximum entropy distribution. Assume that h₀ > H(P^∗) and that the attractor equals

$$Q_{\beta }=\frac{\exp \left(-\beta {\kappa }_i\right)}{Z\left(\beta \right)}$$

By Theorem 8.1, Q_β must be attractor for all ${\mathcal{P}}_{{\kappa }^{*},h}$ with h ∈ [Φ(β); h₀]. Especially, this holds for h = H(P^∗). This shows that P^∗ = Q_β. By Theorem 8.1 the conclusion is now clear. ☐

9 Zipf’s law

Zipf’s law is an empirically discovered relationship for the relative frequencies of the words of a natural language. The law states that

$$\log \left(f_i\right)\approx a \log (\frac{1}{i})+b$$

where f_i is the relative frequency of the i’th most common word in the language, and where a and b denote constants. For large values of i we then have

$$a\approx \frac{\log f_i}{\log \frac{1}{i}}$$

The constants a and b depend on the language, but for many languages a ≈ 1, see [24].

Now consider an ideal language where the frequencies of words is described by a hyperbolic probability distribution P^∗. Assume that the entropy of the distribution is finite. We shall discribe in qualitative terms the consequences of these assumptions as they can be derived from the developed theory, especially Theorem 8.4. We shall see that our asumption introduces a kind of stability of the language which is desirable in most situations.

Small children with a limited vocabulary will use the few words they know with relative frequencies very different from the probabilities described by P^∗. They will only form simple sentences, and at this stage the number of bits per word will be small in the sense that the entropy of the childs probability distribution is small. Therefore the parents will often be able to understand the child even though the pronounciation is poor. The parents will, typically, talk to their children with a lower bit rate than they normally use, but with a higher bit rate than their children. Thereby new words and grammatical structures will be presented to the child, and, adopting elements of this structure, the child will be able to increase its bit rate. At a certain stage the child will be able to communicate at a reasonably high rate (about H(P^∗)). Now the child knows all the basic words and structures of the language.

The child is still able to increase its bit rate, but from now on this will make no significant change in the relative frequencies of the words. Bit rates higher than H(P^∗) are from now on obtained by the introduction of specialized words, which occur seldom in the language as a whole. The introduction of new specialized words can be continued during the rest of the life. Therefore one is able to express even complicated ideas without changing the basic structure of the language, indeed there is no limit, theoretically, to the bit rate at which one can communicate without change of basic structure.

We realize that in view of our theoretical results, specifically Theorem 8.4, the features of a natural language as just discussed are only possible if the language obeys Zipf’s law. Thus we have the striking phenomenon that the apparent “irregular” behaviour of models with entropy loss (or just potential entropy loss) is actually the key to desirable stability, the fact that for such models you can increase the bit rate, the level of communication, and maintain the basic features of the language. One could even speculate that modelling based on entropy loss lies behind the phenomenon that many will realize as a fact, viz. that “we can talk without thinking” . We just start talking using basic structure of the language (and rather common words) and then from time to time stick in more informative words and phrases in order to give our talk more semantic content, but in doing so, we use relatively infrequent words and structures, thus not violating basic principles – hence still speaking recognizably danish, english or what the case may be, so that also the receiver or listener feels at ease and recognizes our talk as unmistakenly danish, english or ...

We see that very informative speeking can be obtained by use of infrequent expressions. Therefore a conversation between, say 2 physicists may use English supplied with specialized words like electron and magnetic flux. We recognize their language as English because the basic words and grammer is the same in all English. The specialists only have to know special words, not a special grammer. In this sense the languages are stable. If the entropy of our distribution is infinite the language will behave in just about the same manner as described above. In fact one would not feel any difference between a language with finite entropy and a language with infinite entropy.

We see that it is convienient that a language follows a Zipf’s law, but the information theoretic methods also gives some explanation of how the language may have evolved into a state which obeys Zipf’s law. The set of hyperbolic distributions is convex. Therefore if 2 information sources both follows Zipf’s law then so do their mixture, and if 2 information sources both approximately follows Zipf’s law their mixture will do this even more. The information sources may be from different languages, but it is more interesting to consider a small child learning the language. The child gets input from different sources: the mother, father, other children ect. trying to imitate their language the child will use the words with frequences which are closer to Zipf’s law the the sources. As the language develops during the centuries the frequences will converge to a hyperbolic distribution.

Here we have discussed entropy as bit per word and not bit per letter. The letters give an encoding of the words which should primarilly be understood by others, and therefore the encoding cannot just be changed to obtain a better data compression. To stress the difference between bit per word and bit per letter we remark the the words are the basic semantic structure in the language. Therefore we may have an internal representation of the words which has very little to do with their length when spoken, which could explain that it is often much easier to remember a long word in a language you understand than a short word in a language you do not understand. It would be interesting to compare these ideas with empirical measurements of the entropy here considered but, precisely in the regime where Zipf’s law holds, such a study is very difficult as convergence of estimators of the entropy is very slow, cf. [1].