# Divergence and Sufficiency for Convex Optimization

Peter Harremoës

###### Abstract

Logarithmic score and information divergence appear in information theory,
statistics, statistical mechanics, and portfolio theory. We demonstrate that
all these topics involve some kind of optimization that leads directly to
regret functions and such regret functions are often given by a Bregman
divergence. If the regret function also fulfills a sufficiency condition it
must be proportional to information divergence. We will demonstrate that
sufficiency is equivalent to the apparently weaker notion of locality and it
is also equivalent to the apparently stronger notion of monotonicity. These
sufficiency conditions have quite different relevance in the different areas
of application, and often they are not fulfilled. Therefore sufficiency
conditions can be used to explain when results from one area can be
transferred directly to another and when one will experience differences.

##  1 Introduction

One of the main purposes of information theory is to compress data so that
data can be recovered exactly or approximately. One of the most important
quantities was called entropy because it is calculated according to a formula
that mimics the calculation of entropy in statistical mechanics. Another key
concept in information theory is information divergence (KL-divergence) that
is defined for probability vectors $P$ and $Q$ as

$D\left(P\|Q\right)=\sum_{x}P(x)\ln\frac{P(x)}{Q(x)}.$

It was introduced by Kullback and Leibler in 1951 in a paper entitled
information and sufficiency Kullback and Leibler (1951). The link from
information theory back to statistical physics was developed by E.T. Jaynes
via the maximum entropy principle Jaynes (1957, 1989). The link back to
statistics is now well established Liese and Vajda (1987); Barron et al.
(1998); Csiszár and Shields (2004); Grünwald and Dawid (2004); Grünwald
(2007).

Related quantities appear in information theory, statistics, statistical
mechanics, and finance, and we are interested in a theory that describes when
these relations are exact and when they just work by analogy. First we
introduce some general results about optimization on state spaces of finite
dimensional C*-algebras. This part applies exactly to all the topics under
consideration and lead to Bregman divergences. Secondly, we introduce several
notions of sufficiency and show that this leads to information divergence.
This second step is not always applicable which explains when the different
topics are really different.

##  2 Structure of the state space

Our knowledge about a system will be represented by a state space. I many
cases the state space is given by a set of probability distributions on a
sample space. In such cases the state space is a simplex, but it is well-known
that the state space is not a simplex in quantum physics. For applications in
quantum physics the state space is often represented by a set of density
matrices, i.e. positive semidefinite complex matrices with trace 1. In some
cases the states are represented as elements of a finite dimensional
$C^{*}$-algebra, which is a direct sum of matrix algebras. A finite
dimensional $C^{*}$-algebra that is a sum of $1\times 1$ matrices has a state
space that is a simplex, so the state spaces of finite dimensional
$C^{*}$-algebras contain the classical probability distributions as special
cases.

The extreme points in the set of states are the pure states. The pure states
of a $C^{*}$-algebra can be identified with projections of rank 1. Two density
matrices $s_{1}$ and $s_{2}$ are said to be orthogonal if
$s_{1}s_{2}=s_{2}s_{1}=0.$ Any state $s$ has a decomposition

$s=\sum\lambda_{i}s_{i}$

where $s_{i}$ are orthogonal pure states. Such a decomposition is not unique,
but for a finite dimensional $C^{*}$-algebra the coefficients
$\lambda_{1},\lambda_{2},\dots,\lambda_{n}$ are unique and are called the
spectrum of the state.

Sometimes more general state spaces are of interest. In generalized
probabilistic theories a state space is a convex set where mixtures are
defined by randomly choosing certain states with certain probabilities Holevo
(1982); Krumm et al. (2016). A convex set where all orthogonal decompositions
of a state have the same spectrum is called a spectral state space. Much of
the theory in this paper can be generalized to spectral sets. The most
important spectral sets are sets of positive elements with trace 1 in Jordan
algebras. For questions related to the foundation of quantum theory the Jordan
algebras and other spectral sets give new insight Barnum et al. (2014);
Harremoës (2016, 2017), but in this paper we will restrict our attention to
states on finite dimensional $C^{*}$-algebras. Nevertheless some of the
theorems and proofs are stated in such a way that they hold for more general
state spaces.

##  3 Optimization

Let $\mathcal{S}$ denotes a state space of a finite dimensional
$C^{*}$-algebra and let $\mathcal{A}$ denote a set of self-adjoint operators.
Each $a\in\mathcal{A}$ is identified with a real valued measurement. The
elements of $\mathcal{A}$ may represent feasible _actions_ (decisions) that
lead to a payoff like the score of a statistical decision, the energy
extracted by a certain interaction with the system, (minus) the length of a
codeword of the next encoded input letter using a specific code book, or the
revenue of using a certain portfolio. For each $s\in\mathcal{S}$ the mean
value of the measurement $a\in\mathcal{A}$ is given by

$\left\langle a,s\right\rangle=\rm{tr}(as).$

In this way the set of actions may be identified with a subset of the dual
space of $\mathcal{S}$. Next we define

$F\left(s\right)=\sup_{a\in\mathcal{A}}\left\langle a,s\right\rangle.$

We note that $F$ is convex, but $F$ need not be strictly convex. In principle
$F(s)$ may be infinite but we will assume that $F(s)<\infty$ for all states
$s$. We also note that $F$ is lower semi-continuous. In this paper we will
assume that the function $F$ is continuous. The assumption that $F$ real
valued continuous function is fulfilled for all the applications we consider.

If $s$ is a state and $a\in\mathcal{A}$ is an action then we say that $a$ is
optimal for $s$ if $\left\langle a,s\right\rangle=F\left(s\right)$. A sequence
of actions $a_{n}\in\mathcal{A}$ is said to be asymptotically optimal for the
state $s$ if $\left\langle a,s\right\rangle\to F\left(s\right)$ for
$n\to\infty.$

If $a_{i}$ are actions and $\left(t_{i}\right)$ is a probability vector then
we we may define the mixed action $\sum t_{i}\cdot a_{i}$ as the action where
we do the action $a_{i}$ with probability $t_{i}.$ We note that
$\left\langle\sum t_{i}\cdot a_{i},s\right\rangle=\sum t_{i}\cdot\left\langle
a_{i},s\right\rangle.$ We will assume that all such mixtures of feasible
actions are also feasible. If $a_{1}\left(s\right)\geq a_{2}\left(s\right)$
almost surely for all states we say that $a_{1}$ dominates $a_{2}$ and if
$a_{1}\left(s\right)>a_{2}\left(s\right)$ almost surely for all states $s$ we
say that $a_{1}$ strictly dominates $a_{2}.$ All actions that are dominated
may be removed from $\mathcal{A}$ without changing the function $F.$ Let
$\mathcal{A}_{F}$ denote the set of self-adjoint operators (observables) such
that $\left\langle m,s\right\rangle\leq F\left(s\right).$ Then
$F\left(s\right)=\sup_{a\in\mathcal{A}_{F}}\left\langle a,s\right\rangle.$
Therefore we may replace $\mathcal{A}$ by $\mathcal{A}_{F}$ without changing
the optimization problem.

In the definition of regret we follow Servage Servage (1951) but with
different notation.

######  Definition 1.

Let $F$ denote a convex function on the state space $\mathcal{S}$. If
$F\left(s\right)$ is finite _the regret_ of the action $a$ is defined by

$D_{F}\left(s,a\right)=F\left(s\right)-\left\langle a,s\right\rangle.$ (1)

######  Proposition 1.

The regret $D_{F}$ of actions has the following properties:

  * •

$D_{F}\left(s,a\right)\geq 0$ with equality if $a$ is optimal for $s$.

  * •

$s\to D_{F}\left(s,a\right)$ is a convex function.

  * •

If $\bar{a}$ is optimal for the state $\bar{s}=\sum t_{i}\cdot s_{i}$ where
$\left(t_{1},t_{2},\dots,t_{\ell}\right)$ is a probability vector then

$\sum t_{i}\cdot D_{F}\left(s_{i},a\right)=\sum t_{i}\cdot
D_{F}\left(s_{i},\bar{a}\right)+D_{F}\left(\bar{s},a\right).$

  * •

$\sum t_{i}\cdot D_{F}\left(s_{i},a\right)$ is minimal if $a$ is optimal for
$\bar{s}=\sum t_{i}\cdot s_{i}$.

$0$$1$$D_{F}(s_{1},s_{0})$$f(t)$$t$ Figure 1: The regret equals the vertical
distance between curve and tangent.

If the state is $s_{1}$ but one acts as if the state were $s_{0}$ one may
compare what one achieves and what could have been achieved. If the state
$s_{0}$ has a unique optimal action $a$ we may simply define the regret of
$s_{0}$ by

$D_{F}\left(s_{1},s_{0}\right)=D_{F}\left(s_{1},a\right)$

The following definition leads to a regret function that is essentially
equivalent to the so-called generalized Bregman divergences defined by Kiwiel
Kiwiel (1997a, b).

######  Definition 2.

Let $F$ denote a convex function on the state space $\mathcal{S}$. If
$F\left(s_{1}\right)$ is finite then we define _the regret of the state_
$s_{0}$ as

$D_{F}\left(s_{1},s_{0}\right)=\inf_{\left(a_{n}\right)}\lim_{n\to\infty}D_{F}\left(s_{1},a\right)$

where the infimum is taken over all sequences of actions $\left(a_{n}\right)$
that are asymptotically optimal for $s_{0}.$

With this definition the regret is always defined with values in $[0,\infty$.
We note that with this definition the value of the regret
$D_{F}\left(s_{1},s_{0}\right)$ only depends on the restriction of the
function $F$ to the line segment from $s_{0}$ to $s_{1}$. Let $f$ denote the
function $f(t)=F\left((1-t)s_{0}+ts_{1}\right)$ where $t\in[0,1]$. As
illustrated in Figure 1 we have

$D_{F}\left(s_{1},s_{0}\right)=f\left(1\right)-\left(f\left(0\right)+f^{\prime}_{+}(0)\right)$
(2)

where $f^{\prime}_{+}(0)$ denotes the right derivative of $f$ at $t=0$.
Equation (2) is even valid when the regret is infinite if we allow the right
derivative to take the value $\infty$.

If the state $s_{0}$ has the unique optimal action $a\in\mathcal{A}$ then

$F\left(s_{1}\right)=D_{F}\left(s_{1},s_{0}\right)+\left\langle
a,s_{1}\right\rangle$ (3)

so the function $F$ can be reconstructed from $D_{F}$ except for an affine
function of $s_{1}.$ The closure of the convex hull of the set of functions
$s\to\left\langle a,s\right\rangle$ is uniquely determined by the convex
function $F.$ The following proposition follows from Alexandrov’s theorem. See
(Rockafellar, 1970, Theorem 25.5) for details.

######  Proposition 2.

A convex function on a finite dimensional convex set is differentiable almost
everywhere with respect to the Lebesgue measure.

A state $s_{0}$ where $F$ is differentiable has a unique optimal action.
Therefore Equation (3) holds for almost any state $s_{0}$. In particular the
function $F$ can be reconstructed from $D_{F}$ except for an affine function.

######  Proposition 3.

The regret $D_{F}$ of states has the following properties:

  * •

$D_{F}\left(s_{1},s_{0}\right)\geq 0$ with equality if there exists an action
$a$ that is optimal for both $s_{1}$ and $s_{0}$.

  * •

$s_{1}\to D_{F}\left(s_{1},s_{0}\right)$ is a convex function.

Further the following two conditions are equivalent.

  * •

$D_{F}\left(s_{1},s_{0}\right)=0$ implies $s_{1}=s_{0}$ .

  * •

The function $F$ is strictly convex.

We say that a regret function $D_{F}$ is strict if $F$ is strictly convex. The
two last properties Proposition 1 do not carry over to regret for states
except if the regret is a Bregman divergence as defined below. The regret is
called a _Bregman divergence_ if it can be written in the following form

$\displaystyle D_{F}\left(s_{1},s_{0}\right)$
$\displaystyle=F\left(s_{1}\right)-\left(F\left(s_{0}\right)+\left\langle
s_{1}-s_{0},\nabla F\left(s_{0}\right)\right\rangle\right)$ (4)

where $\left\langle\cdot,\cdot\right\rangle$ denotes the (Hilbert-Smidt) inner
product. In the context of forecasting and statistical scoring rules the use
of Bregman divergences dates back to Hendrickson and Buehler (1971). A similar
but less general definition of regret was given by Rao and Nayak Rao and Nayak
(1985) where the name _cross entropy_ was proposed. Although Bregman
divergences have been known for many years they did not gain popularity before
the paper Banerjee et al. (2005) where a systematic study of Bregman
divergences was presented.

We note that if $D_{F}$ is a Bregman divergence and $s_{0}$ minimizes $F$ then
$\nabla F\left(s_{0}\right)=0$ so that the formula for the Bregman divergence
reduces to

$D_{F}\left(s_{1},s_{0}\right)=F\left(s_{1}\right)-F\left(s_{0}\right).$

Bregman divergences satisfy the _Bregman identity_

$\sum t_{i}\cdot D_{F}\left(s_{i},s\right)=\sum t_{i}\cdot
D_{F}\left(s_{i},\bar{s}\right)+D_{F}\left(\bar{s},s\right),$ (5)

but if $F$ is not differentiable this identity can be violated.

######  Example 1.

Let the state space be the interval $\left[0,1\right]$ with two actions
$\left<a_{0},s\right>=1-2s$ and $\left<a_{1},s\right>=2s-1.$ Let $s_{0}=0$ and
$s_{1}=1.$ Let further $t_{0}=\nicefrac{{1}}{{3}}$ and
$t_{1}=\nicefrac{{2}}{{3}}.$ Then $\bar{s}=\nicefrac{{2}}{{3}}.$ If
$s=\nicefrac{{1}}{{2}}$ then

$\sum t_{i}\cdot D_{F}\left(s_{i},s\right)=0,$

but

$\displaystyle\sum t_{i}\cdot D_{F}\left(s_{i},\bar{s}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{3}\cdot\left(\left<a_{0},0\right>-\left<a_{1},0\right>\right)+\frac{2}{3}\cdot\left(\left<a_{1},1\right>-\left<a_{1},1\right>\right)$
$\displaystyle=$ $\displaystyle\frac{1}{3}\cdot\left(1-\left(-1\right)\right)$
$\displaystyle=$ $\displaystyle\frac{2}{3}.$

Clearly the Bregman identity (5) is violated and $\sum t_{i}\cdot
D_{F}\left(s_{i},s\right)$ will increase if $s$ is replaced by $\bar{s}$.

The following proposition is easily proved.

######  Proposition 4.

For a convex and continuous function $F$ the following conditions are
equivalent.

  * •

The function $F$ is differentiable.

  * •

The regret $D_{F}$ is a Bregman divergence.

  * •

The Bregman identity is always satisfied.

  * •

For any probability vectors $\left(t_{1},t_{2},\dots,t_{n}\right)$ the sum
$\sum t_{i}\cdot D_{F}\left(s_{i},s\right)$ is always minimal when $s=\sum
t_{i}\cdot s_{i}$ .

##  4 Examples

In this section we shall see how regret functions are defined in some
applications.

###  4.1 Information theory

We recall that a code is uniquely decodable if any finite sequence of input
symbols give a unique sequence of output symbols. It is well-known that a
uniquely decodable code satisfies Kraft’s inequality

$\sum_{a\in\mathbb{A}}\beta^{\textrm{-}\ell\left(a\right)}\leq 1$ (6)

where $\ell\left(a\right)$ denotes the length of the codeword corresponding to
the input symbol $a\in\mathbb{A}$ and $\beta$ denotes the size of the output
alphabet $\mathbb{B}$. Here the length of a codeword is an integer. If
$P=\left(p_{a}\right)_{a\in\mathbb{A}}$ is a probability vector over the input
alphabet, then the mean code-length is

$\sum_{a\in\mathbb{A}}\ell\left(a\right)\cdot p_{a}.$

Our goal is to minimize the expected code-length. Here the state space consist
of probability distributions over the input alphabet and the actions are code-
length functions.

Shannon established the inequality

$-\sum_{a\in\mathbb{A}}\log_{b}\left(p_{a}\right)\cdot
p_{a}\leq\min\sum_{a\in\mathbb{A}}\ell\left(a\right)\cdot
p_{a}\leq-\sum_{a\in\mathbb{A}}\log_{b}\left(p_{a}\right)\cdot p_{a}+1.$

It is a combinatoric problem to find the optimal code length function. In the
simplest case with a binary output alphabet the optimal code-length function
is determined by the Huffmann algorithm.

A code-length function dominates another code-length function if all letters
have it has shorter code-length. If a code-length function is not dominated by
another code-length function then for all $a\in\mathbb{A}$ the length is
bounded by $\ell\left(a\right)\leq\left|\mathbb{A}\right|-1.$ For fixed
alphabets $\mathbb{A}$ and $\mathbb{B}$ there exists only a finite number of
code-length functions $\ell$ that satisfy Kraft’s inequality and are not
dominated by other code-length functions that satisfying Kraft’s inequality.

###  4.2 Scoring rules

The use of scoring rules has a long history in statistics. An early
contribution was the idea of minimizing the sum of square deviations that
dates back to Gauss and works perfectly for Gaussian distributions. In the
1920s Ramsay and de Finetti proved versions of the Dutch book theorem where
determination of probability distributions were considered as dual problems of
maximizing a payoff function. Later it was proved that any consistent
inference procedure corresponds to optimizing with respect to some payoff
function. A more systematic study of scoring rules was given by McCarthy
McCarthy (1956).

Consider an experiment with $\mathcal{X}=\left\\{1,2,\dots,\ell\right\\}$ as
sample space. A _scoring rule_ $f$ is defined as a function $\mathcal{X}\times
M_{1}^{+}\left(\mathcal{X}\right)\to\mathbb{R}$ such that the score is
$f\left(x,Q\right)$ when a prediction has been given in terms of a probability
distribution $Q$ and $x\in\mathcal{X}$ has been observed. A scoring rule is
_proper_ if for any probability measure $P\in
M_{1}^{+}\left(\mathcal{X}\right)$ the score
$\sum_{x\in\mathcal{X}}P\left(x\right)\cdot f\left(x,Q\right)$ is minimal when
$Q=P.$ Here the state space consist of probability distributions over
$\mathcal{X}$ and the actions are predictions over $\mathcal{X}$, which are
also probability distributions over $\mathcal{X}$.

There is a correspondence between proper scoring rules and Bregman divergences
as explained in Gneiting and Raftery (2007); Ovcharov (2015). If $D_{F}$ is a
Bregman divergence and $g$ is a function with domain ${\mathcal{X}}$ then $f$
given by $f\left(x,Q\right)=g\left(x\right)-D_{F}\left(\delta_{x},Q\right)$
defines a scoring rule.

Assume that $f$ is a proper scoring function. Then a function $F$ can be
defined as

$F(P)=\sum_{x\in\mathcal{X}}P\left(x\right)\cdot f\left(x,P\right)$

This lead to the regret function

$D_{F}\left(P,Q\right)=F(P)-\sum_{x\in\mathcal{X}}P\left(x\right)\cdot
f\left(x,Q\right).$ (7)

Since $f$ is assumed to be proper $D_{F}\left(P,Q\right)\geq 0$. The Bregman
identity (5) follows by straight forward calculations. With these two results
we see that the regret function $D_{F}$ is a Bregman divergence and that

$\displaystyle D_{F}\left(\delta_{y},Q\right)$
$\displaystyle=\sum_{x\in\mathcal{X}}\delta_{y}\left(x\right)\cdot
f\left(x,\delta_{y}\right)-\sum_{x\in\mathcal{X}}\delta_{y}\left(x\right)\cdot
f\left(x,Q\right)$
$\displaystyle=f\left(y,\delta_{y}\right)-f\left(y,Q\right).$ (8)

Hence a proper scoring rule $f$ has the form
$f\left(x,Q\right)=g(x)-D_{F}\left(\delta_{x},Q\right)$ where
$g(x)=f\left(x,\delta_{x}\right)$. A strictly proper scoring rule can be
defined as a proper scoring rule where the corresponding Bregman divergence is
strict.

######  Example 2.

The Brier score is given by

$f\left(x,Q\right)=\frac{1}{n}\left(\sum_{y\in\mathcal{X}}\left(Q\left(y\right)-\delta_{x}\left(y\right)\right)^{2}\right).$

The Brier score is generated by the strictly convex function
$F\left(P\right)=\frac{1}{n}\sum_{x\in\mathcal{X}}P\left(x\right)^{2}$

###  4.3 Statistical mechanics

Thermodynamics is the study of concepts like heat, temperature and energy. A
major objective is to extract as much energy from a system as possible. The
idea in statistical mechanics is to view the macroscopic behavior of a
thermodynamic system as a statistical consequence of the interaction between a
lot of microscopic components where the interacting between the components are
governed by very simple laws. Here the central limit theorem and large
deviation theory play a major role. One of the main achievements is the
formula for entropy as a logarithm of a probability.

Here we shall restrict the discussion to the most simple kind of thermodynamic
system from which we want to extract energy. We may think of a system of non-
interacting spin particles in a magnetic field. For such a system the
Hamiltonian is given by

$\hat{H}\left(\sigma\right)=-\mu\sum h_{j}\sigma_{j}$

where $\sigma$ is the spin configuration, $\mu$ is the magnetic moment,
$h_{j}$ is the strength of an external magnetic field, and $\sigma_{j}=\pm 1$
is the spin of the the $j$’th particle. If the system is in thermodynamic
equilibrium the configuration probability is

$P_{\beta}\left(\sigma\right)=\frac{\exp\left(-\beta\hat{H}\left(\sigma\right)\right)}{Z_{\beta}}$

where $Z\left(\beta\right)$ is the partition function

$Z\left(\beta\right)=\sum_{\sigma}\exp\left(-\beta\hat{H}\left(\sigma\right)\right).$

Here $\beta$ is the inverse temperature $\left(kT\right)^{-1}$ of the spin
system and $k=1.381\cdot 10^{-23}\nicefrac{{\mathrm{J}}}{{\mathrm{K}}}$ is
Boltzmann’s constant.

The mean energy is given by

$\sum_{\sigma}P_{\beta}\left(\sigma\right)\hat{H}\left(\sigma\right)$

which will be identified with the internal energy $U$ defined in
thermodynamics. The Shannon entropy can be calculated as

$\displaystyle-\sum_{\sigma}P_{\beta}\left(\sigma\right)\ln
P_{\beta}\left(\sigma\right)$
$\displaystyle=-\sum_{\sigma}P_{\beta}\left(\sigma\right)\ln\frac{\exp\left(-\beta\hat{H}\left(\sigma\right)\right)}{Z_{\beta}}$
$\displaystyle=-\sum_{\sigma}P_{\beta}\left(\sigma\right)\left(-\beta\hat{H}\left(\sigma\right)-\ln
Z\left(\beta\right)\right)$ $\displaystyle=\beta\cdot U+\ln
Z\left(\beta\right).$

The Shannon entropy times $k$ will be identified with the thermodynamic
entropy $S$.

The amount of energy that can be extracted from the system if a heat bath is
available, is called the _exergy_ Gundersen (2011). We assume that the heat
bath has temperature $T_{0}$ and the internal energy and entropy of the system
are $U_{0}$ and $S_{0}$ if the system has been brought in equilibrium with the
heat bath. The exergy can be calculated by

$\displaystyle Ex$ $\displaystyle=U-U_{0}-T_{0}\left(S-S_{0}\right)$
$\displaystyle=U-U_{0}-kT_{0}\left(\beta\cdot U+\ln
Z\left(\beta\right)-\beta_{0}U_{0}-\ln Z\left(\beta_{0}\right)\right)$
$\displaystyle=kT_{0}\left(\left(\beta_{0}-\beta\right)\cdot
U+\ln\frac{Z\left(\beta_{0}\right)}{Z\left(\beta\right)}\right).$

The information divergence between the actual state and the corresponding
state that is in equilibrium with the environment is

$\displaystyle D\left(\left.P_{\beta}\right\|P_{\beta_{0}}\right)$
$\displaystyle=\sum_{\sigma}P_{\beta}\left(\sigma\right)\ln\frac{P_{\beta}\left(\sigma\right)}{P_{\beta_{0}}\left(\sigma\right)}$
$\displaystyle=\sum_{\sigma}P_{\beta}\left(\sigma\right)\ln\frac{\frac{\exp\left(-\beta\hat{H}\left(\sigma\right)\right)}{Z\left(\beta\right)}}{\frac{\exp\left(-\beta_{0}\hat{H}\left(\sigma\right)\right)}{Z\left(\beta_{0}\right)}}$
$\displaystyle=\sum_{\sigma}P_{\beta}\left(\sigma\right)\left(-\beta\hat{H}\left(\sigma\right)+\beta_{0}\hat{H}\left(\sigma\right)+\ln\frac{Z\left(\beta_{0}\right)}{Z\left(\beta\right)}\right)$
$\displaystyle=\left(\beta_{0}-\beta\right)\cdot\sum_{\sigma}P_{\beta}\left(\sigma\right)\hat{H}\left(\sigma\right)+\ln\frac{Z\left(\beta_{0}\right)}{Z\left(\beta\right)}$
$\displaystyle=\left(\beta_{0}-\beta\right)\cdot
U+\ln\frac{Z\left(\beta_{0}\right)}{Z\left(\beta\right)}.$

Hence

$Ex=kT_{0}D\left(\left.P_{\beta}\right\|P_{\beta_{0}}\right).$

This equation appeared already in Harremoës (1993).

###  4.4 Portfolio theory

The relation between information theory and gambling was established by Kelly
Kelly (1956). Logarithmic terms appear because we are interested in the
exponent in the exponential growth rate of our wealth. Later Kelly’s approach
has been generalized to trading of stocks although the relation to information
theory is weaker Cover and Thomas (1991).

Let $X_{1},X_{2},\dots,X_{k}$ denote _price relatives_ for a list of $k$
assets. For instance $X_{5}=1.04$ means that asset no. 5 increases its value
by 4 %. Such price relatives are mapped into a price relative vector
$\vec{X}=\left(X_{1},X_{2},\dots,X_{k}\right).$

######  Example 3.

A special asset is the _safe asset_ where the price relative is 1 for any
possible price relative vector. Investing in this asset corresponds to placing
the money at a safe place with interest rate equal to 0 % .

A _portfolio_ is a probability vector
$\vec{b}=\left(b_{1},b_{2},\dots,b_{k}\right)$ where for instance $b_{5}=0.3$
means that 30 % of the money is invested in asset no. 5. We note that a
portfolio may be traded just like the original assets. The price relative for
the portfolio $\vec{b}$ is $X_{1}\cdot b_{1}+X_{2}\cdot b_{2}+\dots+X_{k}\cdot
b_{k}=\left\langle\vec{X},\vec{b}\right\rangle.$ The original assets may be
considered as extreme points in the set of portfolios. If an asset has the
property that the price relative is only positive for one of the possible
price relative vectors, then we may call it a _gambling asset_.

We now consider a situation where the assets are traded once every day. For a
sequence of price relative vectors $\vec{X}_{1},\vec{X_{2}},\dots\vec{X}_{n}$
and _a constant re-balancing portfolio_ $\vec{b}$ the wealth after $n$ days is

$\displaystyle S_{n}$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{n}\left\langle\vec{X}_{i},\vec{b}\right\rangle$ (9)
$\displaystyle=$
$\displaystyle\exp\left(\sum_{i=1}^{n}\ln\left(\left\langle\vec{X}_{i},\vec{b}\right\rangle\right)\right)$
(10) $\displaystyle=$ $\displaystyle\exp\left(n\cdot
E\left[\ln\left\langle\vec{X},\vec{b}\right\rangle\right]\right)$ (11)

where the expectation is taken with respect to the empirical distribution of
the price relative vectors. Here
$E\left[\ln\left\langle\vec{X},\vec{b}\right\rangle\right]$ is proportional to
the _doubling rate_ and is denoted $W\left(\vec{b},P\right)$ where $P$
indicates the probability distribution of $\vec{X}$. Our goal is to maximize
$W\left(\vec{b},P\right)$ by choosing an appropriate portfolio $\vec{b}.$

######  Definition 3.

Let $\vec{b}_{1}$ and $\vec{b}_{2}$ denote two portfolios. We say that
$\vec{b}_{1}$ _dominates_ $\vec{b}_{2}$ if
$\left\langle\vec{X}_{j},\vec{b}_{1}\right\rangle\geq\left\langle\vec{X}_{j},\vec{b}_{2}\right\rangle$
for any possible price relative vector $\vec{X}_{j}$ $j=1,2,\dots,n.$ We say
that $\vec{b}_{1}$ _strictly dominates_ $\vec{b}_{2}$ if
$\left\langle\vec{X}_{j},\vec{b}_{1}\right\rangle>\left\langle\vec{X}_{j},\vec{b}_{2}\right\rangle$
for any possible price relative vector $\vec{X}_{j}$ $j=1,2,\dots,n.$ A set
$A$ of assets is said to dominate the set of assets $B$ if any asset in $B$ is
dominated by a portfolio of assets in $A.$

The maximal doubling rate does not change if dominated assets are removed.
Sometimes assets that are dominated but not strictly dominated may lead to
non-uniqueness of the optimal portfolio.

Let $\vec{b}_{P}$ denote a portfolio that is optimal for $P$ and define

$G(P)=W\left(\vec{b}_{P},P\right).$ (12)

The regret of choosing a portfolio that is optimal for $Q$ when the
distribution is $P$ is given by the regret function

$D_{G}(P,Q)=W\left(\vec{b}_{P},P\right)-W\left(\vec{b}_{Q},P\right).$ (13)

If $\vec{b}_{Q}$ is not uniquely determined we take a minimum over all
$\vec{b}$ that are optimal for $Q.$

######  Example 4.

Assume that the price relative vector is $\left(2,\nicefrac{{1}}{{2}}\right)$
with probability $1-t$ and $\left(\nicefrac{{1}}{{2}},2\right)$ with
probability $t$. Then the portfolio concentrated on the first asset is optimal
for $t\leq\nicefrac{{1}}{{5}}$ and the portfolio concentrated on the second
asset is optimal for $t>\nicefrac{{4}}{{5}}$. For values of $t$ between
$\nicefrac{{1}}{{5}}$ and $\nicefrac{{4}}{{5}}$ the optimal portfolio invests
money on both assets as illustrated in Figure 2.

$G(1-t,t)$$t$$0$$0.2$$0.8$$1$ Figure 2: The function $G$ for the price
relative vectors in Example 4.

######  Lemma 1.

If there are only two price relative vectors and the regret function is strict
then either one of the assets dominates all other assets or two of the assets
are orthogonal gambling assets that dominate all other assets.

###### Proof.

We will assume that no assets are dominated by other assets. Let

$\displaystyle\vec{X}$ $\displaystyle=$
$\displaystyle\left(X_{1},X_{2},\dots,X_{k}\right)$ $\displaystyle\vec{Y}$
$\displaystyle=$ $\displaystyle\left(Y_{1},Y_{2},\dots,Y_{k}\right)$

denote the two price relative vectors. Without loss of generality we may
assume that

$\frac{X_{1}}{Y_{1}}\geq\frac{X_{2}}{Y_{2}}\geq\dots\geq\frac{X_{k}}{Y_{k}}.$

If $\frac{X_{i}}{Y_{i}}=\frac{X_{i+1}}{Y_{i+1}}$ then
$\frac{X_{i}}{X_{i+1}}=\frac{Y_{i}}{Y_{i+1}}$ so that if $X_{i}\leq X_{i+1}$
then $Y_{i}\leq Y_{i+1}$ and the asset $i$ is dominated by the asset $i+1.$
Since we have assumed that no assets are dominated we may assume that

$\frac{X_{1}}{Y_{1}}>\frac{X_{2}}{Y_{2}}>\dots>\frac{X_{k}}{Y_{k}}.$

If $P=\left(1-t,t\right)$ is a probability vector over the two price relative
vectors then according to Cover and Thomas (1991) the portfolio
$\vec{b}=\left(b_{1},b_{2},\dots,b_{n}\right)$ is optimal if and only if

$(1-t)\frac{X_{i}}{b_{1}X_{1}+\dots+b_{k}X_{k}}+t\frac{Y_{i}}{b_{1}Y_{1}+\dots+b_{k}Y_{k}}\leq
1$

for all $i\in\left\\{1,2,\dots,k\right\\}$ with equality if $b_{i}>0.$ Assume
that the portfolio $\vec{b}=\delta_{j}$ is optimal. Now

$\left(1-t\right)\frac{X_{j+1}}{X_{j}}+t\frac{Y_{j+1}}{Y_{j}}\leq 1$

is equivalent to

$t\leq\frac{\frac{X_{j}}{Y_{j+1}}-\frac{X_{j+1}}{Y_{j+1}}}{\frac{X_{j}}{Y_{j}}-\frac{X_{j+1}}{Y_{j+1}}}.$
(14)

Similarly

$\left(1-t\right)\frac{X_{j-1}}{X_{j}}+t\frac{Y_{j-1}}{Y_{j}}\leq 1$

is equivalent to

$t\geq\frac{\frac{X_{j}}{Y_{j-1}}-\frac{X_{j-1}}{Y_{j-1}}}{\frac{X_{j}}{Y_{j}}-\frac{X_{j-1}}{Y_{j-1}}}.$
(15)

We have to check that

$\frac{\frac{X_{j}}{Y_{j-1}}-\frac{X_{j-1}}{Y_{j-1}}}{\frac{X_{j}}{Y_{j}}-\frac{X_{j-1}}{Y_{j-1}}}<\frac{\frac{X_{j}}{Y_{j+1}}-\frac{X_{j+1}}{Y_{j+1}}}{\frac{X_{j}}{Y_{j}}-\frac{X_{j+1}}{Y_{j+1}}},$

which is equivalent with

$0<X_{j}Y_{j-1}-Y_{j-1}X_{j+1}-Y_{j}X_{j-1}-\left(X_{j}Y_{j+1}-Y_{j+1}X_{j-1}-Y_{j}X_{j+1}\right).$

The right hand side equals the determinant

$\left|\begin{array}[]{cc}X_{j+1}-X_{j-1}&X_{j}-X_{j-1}\\\
Y_{j+1}-Y_{j-1}&Y_{j}-Y_{j-1}\end{array}\right|,$

which is positive because asset $j$ is not dominated by a portfolio based on
asset $j-1$ and asset $j+1.$

We see that the portfolio concentrated in asset $j$ is optimal for $t$ in an
interval of positive length and the regret between distributions in such an
interval will be zero. In particular the regret will not be strict.

Strictness of the regret function is only possible if there are only two
assets and if a portfolio concentrated on one of these assets is only optimal
for a singular probability measure. According to the formulas for the end
points of intervals (14) and (15) this is only possible if the assets are
gambling assets. ∎

######  Theorem 1.

If the regret function is strict it equals information divergence, i.e.

$D_{G}(P,Q)=D\left(P\|Q\right).$ (16)

###### Proof.

If the regret function is strict then it is also strict when we restrict to
two price relative vectors. Therefore any two price relative vectors are
orthogonal gambling assets. If the assets are orthogonal gambling assets we
get the type of gambling described by Kelly Kelly (1956). For gambling
equation can easily be derived Cover and Thomas (1991). ∎

##  5 Sufficiency Conditions

In this section we will introduce some conditions on a regret function. Under
some mild conditions they turn out to be equivalent.

######  Theorem 2.

Let $D_{F}$ denote a regret function based on a continuous and convex function
$F$ defined on the state space of a finite dimensional $C^{*}$-algebra. If the
state space has at least three orthogonal states then the following conditions
are equivalent.

  * •

The function $F$ equals entropy times a negative constant plus an affine
function.

  * •

The regret $D_{F}$ is proportional to information divergence.

  * •

The regret is monotone.

  * •

The regret is satisfies sufficiency.

  * •

The regret is local.

In the rest of this section we will describe each of these equivalent
conditions and prove that they are actually equivalent. The theorems and
proofs will be stated so that they hold even for more general state spaces
than the ones considered in this paper.

###  5.1 Entropy and Information Divergence

######  Definition 4.

Let $s$ denote an element in a state space. The _entropy_ of $s$ is be defined
as

$H\left(s\right)=\inf\left(-\sum_{i=1}^{n}\lambda_{i}\ln\left(\lambda_{i}\right)\right)$

where the infimum is taken over all decompositions
$s=\sum_{i=1}^{n}\lambda_{i}s_{i}$ of $s$ into pure states $s_{i}$.

This definition of the entropy of a state was first given by Uhlmann Uhlmann
(1970). Using that entropy is decreasing under majorization we see that the
entropy of $s$ is attained at an orthogonal decomposition Harremoës (2016) and
we obtain the familiar equation

$H(s)=-\mathrm{tr}\left[s\ln(s)\right].$

In general this definition of entropy does not provide a concave function on a
convex set. For instance the entropy of points in the square has local maximum
in the four different points. A characterization of the convex sets with
concave entropy functions is lacking.

######  Definition 5.

If the entropy is a concave function then the Bregman divergence $D_{-H}$ is
called _information divergence_.

The information divergence is also called _Kullback-Leibler divergence_ ,
_relative entropy_ or _quantum relative entropy_. In a C*-algebra we get

$\displaystyle D_{-H}\left(s_{1},s_{2}\right)$
$\displaystyle=-H\left(s_{1}\right)-\left(-H\left(s_{2}\right)+\left\langle
s_{1}-s_{2},-\nabla H\left(s_{2}\right)\right\rangle\right)$
$\displaystyle=H\left(s_{2}\right)-H\left(s_{1}\right)+\left\langle
s_{1}-s_{2},\nabla H\left(s_{2}\right)\right\rangle$
$\displaystyle=\mathrm{tr}\left[f\left(s_{2}\right)\right]-\mathrm{tr}\left[f\left(s_{1}\right)\right]+\mathrm{tr}\left[\left(s_{1}-s_{2}\right)f^{\prime}\left(s_{2}\right)\right]$
$\displaystyle=\mathrm{tr}\left[f\left(s_{2}\right)-f\left(s_{1}\right)+\left(s_{1}-s_{2}\right)f^{\prime}\left(s_{2}\right)\right]$

where $f\left(x\right)=-x\ln\left(x\right).$ Now
$f^{\prime}\left(x\right)=-\ln\left(x\right)-1$ so that

$\displaystyle
f\left(s_{2}\right)-f\left(s_{1}\right)+\left(s_{1}-s_{2}\right)f^{\prime}\left(s_{2}\right)$
$\displaystyle=-s_{2}\ln\left(s_{2}\right)+s_{1}\ln\left(s_{1}\right)+\left(s_{1}-s_{2}\right)\left(-\ln\left(s_{2}\right)-1\right)$
$\displaystyle=s_{1}\left(\ln\left(s_{1}\right)-\ln\left(s_{2}\right)\right)+s_{2}-s_{1}.$

Hence

$D_{-H}\left(s_{1},s_{2}\right)=\mathrm{tr}\left[s_{1}\left(\ln\left(s_{1}\right)-\ln\left(s_{2}\right)\right)+s_{2}-s_{1}\right].$

For states $s_{1},s_{2}$ it reduces to the well-known formula

$D_{-H}\left(s_{1},s_{2}\right)=\mathrm{tr}\left[s_{1}\ln\left(s_{1}\right)-s_{1}\ln\left(s_{2}\right)\right].$

###  5.2 Monotonicity

We consider a set $\mathcal{T}$ of maps of the state space into itself. The
set $\mathcal{T}$ will be used to represent those transformations that we are
able to perform on the state space before we choose a feasible action
$a\in\mathcal{A}$. Let $\Phi:\mathcal{S}\curvearrowright\mathcal{S}$ denote a
map. Then the dual map $\Phi^{*}$ maps actions into actions and is given by

$\left\langle
a,\Phi\left(s\right)\right\rangle=\left\langle\Phi^{*}(a),s\right\rangle.$

######  Proposition 5 (The principle of lost opportunities).

If $\Phi^{*}$ maps the set of feasible actions $\mathcal{A}$ into itself then

$F\left(\Phi\left(s\right)\right)\leq F\left(s\right).$ (17)

###### Proof.

If $a\in\mathcal{A}$ then

$\displaystyle\left\langle a,\Phi\left(s\right)\right\rangle$ $\displaystyle=$
$\displaystyle\left\langle\Phi^{*}(a),s\right\rangle$ $\displaystyle\leq$
$\displaystyle F\left(s\right)$

because $\Phi^{*}(a)\in\mathcal{A}$. Inequality (17) follows because
$F\left(\Phi\left(s\right)\right)=\sup_{a}\left\langle
a,\Phi\left(s\right)\right\rangle.$ ∎

######  Corollary 1 (Semi-monotonicity).

Let $\Phi$ denote a map of the state space into itself such that $\Phi^{*}$
maps the set of feasible actions $\mathcal{A}$ into itself and let $s_{2}$
denote a state that minimizes the function $F$. If $D_{F}$ is a Bregman
divergence then

$D_{F}\left(\Phi\left(s_{1}\right),\Phi\left(s_{2}\right)\right)\leq
D_{F}\left(s_{1},s_{2}\right).$ (18)

###### Proof.

Since $s_{2}$ minimizes $F$ and $F$ is differentiable we have $\nabla
F\left(s_{2}\right)=0$. Since $s_{2}$ minimizes $F$ and
$F\left(\Phi\left(s_{2}\right)\right)\leq F\left(s_{2}\right)$ we also have
that $\Phi\left(s_{2}\right)$ minimizes $F$ and that $\nabla
F\left(\Phi\left(s_{2}\right)\right)=0$. Therefore

$\displaystyle
D_{F}\left(\Phi\left(s_{1}\right),\Phi\left(s_{2}\right)\right)$
$\displaystyle=F\left(\Phi\left(s_{1}\right)\right)-\left(F\left(\Phi\left(s_{2}\right)\right)+\left\langle\Phi\left(s_{1}\right)-\Phi\left(s_{2}\right),\nabla
F\left(\Phi\left(s_{2}\right)\right)\right\rangle\right)$
$\displaystyle=F\left(\Phi\left(s_{1}\right)\right)-F\left(\Phi\left(s_{2}\right)\right)$
$\displaystyle\leq F\left(s_{1}\right)-F\left(s_{2}\right)$
$\displaystyle=D_{F}\left(s_{1},s_{2}\right),$

which proves the inequality. ∎

Next we introduce the stronger notion of monotonicity.

######  Definition 6.

Let $D_{F}$ denote a regret function on the state space $\mathcal{S}$ of a
finite dimensional C*-algebra. Then $D_{F}$ is said to be _monotone_ if

$D_{F}\left(\Phi\left(s_{1}\right),\Phi\left(s_{2}\right)\right)\leq
D_{F}\left(s_{1},s_{2}\right)$

for any affine map $\Phi:S\to S.$

######  Proposition 6.

If a regret function $D_{F}$ based on a convex and continuous function $F$ is
monotone then it is a Bregman divergence.

###### Proof.

Assume that $D_{F}$ is monotone. We have to prove that $F$ is differentiable.
Since $F$ is convex it is sufficient to prove that any restriction of $F$ to a
line segment is differentiable. Let $s_{0}$ and $s_{1}$ denote states that are
the end points of a line segment. The restriction of $F$ to the line segment
is given by the convex and continuous function $f(t)=F((1-t)s_{0}+ts_{1})$ so
we have to prove that $f$ is differentiable.

If $0<t_{1}<t_{2}<1$ then according to Equation (2) we have

$D_{F}\left((1-t_{2})s_{0}+t_{2}s_{1},(1-t_{1})s_{0}+t_{1}s_{1}\right)=f\left(t_{2}\right)-\left(f\left(t_{1}\right)+\left(t_{2}-t_{1}\right)\cdot
f^{\prime}_{+}\left(t_{1}\right)\right)$

where $f_{+}$ denotes the denote the derivative from the right. A dilation by
a factor $r\leq 1$ around $s_{0}$ decreases the regret so that

$r\to f\left(r\cdot t_{2}\right)-\left(f\left(r\cdot
t_{1}\right)+r\cdot\left(t_{2}-t_{1}\right)\cdot f^{\prime}_{+}\left(r\cdot
t_{1}\right)\right)$ (19)

is increasing. Since $f$ is convex the function $r\to
f^{\prime}_{+}\left(r\cdot t_{1}\right)$ is increasing. Assume that $f$ is not
differentiable so that $r\to f^{\prime}_{+}\left(r\cdot t_{1}\right)$ has a
positive jump as illustrated on Figure 3. This contradicts that the function
(19) is increasing. Therefore $f^{\prime}_{+}$ is continuous and $f$ is
differentiable.

$r\cdot t_{2}$$t_{2}$$r\cdot t_{1}$$t_{1}$$t$$f(t)$ Figure 3: Example of a
dilation that increases regret.

∎

Recently it has been proved that information divergence on a complex Hilbert
space is decreasing under positive trace preserving maps Müller-Hermes and
Reeb (2015); Christandl and Müller-Hermes (2016). Previously this was only
known to hold if some extra condition like complete positivity or 2-positivity
was assumed Petz (2003).

######  Theorem 3.

Information divergence is monotone under any positive trace preserving map on
the states of a finite dimensional $C^{*}$-algebra.

###### Proof.

Any finite dimensional $C^{*}$-algebra $\mathcal{B}$ can be embedded in
$\mathbb{B}\left(\mathbb{H}\right)$ and there exist a conditional expectation
$\mathbb{E}:\mathbb{B}\left(\mathbb{H}\right)\to\mathcal{B}.$ If $\Phi$ is a
positive trace preserving map of the density matrices of $\mathcal{B}$ into it
self then $\Phi\circ\mathbb{E}$ is positive and trace preserving on
$\mathbb{B}\left(\mathbb{H}\right).$ According to Müller-Hermes and Reeb
Müller-Hermes and Reeb (2015) we have

$D\left(\left.\Phi\circ\mathbb{E}\left(s_{1}\right)\right\|\Phi\circ\mathbb{E}\left(s_{2}\right)\right)\leq
D\left(\left.s_{1}\right\|s_{2}\right)$

for density matrices in $\mathbb{B}\left(\mathbb{H}\right).$ In particular
this inequality holds for density matrices in $\mathcal{B}$ and for such
matrices we have $\mathbb{E}\left(s_{i}\right)=s_{i}$. ∎

###  5.3 Sufficiency

The notion of sufficiency plays an important role in statistics and related
fields. We shall present a definition of sufficiency that is based on Petz
(1988), but there are a number of other equivalent ways of defining this
concept. We refer to Jenčová and Petz (2006) where the notion of sufficiency
is discussed in great detail.

######  Definition 7.

Let $\left(s_{\theta}\right)_{\theta}$ denote a family of states and let
$\Phi$ denote an affine map $\mathcal{S}\to\mathcal{T}$ where $\mathcal{S}$
and $\mathcal{T}$ denote state spaces. A _recovery map_ is an affine map
$\Psi:\mathcal{T}\to\mathcal{S}$ such that
$\Psi\left(\Phi\left(s_{\theta}\right)\right)=s_{\theta}.$ The map $\Phi$ is
said to be _sufficient_ for $\left(s_{\theta}\right)_{\theta}$ if $\Phi$ has a
recovery map.

######  Proposition 7.

Assume $D_{F}$ is a regret function based on a convex and continuous function
$F$ and assume that $\Phi$ is sufficient for $s_{1}$ and $s_{2}$ with recovery
map $\Psi$. Assume that both $\Phi^{*}$ and $\Psi^{*}$ map the set of feasible
actions $\mathcal{A}$ into itself. Then

$D_{F}\left(\Phi\left(s_{1}\right),\Phi\left(s_{2}\right)\right)=D_{F}\left(s_{1},s_{2}\right).$

###### Proof.

According to the principle of lest opportunities (Proposition 5) we have

$\displaystyle F\left(s_{2}\right)$
$\displaystyle=F\left(\Psi\left(\Phi\left(s_{2}\right)\right)\right)$
$\displaystyle\leq F\left(\Phi\left(s_{2}\right)\right)$ $\displaystyle\leq
F\left(s_{2}\right).$

Therefore $F\left(\Phi\left(s_{2}\right)\right)=F\left(s_{2}\right).$ Let $a$
denote an action that is optimal for $s_{2}.$ Then

$\displaystyle F\left(\Phi\left(s_{2}\right)\right)$
$\displaystyle=F\left(s_{2}\right)$ $\displaystyle=\left\langle
a,s_{2}\right\rangle$ $\displaystyle=\left\langle
a,\Psi\left(\Phi\left(s_{2}\right)\right)\right\rangle$
$\displaystyle=\left\langle\Psi^{*}(a),\Phi\left(s_{2}\right)\right\rangle$

and we see that $\Psi^{*}(a)$ is optimal for $\Phi\left(s_{2}\right).$ Now

$\displaystyle D_{F}\left(s_{1},s_{2}\right)$
$\displaystyle=\inf_{a}\left(F\left(s_{1}\right)-\left\langle
a,s_{1}\right\rangle\right)$
$\displaystyle=\inf_{a}\left(F\left(s_{1}\right)-\left\langle\Psi^{*}(a),\Phi\left(s_{1}\right)\right\rangle\right)$

where the infimum is taken over actions $a$ that are optimal for $s_{2}.$ Then

$\displaystyle\inf_{a}\left(F\left(s_{1}\right)-\left\langle\Psi^{*}(a),\Phi\left(s_{1}\right)\right\rangle\right)$
$\displaystyle\geq\inf_{\tilde{a}}\left(F\left(\Phi\left(s_{1}\right)\right)-\left\langle\tilde{a},\Phi\left(s_{1}\right)\right\rangle\right)$
$\displaystyle=D_{F}\left(\Phi\left(s_{1}\right),\Phi\left(s_{2}\right)\right)$

so we have $D_{F}\left(s_{1},s_{2}\right)\geq
D_{F}\left(\Phi\left(s_{1}\right),\Phi\left(s_{2}\right)\right).$ The reverse
inequality is proved in the same way. ∎

The notion of sufficiency as a property of divergences was introduced in
Harremoës and Tishby (2007). The crucial idea of restricting the attention to
maps of the state space into itself was introduced in Jiao et al. (2014). It
was shown in Jiao et al. (2014) that a Bregman divergence on the simplex of
distributions on an alphabet that is not binary and satisfies sufficiency
equals information divergence up a multiplicative factor. Here we extend the
notion of sufficiency from Bregman divergences to regret functions.

######  Definition 8.

Let $D_{F}$ denote a regret function based on a convex and continuous function
$F$ on a state space ${\mathcal{S}}$. We say $D_{F}$ satisfies _sufficiency_
if

$D_{F}\left(\Phi\left(s_{1}\right),\Phi\left(s_{2}\right)\right)=D_{F}\left(s_{1},s_{2}\right)$

for any affine map $\mathcal{S}\to\mathcal{S}$ that is sufficient for
$\left(s_{1},s_{2}\right).$

######  Proposition 8.

Let $D_{F}$ denote a regret function based on a convex and continuous function
$F$ on a state space ${\mathcal{S}}$. If the regret function $D_{F}$ is
monotone then it satisfies sufficiency.

###### Proof.

Assume that the regret function $D_{F}$ is monotone. Let $s_{1}$ and $s_{2}$
denote two states and let $\Phi$ and $\Psi$ denote maps on the state space
such that $\Phi\left(\Psi\left(s_{i}\right)\right)=s_{i},\,i=1,2$ . Then

$\displaystyle D_{F}\left(s_{1},s_{2}\right)$
$\displaystyle=D_{F}\left(\Phi\left(\Psi\left(s_{1}\right)\right),\Phi\left(\Psi\left(s_{2}\right)\right)\right)$
$\displaystyle\leq
D_{F}\left(\Psi\left(s_{1}\right),\Psi\left(s_{2}\right)\right)$
$\displaystyle\leq D_{F}\left(s_{1},s_{2}\right).$

Hence
$D_{F}\left(\Psi\left(s_{1}\right),\Psi\left(s_{2}\right)\right)=D_{F}\left(s_{1},s_{2}\right).$
∎

Combining the previous results we get that information divergence satisfies
sufficiency. Under some conditions there exists an inverse version of
Proposition 8 stating that if monotonicity holds with equality then the map is
sufficient. In statistics where the state space is a simplex, this result is
well established. For density matrices over the complex numbers it has been
proved for completely positive maps in Jenčová and Petz (2006). Some new
results on this topic can be found in Jenčová (2017).

###  5.4 Locallity

Often it is relevant to use the following weak version of the sufficiency
property.

######  Definition 9.

Let $D_{F}$ denote a regret function based on a convex and continuous function
$F$ on a state space ${\mathcal{S}}$. The regret function $D_{F}$ is said to
be local if

$D_{F}\left(s_{1},t\cdot
s_{1}+\left(1-t\right)\cdot\sigma\right)=D_{F}\left(s_{1},t\cdot
s_{1}+\left(1-t\right)\cdot\rho\right)$

when the states $\sigma$ and $\rho$ are orthogonal to $s_{1}$ and
$t\in\left]0,1\right[.$

######  Example 5.

On a 1-dimensional simplex (an interval) or on the Block sphere any regret
function $D_{F}$ is local. The reason is that if $\sigma$ and $\rho$ are
states that are orthogonal to $s_{1}$ then $\sigma=\rho.$

######  Proposition 9.

Let $D_{F}$ denote a regret function based on a convex and continuous function
$F$ on a state space ${\mathcal{S}}$. If the regret function $D_{F}$ satisfies
sufficiency then $D_{F}$ is local.

###### Proof.

Let $\sigma$ and $\rho$ be states that are orthogonal to $s_{1}.$ Let $p$
denote the projection supporting the state $s_{0}$. Let the maps $\Phi$ and
$\Psi$ be defined by

$\displaystyle\Phi\left(s\right)$ $\displaystyle={\rm tr}(ps)\cdot
s_{1}+(1-{\rm tr}(ps))\cdot\rho,$ $\displaystyle\Psi\left(s\right)$
$\displaystyle={\rm tr}(ps)\cdot s_{1}+(1-{\rm tr}(ps))\cdot\sigma.$

Then $\Phi\left(s_{1}\right)=\Psi\left(s_{1}\right)=s_{1}$ and
$\Phi\left(\sigma\right)=\rho$ and $\Psi\left(\rho\right)=\sigma.$ Therefore

$\displaystyle\Phi\left(t\cdot s_{1}+\left(1-t\right)\cdot\sigma\right)$
$\displaystyle=t\cdot s_{1}+\left(1-t\right)\cdot\rho$
$\displaystyle\Psi\left(t\cdot s_{1}+\left(1-t\right)\cdot\rho\right)$
$\displaystyle=t\cdot s_{1}+\left(1-t\right)\cdot\sigma$

and

$D_{F}\left(s_{1},t\cdot
s_{1}+\left(1-t\right)\cdot\sigma\right)=D_{F}\left(s_{1},t\cdot
s_{1}+\left(1-t\right)\cdot\rho\right).$

∎

######  Theorem 4.

Let $\mathcal{S}$ be the state space of a $C^{*}$-algebra with at least three
orthogonal states, and let $D_{F}$ denote a regret function based on a convex
and continuous function $F$ on the state space ${\mathcal{S}}$. If the regret
function $D_{F}$ is local then it is the Bregman divergence generated by the
entropy times a negative constant.

###### Proof.

In the following proof we will assume that the regret function is based on the
convex function $F:\mathcal{S}\to\mathbb{R}.$ First we will prove that the
regret function is a Bregman divergence.

Let $K$ denote the convex hull of a set $s_{0},s_{1},\dots s_{n}$ of
orthogonal states. For $x\in[0,1[$ let $g_{i}$ denote the function
$g_{i}\left(x\right)=D_{F}\left(s_{i},xs_{i}+\left(1-x\right)s_{i+1}\right)$.
Note that $g_{i}$ is decreasing and continuous from the left. Let $P=\sum
p_{i}s_{i}$ and $Q=\sum q_{i}s_{i}$ where $p_{i},q_{i}\in\left]0,1\right[$ for
all $i=0,1,2,\dots n$. If $F$ is differentiable in $P$ then locality implies
that

$\displaystyle D_{F}\left(P,Q\right)$ $\displaystyle=$ $\displaystyle\sum
p_{i}D_{F}\left(s_{i},Q\right)-\sum p_{i}D_{F}\left(s_{i},P\right)$
$\displaystyle=$ $\displaystyle\sum p_{i}g_{i}\left(q_{i}\right)-\sum
p_{i}g_{i}\left(p_{i}\right)$ $\displaystyle=$ $\displaystyle\sum
p_{i}\left(g_{i}\left(q_{i}\right)-g_{i}\left(p_{i}\right)\right).$

Note that $P\to D_{F}\left(P,Q\right)$ is a convex function and thereby it is
continuous. Assume that $P_{0}$ is an arbitrary element in $K$ and let
$\left(P_{n}\right)_{n\in\mathbb{N}}$ denote a sequence such that $P_{n}\to
P_{0}$ for $n\to\infty.$ The sequence $\left(P_{n}\right)_{n\in\mathbb{N}}$
can be choosen so that regret is differentiable in $P_{n}$ for all
$n\in\mathbb{N}.$ Further the sequence $P_{n}$ can be chosen such that
$p_{n,i}$ is increasing for all $i\neq j.$ Then

$D_{F}\left(P_{0},Q\right)=\sum
p_{0,i}\left(g_{i}\left(q_{i}\right)-g_{i}\left(p_{0,i}\right)\right)+p_{0,j}g_{j}\left(p_{0,j}\right)-p_{0,j}\lim_{n\to\infty}g_{j}\left(p_{n,j}\right).$

Similarly, if the sequence $P_{n}$ can be chosen such that $p_{n,i}$ is
increasing for all $i\neq j,j+1$ then

$D_{F}\left(P_{0},Q\right)=\sum
p_{0,i}\left(g_{i}\left(q_{i}\right)-g_{i}\left(p_{0,i}\right)\right)+p_{0,j}g_{j}\left(p_{0,j}\right)-p_{0,j}\lim_{n\to\infty}g_{j}\left(p_{n,j}\right)\\\
+p_{0,j+1}g_{j+1}\left(p_{0,j+1}\right)-p_{0,j+1}\lim_{n\to\infty}g_{j+1}\left(p_{n,j+1}\right),$

which implies that
$p_{0,j+1}g_{j+1}\left(p_{0,j+1}\right)-p_{0,j+1}\lim_{n\to\infty}g_{j+1}\left(p_{n,j+1}\right)=0$
and that

$\lim_{n\to\infty}g_{j+1}\left(p_{n,j+1}\right)=g_{j+1}\left(p_{0,j+1}\right)$

for all $j$. Therefore

$D_{F}\left(P_{0},Q\right)=\sum
p_{0,i}\left(g_{i}\left(q_{i}\right)-g_{i}\left(p_{0,i}\right)\right)$ (20)

for all $P_{0},Q$ in the interior of $K$. In the following calculations we
will assume that the distributions lie in the interior of $K$. The validity of
the Bregman identity (5) follows directly from Equation 20 implying that
$D_{F}$ is a Bregman divergence.

As a function of $Q$ the regret is minimal when $Q=P.$ In the following
calculations we write $x=p_{i}$, $z=p_{j}$, $y=q_{i}$, and $w=q_{j}$. If
$p_{\ell}=q_{\ell}$ for $\ell\neq i,j$ then non-negativity of regret can be
written as

$x\left(g_{i}\left(y\right)-g_{i}\left(x\right)\right)+z\left(g_{j}\left(w\right)-g_{j}\left(z\right)\right)\geq
0$

and we note that this inequality should hold as long as $x+z=y+w\leq 1.$
Permutation of $i$ and $j$ leads to the inequality

$x\left(g_{j}\left(y\right)-g_{j}\left(x\right)\right)+z\left(g_{i}\left(w\right)-g_{i}\left(z\right)\right)\geq
0$

that implies

$x\left(g_{ij}\left(y\right)-g_{ij}\left(x\right)\right)+z\left(g_{ij}\left(w\right)-g_{ij}\left(z\right)\right)\geq
0$ (21)

where $g_{ij}=\frac{g_{i}+g_{j}}{2}.$

Assume that $x=z=\frac{y+w}{2}$ in Inequality (21). Then

$\displaystyle
x\left(g_{ij}\left(y\right)-g_{ij}\left(x\right)\right)+x\left(g_{ij}\left(w\right)-g_{ij}\left(x\right)\right)$
$\displaystyle\geq$ $\displaystyle 0$ $\displaystyle
g_{ij}\left(y\right)-g_{ij}\left(x\right)+g_{ij}\left(w\right)-g_{ij}\left(x\right)$
$\displaystyle\geq$ $\displaystyle 0$
$\displaystyle\frac{g_{ij}\left(y\right)+g_{ij}\left(w\right)}{2}$
$\displaystyle\geq$ $\displaystyle g_{ij}\left(x\right)$

so that $g_{ij}$ is mid-point convex, which for a measurable function implies
convexity. Therefore $g_{ij}$ is differentiable from left and right.

If $y=w$ and $x=y+\epsilon$ and $z=y-\epsilon$ then we have

$\left(y+\epsilon\right)\left(g_{ij}\left(y\right)-g_{ij}\left(y+\epsilon\right)\right)+\left(y-\epsilon\right)\left(g_{ij}\left(y\right)-g_{ij}\left(y-\epsilon\right)\right)\geq
0$

with equality when $\epsilon=0.$ We differentiate with respect to $\epsilon$
from right.

$\left(g_{ij}\left(y\right)-g_{ij}\left(y+\epsilon\right)\right)+\left(y+\epsilon\right)\left(-g_{ij+}^{\prime}\left(y+\epsilon\right)\right)-\left(g_{ij}\left(y\right)-g_{ij}\left(y-\epsilon\right)\right)+\left(y-\epsilon\right)\left(g_{ij-}^{\prime}\left(y-\epsilon\right)\right)$

which is positive for $\epsilon=0$ so that

$\displaystyle-y\cdot g_{ij+}^{\prime}\left(y\right)+y\cdot
g_{ij-}^{\prime}\left(y\right)$ $\displaystyle\geq$ $\displaystyle 0$ (22)
$\displaystyle y\cdot g_{ij-}^{\prime}\left(y\right)$ $\displaystyle\geq$
$\displaystyle y\cdot g_{ij+}^{\prime}\left(y\right).$ (23)

Since $g_{ij}$ is convex we have $g_{ij-}^{\prime}\left(y\right)\leq
g_{ij+}^{\prime}\left(y\right)$ which in combination Inequality (23) implies
that $g_{ij-}^{\prime}\left(y\right)=g_{ij+}^{\prime}\left(y\right)$ so that
$g_{ij}$ is differentiable. Since $g_{i}=g_{ij}+g_{ik}-g_{jk}$ the function
$g_{i}$ is also differentiable.

As a function of $Q$ the Bregman divergence $D_{F}(P,Q)$ has a minimum at
$Q=P$ under the condition $\sum q_{i}=1$. Since the functions $g_{i}$ are
differentiable we can characterize this minimum using Lagrange multipliers. We
have

$\frac{\partial}{\partial
q_{i}}D_{F}\left(P,Q\right)=p_{i}g_{i}^{\prime}\left(q_{i}\right)$

and

$\frac{\partial}{\partial q_{i}}D_{F}\left(P,Q\right)_{\mid Q=P}=p_{i}\cdot
g_{i}^{\prime}\left(p_{i}\right).$

Further $\frac{\partial}{\partial q_{i}}\sum q_{i}=1$ so there exist a
constant $c_{K}$ such that $p_{i}\cdot
g_{i}^{\prime}\left(p_{i}\right)=c_{K}.$ Hence
$g_{i}^{\prime}\left(p_{i}\right)=\frac{c_{K}}{p_{i}}$ so that
$g_{i}\left(p_{i}\right)=c_{K}\cdot\ln\left(p_{i}\right)+m_{i}$ for some
constant $m_{i}.$

Now we get

$\displaystyle D_{F}\left(P,Q\right)$ $\displaystyle=$ $\displaystyle\sum
p_{i}\left(g_{i}\left(q_{i}\right)-g_{i}\left(p_{i}\right)\right)$
$\displaystyle=$ $\displaystyle\sum
p_{i}\left(\left(c_{K}\cdot\ln\left(q_{i}\right)+m_{i}\right)-\left(c_{K}\cdot\ln\left(p_{i}\right)+m_{i}\right)\right)$
$\displaystyle=$ $\displaystyle-c_{K}\cdot\sum p_{i}\ln\frac{p_{i}}{q_{i}}$
$\displaystyle=$ $\displaystyle D_{-c_{K}\cdot H}\left(P,Q\right).$

Therefore there exists an affine function defined on $K$ such that

$F_{\mid K}(P)=-c_{K}\cdot H_{\mid K}(P)+g_{K}$ (24)

for all $P$ in the interior of $K$. Since $H_{K}$ is continuous on $K$
Equation (24) holds for any $P\in K$. If each of the sets $K$ and $L$ is a
simplex and $x\in K\cap L$ then

$-c_{K}\cdot H_{\mid K}\left(x\right)+g_{K}\left(x\right)=-c_{L}\cdot H_{\mid
L}\left(x\right)+g_{L}\left(x\right)$

so that

$\left(c_{L}-c_{K}\right)\cdot H_{\mid
K}\left(x\right)=g_{L}\left(x\right)-g_{K}\left(x\right).$

If $K\cap L$ has dimension greater than zero then the right hand side is
affine so the left hand side is affine, which is only possible when
$c_{K}=c_{L}.$ Therefore we also have
$g_{L}\left(x\right)=g_{K}\left(x\right)$ for all $x\in K\cap L.$ Therefore
the functions $g_{K}$ can be extended to a single affine function on the whole
of $\mathcal{S}.$ ∎

##  6 Applications

###  6.1 Information theory

If only integer values of a code-length function $\ell$ are allowed then there
are only finitely many actions that are not dominated. Therefore the function
$F$ given by

$F\left(P\right)=-\min_{\ell}\sum\ell\left(a\right)\cdot p_{a}$

is piece-wise linear. In particular $F$ is not differentiable so that the
regret is not a Bregman divergence and cannot be monotone according to
Proposition 6. In information theory monotonicity of a divergence function is
closely related to the _data processing inequality_ and since the data
processing inequality is one of the most important tools for deriving
inequalities in information theory we need to modify our notion of code-length
function in order to achieve a data processing inequality.

We now formulate a version of Kraft’s inequality that allow the code length
function to be non-integer valued.

######  Theorem 5.

Let $\ell:\mathbb{A}\rightarrow\mathbb{R}$ be a function. Then the function
$\ell$ satisfies Kraft’s inequality (6) if and only if for all $\varepsilon>0$
there exists an integer $n$ and a uniquely decodable fixed-to-variable length
block code $\kappa:\mathbb{A}^{n}\rightarrow\mathbb{B}^{\ast}$ such that

$\left|\bar{\ell}_{\kappa}\left(a^{n}\right)-\frac{1}{n}\sum_{i=1}^{n}\ell\left(a_{i}\right)\right|\leq\varepsilon$

where $\bar{\ell}_{\kappa}\left(a^{n}\right)$ denotes the length
$\ell_{\kappa}\left(a^{n}\right)$ divided by $n.$ The uniquely decodable block
code can be chosen to be prefix free.

###### Proof.

Assume that $\ell$ satisfies Kraft’s inequality. Then

$\sum_{a_{1}a_{2}...a_{n}\in\mathbb{A}^{n}}\beta^{\textrm{-}\sum_{i=1}^{n}\ell\left(a_{i}\right)}=\left(\sum_{a\in\mathbb{A}}\beta^{\textrm{-}\ell\left(a\right)}\right)^{n}\leq
1^{n}=1.$

Therefore the function $\tilde{\ell}:\mathbb{A}^{n}\rightarrow\mathbb{N}$
given by

$\tilde{\ell}\left(a_{1}a_{2}...a_{n}\right)=\left\lceil\sum_{i=1}^{n}\ell\left(a_{i}\right)\right\rceil$

is integer valued and satisfies Kraft’s inequality (6) and there exists a
prefix-free code $\kappa:\mathbb{A}^{n}\rightarrow\left\\{0,1\right\\}^{\ast}$
such that
$\ell_{\kappa}\left(a_{1}a_{2}...a_{n}\right)=\tilde{\ell}\left(a_{1}a_{2}...a_{n}\right).$
Therefore

$\left|\bar{\ell}_{\kappa}\left(a_{1}a_{2}...a_{n}\right)-\frac{1}{n}\sum_{i=1}^{n}\ell\left(a_{i}\right)\right|=\frac{1}{n}\left|\left\lceil\sum_{i=1}^{n}\ell\left(a_{i}\right)\right\rceil-\sum_{i=1}^{n}\ell\left(a_{i}\right)\right|\leq\frac{1}{n}$

so for any $\varepsilon>0$ choose $n$ such that
$\nicefrac{{1}}{{n}}\leq\varepsilon.$

Assume that for all $\varepsilon>0$ there exists a uniquely decodable fixed-
to-variable length code
$\kappa:\mathbb{A}^{n}\rightarrow\left\\{0,1\right\\}^{\ast}$ such that

$\left|\bar{\ell}_{\kappa}\left(a_{1}a_{2}...a_{n}\right)-\frac{1}{n}\sum_{i=1}^{n}\ell\left(a_{i}\right)\right|\leq\varepsilon$

for all strings $a_{1}a_{2}...a_{n}\in\mathbb{A}^{n}.$ Then
$n\bar{\ell}_{\kappa}\left(a_{1}a_{2}...a_{n}\right)$ satisfies Kraft’s
Inequality(6) and

$\displaystyle\left(\sum_{a\in\mathbb{A}}\beta^{\textrm{-}\ell\left(a\right)}\right)^{n}$
$\displaystyle=\sum_{a_{1}a_{2}...a_{n}\in\mathbb{A}^{n}}\beta^{\textrm{-}\sum_{i=1}^{n}\ell\left(a_{i}\right)}$
$\displaystyle\leq\sum_{a_{1}a_{2}...a_{n}\in\mathbb{A}^{n}}\beta^{\textrm{-}n\left(\bar{\ell}_{\kappa}\left(a_{1}a_{2}...a_{n}\right)-\varepsilon\right)}$
$\displaystyle=\beta^{n\varepsilon}\sum_{a_{1}a_{2}...a_{n}\in\mathbb{A}^{n}}\beta^{\textrm{-}n\bar{\ell}_{\kappa}\left(a_{1}a_{2}...a_{n}\right)}$
$\displaystyle\leq\beta^{n\varepsilon}.$

Therefore
$\sum_{a\in\mathbb{A}}\beta^{\textrm{-}\ell\left(a\right)}\leq\beta^{\varepsilon}$
for all $\varepsilon>0$ and the result is obtained. ∎

Like in Bayesian statistics we focus on finite sequences. Contrary to Bayesian
statistics we should always consider a finite sequence as a prefix of _longer
finite_ sequences. Contrary to frequential statistics we do not have to
consider a finite sequence as a prefix of an _infinite_ sequence.

If we minimize the mean code-length over functions that satisfy Kraft’s
inequality (6), but without an integer constraint the code-length should be
$\ell\left(a\right)=-\log_{\beta}\left(p_{a}\right)$ and the function $F$ is
given by

$F\left(P\right)=\sum_{a}p_{a}\cdot\log_{\beta}\left(p_{a}\right).$

The function $F$ is proportional to the Shannon entropy and the (negative)
proportionality factor is determined by the size of the output alphabet.

In lossy source coding and rate distortion theory it is important to choose a
distortion function with tractable properties. The notion of sufficiency for
divergence functions was introduced in Harremoës and Tishby (2007) in order to
characterize such tractable distortions functions. In this paper the main
result was that sufficiency together with properties related to Bregman
divergence lead directly to the information bottleneck method introduced by N.
Tishby Tishby et al. (1999). Logarithmic loss has also been studied for lossy
compression in No and Weissman (2015).

###  6.2 Statistics

In statistics one is often interested in scoring rules that are local, which
means a scoring rule where the payoff only depends on the probability of the
observed value and not on the predicted distribution over unobserved values.
The notion of locality has recently been extended by Dawid, Lauritzen and
Parry Dawid et al. (2012), but here we shall focus on the original definition.
The basic result is that the only local strictly proper scoring rule is
logarithmic score that was proved by Bernardo under the assumption that
scoring rule is given by a smooth function Bernardo (1978).

######  Definition 10.

A _local strictly proper scoring rule_ is a scoring rule of the form
$f\left(x,Q\right)=g\left(Q\left(x\right)\right).$

######  Theorem 6.

On a finite space a local strictly proper scoring rule is given by a local
regret function.

###### Proof.

The regret function of a local strictly proper scoring rule is given by

$D\left(P,Q\right)=\sum_{x}P\left(x\right)\left(g\left(P\left(x\right)\right)-g\left(Q\left(x\right)\right)\right).$

If $Q=\left(1-t\right)P+tQ_{i}$ and $P$ and $Q$ are mutually singular then

$\displaystyle D\left(P,Q\right)$
$\displaystyle=\sum_{x}P\left(x\right)\left(g\left(P\left(x\right)\right)-g\left(\left(1-t\right)P\left(x\right)+tQ_{i}\left(x\right)\right)\right)$
$\displaystyle=\sum_{x}P\left(x\right)\left(g\left(P\left(x\right)\right)-g\left(\left(1-t\right)P\left(x\right)+0\right)\right)$

and we see that the regret does not depend on $Q_{i}$ because $Q_{i}$ vanish
on the support of $P.$ Therefore the regret function is local. ∎

######  Corollary 2.

On a finite space with at least three elements a local strictly proper scoring
rule is given by a function $g$ of the form
$g\left(x\right)=a\cdot\ln\left(x\right)+b$ for some constants $a$ and $b.$

Also the notion of sufficiency plays an important role in statistics. Here we
will restrict the discussion to 1-dimensional exponential families. A natural
exponential family is a family of probability distributions of the form

$\frac{\mathrm{d}P_{\beta}}{\mathrm{d}Q}=\frac{\exp\left(\beta
x\right)}{Z\left(\beta\right)}$

where $Q$ is a reference measure on the real numbers and $Z$ is the moment
generating function given by $Z\left(\beta\right)=\int\exp\left(\beta
x\right)\,\mathrm{d}Qx$. Then $x_{1}^{n}\to x_{1}+x_{2}+\dots+x_{n}$ is a
sufficient statistic for the family $\left(P_{\beta}^{\otimes
n}\right)_{\beta}.$

######  Example 6.

In a Bernoulli model a sequence $x_{1}^{n}\in\left\\{0,1\right\\}^{n}$ is
predicted with probability

$\prod_{i=1}^{n}p^{x_{i}}\left(1-p\right)^{1-x_{i}}=\exp\left(\left(\sum_{i=1}^{n}x_{1}\right)\ln\left(p\right)+\left(n-\sum_{i=1}^{n}x_{1}\right)\ln\left(1-p\right)\right).$

The function $x_{1}^{n}\to x_{1}+x_{2}+\dots+x_{n}$ induces a sufficient map
$\Phi$ from probability distributions on $\left\\{0,1\right\\}^{n}$ to
probability distributions on $\left\\{0,1,2,\dots,n\right\\}.$ The reverse map
maps a measure concentrated in $j\in\left\\{0,1,2,\dots,n\right\\}$ into a
uniform distributions over sequences $x_{1}^{n}\in\left\\{0,1\right\\}^{n}$
that satisfy $\sum_{i=1}^{n}x_{1}=j.$

The mean value of $P_{\beta}$ is

$\int x\cdot\frac{\exp\left(\beta
x\right)}{Z\left(\beta\right)}\,\mathrm{d}Qx\,.$

The set of possible mean values is called the mean value range and is an
interval. Let $P^{\mu}$ denote the element in the exponential family with mean
value $\mu.$ Then a Bregman divergence on the mean value range is defined by
$D\left(\lambda,\mu\right)=D\left(P^{\lambda}\left\|P^{\mu}\right.\right).$
Note that the mapping $\mu\to P^{\mu}$ is not affine so the Bregman divergence
$D\left(\lambda,\mu\right)$ will in general not be given by the formula for
information divergence with the family of binomial distributions as the only
exception. Nevertheless the Bregman divergence $D\left(\lambda,\mu\right)$
encode important information about the exponential family. In statistics it is
common to use squared Euclidean distance as distortion measure, but often it
is better to use the Bregman divergence $D\left(\lambda,\mu\right)$ as
distortion measure. Note that $D\left(\lambda,\mu\right)$ is only proportional
to squared Euclidean distance for the Gaussian location family.

######  Example 7.

An exponential distribution has density

$f_{\lambda}\left(x\right)=\begin{cases}\frac{1}{\lambda}\exp\left(-\frac{x}{\lambda}\right)\,,&\mathrm{for}\,x\geq
0;\\\ 0\,,&else.\end{cases}$

This leads to a Bregman divergence on the interval $\left[0;\infty\right[$
given by

$\displaystyle\int_{0}^{\infty}f_{\lambda}\left(x\right)\ln\left(\frac{f_{\lambda}\left(x\right)}{f_{\mu}\left(x\right)}\right)\,\mathrm{d}x$
$\displaystyle=\frac{\lambda}{\mu}-1-\ln\left(\frac{\lambda}{\mu}\right)$
$\displaystyle=D_{-\ln}\left(\lambda,\mu\right)$

This Bregman divergence is called the _Isakura-Saito distance_. The Isakura-
Saito distance is defined on an unbounded set so our previous results cannot
be applied. Affine bijections on $\left[0;\infty\right[$ have the form
$\Phi\left(x\right)=k\cdot x$ for some constant $k>0$. The Isakura-Saito
distance obviously satisfy sufficiency for such maps and it is a simple
exercise to check that the Isakura-Saito distance is the only Bregman
divergence on $[0,\infty]$ that satisfies sufficiency. Any affine map
$\left[0;\infty\right[\to\left[0;\infty\right[$ is composed of a map $x\to
k\cdot x$ where $k\geq 0$ and a right translation $x\to x+t$ where $t\geq 0.$
The Itakura-Saito distance decreases under right translations because

$\displaystyle\frac{\partial}{\partial t}D_{-\ln}\left(\lambda+t,\mu+t\right)$
$\displaystyle=\frac{\partial}{\partial
t}\left(\frac{\lambda+t}{\mu+t}-1-\ln\left(\frac{\lambda+t}{\mu+t}\right)\right)$
$\displaystyle=\frac{\left(\mu+t\right)-\left(\lambda+t\right)}{\left(\mu+t\right)^{2}}-\frac{1}{\lambda+t}+\frac{1}{\mu+t}$
$\displaystyle=-\frac{\left(\lambda-\mu\right)^{2}}{\left(\lambda+t\right)\left(\mu+t\right)^{2}}\leq
0.$

Thus the Isakura-Saito distance is monotone.

Both sufficiency and the Bregman identity are closely related to inference
rules. In Csiszár (1991) I. Csiszár explained why information divergence is
the only divergence function on the cone of positive measures that lead to
tractable inference rules. One should observe that his inference rules are
closely related to sufficiency and the Bregman identity, and the present paper
may be view as a generalization of these results of I. Csiszár.

###  6.3 Statistical mechanics

Statistical mechanics can be stated based on classical mechanics or quantum
mechanics. For our purpose this makes no difference because our theorems are
valid for both classical systems and quantum systems.

As we have seen before

$Ex=kT_{0}\cdot D\left(s\left\|s_{0}\right.\right).$ (25)

Our general results for Bregman divergences imply that the Bregman divergence
based on this exergy satisfies

$D_{Ex}\left(s_{1},s_{2}\right)=kT_{0}\cdot
D\left(s_{1}\left\|s_{2}\right.\right).$

Therefore

$D_{Ex}\left(\Phi\left(s_{1}\right),\Phi\left(s_{2}\right)\right)=D_{Ex}\left(s_{1},s_{2}\right)$

for any map that is sufficient for $\left\\{s_{1},s_{2}\right\\}.$ The
equality holds for any regret function that is reversible and conserves the
state that is in equilibrium with the environment. Since a different
temperature of the environment leads to a different state that is in
equilibrium the equality holds for any reversible map that leave some
equilibrium state invariant. We see that $D_{Ex}\left(s_{1},s_{2}\right)$ is
uniquely determined as long as there exists a sufficiently large set of maps
that are reversible.

In this exposition we have made some short-cuts. First of all we did not
derive equation 25. In particular the notion of temperature was used without
discussion. Secondly we identified the internal energy with the mean value of
the Hamiltonian and identified the thermodynamic entropy with $k$ times the
Shannon entropy. Finally, in the argument above we need to verify in all
details that the set of reversible maps is sufficiently large to determine the
regret function. For classical thermodynamics the most comprehensive
exposition was done by Lieb and Yngvason Lieb and Yngvason (1998, 2010). In
their exposition randomness was not taken into account. With the present
framework it is also possible to handle randomness so that one can make a
bridge between thermodynamics and statistical mechanics. A detailed exposition
will be given in a future paper.

According to Equation (25) any bit of information can be converted into an
amount of energy! One may ask how this is related to the mixing paradox (a
special case of Gibbs’ paradox). Consider a container divided by a wall with a
blue and a yellow gas on each side of the wall. The question is how much
energy can be extracted by mixing the blue and the yellow gas?

We loose one bit of information about each molecule by mixing the blue and the
green gas, but if the color is the _only difference_ no energy can be
extracted. This seems to be in conflict with Equation (25), but in this case
different states cannot be converted into each other by reversible processes.
For instance one cannot convert the blue gas into the yellow gas. To get
around this problem one can restrict the set of preparations and one can
restrict the set of measurements. For instance one may simply ignore
measurements of the color of the gas. What should be taken into account and
what should be ignored, can only be answered by an experienced physicist.
Formally this solves the mixing paradox, but from a practical point of view
nothing has been solved. If for instance the molecules in one of the gases are
much larger than the molecules in the other gas then a semi-permeable membrane
can be used to create an osmotic pressure that can be used to extract some
energy. It is still an open question which differences in properties of the
two gases that can be used to extract energy.

###  6.4 Monotone regret for portfolios

We know that in general a local regret function on a state space with at least
three orthogonal states is proportional to information divergence. In
portfolio theory we get the stronger result that monotonicity implies that we
are in the situation of gambling introduced by Kelly Kelly (1956).

######  Theorem 7.

Assume that none of the assets are dominated by a portfolio of other assets.
If the regret function $D_{G}(P,Q)$ given by (13) is monotone then the regret
function equals information divergence and the measures $P$ and $Q$ are
supported by $k$ distinct price relative vectors of the form
$\left(o_{1},0,0,\dots 0\right)$, $\left(0,o_{2},0,\dots 0\right),$ until
$\left(0,0,\dots o_{k}\right).$

###### Proof.

If there are more than three price relative vectors then a monotone regret
function is always proportional to information divergence which is a strict
regret function. Therefore we may assume that there are only two price
relative vectors. Assume that the regret function is not strict. Then the
function $G$ defined by (12) is not strictly convex. Assume that
$D_{G}(P,Q)=0$ so that $G$ is affine between $P$ and $Q$. Let $\Phi$ be a
contraction around one of the end points of intersection between the state
space and the line through $P$ and $Q$. Then monotonicity implies that
$D_{G}(\Phi(P),\Phi(Q))=0$ so that $G$ is affine on the line between $\Phi(P)$
and $\Phi(Q)$. This holds for contractions around any point. Therefore $G$ is
affine on the whole state space which implies that there is a single portfolio
that dominates all assets. Such a portfolio must be supported on a single
asset. Therefore monotonicity implies that if two assets are not dominated
then the regret function is strict and according to Theorem 1 we have already
proved that a strict regret function in portfolio theory is proportional to
information divergence. ∎

######  Example 8.

If the regret function divergence is monotone and one of the assets is the
safe asset then there exists a portfolio $\vec{b}$ such that $b_{i}\cdot
o_{i}\geq 1$ for all $i.$ Equivalently $b_{i}\geq o_{i}^{-1}$ which is
possible if and only if $\sum o_{i}^{-1}\leq 1.$ One say that the gamble is
_fair_ if $\sum o_{i}^{-1}=1$. If the gamble is _super-fair_ , i.e. $\sum
o_{i}^{-1}<1$, then the portfolio $b_{i}=o_{i}^{-1}/\sum o_{i}^{-1}$ gives a
price relative equal to $\left(\sum o_{i}^{-1}\right)^{-1}>1$ independently of
what happens, which is a _Dutch book_.

######  Corollary 3.

In portfolio theory the regret function $D_{G}(P,Q)$ given by (13) is monotone
if and only if it is strict.

###### Proof.

We use that in portfolio theory the regret function is monotone if and only it
is proportional to information. ∎

##  7 Concluding remarks

In Pitrik and Virosztek (2015) it was proved that if $f$ is a function such
that the Bregman divergence based on $tr(f(\rho))$ is monotone on any (simple)
C*-algebra then the Bregman divergence is jointly convex. As we have seen that
monotonicity implies that the Bregman divergence must be proportional to
inform divergence, which is jointly convex in both arguments. We also see that
in general joint convexity is not a sufficient condition for monotonicity, but
in the case where the state space has only two orthogonal states it is not
known if joint convexity of a Bregman divergence is sufficient to conclude
that the Bregman divergence is monotone.

One should note that the type of optimization presented in this paper is
closely related to a game theoretic model developed by F. Topsøe Topsøe (2008,
2011). In his game theoretic model he needed what he called the perfect match
principle. Using the terminology presented in this paper the perfect match
principle states that the regret function is a strict Bregman divergence. As
we have seen the perfect match principle is only fulfilled in portfolio theory
if all the assets are gambling assets. Therefore the theory of F. Topsøe can
only be used to describe gambling while our optimization model can describe
general portfolio theory and our sufficient conditions can explain exactly
when our general model equals gambling.

The original paper of Kullback and Leibler Kullback and Leibler (1951) was
called “On Information and Sufficiency”. In the present paper we have made the
relation between information divergence and the notion of sufficiency more
explicit. The results presented in this paper are closely related to the
result that a divergence that is both an $f$-divergence and a Bregman
divergence is proportional to information divergence (see Harremoës and Tishby
(2007) or Amari (2009) and references therein). All $f$-divergences satisfy a
sufficiency condition, which is the reason why this class of divergences has
played such a prominent role in the study of the relation between information
theory and statistics. One major question has been to find reasons for
choosing between the different $f$-divergences. For instance $f$-divergences
of power type (often called Tsallis divergences or Cressie-Read divergences)
are popular, but there are surprisingly few papers that can point at a single
value of the power $\alpha$ that is optimal for a certain problem except if
this value is 1. In this paper we have started with Bregman divergences
because each optimization problem comes with a specific Bregman divergence.
Often it is possible to specify a Bregman divergence for an optimization
problem and only in some of the cases this Bregman divergence is proportional
to information divergence.

The idea of sufficiency has different relevance in different applications, but
in all cases information divergence prove to be the quantity that convert the
general notion of sufficiency into a number. In information theory information
divergence appear as a consequence of Kraft’s inequality. For code length
functions of integer length we get functions that are piecewise linear. Only
if we are interested in extend-able sequences we get a regret function that
satisfies a data processing inequality. In this sense information theory is a
theory of extend-able sequences. For scoring functions in statistics the
notion of locality is important. These applications do not refer to sequences.
Similarly the notion of sufficiency that plays a major role in statistics,
does not refer to sequences. Both sufficiency and locality imply that regret
is proportional to information divergence, but these reasons are different
from the reasons why information divergence is used in information theory. Our
description of statistical mechanics does not go into technical details, but
the main point is that the many symmetries in terms of reversible maps form a
set of maps so large that our result on invariance of regret under sufficient
maps applies. In this sense statistical mechanics and statistics both apply
information divergence for reasons related to sufficiency. For portfolio
theory the story is different. In most cases one has to apply the general
theory of Bregman divergences because we deal with an optimization problem.
The general Bregman divergences only reduce to information divergence when the
assets are gambling assets.

Often one talk about applications of information theory in statistics,
statistical mechanics and portfolio theory. In this paper we have argued that
information theory is mainly a theory of sequences, while some problems in
statistics and statistical mechanics are also relevant without reference to
sequences. It would be more correct to say that convex optimization has
various application such as information theory, statistics, statistical
mechanics, and portfolio theory and that certain conditions related to
sufficiency lead to the same type of quantities in all these applications.

## Acknowledgment

The author want to thank Prasad Santhanam for inviting me to the Electrical
Engineering Department, University of Hawai‘i at Mānoa, where many of the
ideas presented in this paper were developed. I also want to thank Alexander
Müller-Hermes, Frank Hansen, and Flemming Topsøe for stimulating discussions
and correspondence. Finally I want to thank the reviewers for their valuable
comments.

## References

  * Kullback and Leibler (1951) Kullback, S.; Leibler, R.  On Information and Sufficiency.  Ann. Math. Statist. 1951, 22, 79–86.
  * Jaynes (1957) Jaynes, E.T.  Information Theory and Statistical Mechanics, I and II.  Physical Reviews 1957, 106 and 108, 620–630 and 171–190.
  * Jaynes (1989) Jaynes, E.T.  Clearing up mysteries – The original goal. In Maximum Entropy and Bayesian Methods; Skilling, J., Ed.; Kluwer: Dordrecht, 1989.
  * Liese and Vajda (1987) Liese, F.; Vajda, I.  Convex Statistical Distances; Teubner: Leipzig, 1987.
  * Barron et al. (1998) Barron, A.R.; Rissanen, J.; Yu, B.  The Minimum Description Length Principle in Coding and Modeling.  IEEE Trans. Inform. Theory 1998, 44, 2743–2760.  Commemorative issue.
  * Csiszár and Shields (2004) Csiszár, I.; Shields, P.  Information Theory and Statistics: A Tutorial; Foundations and Trends in Communications and Information Theory, Now Publishers Inc., 2004.
  * Grünwald and Dawid (2004) Grünwald, P.D.; Dawid, A.P.  Game Theory, Maximum Entropy, Minimum Discrepancy, and Robust Bayesian Decision Theory.  Annals of Mathematical Statistics 2004, 32, 1367–1433.
  * Grünwald (2007) Grünwald, P.  the Minimum Description Length principle; MIT Press, 2007.
  * Holevo (1982) Holevo, A.S.  Probabilistic and Statistical Aspects of Quantum Theory; Vol. 1, North-Holland Series in Statistics and Probability, North-Holland: Amsterdam, 1982.
  * Krumm et al. (2016) Krumm, M.; Barnum, H.; Barrett, J.; Müller, M.  Thermodynamics and the structure of quantum theory.  arXiv:1608.04461.
  * Barnum et al. (2014) Barnum, H.; Müller, M.P.; Ududec, C.  Higher-order interference and single-system postulates characterizing quantum theory.  New Journal of Physics 2014, 16, 123029.
  * Harremoës (2016) Harremoës, P.  Maximum Entropy and Sufficiency.  Proceedings MaxEnt2016. American Institute of Physics (AIP), 2016, [arXiv:1607.02259].
  * Harremoës (2017) Harremoës, P.  Quantum information on Spectral Sets.  arXiv:1701.06688 Accepted for presentation at ISIT 2017.
  * Servage (1951) Servage, L.J.  The Theory of Statistical Decision.  Journal of the American Statistical Association 1951, 46, 55–67.
  * Kiwiel (1997a) Kiwiel, K.C.  Proximal Minimization Methods with Generalized Bregman Functions.  SIAM Journal on Control and Optimization 1997, 35, 1142–1168, [http://dx.doi.org/10.1137/S0363012995281742].
  * Kiwiel (1997b) Kiwiel, K.C.  Free-steering Relaxation Methods for Problems with Strictly Convex Costs and Linear Constraints.  Math. Oper. Res. 1997, 22, 326–349.
  * Rockafellar (1970) Rockafellar, R.T.  Convex Analysis; Princeton Univ. Press: New Jersey, 1970.
  * Hendrickson and Buehler (1971) Hendrickson, A.D.; Buehler, R.J.  Proper scores for probability forecasters.  Ann. Math. Statist. 1971, 42, 1916–1921.
  * Rao and Nayak (1985) Rao, C.R.; Nayak, T.K.  Cross Entropy, Dissimilarity Measures, and Characterizations of Quadratic Entropy.  IEEE Trans. Inform. Theory 1985, 31, 589–593.
  * Banerjee et al. (2005) Banerjee, A.; Merugu, S.; Dhillon, I.S.; Ghosh, J.  Clustering with Bregman Divergences.  Journal of Machine Learning Research 2005, 6, 1705–1749.
  * McCarthy (1956) McCarthy, J.  Measures of the value of information.  Proc. Nat. Acad. Sci. 1956, 42, 654–655.
  * Gneiting and Raftery (2007) Gneiting, T.; Raftery, A.E.  Strictly Proper Scoring Rules, Prediction, and Estimation.  Journal of the American Statistical Association 2007, 102, 359–378, [http://dx.doi.org/10.1198/016214506000001437].
  * Ovcharov (2015) Ovcharov, E.Y.  Proper Scoring Rules and Bregman Divergences.  Sept. 2015. arXiv:1502.01178.
  * Gundersen (2011) Gundersen, T.  An Introduction to the Concept of Exergy and Energy Quality.  Technical report, Department of Energy and Process Engineering, Norwegian University of Science and Technology, Trondheim, Norway, 2011.  http://www.ivt.ntnu.no/ept/fag/tep4120/innhold/Exergy
  * Harremoës (1993) Harremoës, P.  Time and Conditional Independence; Vol. 255, IMFUFA-tekst, IMFUFA Roskilde University, 1993.  Original in Danish entitled Tid og Betinget Uafhængighed. English translation partially available.
  * Kelly (1956) Kelly, J.L.  A New Interpretation of Information Rate.  Bell System Technical Journal 1956, 35, 917–926.
  * Cover and Thomas (1991) Cover, T.; Thomas, J.A.  Elements of Information Theory; Wiley, 1991.
  * Uhlmann (1970) Uhlmann, A.  On the Shannon Entropy and Related Functionals on Convex Sets.  Reports on Mathematical Physics 1970, 1, 147–159.
  * Müller-Hermes and Reeb (2015) Müller-Hermes, A.; Reeb, D.  Monotonicity of the Quantum Relative Entropy Under Positive Maps.  Annales Henri Poincare 2015, [Sept. 2016. arXiv:1512.06117v2].
  * Christandl and Müller-Hermes (2016) Christandl, M.; Müller-Hermes, A.  Relative Entropy Bounds on Quantum, Private and Repeater Capacities.  April, 2016. arXiv:1604.03448.
  * Petz (2003) Petz, D.  Monotonicity of Quantum Relative Entropy Revisited.  Reviews in Mathematical Physics 2003, 15, 79–91, [http://www.worldscientific.com/doi/pdf/10.1142/S0129055X03001576].
  * Petz (1988) Petz, D.  Sufficiency of Channels over von Neumann algebras.  Quart. J. Math. Oxford 1988, 39, 97–108,.
  * Jenčová and Petz (2006) Jenčová, A.; Petz, D.  Sufficiency in quantum statistical inference.  Communications in Mathematical Physics 2006, 263, 259–276.
  * Harremoës and Tishby (2007) Harremoës, P.; Tishby, N.  The Information Bottleneck Revisited or How to Choose a Good Distortion Measure.  Proceedings ISIT 2007, Nice. IEEE Information Theory Society, 2007, pp. 566–571.
  * Jiao et al. (2014) Jiao, J.; amd Albert No, T.C.; Venkat, K.; Weissman, T.  Information Measures: the Curious Case of the Binary Alphabet.  Trans. Inform. Theory 2014, 60, 7616–7626.
  * Jenčová (2017) Jenčová, A.  Preservation of a quantum Rényi relative entropy implies existence of a recovery map.  Journal of Physics A: Mathematical and Theoretical 2017, 50, 085303.
  * Tishby et al. (1999) Tishby, N.; Pereira, F.; Bialek, W.  The information bottleneck method.  Proceedings of the 37-th Annual Allerton Conference on Communication, Controland Computing, 1999, pp. 368–377.
  * No and Weissman (2015) No, A.; Weissman, T.  Universality of logarithmic loss in lossy compression.  2015 IEEE International Symposium on Information Theory (ISIT), 2015, pp. 2166–2170.
  * Dawid et al. (2012) Dawid, A.P.; Lauritzen, S.; Perry, M.  Proper local scoring rules on discrete sample spaces.  The Annals of Statistics 2012, 40, 593–603.
  * Bernardo (1978) Bernardo, J.M.  Expected Information as Expected Utility.  The Annals of Statistics 1978, 7, 686–690.  Institute of Mathematical Statistics.
  * Csiszár (1991) Csiszár, I.  Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems.  Ann. Stat. 1991, 19, 2032–2066.
  * Lieb and Yngvason (1998) Lieb, E.; Yngvason, J.  A Guide to Entropy and the Second Law of Thermodynamics.  Notices of the AMS 1998, 45, 571–581.
  * Lieb and Yngvason (2010) Lieb, E.; Yngvason, J., The Mathematics of the Second Law of Thermodynamics.  In Visions in Mathematics; Alon, N.; Bourgain, J.; Connes, A.; Gromov, M.; Milman, V., Eds.; Birkhäuser Basel, 2010; pp. 334–358.
  * Pitrik and Virosztek (2015) Pitrik, J.; Virosztek, D.  On the Joint Convexity of the Bregman Divergence of Matrices.  Letters in Mathematical Physics 2015, 105, 675–692.
  * Topsøe (2008) Topsøe, F.  Game theoretical optimization inspired by information theory.  Journal of Global Optimization 2008, 43, 553.
  * Topsøe (2011) Topsøe, F.  Cognition and Inference in an Abstract Setting.  Proceedings WITMSE 2011, 2011.
  * Amari (2009) Amari, S.I.  $\alpha$-Divergence Is Unique, Belonging to Both $f$-Divergence and Bregman Divergence Classes.  IEEE Transactions on Information Theory 2009, 55, 4925–4931.