Les univers sont des objects mathématiques beaucoup plus riche que les ensembles qui sont finalement assez ternes, et permettent des analogie dans différents domaines, logique, statistique, thermodynamique, théorie des modèles...
Une notion clef est celle d'indépendance, qui peut être définie de façon exacte dans un univers, puis celle de la quantité d'information qui introduit la notion d'entropie.
La probabilité est définie dans un univers. Nous avons construit les univers en énumérant leurs variables booléennes libres, et en construisant les évènements élémentaires, appelés mondes, comme étant les n-uplets de valeurs possibles de ces variables booléennes. Puis nous avons munie cet univers d'une mesure de probabilité en affectant une valeur comprise entre 0 et 1 à chaque monde, avec comme seul condition que la somme des valeurs des mondes fasse 1. La valeur d'un monde représente sa probabilité.
Comme dans un espace vectoriel, la liste des variables d'univers est appellées une base. Ces variables vont augmenter le langage propositionnelle et permettront de désigner les évènements par des expressions booléennes. La présentation du langage logique est :
L = {0, 1, ¬(.), et(.,.), ou(.,.), <=>(.,.), =>(.,.), w(.,.), +(.,.), *(.,.)}
Nous avons simplement selectionné des opérations logiques courantes d'arité 0, 1 et 2. On a ajouter l'opérations * qui est identique au et, l'opération + qui est identique au "ou exclusif" noté w, et qui modulo l'équivalence, permettent de définir une structure de corps :
B = L/<=>
B = <0,1,+,*>
Nous pouvons prendre tout autre sorte d'opérateur logique pour définir le langage L. Si le langage peut programmer le ¬et, alors il est complet et peut programmer tous les opérateurs logiques d'arité fixée. Puis le langage est augmenté par des variables boléennes, par exemple ajoutons les variables x, y, z. Il s'agit alors d'une extension élémentaire notée :
L[x,y,z]
Et comme L /<=> est une structure de corps, L[x,y,z] / <=> qui est identique à (L/<=>)[x,y,z], c'est à dire à B[x,y,z], est une structure d'anneau des polynômes. Par exemple l'expression booléenne (x => z) w (y=>z) est un mot du langage L[x,y,z], et il désigne modulo l'équivalence, un élément de B[x,y,z] c'est à dire un polynome qui est en l'occurrence x*z + y*z + x + z.
Un évènement est une expression booléenne à équivalence près, c'est à dire un élément de B[x,y,z]. Si deux expressions booléennes sont équivalentes, elles désignent évidement le même évènement. Autrement dit, l'ensemble des évènements, noté E, est identique à la structure L quotientée par relation <=> et étendue aux variables x,y,z. Autrement dit E est identique à l'anneau des polynômes B[x,y,z].
E = B[x,y,z]
E = L[x,y,z] / <=>
L'ensemble des évènements, E, qui constitue l'univers, est un espace vectorielle de dimension égale au nombre de variables libres. Pour munir cet ensemble d'évènements d'une mesure de probabilité, il faut y définir une valuation particulière. Cela peut se faire en définissant une valeur pour chaque évènement élémentaire dont la somme fasse 1, comme indiqué au début, ou bien d'une manière globale en construisant une valuation P vérifiant les propriétés suivantes :
∀e∈E, ∀u∈E
P(e) est réel
P(e) ≥ 0
P(e) ≤ 1
P(¬e) = 1-P(e)
P(e) = P(e et ¬u) + P(e et u)
On verra par la suite que les trois premières conditions pourront changer, en se limitant à des corps dénombrables ou à des corps finis, et en s'étendant à des corps plus riches tel que les complexes ou les quaternions.
Les évènements élémentaires sont appelés mondes ou état microscopique de l'univers, et correspondent à des évènements particulier où toutes les variables d'univers sont déterminées. Un évènement quelconque est une disjonction d'évènements élémentaires, autrement dit un ensemble de mondes, autrement dit un ensemble d'états microscopiques possibles pour un même état macroscopique que constitu l'évènement.
Une notion clef pour exploiter les probabilités, est la notion d'indépendance. Deux évènements u,v sont indépendants si et seulement si la probabilité de leur conjonction est égale au produit de leur probabilité :
Sémantiquement, la probabilité est une fréquence d'apparition. L'univers énumère ses mondes de façon aléatoire en respectant sa loi de probabilité que constitue la liste des probabilités élémentaires, et en respectant une notion plus difficile à décrire qu'est l'indépendance de l'ordre d'énumération. On contourne cette dernière difficulté en ignorant l'ordre d'énumération des tirages. A chaque tirage au sort apparait un monde possible de l'univers.
Lorsque le nombre N de tirage est suffisament grand, la probabilité d'un évènement e, est égale à sa fréquence d'apparition, c'est à dire au nombre de tirages où l'évènement a eu lieu divisé par le nombre totale de tirages. Mais cette égalité n'est qu'une approximation qui peut être rendu aussi fine que l'on veut en prenant N suffisament grand.
On définie sémantiquement P(u / v), la probabilité de u sachant v, comme étant la fréquence de l'évènement u parmis les évènements v. Mais cette égalité n'est qu'une approximation qui peut être rendu aussi fine que l'on veut en prenant N suffisament grand.
On lui préfère la notation exacte et non approximée, en terme de probabilité et qui constitue sa définition formelle :
L'évènement u est indépendant de v si et seulement si la probabilité de u sachant v ne diffère pas de la probabilité de u, c'est à dire si et seulement si P(u / v) = P(u).
En supposant {u,v} indépendant, et en utilisant les propriété de la valuation P, nous déduisons :
P(u) = P(u et v) + P(u et ¬v)
P(u) = P(u)*P(v) + P(u et ¬v)
P(u) - P(u)*P(v) = P(u et ¬v)
P(u)*(1 - P(v)) = P(u et ¬v)
P(u)*P(¬v) = P(u et ¬v)
{u,¬v} indépendant
Et donc par symétrie {u,v} indépendant entraine {u,¬v} indépendant et {¬u,v} indépendant et {¬u,¬v} indépendant.
Un ensemble d'évènements est dit indépendant si pour tous ses sous-ensembles, le produit des probabilités de ses éléments est égale à la probabilité de leur conjonction. Ainsi pour {x,y,z} nous avons :
{x,y,z} indépendant <=> P(x et y) = P(x)*P(y)
P(x et z) = P(x)*P(z)
P(y et z) = P(y)*P(z)
P(x et y et z) = P(x)*P(y)*P(z)
Cela fait 4 équations nécessaires. Et dans le cas de n évènements indépendants, il y a 2n - n - 1 équations.
Etant donné un ensemble d'évènements indépendant {x,y,z,t}, la probabilité d'une conjontion d'évènements parmis ceux-ci et leur négations, à condition de ne pas choisir à la fois un évènement et sa négation, est égale au produit des probabilités des évènements ou de leur négations qui la compose. Par exemple nous aurons P(x et ¬y et t) = P(x)*P(¬y)*P(t).
---- 6 avril 2013 ----
Par raison de symétrie, en l'absence de connaissance préalable sur la table de vérité, sachant que la charge de la preuve revient aux intéréssés, la liste des évènements élémentaires est supposée équiprobable. Et c'est le caractère structurellement élémentaire et non-divisible des évènements considérés qui conforte ce principe. Ainsi le quanta de probabilité est égale à l'inverse de la cardinalité de l'univers. Un univers à n degrés de liberté booléen possède 2^n mondes, chacun ayant une probabilité élémentaire égale à 1 / 2^n.
Un évènement e est une expression booléenne, et c'est aussi un ensemble de mondes qui correspond exactement à sa décomposition en une disjonction d'évènements élémentaires. Un évènement e est donc un esnsemble de mondes et possède une cardinalité notée |e|. La probabilité de l'évènement e est :
P(e) = |e| / 2^n
L'évènement le plus précis est l'évènement élémentaire car il désigne exactement un seul monde. Et il correspond à une quantité d'information de n bits, qui contient les valeurs des n variables d'univers déterminant le monde tiré au sort. Les autres évènements sont des ensembles d'évènements élémentaires et ne précise pas, parmis leurs éléments, celui qui a été tiré au sort. Ils correspondent alors à une quantité d'information moindre. Le calcul de la quantité d'information se fait à partir de l'entropie.
On définie l'entropie S(e) comme étant le logarithme en base 2 du nombre d'états microscopiques pour le même état macroscopique, l'évènement e correspondant à l'état macroscopique, et les évènements élémentaires correspondants aux états microscopiques :
S(e) = log(|e|)
Cela correspond au nombre de bits nécessaires pour pouvoir représenter (ou plus exactement numéroter) un évènement élémentaire parmis ceux de e. Notons true (identique à la valeur logique 1) l'évènement toujours réalisé qui comprend tous les évènements élémentaires. Il y a 2^n évènements élémentaires. Nous avons donc :
|true| = 2^n
S(true) = n
Puis on définie la quantité d'information acquise globalement (comprenant ajout et perte) d'un système passant de la connaissant u à la connaissance v.
I(u --> v) = S(u) - S(v)
Puis la quantité d'information apporté par la connaissance u sachant v qui est définie ainsi :
I(u / v) = I(v --> u et v)
I(u / v) = S(v) - S(u et v)
I(u / v) = log(|v|) - log(|u et v|)
I(u / v) désigne la quantité d'information apportée par le message "l'évènement élémentaire qui a été tiré au sort appartient à u" à un système possédant déjà l'information "l'évènement élémentaire qui a été tiré au sort appartient à v".
I(u) = I(u / true)
I(u) = log(|true|) - log(|u|)
I(u) = n - log(|u|)
L'entropie nulle correspond à une connaissance maximale, et l'entropie maximale correspond à une connaissance nulle :
si |e| = 1 alors S(e) = 0 et I(e) = n
S(true) = n
I(true) = 0
L'univers et les mondes se définissent également en logique. Un univers est définie par une liste de variables booléennes tel que x, y ,z et se note U(x, y ,z). Un monde de cet univers est une liste de valeurs pour ces variables. Par exemple considérons l'univers Ω de dimension 3 avec comme variables d'univers x,y,z. (Ces 3 variables représentent 3 bits, c'est à dire 3 mémoires booléennes) :
Ω = U(x, y ,z)
L' ensemble des mondes possibles de Ω se note également Ω. On laisse le soin au contexte de lever l'ambiguité, à savoir si l'on parle d'ensemble de mondes Ω ou d'une structure de donnés Ω composée de n bits.
Ω = {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}
En logique, les mondes sont appelés modèles, mais nous continuerons à les appeller mondes car nous leur donnerons par la suite des qualités d'avantage constructives et probabilistes qui les diffèrecieront inévitablement de leurs conceptions initiales de modèles au sense classiques.
Lorsque l'on ne considère que des variables ayant un nombre fini d'états possibles, alors le modèle est une formule complète qui spécifie une valeur pour chaque variable d'univers. Un monde est un modèle, une formule complète, un évènement élémentaire, un état microscopique.
Les mondes sont codés en des entiers, selon un ordre naturel, qui correspond à l'endianess big-endian. Le monde (x,y,z,t) est codé par l'entier x*2³ + y*2² + z*2¹ + t*2⁰. La notation (u0,u1,u2,u3) désigne l'état microscopique de l'univers caractérisé par l'égalité des 4 premières valeurs booléennes (u0,u1,u2,u3) aux 4 premières variables de l'univers (x,y,z,t), c'est à dire, l'état microscopique caractérisé par x=u0, y=u1, z=u2, t=u3.
État microscopique, évènement élémentaire, monde, modèle, formule complètes, sont cinq synonymes. Le terme générique est monde.
On définie le langage logique L.
L = {false, true, ¬(.), et(.,.), ou(.,.), <=>(.,.), =>(.,.), w(.,.), +(.,.), *(.,.)}
Puis on étend ce langage aux variables d'univers. C'est une une extension élémentaire notée :
L[x,y,z]
Les expressions de ce langage définissent d'autres variables booléennes. Par exemple l'expression (x => z) w (y=>z) qui appartient bien à L[x,y,z] définie une nouvelle variable que nous appellerons f :
f = (x => z) w (y=>z)
Mais cette variables est liées aux variables d'univers x,y,z. La variable f n'est pas une variable libre, sa valeur est déterminée dans chaque monde. La variable liée f correspond exactement à un évènement, l'évènement désigné par la formule f. Un évènement représente une formule modulo la relation d'équivalence près, ainsi deux formules équivalentes désignent le même évènement.
La définition de f est également une formule, un programme de calcul de f, ou plus exactement une interface de calcul entre f et le framwork L[x,y,z]. Un langage devient un framwork lorsque chacun de ses opérateurs est programmé et peut être ainsi évalué par un calcul. (Le calcul de la valeur d'un opérateur programmé utilise des ressources pour s'effectuer. Quels types de ressource faut-il considérer ? a priori il faut considérer des ressources mémoires en nombre de bits, des ressources procédurales en nombre de processeurs, et des ressources calculatoires en nombre de cycles de calcul pour chaque processeur. Qu'est ce-qu'un calcul ? Nous ne répondrons pas tout de suite à cette question.)
La table de vérité d'une variables liées f (c'est à dire d'un évènement) contient simplement la liste de ses valeurs pour chaque monde possible. Chaque ligne de la table de vérité correspond à un monde :
(x,y,z)
Les mondes étant numérotés selon l'ordre naturel. La variable liée f est décrite par la suite naturelle de ses valeurs (0,0,1,0,1,0,0,0) et correspond exactement à un évènement. Ces valeurs s'obtiennent en développant l'expression booléenne f en une disjonction de formules complètes, appelée sa Forme Normale Disjonctive, une disjonction de d'évènements élémentaires, de mondes, mis dans l'ordre sous forme d'une suite et dans laquelle on a enlevé les identifiants des mondes rendus redondant avec l'ordre naturel de la suite.
Dans un univers à n dimensions, les variables liées (ou évènements) corespondent exactement aux listes de 2^n valeurs booléennes. Il y a donc 2^(2^n) variables liés différentes (ou évènements différents). On les appel aussi classes d'equivalence des formules.
Un monde spécifie la valeur de chaque variable d'univers. Une formule f du langage L[x,y,z], (c'est le langage propositionnel étendue aux variables d'univers x,y,z), se résoud dans chaque monde, en remplaçant ses variables par leur valeurs définies dans le monde en question, et possède alors un résultat booléen. Etant donné un monde m, et une formule f. On dira que m satisfait f, ou que f est satisfaite dans m, si et seulement si f est vrai dans m, c'est à dire a pour valeur résultat 1 (true), et on notera
m ⊨ f
Inversement si f est faux dans m, on notera
m ⊭ f
L'évènement e correspond à la formule f modulo la relation d'équivalence. Etant donné un monde m, et un évènement e. On dira que m réalise e, ou que e est réalisé dans m, si et seulement si e contient m dans ses alternatives, c'est à dire si m appartient à e, et on notera :
m ∈ e
Inversement si l'évènement e n'est pas réalisé dans m, on notera
m ∉ e
Noter que cette notation fait implicitement le choix de décomposer l'évènement en une disjonction d'évènements élémentaires, c'est à dire de considérer l'évènement comme un ensemble de mondes. D'autre choix sont possibles qui entraineront d'autres notations naturelles.
Les formules se répartissent en trois catégories :
La tautologie est définie comme étant une formule toujours vrai. Une formule est tautologique si et seulement si elle est satisfaite dans tous les mondes de l'univers.
La contradiction est définie comme étant une formule toujours fausse. Une formule est incohérente si et seulement si elle n'est satisfaite dans aucun monde de l'univers.
La contingence est définie comme étant ni la tautologie ni la contradiction. Une formule est contingente si et seulement si il existe deux mondes dans l'univers pour lesquel la formule est satisfaite dans le premier monde et n'est pas satisfaite dans le second monde.
Dans tous les mondes f est vrai. Il existe au moins un monde m où f est faux. Dans tous les mondes f est faux.
Il existe au moins un monde m où f est vrai.
On définie les trois autres catégories duales obtenues par négation :
La cohérence est définie comme étant la non contradiction. Une formule est cohérente si et seulement si elle est satisfaite dans au moins un monde de l'univers.
L'évènement est une formule modulo la relation d'équivalence. C'est aussi un ensemble de mondes. Dans un univers, on distingues 2 types d'évènements particulièrements simples : les évènements élémentaires, et les évènements de base. L'évènement élémentaire correspond à un singleton, il est réalisé dans un et un seul monde. L'évènement de base précise la valeur d'une variable d'univers, il est réalisé dans tous les mondes où cette variable à la valeur désignée.
La classification des formules selon les trois catégories ; tautologique, contingente, contradictoire, se traduit par une classification des évènements ; l'évènement true réalisé dans tous les mondes, l'évènement false réalisé dans aucun monde, et les autres évènements dits contingents ni true ni false, c'est à dire réalisés dans un monde et non réalisé dans un autre. L'évènemnet true est l'ensemble de tous les mondes, l'évènement false est l'ensemble vide. Les évènements contingents sont les sous-ensembles propres.
La formulation m ⊨ f étant disymétrique, il convient de regarder s'il on ne peut pas donner une signification à la formulation inverse f ⊨ m, à savoir une formule f satisfaisant un monde m, faisant de la formule un monde, et d'un monde une formule. On peut le faire naturellement. Par exemple, considérons un univers à deux dimensions U(x,y). Dans cette univers il y a 4 mondes, représentés par les 4 formules complètes et leur différents codes.
complète
nominal
selon la base
(x,y)
selon la base
(x,y)
selon la base
(x,y)
selon la base
(x,y)
Une formule quelconque telle que (x ou y), mise sous sa Forme Normal Disjonctive constitue une disjonction de formules complètes (¬x et y) ou (x et ¬y) ou (x et y), c'est à dire un ensemble de mondes {{x=0, y=1}, {x=1, y=0}, {x=1, y=1}}, c'est à dire un évènement. Et cet évènement va constituer un méta-monde, c'est à dire un méta-èvènement élémentaire :
Forme Normale Disjonctive
selon la base (x,y)
selon la base (x,y)
selon la base (x,y)
Méta-évènement élémentaire
selon la base (x,y)
selon la base (x,y)
selon la base (x,y)
selon la base (x,y)
selon la base (x,y)
selon la base (x,y)
Le méta-univers de U(x,y) est l'univers construit à partir des 4 mondes de U(x,y) (codés en entier selon la base (x,y) par {0,1,2,3}), posés comme des variables boléennes libres. Il se note U(M0, M1, M2, M3) où :
La formule représente un méta-monde, c'est à dire un monde dans le méta-univers. Et le monde représente une méta-variable, c'est à dire une variable dans le méta-univers. Et une variable est une formule simple. Par exemple, le monde (x et y) représente la méta-variable M3, et la formule (x<=>y) représente le méta-monde (M0 et ¬M1 et ¬M2 et M3)
Pour que la dualité existe il faut qu'on retourne sur nos pieds aprés deux opérations de symétrie. Autrement dit, le méta-méta-univers est-il identifiable à l'univers ?
Il convient de décrire plus précisèment la structure composée d'un univers et de son méta-univers, et de codifier toutes les étapes de construction et de transformation s'y opèrant. On formalise les différentes représentations comme autant de langages, et on nomme les transformations permettant de passer de l'une à l'autre.
Etant donné un univers de dimension n et de variables booléennes x,y,z.... La cardinalité de l'ensemble des variables {x,y,z...}est donc égale à n. Les variables rangées dans l'ordre forme la base (x,y,z...). Les mondes ont trois représentations appellés mondes codés, mondes entiers, mondes ensembles.
On numérote les variables en commençant par zéro.
0 désigne x,
1 désigne y,
2 désigne z,
etc..
Délors il n'est plus nécessaire de préciser la base. La base par défaut est (0,1,2...).
Revisitons les exemples précédents :
Méta-monde nommé
Pour nommer les mondes on utilise des expressions du genre 3↢1 qui signifie que la variable n°3 est affecté à la valeur 1. Et on laisse le soin au contexte de déterminer le niveau de codage entier des noms de variable, à savoir si c'est une variable, un monde utilisé comme variable, un meta-monde utilisé comme variable, etc.. Sachant qu'un monde doit affecter chaque variable de l'univers à une valeur.
La probabilité est définie dans un univers. Mais l'univers, dans sa généralité, est essentiellement définie par l'ensemble des mondes, c'est à dire l'ensemble des évènements élémentaires. Nous avons détaillé un certain type d'univers où les mondes sont obtenus comme des n-uplet de booléens. Il existe donc une partie mécanique dans l'univers qui construit les mondes à partir d'éléments de base d'une autre nature tel que des variables booléennes libres, et qui est le plus souvent ignorée par les probabilistes purs qui ne s'intérressent qu'à l'ensemble des évènements élémentaires et à la mesure de leur probabilité. Ce mécanisme de construction peut être aussi complexe que l'on veut, c'est un programme écrit dans un langage de programmation, mais un langage finie et un programme de taille finie.
Pour nous familiariser, nous procédons par étapes. Une première généralisation consiste à prendre des variables de base autres que booléennes, qui possède un nombre d'états plus important spécifique à chaque variable. Le mécanisme de construction des évènement élémentaires se perfectionne. Un monde est maitenant un n-uplet de valeurs non nécessairement booléennes. Mais les valeurs dont il s'agit sont bornées et ordonnées, et peuvent ainsi être codées simplement, de manière naturelle. On identifie ces valeurs à des éléments d'un anneau Z/nZ ou d'un sous ensemble d'entiers de la forme {0,1,2...n}. Ces deux structures seront souvents utilisées.
Le type d'univers est définie par la liste des nombres d'états de chaque variable de la base. Ainsi U(3,2) désigne un type d'univers où les mondes sont composés d'une première valeur ternaire (pouvant être 0, 1, 2) et d'une seconde valeur booléenne (pouvant être 0, 1). Les mondes sont numérotés dans l'ordre naturel, un ordre respectant l'endianess big-endian, c'est à dire pour l'exemple U(3,2) nous avons la liste des mondes dans l'ordre (0,0), (0,1), (1,0), (1,1), (2,0), (2,1). Par convention une liste commence par les éléments jugés les plus important, c'est le principe de l'endianess big-endian, on accorde un poid plus fort au premier terme d'une liste. On considère qu'il convient de transmettre en premier l'information la plus importante, et en second celle un peu moins importante et aini de suite, et on considère que le mécanisme de transmission et de lecture d'une liste, lit une liste selon son ordre naturelle, c'est à dire en lisant d'abord le premier élément puis le second, puis en incrémentant d'un en un un curseur lit les éléments suivants de gauche à droite ainsi de suite.
Dans un type d'univers U(A,B,C,D), un monde (x,y,z,t) est codé naturellement par l'entier x*B*C*D + y*C*D + z*D + t. l'univers comprend A*B*C*D mondes pour lesquels il faut préciser une probabilité élémentaire, afin de parachever l'univers. Cela peut se faire avec une fonction, notée sous forme de variable indicée Pn, qui associe à tout entier compris entre 0 et A*B*C*D-1 une valeur réel positive. Ainsi l'univers U(A,B,C,D)(n-->Pn) est complétement définie si A, B, C, D sont définie et si la fonction (n-->Pn) est définie sur l'ensemble {0, 1, 2...., A*B*C*D-1}. La probabilité doit respecter de plus une règle supplémentaire, la somme des probabilités élémentaires doit être égale à 1. Sans cette dernière règle, la valuation positive (n-->Pn) correspond à munir chaque monde d'un poid, et si on divise chaque poid par la sommes des poids, on obtient alors une probabilité.
L'entropie d'une formule, relativement à un univers équiprobable, est égale au logarithme du nombre des mondes (appartenant à l'univers en question) qui la satisfont.
Une proposition logique e est une disjonction de formules complètes, autrement dit un ensemble de mondes, l'ensemble des mondes où la proposition logique est vrai, et c'est aussi un ensemble d'états microscopiques, pour un même état macroscopique que représente la proposition logique. C'est pourquoi on définie l'entropie d'une proposition logique, comme étant égale au logarithme en base 2 du nombres de mondes la satisafaisant.
S(e) = log(|e|)
S(e) représente le nombre de bits nécessaires pour mémoriser, ou plus exactement pour numéroter, les différents états microscopiques possibles. Le gain d'information se traduit par une diminution d'entropie. Sans connaissance préalable, les 2^n états microscopiques de l'univers sont possibles, et il faut n bits pour les numéroter. Puis après avoir reçu un message nous informant que l'évènement réalisé est e, il n'y a plus que |e| états microscopiques possibles et il est seulement nécessaire d'avoir log(|e|) bits pour pouvoir les mémoriser en les numérotant, le gain d'information est donc de n - log(|e|) bits.
Comment définir l'entropie d'un univers ? Il existe plusieurs définitions possibles, plusieurs notions d'entropie d'univers. On pourrait penser que l'entropie de l'univers est simplement égale au logarithme en base 2 du nombre de ses mondes.
S(Ω) = log(|Ω|)
Mais si la probabilité d'un monde est nulle, est-il pertinent de le comptabiliser ?. Ne faudrait-il pas restreindre la formules aux seuls mondes possibles (c'est à dire de probabilité non nulle). Et même d'avantage, ne faudrait-il pas alors tenir compte pleinement des probabilités des mondes dans le calcul de l'entropie de l'univers ?. Cela s'appelle l'entropie de la source, et la formule reste valable pour les cas d'univers équiprobables.
On procéde ainsi autrement en calculant la quantité d'information apporté par le message engendré par l'univers que constitue la succéssion de ses tirages au sort de monde, des mondes mis sous forme de caractères. Et cela s'appelle l'entropie de la source. L'univers est considéré comme une source d'information qui émet un flux de caractères, où chaque caractère correspond à un monde tiré au sort. L'ordre des tirages n'intervient pas, la source est dite sans mémoire. Un message est une portion de ce flux de caractères.
Dans un univers équiprobable, chaque caractère apporte une même quantité d'information égale au nombre de bits nécessaires pour numéroter les différents caractères possibles qui sont les différents mondes possibles de l'univers. La source est alors dite sans redondance. Et son entropie est S(Ω) = log(|Ω|).
Connaissant la loi de probabilité de l'univers, c'est à dire la probabilité élémentaire de chaque monde, le caractère émis, c'est à dire le monde qui a été tiré au sort, nous apporte une quantité d'information qui peut être évaluée. Le gain d'information apporté par ce caractère, traduit l'évolution entre notre connaissance, avant réception, exprimée par la probabilité P du caractère en question, et notre connaissance après réception, exprimée par la certitude du caractère en question, c'est à dire une probabilité 1.
I = log (1) - log(P)
I = - log(P)
I = log(1/P)
Le logarithme est en base 2 car l'unité d'information est le bit. P est la probabilité du caractère estimé par le système avant reception, et qui correspond à la probabilité du caractère tel qu'il est définie dans l'univers. C'est la formule de Wiener, établie en 1948, qui définie la quantité d'information I(e) = - log(P(e)) apportée par un évènement e de probabilité P(e). Pour la démontrer, il faut faire l'hypothèse suivante, supposer l'existe d'une mesure de la quantité d'information I définie sur l'ensemble des évènements telle que ∀e I(e) ≥ 0, et telle que si deux évènements e1 et e2 sont indépendant alors I(e1 et e2) = I(e1) + I(e2), et telle que I(1/2) = 1 bit.
Maintenant répétons un grand nombre de fois l'opération. L'univers est une source sans mémoire générant n caractères de probabilité Pn. La quantité d'information moyenne apportée par un tirage obéit à la loi de probabilité :
Imoyen = - (P0*log(P0) + P1*log(P1) + P2*log(P2) + P3*log(P3) + .... + Pn-1*log(Pn-1))
Imoyen = - log(P0P0 * P1P1 * P2P2 * P3P3 * ... * Pn-1Pn-1)
L'entropie d'un univers, aussi appellée entropie de la source, est égale la quantité d'information apportée en moyenne par un caractère, c'est à dire par un tirage au sort d'un monde selon la loi de probabilité de l'univers en question.
D'après la théorie de l'information (C.E. Shannon), une source sans mémoire génère un message qui ne peut dans sa généralité être comprimé d'avantage que par son codage entropique c'est à dire utilisant en moyenne un nombre de bits par caractères égale à son entropie.
Pour un univers équiprobable possèdant n mondes, la probabilité d'un monde est 1/n, et donc la quantité d'information apportée par un caractère est log(n). Et cela correspond à l'entropie de l'univers en question. Parcontre, pour un univers certain, qui ne possède qu'un monde sûre, de probabilité 1, l'entropie est nulle. Les tirages n'apportent aucune information puisque nous savons à l'avance qu'elle est l'unique monde qui sera tiré.
L'univers se différencie d'une formule puisqu'il introduit pleinement les probabilités. Et si nous regardons les formules comme des sous-univers, des univers restreincts aux seuls mondes satifaisants la formule et où la probabilité de chaque monde est redéfinie en la divisant par la probabilité de la formule afin que leurs somme soit bien égale à 1, alors nous pouvons définir une seconde entropie pour les formules, relative à un univers, et qui prenne pleinement en compte les probabilités. La forrmule est considéré comme un sous-univers puis comme une source d'information.
Etant donné une formule e satisfaite exactement dans n mondes m1, m2, m3, ..., mn de probabilités respectives p1, p2, p3, ..., pn. L'entropie de e est :
S(e) = - log( (P1/Q)(P1/Q) * (P2/Q)(P2/Q) * (P3/Q)(P3/Q) * ... * (Pn/Q)(Pn/Q) )
S(e) = - ((P1/Q)*log(P1/Q) + (P2/Q)*log(P2/Q) + (P3/Q)*log(P3/Q) + ... + (Pn/Q)*log(Pn/Q))
S(e) = log(Q) - log(P0P0 * P1P1 * P2P2 * P3P3 * ... * Pn-1Pn-1)/Q
où Q = p1+p2+p3+...+pn.
Dans le cas d'un univers équiprobable, l'entropie d'une formule e est log(|e|).
Cette deuxième définition de l'entropie, appelée entropie de la source, complète en faite la première. Elle coïncide avec la première dans les cas d'univers équiprobables, et elle permet de tenir compte pleinement des probabilités. Il apparait alors un paradoxe. Lors de l'apport d'information que constitue la connaissance d'une formule e, il se peut que l'entropie du système augmente, ce qui devrait traduire une perte d'information.
Explorons ce paradoxe dans un cas simple pour pouvoir percevoir les conceptes pertinents devant être mis en avant. L'exemple se base sur un univers à 2 dimenssions de loi de probabilité Ω = (5/8, 1/8, 1/8, 1/8), c'est à dire dont la table de vérité est :
binaire
entier
Probabilités
probabilités
et la formule considéré est :
e = x ou y
On considère un système qui connait la loi de probabilité de l'univers, c'est à dire la probabilité d'apparition de chaque monde. Il peut quantifier l'information apporté par la connaissance du monde tiré au sorts sachant sa probabilité dans l'univers.
I(¬x et ¬y) = - log(5/8) = 0.678
I(¬x et y) = - log(1/8) = 3
I(x et ¬y) = - log(1/8) = 3
I(x et y) = - log(1/8) = 3
A chaque monde correspond un caractère, ici les caractères peuvent être définis par le code entier des mondes 0,1,2,3. Le message est alors une suite finie de ces caractères, c'est à dire un élément de {0,1,2,3}*, où * est l'opération de Kleene. Le message de n caractères bruts occupe n*2 bits. Cela correspond à n fois l'entropie de la source dans le cas d'un univers équiprobable.
Il existe un encodage qui permet de mémoriser ce message sur un nombre plus petit de bits basé sur la quantité d'information apportée par chaque caractère. Lorsque le caractère 0 se produit il peut être idéalement mémorisé sur 0.678 bit, et lorsque le caractère 1, 2 ou 3 se produit il peut être mémorisé sur 3 bits. Cet encodage correspond à une compression lorsque n est grand.. La compression s'opère sur une portion du flux de caractères appelée message. Par exemple le message 0000000000 occupe 10*2 = 20 bits, et pourra se comprimer sur 10*0.678 = 7 bits. Et le message 1231231231 une fois encodé occupera 10 * 3 = 30 bits, soit d'avantage de bits. La compression ne se perçoit que statistiquement sur des longs messages. Le message 0001000200 une fois encodé occupera 8*0.678 + 2*3 = 12 bits.
Si on acquère l'information suivante, que le monde tiré satisfait la formule e = x ou y, alors on opère une restriction d'univers. Tout ce passe comme si nous nous trouvions devant un nouvel univers constitué du premier univers et d'un filtre ne laissant passer que les mondes satisfaisants la formule e. La lois de probabilité de cet univers restreint s'obtient simplement en divisant les probabilités de chaque monde satisfaisant e par leur sommes. Et cet univers peut avoir une entropie plus grande (mais ne dépassant pas celle du à l'équiprobabilité appliqué aux |e| mondes satisfaisant e), comme on peut le constater par l'expérience. Et, c'est une illusion du à la compression du temps qu'opère en fin de compte cette restriction.
Pour construire notre algorithme de compression on part du cas le plus simple, une source constituée par un univers à une dimension booléenne de probabilité P. Les messages sont des éléments de {0,1}*, et la probabilité de tiré le caractère 1 vaut P, et la probabilité de tiré le caractère 0 vaut 1-P. La théorie de l'information nous dit alors que le caractère 1 apporte une quantité d'information égale à -log(P) bits, et le caractère 0 apporte une quantité d'information égale à -log(1-P) bits. Il ne reste plus qu'à trouver l'algorithme canonique d'encodage qui concrétise cette quantité d'information au bit près pour un message de n caractères.
.../...
Comme pour les structures, les moyens de construction d'univers se regroupent selon 4 grande schémas : La restriction, l'extension, le quotientage, et la concrétisation.
Dans les schémas de restriction, la formule joue le rôle principal. Dans les schémas d'extension, le produit directe joue le rôle principal. Dans les schémas de quotientage, il faut considérer à part les quotientages sur les produits directes d'univers permettant de définir des produits directes d'univers à un groupe de permutation près.
.../...
Le produit directe de deux univers U*V se définie canoniquement. Un mondes de l'univers U*V est un couple d'un monde de U et d'un monde de V. La base de l'univers U*V, c'est à dire la liste de ses variables dans l'ordre (selon l'endianess big-endian), s'obtient en concaténant les bases de U et de V dans l'ordre. L'entropie d'un produit direct d'univers est égale à la somme des entropies. L'univers se comporte comme un système physique, et le produit directe de deux univers consiste à réunire les deux systèmes dans un ordre pour ne former qu'un système.
Le quotientage se fait selon une relation d'équivalence. Il y a des relations d'équivalence structurelles qui apparaissent lorsque on opère un produit directe d'un même univers n fois. Elles correspondent aux groupes de permutations de n éléments. Et elles permettent de définir des produits directe d'univers à un groupe de permutation près.
On considère l'univers comme un monde d'un méga-univers. Mais pour cela, il faut quantifier les probabilités afin qu'il n'y ait qu'un nombre finie de configurations possibles et qu'elles ne portent finalement qu'une quantité d'information finie. Il y a plusieurs façons de quantifier les probabilités, de définir un méga-univers, ouvrant chacune à la définition d'une entropie spécifique.
Pour des raisons d'interropérabilité, il est pertinent de choisir comme ensemble sous-jacent des probabilitées, un ensemble qui peut être en lien avec l'ensemble sous-jacent des valeurs des variables d'univers. Une première construction consiste à considérer des quantas de probabilité 1/n.
Ce faisant, un type d'univers possèdant K mondes ne peut définire qu'un nombre fini d'univers répartissant les n quanta de probabilité sur ses K mondes. Et il y a (n+K-1)! / (n!*(K-1)!) configurations possibles. Avec l'hypothèse que l'univers est un monde du méga-univers ainsi définie, la quantité d'information qu'il représente est tout simplement log((n+K-1)! / (n!*(K-1)!)), c'est le nombre de bits nécessaires pour numéroté chaque univers possible, monde du méga-univers. C'est l'entropie de la formule true dans le méga-univers, chaque état microscopique du méga-univers correspondant à un univers. Et c'est l'entropie du méga-univers dans le cas d'un méga-univers équiprobable.
------- 30 avril 2012 ------
Pour calculer la probabilité sur des évènements portant sur non pas un tirage mais n tirage
L'estimation des probabilités à partir de n tirages
On considère un univers qui comprend une variable booléenne de probabilité p. On veut calculer la probabilité des différents résultats pe que l'on peut obtenir en estimant la probabilité p à partir de n tirages. Pour modéliser ce calcul, on définie un univers plus grand qui comprend n variables booléennes x0, x1, x2..., x(n-1), chacune de probabilité p indépendante. Les évènements élémentaires sont (x0, x1, x2..., x(n-1)) et leur probabilité vaut p^r*(1-p)^(n-r) où r est le nombre de variable xi à 1. L'estimation de p faite par cet évènement est simplement pe = r/n.
L'estimation de la probabilité est la somme des valeurs des n variables x0 + x1 + x2 + ... x(n-1) dans le corps Z/nZ exprimé en quanta de probabilité 1/n, et que l'on note pe.
Du fait de l'indépendance des probabilités, la probabilités des conjonctions d'évènements élémentaires s'obtiennent par le produits des évènements élémentaires en questions. La probabilité qu'il y ait r variables valant 1 parmis {x1,x2,x3...,x(n-1)}, vaut : n!/(r!*(n-r)!) * p^r * (1-p)^(n-r). Et c'est la probabilité que pe = r/n.
On vérifie cette formule en s'assurant que la sommation des probabilités fasse 1.
Le processus de construction des mondes peut intégrer en même temp un processus de construction des probabilités élémentaires. Et ce procédé peut être aussi complexe que l'on veur. Ce faisant, l'univers est alors le résultat de ce processus de construction, fait à partir de paramètres posés en amonts. Une manière de définir une probabilité de probabilité consiste à définir un processus de construction d'univers en 2 étapes. Une première étape qui choisie aléatoirement un des univers parmis les configurations possibles, et une deuxième étape qui exploite cet univers choisi pour engendrer une énumération de mondes. Les paramètres en amonts sont alors de deux sortes, les probabilités de choix de la première étape, et les probabilités de choix de la deuxième étapes qui dépendent du choix fait lors de la première étape. L'univers résultant prend une forme inattendue.
Prenons un exemple simple. Considérons les 3 univers à une dimension x, U(2)(p0), U(2)(p1), U(2)(p2), où p0, p1, p2 désignent la probabilité élémentaire de x dans chacun des trois univers. Le type d'univers (2) indique que la première composante que l'on nomme ici par x est une variable d'univers à deux état, autrement dit un booléen. Puis considérons qu'un premier choix s'oppère entre ces trois univers selon les probabilités A0, A1, A2. Ce premier choix est un univers comprenant une variable à 3 états, que l'on note U(3)(A0, A1, A2).
On suppose qu'un premier tirage au sort va choisir un univers parmi m univers de paramètre respectif p0, p1, p2..., p(m-1) selon les probabilités respectives A0, A1, A2,... A(m-1). Puis un deuxième tirages va donner la valeurs booléennes à la variables x selon une probabilité pk déterminée par le premier tirage d'univers.
Les évènements élémentaires sont de la forme k, (x0,x1....,x(n-1)) et leur probabilité vaut Ak* pk^r * (1-pk)^(n-r). Il existe alors une probabilité résultante tenant compte de la succéssion des deux tirages qui est
P(x0) = A0*p0 + A1*p1 + A2*p2 .... + A(m-1)*p(m-1)
La probabilité d'être dans l'univers k est P(u=k) = Ak.
On veut calculer la probabilité que u=k sachant qu'il y a r variables valant 1 parmis {x1,x2,x3...,x(n-1)}.
P(u=k / "r variables valent 1" et "(n-r) variables valent 0") =
Loi binomiale
Prenons n canaux transmettant une copie du bit x brouillé, tous de même de probabilité de non erreur A, et supposons que n0 canaux transmettent la valeur 0 et n1 canaux transmettent la valeur 1. La probabilité que x=1 sachant les n1 transmissions à 1 et les n0 transmissions à 0 vaut :
P(x / u et v et w) = µ//(A//...n1 fois...//A)//((¬A//...n0 fois...//¬A)
| Précédent : La composition de brouillages booléens | Suite de la discussion : Probabilité et quantité d'information |