Entropy: The Markov Ordering Approach

Introduction

Two functions, energy and entropy, rule the Universe.

In 1865 R. Clausius formulated two main laws Clausius1865 :

The entropy of the Universe tends to a maximum.

The universe is isolated. For non-isolated systems energy and entropy can enter and leave, the change in energy is equal to its income minus its outcome, and the change in entropy is equal to entropy production inside the system plus its income minus outcome. The entropy production is always positive.

Ten years later J.W. Gibbs Gibbs1875 developed a general theory of equilibrium of complex media based on the entropy maximum: the equilibrium is the point of the conditional entropy maximum under given values of conserved quantities. The entropy maximum principle was applied to many physical and chemical problems. At the same time J.W. Gibbs mentioned that entropy maximizers under a given energy are energy minimizers under a given entropy.

The classical expression $\int p\ln p$ became famous in 1872 when L. Boltzmann proved his $H$-theorem Boltzmann1872 : the function

decreases in time for isolated gas which satisfies the Boltzmann equation (here $f(x,v)$ is the distribution density of particles in phase space, $x$ is the position of a particle, $v$ is velocity). The statistical entropy was born: $S=-kH$. This was the one-particle entropy of a many-particle system (gas).

In 1902, J.W. Gibbs published a book “Elementary principles in statistical dynamics” Gibbs1902 . He considered ensembles in the many-particle phase space with probability density $\rho(p_{1},q_{1},\ldots p_{n},q_{n})$, where $p_{i},q_{i}$ are the momentum and coordinate of the $i$th particle. For this distribution,

Gibbs introduced the canonical distribution that provides the entropy maximum for a given expectation of energy and gave rise to the entropy maximum principle (MaxEnt).

The Boltzmann period of history was carefully studied Villani . The difference between the Boltzmann entropy which is defined for coarse-grained distribution and increases in time due to gas dynamics, and the Gibbs entropy, which is constant due to dynamics, was analyzed by many authors Jaynes1965 ; GoldsteinLebov2004 . Recently, the idea of two functions, energy and entropy which rule the Universe was implemented as a basis of two-generator formalism of nonequilibrium thermodynamics Grmela1997 ; Ottinger2005 .

In information theory, R.V.L. Hartley (1928) Hartley1928 introduced a logarithmic measure of information in electronic communication in order “to eliminate the psychological factors involved and to establish a measure of information in terms of purely physical quantities”. He defined information in a text of length $n$ in alphabet of s symbols as $H=n\log s$.

In 1948, C.E. Shannon Shannon1948 generalized the Hartley approach and developed “a mathematical theory of communication”, that is information theory. He measured information, choice and uncertainty by the entropy:

Here, $p_{i}$ are the probabilities of a full set of $n$ events ($\sum_{i=1}^{n}p_{i}=1$). The quantity $S$ is used to measure of how much “choice” is involved in the selection of the event or of how uncertain we are of the outcome. Shannon mentioned that this quantity form will be recognized as that of entropy, as defined in certain formulations of statistical mechanics. The classical entropy (1), (2) was called the Boltzmann–Gibbs–Shannon entropy (BGS entropy). (In 1948, Shannon used the concave function (2), but under the same notation $H$ as for the Boltzmann convex function. Here we use $H$ for the convex $H$-function, and $S$ for the concave entropy.)

In 1951, S. Kullback and R.A. Leibler KullLei1951 supplemented the BGS entropy by the relative BGS entropy, or the Kullback–Leibler divergence between the current distribution $P$ and some “base” (or “reference”) distribution $Q$:

where $F$ is free energy and $T$ is thermodynamic temperature. In physics, $F=U-TS$, where physical entropy $S$ includes an additional multiplier $k$, the Boltzmann constant. The thermodynamic potential $-F/T$ has its own name, Massieu function. Let us demonstrate this interpretation of the Kullback–Leibler divergence. The equilibrium distribution $Q$ provides the conditional entropy (2) maximum under a given expectation of energy $\sum_{i}u_{i}q_{i}=U$ and the normalization condition $\sum_{i}q_{i}=1$. With the Lagrange multipliers $\mu_{U}$ and $\mu_{0}$ we get the equilibrium Boltzmann distribution:

The Lagrange multiplier $\mu_{U}$ is in physics (by definition) $1/kT$, so $S(Q)=\mu_{0}+\frac{U}{kT}$, hence, $\mu_{0}=-\frac{F(Q)}{kT}$. For the Kullback–Leibler divergence this formula gives (4).

After the classical work of Zeldovich (1938, reprinted in 1996 Zeld ), the expression for free energy in the “Kullback–Leibler form”

where $c_{i}$ is concentration and $c^{*}_{i}(T)$ is the equilibrium concentration of the $i$th component, is recognized as a useful instrument for the analysis of kinetic equations (especially in chemical kinetics YBGE ; Hangos2009 ).

Each given positive distribution $Q$ could be represented as an equilibrium Boltzmann distribution for given $T>0$ if we take $u_{i}=-kT\log q_{i}+u_{0}$ for an arbitrary constant level $u_{0}$. If we change the order of arguments in the Kullback–Leibler divergence then we get the relative Burg entropy Burg1967 ; Burg1972 . It has a much more exotic physical interpretation: for a current distribution $P$ we can define the “auxiliary energy” functional $U_{P}$ for which $P$ is the equilibrium distribution under a given temperature $T$. We can calculate the auxiliary free energy of any distribution $Q$ and this auxiliary energy functional: $F_{P}(Q)$. (Up to an additive constant, for $P=P^{*}$ this $F_{P}(Q)$ turns into the classical free energy, $F_{P}^{*}(Q)=F(Q)$.) In particular, we can calculate the auxiliary free energy of the physical equilibrium, $F_{P}(P^{*})$. The relative Burg entropy is

This functional should also decrease in any Markov process with given equilibrium $P^{*}$.

Information theory developed by Shannon and his successors focused on entropy as a measure of uncertainty of subjective choice. This understanding of entropy was returned from information theory to statistical mechanics by E.T. Jaynes as a basis of “subjective” statistical mechanics Jaynes1957a ; Jaynes1957b . He followed Wigner’s idea “entropy is an antropocentric concept”. The entropy maximum approach was declared as a minimization of the subjective uncertainty. This approach gave rise to a MaxEnt “anarchism”. It is based on a methodological hypothesis that everything unknown could be estimated by the principle of the entropy maximum under the condition of fixed known quantities. At this point the classicism in entropy development changed to a sort of scientific modernism. The art of model fitting based on entropy maximization was developed Harre2001 . The principle of the entropy maximum was applied to plenty of problems: from many physical problems Beck2009 , chemical kinetics and process engineering Hangos2009 to econometrics MittJudge2000 ; Judge2002 and psychology Myers1992 . Many new entropies were invented and now one has rich choice of entropies for fitting needs EstMor1995 . The most celebrated of them are the Rényi entropy Renyi1961 , the Burg entropy Burg1967 ; Burg1972 , the Tsallis entropy Tsa1988 ; Abe and the Cressie–Read family CR1984 ; ReadCreass1988 . The nonlinear generalized averaging operations and generalized entropy maximization procedures were suggested Bagci2009 .

Following this impressive stream of works we understand the MaxEnt approach as conditional maximization of entropy for the evaluation of the probability distribution when our information is partial and incomplete. The entropy function may be the classical BGS entropy or any function from the rich family of non-classical entropies. This rich choice causes a new problem: which entropy is better for a given class of applications?

The MaxEnt “anarchism” was criticized many times as a “senseless fitting”. Arguments pro and contra the MaxEnt approach with non-classical entropies (mostly the Tsallis entropy Tsa1988 ) were collected by Cho Cho2002 . This sometimes “messy and confusing situation regarding entropy-related studies has provided opportunities for us: clearly there are still many very interesting studies to pursue” Lin1999 .

2 Key Points

In this paper we do not pretend to invent new entropies. (There appear new functions as limiting cases of the known entropy families, but this is not our main goal). Entropy is understood in this paper as a measure of uncertainty which increases in Markov processes. In our paper we consider a Markov process as a semigroup on the space of positive probability distributions. The state space is finite. Generalizations to compact state spaces are simple. We analyze existent relative entropies (divergences) using several simple ideas:

In Markov processes probability distributions $P(t)$ monotonically approach equilibrium $P^{*}$: divergence $D(P(t)\|P^{*})$ monotonically decrease in time.

In most applications, conditional minimizers and maximizers of entropies and divergences are used, but the values are not. This means that the system of level sets is more important than the functions’ values. Hence, most of the important properties are invariant with respect to monotonic transformations of entropy scale.

The system of level sets should be the same as for additive functions: after some rescaling the divergences of interest should be additive with respect to the joining of statistically independent systems.

The system of level sets should after some rescaling the divergences of interest should have the form of a sum (or integral) over states $\sum_{i}f(p_{i},p_{i}^{*})$, where the function $f$ is the same for all states. In information theory, divergences of such form are called separable, in physics the term trace–form functions is used

The first requirement means that if a distribution becomes more random then it becomes closer to equilibrium (Markov process decreases the information excess over equilibrium). For example, classical entropy increases in all Markov processes with uniform equilibrium distributions. This is why we may say that the distribution with higher entropy is more random, and why we use entropy conditional maximization for the evaluation of the probability distribution when our information is partial and incomplete.

It is worth to mention that some of the popular Bregman divergences, for example, the squared Euclidean distance or the Itakura–Saito divergence, do not satisfy the first requirement (see Section 4.3).

The second idea is just a very general methodological thesis: to evaluate an instrument (a divergence) we have to look how it works (produces conditional minimizers and maximizers). The properties of the instrument which are not related to its work are not important. The number three allows to separate variables if the system consists of independent subsystems, the number four relates to separation of variables for partitions of the space of probability distributions.

Amongst a rich world of relative entropies and divergences, only two families meet these requirements. Both were proposed in 1984. The Cressie–Read (CR) family CR1984 ; ReadCreass1988 :

and the convex combination of the Burg and Shannon relative entropies proposed in G11984 and further analyzed in ENTR1 ; ENTR2 :

When $\lambda\to 0$ the CR divergence tends to the KL divergence (the relative Shannon entropy) and when $\lambda\to-1$ it turns into the Burg relative entropy. The Tsallis entropy was introduced four years later Tsa1988 and became very popular in thermostatistics (there are thousands of works that use or analyze this entropy TsallisBiblio2009 ). The Tsallis entropy coincides (up to a constant multiplier $\lambda+1$) with the CR entropy for $\lambda\in]-1,\infty[$ and there is no need to study it separately (see discussion in Section 2.2).

A new problem arose: which entropy is better for a specific problem? Many authors compare performance of different entropies and metrics for various problems (see, for example, Cachin1997 ; Davis2007 ). In any case study it may be possible to choose “the best” entropy but in general we have no sufficient reasons for such a choice. We propose a possible way to avoid the choice of the best entropy.

Let us return to the idea: the distribution $Q$ is more random than $P$ if there exists a continuous-time Markov process (with given equilibrium distribution $P^{*}$) that transforms $P$ into $Q$. We say in this case that $P$ and $Q$ are connected by the Markov preorder with equilibrium $P^{*}$ and use notation $P\succ^{0}_{P^{*}}Q$. The Markov order $\succ_{P^{*}}$ is the transitive closure of the Markov preorder.

If a priori information gives us a set of possible distributions $W$ then the conditionally “maximally random distributions” (the “distributions without additional information”, the “most indefinite distributions” in $W$) should be the minimal elements in $W$ with respect to Markov order. If a Markov process (with equilibrium $P^{*}$) starts at such a minimal element $P$ then it cannot produce any other distribution from $W$ because all distributions which are more random that $P$ are situated outside $W$. In this approach, the maximally random distributions under given a priori information may be not unique. Such distributions form a set which plays the same role as the standard MaxEnt distribution. For the moment based a priori information the set $W$ is an intersection of a linear manifold with the simplex of probability distributions, the set of minimal elements in $W$ is also polyhedron and its description is available in explicit form. In low-dimensional case it is much simpler to construct this polyhedron than to find the MaxEnt distributions for most of specific entropies.

3 Structure of the Paper

The paper is organized as follows. In Section 2 we describe the known non-classical divergences (relative entropies) which are the Lyapunov functions for the Markov processes. We discuss the general construction and the most popular families of such functions. We pay special attention to the situations, when different divergences define the same order on distributions and provide the same solutions of the MaxEnt problems (Section 2.2). In two short technical Sections 2.3 and 2.4 we present normalization and symmetrization of divergences (similar discussion of these operations was published very recently Petz2010 .

The divergence between the current distribution and equilibrium should decrease due to Markov processes. Moreover, divergence between any two distributions should also decrease (the generalized data processing Lemma, Section 3).

Definition of entropy by its properties is discussed in Section 4. Various approaches to this definition were developed for the BGS entropy by Shannon Shannon1948 , Renyi1970 and by other authors for the Rényi entropy Aczel ; AczDar , the Tsallis entropy Abik4 , the CR entropy and the convex combination of the BGS and Burg entropies ENTR3 . Csiszár Csiszar1978 axiomatically characterized the class of Csiszár–Morimoto divergences (formula (6) below). Another characterization of this class was proved in ENTR3 (see Lemma 1, Section 4.3 below).

From the celebrated properties of entropy Wehrl we selected the following three:

Entropy should be a Lyapunov function for continuous-time Markov processes;

Entropy is additive with respect to the joining of independent systems;

Entropy is additive with respect to the partitioning of the space of states (i.e., has the trace–form).

To solve the MaxEnt problem we have to find the maximizers of entropy (minimizers of the relative entropy) under given conditions. For this purpose, we have to know the sublevel sets of entropy, but not its values. We consider entropies with the same system of sublevel sets as equivalent ones (Section 2.2). From this point of view, all important properties have to be invariant with respect to monotonic transformations of the entropy scale. Two last properties from the list have to be substituted by the following:

There exists a monotonic transformation which makes entropy additive with respect to the joining of independent systems (Section 4.2);

There exists a monotonic transformation which makes entropy additive with respect to the partitioning of the space of states (Section 4.1).

Several “No More Entropies” Theorems are proven in Section 4.3: if an entropy has properties 1, 2’ and 3’ then it belongs to one of the following one-parametric families: to the Cressie–Read family, or to a convex combination of the classical BGS entropy and the Burg entropy (may be, after a monotonic transformation of scale).

It seems very natural to consider divergences as orders on distribution spaces (Section 5.1), the sublevel sets are the lower cones of this orders. For several functions, $H_{1}(P),\ldots,H_{k}(P)$ the sets $\{Q\ |\ H_{i}(P)>H_{i}(Q)\ {\rm for\ all}\ i\}$ give the simple generalization of the sublevel sets. In Section 5 we discuss the more general orders in which continuous time Markov processes are monotone, define the Markov order and fully characterize the local Markov order. The Markov chains with detailed balance define the Markov order for general Markov chains (Section 5.2). It is surprising that there is no necessity to consider other Markov chains for the order characterization (Section 5.2) because no reversibility is assumed in this analysis.

In Section 6.1 we demonstrate how is it possible to use the Markov order to reduce the uncertainty in the standard settings when a priori information is given about values of some moments. Approaches to construction of the most random distributions are presented in Section 6.2.

Various approaches for the definition of the reference distribution (or the generalized canonical distribution) are compared in Section 7.

In Conclusion we briefly discuss the main results.

Non-Classical Entropies

During the time of modernism plenty of new entropies were proposed. Esteban and Morales EstMor1995 attempted to systemize many of them in an impressive table. Nevertheless, there are relatively few entropies in use now. Most of the relative entropies have the form proposed independently in 1963 by I. Csiszar Csiszar1963 and T. Morimoto Morimoto1963 :

where $h(x)$ is a convex function defined on the open ($x>0$) or closed $x\geq 0$ semi-axis. We use here notation $H_{h}(P\|P^{*})$ to stress the dependence of $H_{h}$ both on $p_{i}$ and $p^{*}_{i}$.

These relative entropies are the Lyapunov functions for all Markov chains with equilibrium $P^{*}=(p^{*}_{i})$. Moreover, they have the relative entropy contraction property given by the generalized data processing lemma (Section 3.2 below).

For $h(x)=x\log x$ this function coincides with the Kullback–Leibler divergence from the current distribution $p_{i}$ to the equilibrium $p^{*}_{i}$. Some practically important functions $h$ have singularities at 0. For example, if we take $h(x)=-\log x$, then the correspondent $H_{h}$ is the relative Burg entropy $H_{h}=-\sum_{i}p^{*}_{i}\log(p_{i}/p_{i}^{*})\to\infty$ for $p_{i}\to 0$.

1.2 Required Properties of the Function h​(x)ℎ𝑥h(x)

Formally, $h(x)$ is an extended real-valued proper convex function on the closed positive real half-line $[0,\infty[$. An extended real-valued function can take real values and infinite values $\pm\infty$. A proper function has at least one finite value. An extended real valued function on a convex set $U$ is called convex if its epigraph

is a convex set Rockafellar1970 . For a proper function this definition is equivalent to the Jensen inequality

It is assumed that the function $h(x)$ takes finite values on the open positive real half-line $]0,\infty[$ but the value at point $x=0$ may be infinite. For example, functions $h(x)=-\log x$ or $h(x)=x^{-\alpha}$ ($\alpha>0$) are allowed. A convex function $h(x)$ with finite values on the open positive real half-line is continuous on $]0,\infty[$ but may have a discontinuity at $x=0$. For example, the step function, $h(x)=0$ if $x=0$ and $h(x)=-1$ if $x>0$, may be used.

A convex function is differentiable almost everywhere. Derivative of $h(x)$ is a monotonic function which has left and right limits at each point $x>0$. An inequality holds: $h^{\prime}(x)(y-x)\leq h(y)-h(x)$ (Jensen’s inequality in the differential form). It is valid also for left and right limits of $h^{\prime}$ at any point $x>0$.

Not everywhere differentiable functions $h(x)$ are often used, for example, $h(x)=|x-1|$. Nevertheless, it is convenient to consider the twice differentiable on $]0,\infty[$ functions $h(x)$ and to produce a non-smooth $h(x)$ (if necessary) as a limit of smooth convex functions. We use widely this possibility.

Let $h(x)$ be the step function, $h(x)=0$ if $x=0$ and $h(x)=-1$ if $x>0$. In this case,

The quantity $-H_{h}$ is the number of non-zero probabilities $p_{i}$ and does not depend on $P^{*}$. Sometimes it is called the Hartley entropy.

this is the $l_{1}$-distance between $P$ and $P^{*}$.

this is the usual Kullback–Leibler divergence or the relative BGS entropy;

this is the relative Burg entropy. It is obvious that this is again the Kullback–Leibler divergence, but for another order of arguments.

Convex combinations of $h=x\ln x$ and $h=-\ln x$ also produces a remarkable family of divergences: $h=\beta x\ln x-(1-\beta)\ln x$ ($\beta\in$),

The convex combination of divergences becomes a symmetric functional of $(P,P^{*})$ for $\beta=1/2$. There exists a special name for this case, “Jeffreys’ entropy”.

$h=\frac{x(x^{\lambda}-1)}{\lambda(\lambda+1)}$,

For the CR family in the limits $\lambda\to\pm\infty$ only the maximal terms “survive”. Exactly as we get the limit $l^{\infty}$ of $l^{p}$ norms for $p\to\infty$, we can use the root $({\lambda(\lambda+1)}H_{\rm CR\ \lambda})^{1/|\lambda|}$ for $\lambda\to\pm\infty$ and write in these limits the divergences:

The existence of two limiting divergences $H_{{\rm CR\ \pm\infty}}$ seems very natural: there may be two types of extremely non-equilibrium states: with a high excess of current probability $p_{i}$ above $p_{i}^{*}$ and, inversely, with an extremely small current probability $p_{i}$ with respect to $p_{i}^{*}$.

The Tsallis relative entropy Tsa1988 corresponds to the choice $h=\frac{(x^{\alpha}-x)}{\alpha-1}$, $\alpha>0$.

For this family we use notation $H_{\rm Ts\ \alpha}$.

1.4 Rényi Entropy

The Rényi entropy of order $\alpha>0$ is defined Renyi1961 as

when $\alpha\to 1$, where $S(P)$ is the Shannon entropy.

When $\alpha\to\infty$, the Rényi entropy has a limit $H_{\infty}(X)=-\log\max_{i=1,\ldots n}p_{i}$, which has a special name “Min-entropy”.

It is easy to get the expression for a relative Rényi entropy $H_{{\rm R}\ \alpha}(P\|P^{*})$ from the requirement that it should be a Lyapunov function for any Markov chain with equilibrium $P^{*}$:

For the Min-entropy, the correspondent divergence (the relative Min-entropy) is

It is obvious from (22) below that $\max_{i=1,\ldots n}({p_{i}}/{p_{i}^{*}})$ is a Lyapunov function for any Markov chain with equilibrium $P^{*}$, hence, the relative Min-entropy is also the Lyapunov functional.

2 Entropy Level Sets

A level set of a real-valued function $f$ is a set of the form :

where $c$ is a constant (the “level”). It is the set where the function takes on a given constant value. A sublevel set of $f$ is a set of the form

A superlevel set of $f$ is given by the inequality with reverse sign:

The intersection of the sublevel and the superlevel sets for a given value $c$ is the level set for this level.

In many applications, we do not need the entropy values, but rather the order of these values on the line. For any two distributions $P,Q$ we have to compare which one is closer to equilibrium $P^{*}$, i.e., to answer the question: which of the following relations is true: $H(P\|P^{*})>H(Q\|P^{*})$, $H(P\|P^{*})=H(Q\|P^{*})$ or $H(P\|P^{*})<H(Q\|P^{*})$? To solve the MaxEnt problem we have to find the maximizers of entropy (or, in more general settings, the minimizers of the relative entropy) under given conditions. For this purpose, we have to know the sublevel sets, but not the values. All the MaxEnt approach does not need the values of the entropy but the sublevel sets are necessary.

Let us consider two functions, $\phi$ and $\psi$ on a set $U$. For any $V\subset U$ we can study conditional minimization problems $\phi(x)\to\min$ and $\psi(x)\to\min$, $x\in V$. The sets of minimizers for these two problems coincide for any $V\subset U$ if and only if the functions $\phi$ and $\psi$ have the same sets of sublevel sets. It should be stressed that here just the sets of sublevel sets have to coincide without any relation to values of level.

Let us compare the level sets for the Rényi, the Cressie-Read and the Tsallis families of divergences (for $\alpha-1=\lambda$ and for all values of $\alpha$). The values of these functions are different, but the level sets are the same (outside the Burg limit, where $\alpha\to 0$): for $\alpha\neq 0,1$

where $c=\sum_{i}p_{i}(p_{i}/p_{i}^{*})^{\alpha-1}$.

For $\alpha\to 1$ all these divergences turn into the Shannon relative entropy. Hence, if $\alpha\neq 0$ then for any $P$, $P^{*}$, $Q$, $Q^{*}$ the following equalities A, B, C are equivalent, A$\Leftrightarrow$B$\Leftrightarrow$C:

This equivalence means that we can select any of these three divergences as a basic function and consider the others as functions of this basic one.

For any $\alpha\geq 0$ and $\lambda=\alpha+1$ the Rényi, the Cressie–Read and the Tsallis divergences have the same family of sublevel sets. Hence, they give the same maximizers to the conditional relative entropy minimization problems and there is no difference which entropy to use.

The CR family has a more convenient normalization factor $1/\lambda(\lambda+1)$ which gives a proper convexity for all powers, both positive and negative, and provides a sensible Burg limit for $\lambda\to-1$ (in contrary, when $\alpha\to 0$ both the Rényi and Tsallis entropies tend to 0).

When $\alpha<0$ then for the Tsallis entropy function $h=\frac{(x^{\alpha}-x)}{\alpha-1}$ loses convexity, whereas for the Cressie-Read family convexity persists for all values of $\lambda$. The Rényi entropy also loses convexity for $\alpha<0$. Neither the Tsallis, nor the Rényi entropy were invented for use with negative $\alpha$.

There may be a reason: for $\alpha<0$ the function $x^{\alpha}$ is defined for $x>0$ only and has a singularity at $x=0$. If we assume that the divergence should exist for all non-negative distributions, then the cases $\alpha\leq 0$ should be excluded. Nevertheless, the Burg entropy which is singular at zeros is practically important and has various attractive properties. The Jeffreys’ entropy (the symmetrized Kullback–Leibler divergence) is also singular at zero, but has many important properties. We can conclude at this point that it is not obvious that we have to exclude any singularity at zero probability. It may be useful to consider positive probabilities instead (“nature abhors a vacuum”).

Finally, for the MaxEnt approach (conditional minimization of the relative entropy), the Rényi and the Tsallis families of divergences ($\alpha>0$) are particular cases of the Cressie–Read family because they give the same minimizers. For $\alpha\leq 0$ the Rényi and the Tsallis relative entropies lose their convexity, while the Cressie–Read family remains convex for $\lambda\leq-1$ too.

3 Minima and normalization

For a given $P^{*}$, the function $H_{h}$ achieves its minimum on the hyperplane $\sum_{i}p_{i}=\sum_{i}p_{i}^{*}=$const at equilibrium $p_{i}^{*}$, because at this point

The transformation $h(x)\to h(x)+ax+b$ just shifts $H_{h}$ by constant value: $H_{h}\to H_{h}+a\sum_{i}p_{i}+b=H_{h}+a+b$. Therefore, we can always assume that the function $h(x)$ achieves its minimal value at point $x=1$, and this value is zero. For this purpose, one should just transform $h$:

This normalization transforms $x\ln x$ into $x\ln x-(x-1)$, $-\ln x$ into $-\ln x+(x-1)$, and $x^{\alpha}$ into $x^{\alpha}-1-\alpha(x-1)$. After normalization $H_{h}(P\|P^{*})\geq 0$. If the normalized $h(x)$ is strictly positive outside point $x=1$ ($h(x)>0$ if $x\neq 1$) then $H_{h}(P\|P^{*})=0$ if and only if $P=P^{*}$ (i.e., in equilibrium).

The normalized version of any divergence $H_{h}(P\|P^{*})$ could be produced by the normalization transformation $h(x):=h(x)-h(1)-h^{\prime}(1)(x-1)$ and does not need separate discussion.

4 Symmetrization

Another technical issue is symmetry of a divergence. If $h(x)=x\ln x$ then both $H_{h}(P\|P^{*})$ (the KL divergence) and $H_{h}(P^{*}\|P)$ (the relative Burg entropy) are the Lyapunov functions for the Markov chains, and $H_{h}(P^{*}\|P)=H_{g}(P\|P^{*})$ with $g(x)=-\ln x$. Analogously, for any $h(x)$ we can write $H_{h}(P^{*}\|P)=H_{g}(P\|P^{*})$ with

If $h(x)$ is convex on $\mathbf{R}_{+}$ then $g(x)$ is convex on $\mathbf{R}_{+}$ too because

The transformation (20) is an involution:

The fixed points of this involution are such functions $h(x)$ that $H_{h}(P\|P^{*})$ is symmetric with respect to transpositions of $P$ and $P^{*}$. There are many such $h(x)$. An example of symmetric $H_{h}(P\|P^{*})$ gives the choice $h(x)=-\sqrt{x}$:

Essentially (up to a constant addition and multiplier) this function coincides with a member of the CR family, $H_{{\rm CR}\ -\frac{1}{2}}$ (12), and with one of the Tsallis relative entropies $H_{{\rm Ts}\ \frac{1}{2}}$ (15). The involution (20) is a linear operator, hence, for any convex $h(x)$ we can produce its symmetrization:

For example, if $h(x)=x\log x$ then $h_{\rm sym}(x)=\frac{1}{2}(x\log x-\log x)$; if $h(x)=x^{\alpha}$ then $h_{\rm sym}(x)=\frac{1}{2}(x^{\alpha}+x^{1-\alpha})$.

Entropy Production and Relative Entropy Contraction

Let us consider continuous time Markov chains with positive equilibrium probabilities $p_{j}^{*}$. The dynamics of the probability distribution $p_{i}$ satisfy the Master equation (the Kolmogorov equation):

where coefficients $q_{ij}$ ($i\neq j$) are non-negative. For chains with a positive equilibrium distribution $p_{j}^{*}$ another equivalent form is convenient:

where $p_{i}^{*}$ and $q_{ij}$ are connected by identity

The time derivative of the Csiszár–Morimoto function $H_{h}(p)$ (6) due to the Master equation is

To prove this formula, it is worth to mention that for any $n$ numbers $h_{i}$, $\sum_{i,j,\,j\neq i}q_{ij}p^{*}_{j}(h_{i}-h_{j})=0$. The last inequality holds because of the convexity of $h(x)$: $h^{\prime}(x)(y-x)\leq h(y)-h(x)$ (Jensen’s inequality).

for all positive $x,y$ then $h(x)$ is convex on $\mathbf{R}_{+}$. Therefore, if for some function $h(x)$ $H_{h}(p)$ is the Lyapunov function for all the Markov chains with equilibrium $P^{*}$ then $h(x)$ is convex on $\mathbf{R}_{+}$.

The Lyapunov functionals $H_{h}$ do not depend on the kinetic coefficients $q_{ij}$ directly. They depend on the equilibrium distribution $p^{*}$ which satisfies the identity (23). This independence of the kinetic coefficients is the universality property.

2 “Lyapunov Divergences” for Discrete Time Markov Chains

The Csiszár–Morimoto functions (6) are also Lyapunov functions for discrete time Markov chains. Moreover, they can serve as a “Lyapunov distances” Liese1987 between distributions which decreases due to time evolution (and not only the divergence between the current distribution and equilibrium). In more detail, let $A=(a_{ij})$ be a stochastic matrix in columns:

The ergodicity contraction coefficient for $A$ is a number $\overline{\alpha}(A)$ DobrushinErgCoeff1956 ; Seneta1981 :

Let us consider in this subsection the normalized Csiszár–Morimoto divergences $H_{h}(P\|Q)$ (19): $h(1)=0,\,h(x)\geq 0$.

Theorem about relative entropy contraction. (The generalized data processing Lemma.) For each two probability positive distributions $P,Q$ the divergence $H_{h}(P\|Q)$ decreases under action of stochastic matrix $A$ Cohen1993 ; CohenIwasa1993 :

The generalizations of this theorem for general Markov kernels seen as operators on spaces of probability measures was given by Ledoux2003 . The shift in time for continuous-time Markov chain is a column-stochastic matrix, hence, this contraction theorem is also valid for continuous-time Markov chains.

The question about a converse theorem arises immediately. Let the contraction inequality hold for two pairs of positive distributions $(P,Q)$ and $(U,V)$ and for all $H_{h}$:

Could we expect that there exists such a stochastic matrix $A$ that $U=AP$ and $V=AP$? The answer is positive:

The converse generalized data processing lemma. Let the contraction inequality (27) hold for two pairs of positive distributions $(P,Q)$ and $(U,V)$ and for all normalized $H_{h}$. Then there exists such a column-stochastic matrix $A$ that $U=AP$ and $V=AQ$ Cohen1993 .

This means that for the system of inequalities (27) (for all normalized convex functions $h$ on $]0,\infty[$) is necessary and sufficient for existence of a (discrete time) Markov process which transform the pair of positive distributions $(P,Q)$ in $(U,V)$. It is easy to show that for continuous-time Markov chains this theorem is not valid: the attainable regions for them are strictly smaller than the set given by inequalities (27) and could be even non-convex (see Gorban1979 and Section 8.1 below).

Definition of Entropy by its Properties

An important property of separation of variables is valid for all divergences which have the form of a sum of convex functions $f(p_{i},p_{i}^{*})$. Let the set of states be divided into two subsets, $I_{1}$ and $I_{2}$, and let the functionals $u^{1},\ldots u^{m}$ be linear. We represent each probability distribution as a direct sum $P=P^{1}\oplus P^{2}$, where $P^{1,2}$ are restrictions of $P$ on $I_{1,2}$.

subject to conditions $u^{i}(P)=U_{i}$ for a set of linear functionals $u^{i}(P)$.

The solution $P^{\min}$ to this problem has a form $P^{\min}=P_{1}^{\min}\oplus P_{2}^{\min}$, where $P^{1,2}$ are solutions to the problems

subject to conditions $u^{i}(P_{1,2})=U_{i}^{1,2}$ and $\sum_{i\in I_{1,2}}p_{i}^{1,2}=\pi_{1,2}$ for some redistribution of the linear functionals values, $U_{i}=U_{i}^{1}+U_{i}^{2}$, and of the total probability, $1=\pi_{1}+\pi_{2}$ ($\pi_{1,2}\geq 0$) .

The solution to the divergence minimization problem is composed from solutions of the partial maximization problems. Let us call this property the separation of variables for incompatible events (because $I_{1}\cap I_{2}=\emptyset$).

This property is trivially valid for the Tsallis family (for $\alpha>0$, and for $\alpha<0$ with the change of minimization to maximization) and for the CR family. For the Rényi family it also holds (for $\alpha>0$, and for $\alpha<0$ with the change from minimization to maximization), because the Rényi entropy is a function of those trace–form entropies, their level sets coincide.

2 Additivity Property

The additivity property with respect to joining of subsystems is crucial both for the classical thermodynamics and for the information theory.

Let us consider a system which is result of joining of two subsystems. A state of the system is an ordered pair of the states of the subsystems and the space of states of the system is the Cartesian product of the subsystems spaces of state. For systems with finite number of states this means that if the states of subsystems are enumerated by indexes $j$ and $k$ then the states of the system are enumerated by pairs $jk$. The probability distribution for the whole system is $p_{jk}$, and for the subsystems the probability distributions are the marginal distributions $q_{j}=\sum_{k}p_{jk}$, $r_{k}=\sum_{j}p_{jk}$.

The additive functions of state are defined for each state of the subsystems and for a state of the whole system they are sums of these subsystem values:

where $v_{j}$ and $w_{k}$ are functions of the subsystems state.

In classical thermodynamics such functions are called the extensive quantities. For expected values of additive quantities the similar additivity condition holds:

Let us consider these expected values as functionals of the probability distributions: $u(\{p_{jk}\})$, $v(\{q_{j}\})$ and $w(\{r_{k}\})$. Then the additivity property for the expected values reads:

where $q_{j}$ and the $r_{k}$ are the marginal distributions.

Such a linear additivity property is impossible for non-linear entropy functionals, but under some independence conditions the entropy can behave as an extensive variable.

Let $P$ be a product of marginal distributions. This means that the subsystems are statistically independent: $p_{jk}=q_{j}r_{k}$. Assume also that the distribution $P^{*}$ is also a product of marginal distributions $p^{*}_{jk}=q^{*}_{j}r^{*}_{k}$. Then some entropies reveal the additivity property with respect to joining of independent systems.

The Rényi entropy $H_{{\rm R}\ \alpha}(P\|P^{*})=H_{{\rm R}\ \alpha}(Q\|Q^{*})+H_{{\rm R}\ \alpha}(R\|R^{*})$. For $\alpha\to\infty$ the Min-entropy also inherits this property.

This property implies the separation of variables for the entropy maximization problems if the system consists of independent subsystems, $p_{jk}=q_{j}r_{k}$. Let functionals $u^{1}(\{p_{jk}\}),\ldots u^{m}(\{p_{jk}\})$ be additive (28) (29) and let the relative entropy $H(P\|P^{*})$ be additive with respect to joining of independent systems. Assume that in equilibrium subsystems are also independent, $p^{*}_{jk}=q^{*}_{j}r^{*}_{k}$. Then the solution to the problem

is $p_{jk}^{\min}=q_{j}^{\min}r_{k}^{\min}$, where $q_{j}^{\min}$, $r_{k}^{\min}$ are solutions of partial problems:

for some redistribution of the additive functionals values $U_{i}=V_{i}+W_{i}$.

Let us call this property the separation of variables for independent subsystems.

Neither the CR, nor the Tsallis divergences families have the additivity property. It is proven ENTR3 that a function $H_{h}$ has the additivity property if and only if it is a convex combination of the Shannon and Burg entropies. See also Theorem 3 in Appendix.

Nevertheless, both the CR and the Tsallis families have the property of separation of variables for independent subsystems because of the coincidence of the level sets with the additive function, the Rényi entropy (for all $\alpha>0$).

The Tsallis entropy family has absolutely the same property of separation of variables as the Rényi entropy. To extend this property of the Rényi Tsallis entropies for negative $\alpha$, we have to change there min to max.

For the CR family the result sounds even better: because of better normalization, the separation of variables is valid for $H_{\rm CR\ \lambda}\to\min$ problem for all values $\lambda\in]-\infty,\infty[$.

The condition of independence of subsystems $p_{jk}=q_{j}r_{k}$ in (30) cannot be relaxed: if we assume $p^{*}_{jk}=q^{*}_{j}r^{*}_{k}$ only then the correlations between subsystems may emerge in the solution of the minimization problem. For example, without assumption of independence, for the Burg entropy, the method of Lagrange multipliers gives ($\phi_{i}$ and $\psi_{i}$ are the Lagrange multipliers):

and the subsystems are not independent in this state even if they are independent in equilibrium and the conditions are additive. These emergent correlations may be considered as spurious PresseGhosh2013 or may be interpreted as sensible ones for some finite systems far from thermodynamic limit for modelling of non-canonic ensembles ENTR1 . In any case, the use of entropies which are additive with respect to joining of independent subsystem does not guarantee independence of subsystems but allows only to separate variables under condition of independence.

The stronger condition was used by Shore and Johnson Shore1980 in the axiomatic derivation of the principle of maximum entropy and the principle of minimum divergence (or ‘cross-entropy’). They postulated that the MaxEnt distribution for the whole system is the product of the distributions of the subsystems if the known information (conditions) is the information about subsystems (Axiom III). Independence of subsystems in this axioms is not assumed but should be the consequence of the entropy maximization. This axiom can be called ‘separation of variables under independent conditions’. They supplement this assumption by the separation of variables for partition of the state space (Axiom IV), by the condition of uniqueness of the MaxEnt distribution (Axiom I), and by the requirement of the invariance with respect to the coordinate transformations (Axiom II). All these axioms together give the unique classical BGS entropy. For further discussion see PresseGhosh2013 .

Violation of the Shore and Johnson Axiom III leads to correlation between subsystems and this is an essential difference of the non-classical MaxEnt ensembles from the classical canonical ensembles.

We use the weaker assumption of separation of variables for independent subsystems and additive conditions. Its violation leads to much more counterintuitive consequences: Subsystems remain independent (condition) and other conditions are additive (30) but the solution of the MaxEnt problem is the product of distributions which are not solutions of the partial MaxEnt problems. In other words, the probability distribution for a subsystem is modified just by existence of another subsystem without any interactions and correlations.

It seems to be difficult to find a reason for such a behavior and therefore the assumption of separation of variables for independent subsystems and additive conditions is a sensible axiom. It is weaker than the Shore and Johnson Axiom III Shore1980 and, therefore, leads to a wider family of entropies than just a classical BGS entropy. This wider family includes the CR family (12) and the convex combination of the Shannon and the Burg entropies (10).

The question arises: is there any new divergence that has the following three properties: (i) the divergence $H(P\|P^{*})$ should decrease in Markov processes with equilibrium $P^{*}$, (ii) for minimization problems the separation of variables for independent subsystems holds and (iii) the separation of variables for incompatible events holds. A new divergence means here that it is not a function of a divergence from the CR family or from the convex combination of the Shannon and the Burg entropies.

The answer is: no, any divergence which has these three properties and is defined and differentiable for positive distributions is a monotone function of $H_{h}$ for $h(x)={\alpha}p^{\alpha}$ (${\alpha}\in]-\infty,\infty[$, ${\alpha}\neq 0,1$), that is, essentially, the CR family (12), or $h(x)=\beta x\ln x-(1-\beta)\ln x$ ($\beta\in$). If we relax the differentiability property, then we have to add to the CR family the limits for $\lambda\to\pm\infty$. For $\lambda\to+\infty$ we get the CR analogue of min-entropy

The limiting case for the CR family for $\lambda\to-\infty$ is less known but is also a continuous and piecewise differential Lyapunov function for the Master equation:

Both properties of separation of variables are based on the specific additivity properties: additivity with respect to the composition of independent systems and additivity with respect to the partitioning of the space of states. Separation of variables can be considered as a weakened form of additivity: not the minimized function should be additive but there exists such a monotonic transformation of scale after which the function becomes additive (and different transformations may be needed for different additivity properties).

3 “No More Entropies” Theorems

The classical Shannon work included the characterization of entropy by its properties. This meant that the classical notion of entropy is natural, and no more entropies are expected. In the seminal work of Rényi, again the characterization of entropy by its properties was proved, and for this, extended family the no more entropies theorem was proved too. In this section, we prove the next no more entropies theorem, where two one-parametric families are selected as sensible: the CR family and the convex combination of Shannon’s and Burg’s entropies. They are two branches of solutions of the correspondent functional equation and intersect at two points: Shannon’s entropy ($\lambda=1$ in the CR family) and Burg’s entropy ($\lambda=0$). We consider entropies as equivalent if their level sets coincide. In that sense, the Rényi entropy and the Tsallis entropy (with $\alpha>0$) are equivalent to the CR entropy with $\alpha-1=\lambda$, $\lambda>-1$.

Following Rényi, we consider entropies of incomplete distributions: $p_{i}\geq 0$, $\sum_{i}p_{i}\leq 1$. The divergence $H(P\|P^{*})$ is a $C^{1}$ smooth function of a pair of positive generalized probability distributions $P=(p_{i})$, $p_{i}>0$ and $P^{*}=(p^{*}_{i})$, $p^{*}_{i}>0$, $i=1,\ldots n$.

The following 3 properties are required for characterization of the “natural” entropies.

To provide the separation of variables for incompatible events together with the symmetry property we assume that the divergence is separable, possibly, after a scaling transformation: there exists such a function of two variables $f(p,p^{*})$ and a monotonic function of one variable $\phi(x)$ that $H(P\|P^{*})=\phi(\sum_{i}f(p_{i},p^{*}_{i}))$. This formula allows us to define $H(P\|P^{*})$ for all $n$.

$H(P\|P^{*})$ is a Lyapunov function for the Kolmogorov equation (22) for any Markov chain with equilibrium $P^{*}$. (One can call these functions the universal Lyapunov functions because they do not depend on the kinetic coefficients directly, but only on the equilibrium distribution $P^{*}$.)

To provide separation of variables for independent subsystems we assume that $H(P\|P^{*})$ is additive (possibly after a scaling transformation): there exists such a function of one variable $\psi(x)$ that the function $\psi(H(P\|P^{*}))$ is additive for the union of independent subsystems: if $P=(p_{ij})$, $p_{ij}=q_{j}r_{j}$, $p^{*}_{ij}=q^{*}_{j}r^{*}_{j}$, then $\psi(H(P\|P^{*}))=\psi(H(Q\|Q^{*}))+\psi(H(R\|R^{*}))$.

In a paper ENTR3 this family was identified as the Tsallis relative entropy with some abuse of language, because in the Tsallis entropy the case with $\alpha<0$ is usually excluded.

First of all, let us prove that any function which satisfies the conditions 1 and 2 is a monotone function of a Csiszár–Morimoto function (6) for some convex smooth function $h(x)$. This was mentioned in 2003 by P. Gorban ENTR3 . Recently, a similar statement was published by S. Amari (Theorem 1 in Amari2009 ).

If a Lyapunov function $H(p)$ for the Markov chain is of the trace–form ($H(p)=\sum_{i}f(p_{i},p_{i}^{*})$) and is universal, then $f(p,p^{*})=p^{*}h(\frac{p}{p^{*}})+{\rm const}(p^{*})$, where $h(x)$ is a convex function of one variable.

Let us consider a Markov chain with two states. For such a chain

If $H$ is a Lyapunov function then $\dot{H}\leq 0$ and the following inequality holds:

We can consider $p_{1},p_{2}$ as independent variables from an open triangle $D=\{(p_{1},p_{2})\ |\ p_{1,2}>0,\ p_{1}+p_{2}<1\}$. For this purpose, we can include the Markov with two states into a chain with three states and $q_{3i}=q_{i3}=0$.

This lemma has important corollaries about many popular divergences $H(P(t)\|P^{*})$ which are not Lyapunov functions of Markov chains. This means that there exist such distributions $P_{0}$ and $P^{*}$ and a Markov chain with equilibrium distribution $P^{*}$ that due to the Kolmogorov equations

if $P(0)=P_{0}$. This Markov process increases divergence between the distributions $P,P^{*}$ (in a vicinity of $P_{0}$) instead of making them closer. For example,

The following Bregman divergences Bregman1967 are not universal Lyapunov functions for Markov chains:

Squared Euclidean distance $B(P\|P^{*})=\sum_{i}(p_{i}-p^{*}_{i})^{2}$;

The Itakura–Saito divergence Itakura1968 $B(P\|P^{*})=\sum_{i}\left(\frac{p_{i}}{p_{i}^{*}}-\log\frac{p_{i}}{p_{i}^{*}}-1\right)$. $\ \ \ \square$

These divergences violate the requirement: due to the Markov process distributions always monotonically approach equilibrium. (Nevertheless, among the Bregman divergences there exists a universal Lyapunov function for Markov chains, the Kulback–Leibler divergence.)

We place the proof of Theorem 1 in Appendix.

Remark. If we relax the requirement of smoothness and consider in conditions of Theorem 1 just continuous functions, then we have to add to the answer the limit divergences,

Markov Order

Theorem 1 gives us all of the divergences for which (i) the Markov chains monotonically approach their equilibrium, (ii) the level sets are the same as for a separable (sum over states) divergence and (iii) the level sets are the same as for a divergence which is additive with respect to union of independent subsystems.

We operate with the level sets and their orders, compare where the divergence is larger (for monotonicity of the Markov chains evolution), but the values of entropy are not important by themselves. We are interested in the following order: $P$ precedes $Q$ with respect to the divergence $H_{\ldots}(P\|P^{*})$ if there exists such a continuous curve $P(t)$ ($t\in$) that $P(0)=P$, $P(1)=Q$ and the function $H(t)=H_{\ldots}(P(t)\|P^{*})$ monotonically decreases on the interval $t\in$. This property is invariant with respect to a monotonic (increasing) transformation of the divergence. Such a transformation does not change the conditional minimizers or maximizers of the divergence.

There exists one important property that is not invariant with respect to monotonic transformations. The increasing function $F(H)$ of a convex function $H(P)$ is not obligatorily a convex function. Nevertheless, the sublevel sets given by inequalities $H(P)\leq a$ coincide with the sublevel sets $F(H(P))\leq F(a)$. Hence, sublevel sets for $F(H(P))$ remain convex.

($\theta\in$) is not invariant with respect to monotonic transformations. Instead of them, there appears the max form analogue of the Jensen inequality (quasiconvexity Sion1958 ):

This inequality is invariant with respect to monotonically increasing transformations and it is equivalent to convexity of sublevel sets.

All sublevel sets of a function $H$ on a convex set $V$ are convex if and only if for any two points $P,Q\in V$ and every $\theta\in$ the inequality (32) holds. $\square$

2 Description of Markov Order

The CR family and the convex combinations of Shannon’s and Burg relative entropies are distinguished families of divergences. Apart from them there are many various “divergences”, and even the Csiszár–Morimoto functions (6) do not include all used possibilities. Of course, most users prefer to have an unambiguous choice of entropy: it would be nice to have “the best entropy” for any class of problems. But from some point of view, ambiguity of the entropy choice is unavoidable. In this section we will explain why the choice of entropy is necessarily non unique and demonstrate that for many MaxEnt problems the natural solution is not a fixed distribution, but a well defined set of distributions.

The most standard use of divergence in many application is as follows:

On a given space of states an “equilibrium distribution” $P^{*}$ is given. If we deal with the probability distribution in real kinetic processes then it means that without any additional restriction the current distribution will relax to $P^{*}$. In that sense, $P^{*}$ is the most disordered distribution. On the other hand, $P^{*}$ may be considered as the “most disordered” distribution with respect to some a priori information.

We do not know the current distribution $P$, but we do know some linear functionals, the moments $u(P)$.

We do not want to introduce any subjective arbitrariness in the estimation of $P$ and define it as the “most disordered” distribution for given value $u(P)=U$ and equilibrium $P^{*}$. That is, we define $P$ as solution to the problem:

Without the condition $u(P)=U$ the solution should be simply $P^{*}$.

Now we have too many entropies and do not know what is the optimal choice of $H_{\ldots}$ and what should be the optimal estimate of $P$. In this case the proper question may be: which $P$ could not be such an optimal estimate? We can answer the exclusion question. Let for a given $P^{0}$ the condition hold, $u(P^{0})=U$. If there exists a Markov process with equilibrium $P^{*}$ such that at point $P^{0}$ due to the Kolmogorov equation (22)

then $P^{0}$ cannot be the optimal estimate of the distribution $P$ under condition $u(P)=U$.

The motivation of this approach is simple: any Markov process with equilibrium $P^{*}$ increases disorder and brings the system “nearer” to the equilibrium $P^{*}$. If at $P^{0}$ it is possible to move along the condition plane towards the more disordered distribution then $P^{0}$ cannot be considered as an extremely disordered distribution on this plane. On the other hand, we can consider $P^{0}$ as a possible extremely disordered distribution on the condition plane, if for any Markov process with equilibrium $P^{*}$ the solution of the Kolmogorov equation (22) $P(t)$ with initial condition $P(0)=P^{0}$ has no points on the plane $u(P)=U$ for $t>0$.

Markov process here is considered as a “randomization”. Any set $C$ of distributions can be divided in two parts: the distributions which retain in $C$ after some non-trivial randomization and the distributions which leave $C$ after any non-trivial randomization. The last are the maximally random elements of $C$: they cannot become more random and retain in $C$. Conditional minimizers of relative entropies $H_{h}(P\|P^{*})$ in $C$ are maximally random in that sense.

There are too many functions $H_{h}(P\|P^{*})$ for effective description of all their conditional minimizers. Nevertheless, we can describe the maximally random distributions directly, by analysis of Markov processes.

To analyze these properties more precisely, we need some formal definitions.

(Markov preorder). If for distributions $P^{0}$ and $P^{1}$ there exists such a Markov process with equilibrium $P^{*}$ that for the solution of the Kolmogorov equation with $P(0)=P^{0}$ we have $P(1)=P^{1}$ then we say that $P^{0}$ and $P^{1}$ are connected by the Markov preorder with equilibrium $P^{*}$ and use notation $P^{0}\succ^{0}_{P^{*}}P^{1}$.

Markov order is the closed transitive closure of the Markov preorder. For the Markov order with equilibrium $P^{*}$ we use notation $P^{0}\succ_{P^{*}}P^{1}$.

For a given $P^{*}=(p^{*}_{i})$ and a distribution $P=(p_{i})$ the set of all vectors $v$ with coordinates

where $p_{i}^{*}$ and $q_{ij}\geq 0$ are connected by identity (23) is a closed convex cone. This is a cone of all possible time derivatives of the probability distribution at point $P$ for Markov processes with equilibrium $P^{*}=(p^{*}_{i})$. For this cone, we use notation $\mathbf{Q}_{(P,P^{*})}$

For each distribution $P$ and a $n$-dimensional vector $\Delta$ we say that $\Delta<_{(P,P^{*})}0$ if $\Delta\in\mathbf{Q}_{(P,P^{*})}$. This is the local Markov order.

$\mathbf{Q}_{(P,P^{*})}$ is a proper cone, i.e., it does not include any straight line.

The connection between the local Markov order and the Markov order gives the following proposition, which immediately follows from definitions.

$P^{0}\succ_{P^{*}}P^{1}$ if and only if there exists such a continuous almost everywhere differentiable curve $P(t)$ in the simplex of probability distribution that $P(0)=P^{0}$, $P(1)=P^{1}$ and for all $t\in$, where $P(t)$ is differentiable,

For our purposes, the following estimate of the Markov order through the local Markov order is important.

If $P^{0}\succ_{P^{*}}P^{1}$ then $P^{0}>_{(P^{0},P^{*})}P^{1}$, i.e., $P^{1}-P^{0}\in\mathbf{Q}_{(P,P^{*})}$.

This proposition follows from the characterization of the local order and detailed description of the cone $\mathbf{Q}_{(P(t),P^{*})}$ (Theorem 2 below).

Let us recall that a convex pointed cone is a convex envelope of its extreme rays. A ray with directing vector $x$ is a set of points $\lambda x$ ($\lambda\geq 0$). We say that $l$ is an extreme ray of $\mathbf{Q}$ if for any $u\in l$ and any $x,y\in\mathbf{Q}$, whenever $u=(x+y)/2$, we must have $x,y\in l$. To characterize the extreme rays of the cones of the local Markov order $\mathbf{Q}_{(P,P^{*})}$ we need a graph representation of the Markov chains. We use the notation $A_{i}$ for states (vertices), and designate transition from state $A_{i}$ to state $A_{j}$ by an arrow (edge) $A_{i}\to A_{j}$. This transition has its transition intensity $q_{ji}$ (the coefficient in the Kolmogorov equation (21)).

Any extreme ray of the cone $\mathbf{Q}_{(P,P^{*})}$ corresponds to a Markov process which transition graph is a simple cycle

where $k\leq n$, all the indices $i_{1},\ldots i_{k}$ are different, and transition intensities for a directing vector of such an extreme ray $q_{i_{j+1}\ i_{j}}$ may be selected as $1/p_{i_{j}}^{*}$:

(here we use the standard convention that for a cycle $q_{i_{k+1}\ i_{k}}=q_{i_{1}\ i_{k}}$).

First of all, let us mention that if for three vectors $x,y,u\in\mathbf{Q}_{(P,P^{*})}$ we have $u=(x+y)/2$ then the set of transitions with non-zero intensities for corresponding Markov processes for $x$ and $y$ are included in this set for $u$ (because negative intensities are impossible). Secondly, just by calculation of the free variables in the equations (23) (with additional condition) we find that the the amount of non-zero intensities for a transition scheme which represents an extreme ray should be equal to the amount of states included in the transition scheme. Finally, there is only one scheme with $k$ vertices, $k$ edges and a positive equilibrium, a simple oriented cycle.∎

Any extreme ray of the cone $\mathbf{Q}_{(P,P^{*})}$ corresponds to a Markov process whose transition graph is a simple cycle of the length 2: $A_{i}\rightleftarrows A_{j}$. A transition intensities $q_{ij},\ q_{ji}$ for a directing vector of such an extreme ray may be selected as

Due to Lemma 2, it is sufficient to prove that for any distribution $P$ the right hand side of the Kolmogorov equation (22) for a simple cycle with transition intensities (35) is a conic combination (the combination with non-negative real coefficients) of the right hand sides of this equation for simple cycles of the length 2 at the same point $P$. Let us prove this by induction. For the cycle length 2 it is trivially true. Let this hold for the cycle lengths $2,\ldots n-1$. For a cycle of length $n$, $A_{i_{1}}\to A_{i_{2}}\to\ldots A_{i_{k}}\to A_{i_{1}}$, with transition intensities given by (35) the right hand side of the Kolmogorov equation is the vector $v$ with coordinates

(under the standard convention regarding cyclic order). Other coordinates of $v$ are zeros. Let us find the minimal value of ${p_{i_{j}}}/{p^{*}_{i_{j}}}$ and rearrange the indices by a cyclic permutation to put this minimum in the first place:

The vector $v$ is a sum of two vectors: a directing vector for the cycle $A_{i_{2}}\to\ldots A_{i_{k}}\to A_{i_{2}}$ of the length $n-1$ with transition intensities given by formula (35) (under the standard convention about the cyclic order for this cycle) and a vector

where $v^{2}$ is the directing vector for a cycle of length 2, $A_{i_{1}}\rightleftarrows A_{i_{2}}$ which can have only two non-zero coordinates:

The coefficient in front of $v^{2}$ is positive because ${p_{i_{1}}}/{p^{*}_{i_{1}}}$ is the minimal value of ${p_{i_{j}}}{p^{*}_{i_{j}}}$. A case when ${p_{i_{1}}}/{p^{*}_{i_{1}}}={p_{i_{2}}}/{p^{*}_{i_{2}}}$ does not need special attention because it is equivalent to the shorter cycle $A_{i_{1}}\to A_{i_{3}}\to\ldots A_{i_{k}}\to A_{i_{1}}$ ($A_{i_{2}}$ could be omitted). A conic combination of conic combinations is a conic combination again.∎

It is quite surprising that the local Markov order and, hence, the Markov order also are generated by the reversible Markov chains which satisfy the detailed balance principle. We did not include any reversibility assumptions, and studied the general Markov chains. Nevertheless, for the study of orders, the system of cycles of length 2 all of which have the same equilibrium is sufficient.

3 Combinatorics of Local Markov Order

Let us describe the local Markov order in more detail. First of all, we represent kinetics of the reversible Markov chains. For each pair $A_{i},A_{j}$ ($i\neq j$) we select an arbitrary order in the pair and write the correspondent cycle of the length 2 in the form $A_{i}\leftrightarrows A_{j}$. For this cycle we introduce the directing vector $\gamma^{ij}$ with coordinates

where $\delta_{ik}$ is the Kronecker delta. This vector has the $i$th coordinate $-1$, the $j$th coordinate $1$ and other coordinates are zero. Vectors $\gamma^{ij}$ are parallel to the edges of the standard simplex in $R^{n}$. They are antisymmetric in their indexes: $\gamma^{ij}=-\gamma^{ji}$.

We can rewrite the Kolmogorov equation in the form

where $i\neq j$, each pair is included in the sum only once (in the preselected order of $i,j$) and

The coefficient $r_{ji}\geq 0$ satisfies the detailed balance principle:

With this function we can rewrite Equation (38) again as follows:

The non-zero coefficients $r_{ji}$ may be arbitrary positive numbers. Therefore, using Theorem 2, we immediately find that the cone of the local Markov order at point $P$ is

where cone$\{\}$ stands for the conic hull.

The number ${\rm sign}\left(\frac{p_{i}}{p_{i}^{*}}-\frac{p_{j}}{p_{j}^{*}}\right)$ is 1, when $\frac{p_{i}}{p_{i}^{*}}>\frac{p_{j}}{p_{j}^{*}}$, $-1$, when $\frac{p_{i}}{p_{i}^{*}}<\frac{p_{j}}{p_{j}^{*}}$ and 0, when $\frac{p_{i}}{p_{i}^{*}}=\frac{p_{j}}{p_{j}^{*}}$. For a given $P^{*}$, the standard simplex of distributions $P$ is divided by planes $\frac{p_{i}}{p_{i}^{*}}=\frac{p_{j}}{p_{j}^{*}}$ into convex polyhedra where functions ${\rm sign}\left(\frac{p_{i}}{p_{i}^{*}}-\frac{p_{j}}{p_{j}^{*}}\right)$ are constant. In these polyhedra the cone of the local Markov order (41) $\mathbf{Q}_{(P,P^{*})}$ is also constant. Let us call these polyhedra compartments.

In Figure 5.3 we represent compartments and cones of the local Markov order for the Markov chains with three states, $A_{1,2,3}$. The reversible Markov chain consists of three reversible transitions $A_{1}\leftrightarrows A_{2}\leftrightarrows A_{3}\leftrightarrows A_{1}$ with corresponding directing vectors $\gamma^{12}=(-1,1,0)^{\top}$; $\gamma^{23}=(0,-1,1)^{\top}$; $\gamma^{31}=(1,0,-1)^{\top}$. The topology of the partitioning of the standard simplex into compartments and the possible values of the cone $\mathbf{Q}_{(P,P^{*})}$ do not depend on the position of the equilibrium distribution $P^{*}$.

Let us describe all possible compartments and the correspondent local Markov order cones. For every natural number $k\leq n-1$ the $k$-dimensional compartments are numerated by surjective functions $\sigma:\{1,2,\ldots,n\}\to\{1,2,\ldots,k+1\}$. Such a function defines the partial ordering of quantities $\frac{p_{j}}{p_{j}^{*}}$ inside the compartment:

Let us use for the correspondent compartment notation $\mathcal{C}_{\sigma}$ and for the Local Markov order cone $Q_{\sigma}$. Let $k_{i}$ be a number of elements in preimage of $i$ ($i=1,\ldots,k$): $k_{i}=|\{j\ |\ \sigma(j)=i\}|$. It is convenient to represent surjection $\sigma$ as a tableau with $k$ rows and $k_{i}$ cells in the $i$th row filled by numbers from $\{1,2,\ldots,n\}$. First of all, let us draw diagram, that is a finite collection of cells arranged in left-justified rows. The $i$th row has $k_{i}$ cells. A tableau is obtained by filling cells with numbers $\{1,2,\ldots,n\}$. Preimages of $i$ are located in the $i$th row. The entries in each row are increasing. (This is convenient to avoid ambiguity of the representation of the surjection $\sigma$ by the diagram.) Let us use for tableaus the same notation as for the corresponding surjections.