Project Topics
Get Complete Project Material File(s) Now! »
Classical models of finite structures
In this section, we formalize the relation between finite information structures and usual probability spaces. A finite information structure ¹S; Eº is said to be quasiconcrete if for each nonidentity arrow f : X ! Y in S, the map E ¹ f º is a strict surjection. Concrete information structures are quasi-concrete, but the converse is not always true, as explained in this section. Recall that Obsfin¹ º denotes the poset of finite partitions of a set , ordered by the relation of refinement, with arrows implementing the corresponding surjections (see Section 1.1).
Definition 1.13. A classical model of a quasi-concrete information structure ¹S; Eº is a triple ¹ ; 0; #º, where is a set, 0 : S ! Obsfin¹ º is a functor, and # : E ! 0 is a natural transformation such that:
1. 0 is injective on objects;
2. For each X 2 ObS, the component # X : E¹Xº ! 0¹Xº is a b¼ection;
3. If X ^ Y exists, 0¹X ^ Yº 0¹Xº 0¹Yº. We also refers to ¹ ; º as a representation of ¹S; Eº. If ¹ ; 0; #º is a classical model of S, each observable X in S can be associated (not uniquely) to a function ˜X on , in such away that ¹Xº is the partition induced by ˜X .
Under this representation as functions, all observables commute. It is also possible to introduce quantum models, which respect the noncommutativity of quantum observables, see Section 1.5. A concrete information structure, as defined in Section 1.1, can be seen as a classical model of an underlying generalized information structure. We now show that, in certain cases, limS E provides a model for a structure ¹S; Eº. In general, if we begin with a concrete structure S Obsfin¹ º and forget to obtain a generalized structure ¹S; E idº, the set limS E is different from . See Example 1.20. When 0¹Sº is an information structure, ¹0; #º is a morphism in InfoStr, but the following example shows that this is not always the case.
Quantum probability and quantum models
Let V be a finite dimensional Hilbert space: a complex vector space with a positive definite hermitian form h; i. In the quantum setting, random variables are generalized by endomorphisms of V (operators). An operator H is called hermitian if for all u; v 2 V, one has hu; Hvi hHu; vi. Aquantum observable is a Hermitian operator: the result of a quantum experiment is supposed to be an eigenvalue of such operator, that is always a real number.
Afundamental result of linear algebra, the Spectral Theorem [36, Sec. 79], says that each hermitian operator Z can be decomposed asweighted sum of positive hermitian projectors Z ÍKj 1 zjVj where z1; :::; zK are the (pairwise distinct) real eigenvalues of Z. Each Vj is the projector on the eigenspace spanned by the eigenvectors of zj ; the dimension of this subspace equals the multiplicity of zj as eigenvalue. As hermitian projectors, they satisfy the equation V2 j Vj and V j Vj . They are also mutually orthogonal (VjVk 0 for integers j; k), and their sum equals the identity, Í 1jK Vj IdV: This decomposition of Z is not necessarily compatible with the preferred basis of V (that diagonalizes its hermitian product).
In analogy to the classical case,we consider as equivalent two hermitian operators that define the same orthogonal decomposition fVjgj of V by means of the Spectral Theorem, ignoring the particular eigenvalues. For us, observable and orthogonal decomposition (sometimes just ‘decomposition’, for brevity) are then interchangeable terms. In what follows, we denote by VA both the subspace of V and the orthogonal projector on it. A decomposition fVg2A is said to refine fV0
g2B if each V0 can be expressed as sum of subspaces fVg2A , for certain A A. In that case we say also that fVg2A divides fV0 g2B, and we write fVg2A ! fV0 g2B. With this arrows, direct sums decompositions form a category called Orth¹Vº. Definition 1.24. Aquantum model of an information structure S is a triple ¹V; 0; #º, where V is a finite dimensional Hilbert space and : S ! Orth¹Vº is a functor, and # : E ! 0 is a natural transformation such that:
1. 0 is injective on objects.
2. for each X 2 ObS, the component # X : E¹Xº ! 0¹Xº is a b¼ection.
3. if X ^ Y exists, ¹X ^ Yº ¹Xº ¹Yº.
Aquantum model gives rise to a quantum information structure as defined in [10]. All the cohomological computations in this thesis concern classical probabilities, but the general constructions in Chapter 2 only depend on the abstract structure and are equally valid in the quantum case.
Sheaves of modules
We have a general setting for homological algebra, given by abelian categories and cohomological functors. In this section, we develop an important example of abelian category: sheaves of modules. We shall see later that our information-theoretical constructions are naturally related to them.
Let C be a category. A presheaf of sets is any contravariant functor F from C to Sets, the category of sets. A morphism of presheaves : F ! G is a natural transformation of functors. Presheaves of sets and their morphisms form a new category, denoted by PSh¹Cº. By definition,we say the is injective (resp. surjective) if for every X 2 ObC, the map ¹Xº : F¹Xº ! G ¹Xº is injective (resp. surjective). Proposition 2.5. The injective morphisms defined above are exactly the monomorphisms of PSh¹Cº. The surjective morphisms are exactly the epimorphisms of PSh¹Cº. It is possible to define a topology on a category, obtaining a site. Presheaves that are ‘well-behaved’ for this topology are called sheaves. Moreover, every category admits a trivial topology, such that every presheaf is a sheaf. As we shall use the trivial topology over our information structure S, the general definitions of site and sheaf will not play a special role in the theory, and we omit them. For details, see [32, Ch. 0]. If C is a site, we can consider the full subcategory of PSh¹Cº, whose objects are the sheaves; this category is denoted by Sh¹Cº.
Abelian presheaves are presheaves that take values in abelian groups. They form an abelian category (for a proof, see [60, Ch. 9, Prop. 3.1]). A morphism of abelian presheaves : F ! G is a natural transformation between F and G that induces a homomorphism of abelian groups ¹Xº : F¹Xº ! G ¹Xº on every X 2 ObC. Given a morphism : F ! G , the kernel of is the abelian presheaf
X 7! kerf : F¹Xº!G ¹Xºg and its cokernel is X 7! cokerf : F¹Xº!G ¹Xºg. One has coim im, because it holds over each X 2 ObC. Moreover, a sequence of presheaves F1 ! F2 ! F3 is exact if F1¹Xº ! F2¹Xº ! F3¹Xº is exact as a sequence of groups over every X 2 ObC. Given a site C, the category of
abelian sheaves (denoted by Ab¹Cº) is the full subcategory of PAb¹Cº of those abelian presheaves whose underlying presheaves of sets are sheaves.
Information cohomology
Let S be the poset of variables of an information structure ¹S; E º. We view it as a site with the trivial topology (called topologie grossière or chaotique in [4, II.1.1.4]), such that every presheaf is a sheaf. For each X 2 ObS, setSX : fY 2 ObS j X ! Yg, with the monoid structure given by the product of observables in S: ¹Z; Yº 7! ZY : Z ^ Y. Let AX : R»SX¼ be the corresponding monoid algebra. The contravariant functor X 7! AX is a sheaf of rings; we denote it by A . The pair ¹S;A º is a ringed site. For a fixed object G of Mod¹A º, the covariant functor Hom¹G ; º is always additive and left exact. As Mod¹A º has enough injective objects, it is possible to define the right derived functors associated to any left exact additive covariant functor. In the case of Hom¹A; º, the associated right derived functors are called Extn¹G ; º, for n 0.
Let RS¹Xº be the AX-module defined by the trivial action of AX on the abelian group ¹R; +º (for s 2 SX and r 2 R, take s r r). The presheaf that associates to each X 2 ObS the module RS¹Xº, and to each arrow the identity map is denoted RS. Definition 2.7. The information cohomology associated to the poset of variables S, with coefficients in the A -module F, is H¹S;Fº : Ext¹RS;Fº:
Table of contents :
List of Figures
List of Tables
Introduction
0.1 Axiomatic characterizations of entropy
0.2 Functional equations
0.3 Entropy in combinatorics
0.4 A q-deformation of Shannon’s theory
0.5 Information structures
0.6 Topoi and cohomology
0.7 Cohomology of discrete variables
0.7.1 Probabilistic cohomology
0.7.2 Combinatorial cohomology
0.8 Differential entropy and relative entropy
0.9 Cohomology of continuous variables
I Foundations
1 Information structures
1.1 Random variables and probabilities
1.2 Category of information structures
1.3 Probabilities on finite structures
1.4 Classical models of finite structures
1.5 Quantum probability and quantum models
2 Topoi and cohomology
2.1 Preliminaries on homological algebra
2.1.1 Additive categories
2.1.2 Abelian categories
2.1.3 Derived functors
2.1.4 Sheaves of modules
2.2 Information cohomology
2.3 Relative homological algebra
2.3.1 General results
2.3.2 Example: Presheaves of modules
2.4 Nonhomogeneous bar resolution
2.5 Description of cocycles
II Information cohomology of discrete random variables
3 Probabilistic information cohomology
3.1 Functional module
3.2 Functoriality
3.3 Determination of H0
3.4 Local structure of 1-cocycles
3.5 Determination of H1
3.6 Functorial extensions of algebras
3.7 Product structures and divergence
4 Combinatorial information cohomology
4.1 Counting functions
4.2 Description of cocycles
4.3 Computation of H0
4.4 Computation of H1
4.5 Asymptotic relation with probabilistic information cohomology
5 A functional equation for generalized entropies related to the modular group
III Information theory with finite vector spaces
6 The q-multinomial coefficients
6.1 Definition
6.2 Asymptotic behavior
6.3 Combinatorial explanation for nonadditivity of Tsallis 2-entropy
6.4 Maximum entropy principle
7 Grassmannian process
7.1 The q-binomial distribution
7.2 Parameter estimation by the maximum likelihood method
7.3 A vector-space-valued stochastic process associated to the q-binomial distribution
7.4 Asymptotics
8 Generalized information theory
8.1 Remarks on measure concentration and typicality
8.2 Typical subspaces
8.3 Coding
8.4 Further remarks
IV Information cohomology of continuous random variables
9 Simplicial information structures
9.1 Definition and examples
9.2 Probabilities on information structures
9.2.1 Conditional probabilities
9.2.2 Densities under conditioning and marginalization
9.3 Probabilistic functionals
9.4 Restriction to Gaussian laws; functional module
10 Probabilistic information cohomology on simplicial structures
10.1 Computation of H0
10.2 General properties of 1-cocycles
10.3 Computation of H1: Gaussian case
10.3.1 1-cocycles that depend only on the covariance matrix
10.3.2 Decomposition of S as a sum; Convolutions
10.3.3 General cocycles
10.3.4 Axial cochains and the heat equation
11 Grassmannian categories
11.1 Grassmannian information structures
11.1.1 Definition
11.1.2 Measures
11.1.3 Orthogonal embeddings
11.2 Gaussian laws
11.2.1 Mean and covariance
11.2.2 Moments of order two
11.3 Gaussian modules
11.3.1 Module of moderate functionals
11.3.2 Description of cochains and cocycles
11.3.3 Dirac distributions and parallelism
11.3.4 Axial cocycles over S2
11.3.5 Entropy
11.3.6 Moments
11.4 Grassmannian probability modules
12 Generalized entropy and asymptotic concentration of measure
12.1 Asymptotic equipartition property
12.2 Certainty and divergence
12.3 Example: Rectifiable subspaces of Rn
V General background material
A Category theory
A.1 Notations
A.2 Subobjects and quotients
B Abstract simplicial complexes
C Linear algebra
C.1 Schur complements
D Multivariate normal distributions
E Distribution theory
F Measure theory
F.1 Radon-Nikodym derivative
F.2 Product spaces
F.3 Haar measures
Bibliography
