Interprétation géométrique d’inégalités liées à des probabilités.
Au milieu du XIXe siècle, le mathématicien George Boole s’intéresse aux conditions logiques que doit satisfaire une expérience dans laquelle interviennent des probabilités. Ces conditions dépendent des fréquences relatives d’événements liés et s’expriment à l’aide d’inégalités. Pitowsky donne en 1989 une interprétation géométrique de ces inégalités.
Au milieu du XIXe siècle, le mathématicien George Boole s’intéresse aux conditions logiques que doit satisfaire une expérience dans laquelle interviennent des probabilités. Ces conditions dépendent des fréquences relatives d’événements liés et s’expriment à l’aide d’inégalités. Pitowsky donne en 1989 une interprétation géométrique de ces inégalités. Considérons une urne contenant des boules de différentes couleurs et façonnées dans diverses matières. Admettons que chaque boule peut être caractérisée par deux propriétés, disons « blanche » et « en bois ». Ainsi, une boule décrite est blanche, en bois, ou blanche et en bois. L’état de l’urne est donné par les probabilités associées au tirage d’une boule ayant une de ces propriétés. Soit p1 la proportion de boules blanches dans l’urne, p2 celle de boules en bois et p12 celle de boules blanches et en bois. Si l’urne contient suffisamment de boules, ces proportions sont les probabilités d’obtenir par tirage une boule ayant une de ces propriétés. Les inégalités :
sont vérifiées par les proportions p1, p2 et p12 qui peuvent être considérées comme les probabilités de chaque événement et de leur réunion seulement si ces inégalités sont satisfaites. Mais ces inégalités sont insuffisantes : la probabilité de tirer une boule qui est, soit blanche soit en bois (p1 + p2 - p12), doit être comprise entre 0 et 1, ce qui fournit une autre inégalité :
Les trois inégalités ci-dessus sont nécessaires et suffisantes pour que les nombres p1, p2 et p12 représentent dans l’ordre les probabilités de tirer de l’urne une boule blanche, une boule en bois, une boule blanche qui est en bois. Formons la table de vérité dans laquelle p1, p2 et p1∧ p2 représentent respectivement les propositions : « la balle tirée est blanche », « la balle tirée est en bois », « la balle tirée est blanche et elle est en bois ».
Associons 1 à « Vrai » et 0 à « Faux » et considérons chaque ligne comme les composantes d’un vecteur. Ces vecteurs définissent un polyèdre convexe dont les sommets (points extrêmes) s’interprètent ainsi : (1, 1, 1) l’urne ne contient que des boules blanches en bois. (1, 0, 0) l’urne ne contient que des boules blanches qui ne sont pas en bois. (0, 1, 0) l’urne ne contient que des boules en bois qui ne sont pas blanches. (0, 0, 0) aucune boule blanche ni aucune boule en bois ne se trouve dans l’urne. Les inégalités décrivant l’urne peuvent alors être associées aux plans contenant les faces du polyèdre. Dans ce modèle très simple de l’urne qui ne fait intervenir que deux propriétés, les inégalités (1) et (2) peuvent être devinées facilement. Ce n’est plus possible dès qu’il y a davantage de propriétés, mais on peut trouver toutes les inégalités à partir des sommets d’un polyèdre convexe. Ce problème, connu sous le nom de problème de la frontière (hull problem), peut être résolu algorithmiquement.
Fig. 1 : Polyèdre construit à partir d’une table de vérité comportant deux propositions et leur réunion.
Exercice 1
Construisez les tables de vérité des opérations logiques And, Nand, Nor, Or, Xor pour 2 propositions. Dessinez les polytopes (on appelle polytope un polyèdre borné) associés à ces tables.
Exercice 2
Dessinez la frontière convexe d’un ensemble quelconque de points du plan. Effectuez une triangulation de Delaunay de cet ensemble de points (une triangulation de Delaunay d’un ensemble de points est une triangulation des points de l’ensemble telle que les cercles circonscrits aux triangles ne contiennent aucun point de l’ensemble).
N. B. La solution de ce problème est utile par exemple pour déterminer la longueur minimale d’une clôture. L’aire délimitée par la clôture de longueur minimale qui englobe tous les points est convexe : la ligne reliant deux points intérieurs quelconques est toujours dans l’enclos.
Exercice 3
Une urne contient des boules de différentes couleurs et façonnées dans diverses matières. On utilise, pour décrire les boules, 3 propriétés : « blanche », « lisse » et « en bois ». Désignons par la proportion de boules blanches dans l’urne, par celle de boules lisses, par celle de boules en bois, par celle de boules blanches et lisses, par celle de boules blanches en bois, par celle de boules lisses en bois et par celle de boules blanches lisses et en bois. Quelles conditions ces proportions doivent-elles satisfaire pour donner les probabilités d’obtenir une boule ayant les propriétés correspondantes lors d’un tirage au sort ?
Programmes à installer (disponibles sur le web) pour résoudre l’exercice 3
Komei Fukuda (ETHZ, Zurich et EPFL, Lausanne) a développé depuis 1996 un algorithme permettant de générer le système linéaire d’inégalités décrivant les faces du polytope à partir de ses sommets et d’obtenir, réciproquement, tous les sommets d’un polytope convexe à partir du système linéaire d’inéquations représentant ses faces. Cet algorithme, écrit en C++, implémente la méthode de la double description, d’où son nom « cdd ». Il existe un module Mathematica (CddIF.m), écrit par Stefan Filipp en 2001, qui permet d’exécuter le code binaire (cddmathlink2) de l’algorithme de la double méthode via MathLink et de résoudre l’exercice 3.
Pour en savoir plus
– George Boole, The Calculus of Logic. Cambridge and Dublin. Mathematical Journal, Vol. III (1848), pp. 183-98
– I. Pitowsky. Correlation polytopes : Their geometry and complexity. Mathmatical Programming, 50 : 395–414, 1991.
– Komei Fukuda, Lecture Notes on Oriented Matroids and Geometric Computation, Winter 2000 (revised June 16, 2004).
– Stefan Filipp and Karl Svozil, Boole-Bell-type inequalities in Mathematica, 17 may 2001.