Variables booléennes aléatoires

1) Introduction

Le calcule des probabilités est un calcul combinatoire. Il s'agit de compter toutes les combinaisons satisfaisant certaines propriétées. Une combinaison est un élément d'une structure complexe. Cela nécessite de spécifier un ordre de comptage. Cet ordre est celui d'un énumérateur de la structure. Et l'énumérateur est intimement lié au mécanisme de construction de la structure.

Nous revisitons les bases du dénombrement pour les premières structures rencontrées, et nous classifions les différents procédés de construction de structures.

La méthode intuitionniste qui identifie le raisonnement mathématique au fonctionnement d'une machine va nous guider, en nous dévoilant pour chaque structure son implémentation qui est de nature informatique et qui, tel les files d'une marionette, détermine toutes ses propriétés.

Les structures que nous considérons sont finis.

2) Variable booléenne

Une variable booléenne peut prendre deux valeurs 0 ou 1. Le booléen est le type de donnée non trivial le plus simple.

Les seules valeurs que l'on considère au départ sont le 0 et le 1. A partir de ces deux éléments, nous allons construire tout les autres types et éléments utiles pour notre calcule.

3) Type

Le type d'une variable décrit les valeurs possibles de la variable. On l'identifie à l'ensemble sous-jacent, l'ensemble des valeurs possibles de la variable. Le type booléen est l'ensemble {0,1}.

Par la suite, le type s'enrichira de méthodes ou opérations effectuables sur une ou plusieurs variables de ce type. Et surtout il précisera l'implémentation de la structure de donnés. Le type deviendra synonyme de classe au sens informatique. Mais pour l'instant le type n'est qu'un ensemble.

Reste que l'ensemble n'est pas la structure la plus simple. La suite est plus simple. L'ensemble est une suite d'éléments distincts et à une permutation près.

Les types singletons tel que {0} ou {1} ne contiennent qu'un seul élément. On les ajoute afin que la construction des types se fasse qu'à partir d'autres types et non d'éléments. De plus ils constituront les deux types de bases à partir desquels tous les autres types pourront être construits.

4) Opérations de construction

Le type étant un ensemble, la construction de type s'apparente à la construction d'ensemble. Un ensemble est une liste d'éléments distincts et à une permutation près. La permurtation dont-il s'agit va déterminer un ordre d'énumération de l'ensemble.

L'énumérateur qui énumère les éléments de l'ensemble, s'identifie à la liste des éléments qu'il énumère. Les éléments d'un ensemble sont distincts entre eux. Un énumérateur est donc une liste d'éléments distincts.

Un élément est une construction faite à partir d'autres éléments. Et il est plus simple d'étudier la construction des éléments à partir d'autres éléments que la construction des types à partir d'autre types.

5) Opérations de construction d'éléments

Etant donné deux éléments x et y, voici les procédés de construction d'éléments :

Séquence :

la séquence x,y est la juxtaposition ordonnée des deux éléments x et y.

D'un point de vue informatique, la juxtaposition correspond à des espaces mémoires contigu. La succession ordonnée des mémoires est une propriété topologique des flux d'informations qui découle de la conception du temps, de l'espace et de la quantité d'information.

L'opération de séquence est associative, ce que l'on peut noter par l'expression suivante (x,y),z = x,(y,z) où les parenthèses servent uniquement à prioriser l'opérateur "," qui est l'opérateur de séquence.

Suite :

Le couple (x,y) est une séquence close de x et y dans cet ordre et ne comprenant pas d'autre élément par la suite. Il y a donc une information supplémentaire qui précise que la séquence est close.

D'une manière générale, la suite (x₀,x₁,x₂...x_n-1) est une séquence close de n éléments successifs pris dans cet ordre, et ne comprenant pas d'autre élément par la suite. Il y a donc une information suplémentaire qui précise que la séquence est close.

---- 8 avril 2013 ----

quotientée par une relation d'équivalence et restreinte par une propriété.

Etant donné deux types A et B, voici quelques procédés de construction de type :

Produit : le type A*B est l'ensemble des couples composés d'un élément de A et d'un élément de type B. Exemple :

{0,1} * {0,1} = {(0,0),(0,1),(1,0),(1,1)}

Union : le type A u B est l'ensemble regroupant les éléments de A et les éléments de B.

mais considérés distincts quelque soit la situation. Cela peut être fait en regroupant les éléments de A indicés à 0, et les éléments de B indicés à 1. Exemple :

{0,1} u {0,1} = {0₀,1₀,0₁,1₁}

Et comme l'indice est une composante d'un produit directe : 0₁ = (0,1)

{a,b} u {a,b} = {(a,0),(b,1),(a,0),(b,1)}

Ensemble des parties : le type P(A) est l'ensemble des parties de A. Exemple :

P({0,1}) = {{ },{0},{1},{0,1})

Ensemble des relations entre A et B : le type Rel(A,B) est l'ensemble des relations de A vers B. Exemple :

Rel ({0,1},{0,1}) = { { }, {(0,0)}, {(0,1)}, {(1,0)}, {(1,1)}, {(0,0),(0,1)}, {(1,0),(1,1)},

{(0,0),(1,0)}, {(0,0),(1,0)}, {(0,0),(1,1)}, {(0,1),(1,0)}, {(0,1),(1,1)} }

Ensemble des applications de A vers B : le type App(A,B) est l'ensemble des applications de A vers B. Exemple :

App({0,1},{0,1}) = { {(0,0),(1,0)}, {(0,0),(1,0)}, {(0,0),(1,1)}, {(0,1),(1,0)}, {(0,1),(1,1)} }

construire

Quelles opérations pouvons nous opérer sur une variable bouléenne ? Une opération unaire est une application de {0,1} vers {0,1}. Et il y en a 2^2 = 4 notées {0, 1, id, ¬} dont voici les tables de vérités.

x	0(x)	¬x	id(x)	1(x)
0	0	1	0	1
1	0	0	1	1

A partir de variables booléennes et à partir de différentes opérations de construction de structure, nous alllons construir

La définition de l'ensemble sous-jacent consiste à nommer chaque élément de façon arbitraire. Cet arbitraire équivaut à effectuer une permutation arbitraire des éléments de l'ensemble sous-jacent. Dans l'ensemble {0,1} il y a 2 permutations possibles. Ces deux permutations sont les opérations unaires id et ¬.

Chaque permutation de l'ensemble sous-jacent correspond à une permutation, appelée conjugaison, dans l'ensemble des opérations unaires. La conjugaison par négation laisse invariant les opérations id et ¬ et permute les opérations 0 et 1.

¬ ° id ° ¬ = id ¬ ° ¬° ¬ = ¬ ¬ ° 0 ° ¬ = 1 ¬ ° 1 ° ¬ = 0

∀x ¬(id(¬x)) = id(x) ∀x ¬(¬(¬x)) = ¬(x) ∀x ¬(0(¬x)) = 1(x) ∀x ¬(1(¬x)) = 0(x)

Dans l'ensemble des opérateurs unaires {0, 1, id, ¬}. D'un point de vue informatique, la seul méthode utile est l'opération ¬, invariante par conjugaison.

Quelles opérations pouvons nous opérer sur deux variables bouléennes et qui produit une autre variable booléenne ? Une opération booléenne binaire est une application de {0,1}x{0,1} vers {0,1}. Il y en a 2^4 = 16 qui sont { =>, <=, <=>, et, ou, d, g, 1, ¬=>, ¬<=, ¬<=>, ¬et, ¬ou, ¬d, ¬g, 0} dont voici les tables de vérités. On peut les regrouper par couples d'opposés. La négation de l'équivalence " ¬<=>" correspond au ou exclusif que l'on note plus simplement par "w".

3) La variable aléatoire booléenne

Une variable aléatoire booléenne x est une suite de tirage indépendants de valeur 0 ou 1. on note x(i) le i-ème tirage de x.

3.1) Caractéristique

Quel sont les propriétées possibles qui peuvent caractériser une variable aléatoire booléenne. Il n'y en a qu'une, la probablité p de valoir 1, et qui correspond à sa moyenne. Et si cette variable est indépendante, il n'y a pas d'autre caractéristique. Toute autre caractéristique dénote une relation de dépendance vis à vis d'autres variables.

P(x = 1)  =   p
P(x = 0)  =  1 - p

La variable x étant booléenne, on pourra directement écrire P(x) pour désigner P(x = 1), et P(¬x) pour désigner P(x = 0). Nous avons donc :

P(x)  =  p
P(¬x)  =  1 - p

3.2) Structure

Quelles sont les opérations que l'on peut faire avec une variable aléatoire booléenne indépendante de probabilité p ? On peut en prendre sa négation. On obtient alors une variable booléenne de propabilité 1-p.

3.3) Moyenne

Si on sommes N tirages, et que l'on divise par N afin d'obtenir une estimation v de la moyenne, on obtient une nouvelle variable discrète v obéissant à la distribution de probabilité binomiale. Les calculs ne font pas apparaitre de caractéristique suplémentaire du faits que les tirages succecifs de x sont supposés indépendants, x(i) est indépendant de x(i+1) et ainsi de suite.... Nous avons :

P(v = n)  =  (N-1)!/(n!*(N-n)!) * pⁿ * (1-p)^(N-n)
moyenne(v) = p
écart_type(v) = sqrt(p*(1-p)/N)

L'écart type représente la précision de cette moyenne pour un seuil de probabilité de 68 %, deux écarts types représentent la précision pour un seuil de 95 %, et trois écarts types représentent la précision pour un seuil de 99,7 %. Cela signifie qu'il y a 997 chances sur 1000 pour qu'un tirage de la variable v (qui constitue une estimation de la moyenne de la variable booléenne x) soit comprise entre p - 3*ecart_types et p + 3*ecart_types.

---- 28 mars 2013 ----

2) Un couple de variables aléatoires booléennes

Un petit rappel : On note P(A) la probabilité que l'évènement A se réalise lors d'un tirage. On note P(¬A) la probabilité que A ne se réalise pas, P(A et B) la probabilité que A et B se réalise, et P(Aou B) la probabilité que A ou B se réalise lors d'un tirage. Les probabilités obéissent aux deux règles suivantes, quelques soient les évènements A et B.

P(A) + P(¬A) = 1
P(A ou B) + P(A et B) = P(A) + P(B)

La première construction possible consiste à combiner deux variables booléennes. Elle peuvent être combinées à permutation près ou pas. Et d'une manière plus générale encore, elle peuvent être confondues à une relation d'équivalence près, par exemple, modulo la transformation (a,b) --> (¬b,¬a)

Un couple de variables booléennes (x,y) est caractérisé par les 4 probabilitées correspondant au 4 cas exhaustifs exclusifs :

p0  =  P(¬x et ¬y)
p1  =  P(¬x et  y )
p2  =  P( x  et ¬y)
p3  =  P( x  et  y )

avec p0 + p1 + p2 + p3 = 1.

On choisie de numéroter les 4 cas exclusifs exhaustifs par un entier n de tel sorte que sa décomposition en nombre binaire correspondent au couple de valeurs booléennes : n = 2*x + y. Cela constitue une bijection entre Z/2Z * Z/2Z --> Z/4Z. On a remplacé ainsi deux variables x et y dans Z/2Z par une variable n dans Z/4Z en choisissant x comme bit de poid fort et y comme bit de point faible.

La relation p0 + p1 + p2 + p3 = 1 nous informe qu'une valeur est redondante.

L'exclusivité et l'exhaustivité entraine que P(x) = p2 + p3 et que P(y) = p1 + p3.

La loi de probabilité d'un couple de variable (x,y) est donc exactement déterminé par 3 valeurs de probabilitées P(x), P(y), P(x et y), à partir desquel on peut calculer les probabilités des 4 cas exhaustifs exclusifs :

p3  =  P(x et y)
p2  =  P(x) - P(x et y)
p1  =  P(y) - P(x et y)
p0  =  1 - P(x) - P(y) + P(x et y)

2.1) Les opérations booléennes

Les variables booléennes peuvent se combiner par des opérations booléennes pour produire d'autres variables booléennes. Il y a 2⁽²²⁾ = 16 opérateurs booléens : { =>, <=, <=>, et, ou, d, g, 1, ¬=>, ¬<=, ¬<=>, ¬et, ¬ou, ¬d, ¬g, 0}que l'on peut regrouper par couples d'opposés. La négation de l'équivalence " ¬<=>" correspond au ou exclusif que l'on note plus simplement par "w".

Dans l'algèbre de bool, la négation s'obtient en appliquant la transformation (x--> ¬x)
Dans le corps Z/2Z, la négation s'obtient en appliquant la transformation (x--> x+1)
Dans l'espace des probabilités [0,1], la négation s'obtient en appliquant la transformation (p-->1-p)

2.2) Les variables à 3 états

La combinaison non booléenne de deux booléens x, y peut produire soit une variable à 4 états ou soit une variable à 3 états. Le type d'une variable décrit les valeurs possibles de la variable, appelé ensemble sous-jacent, et décrit les opérations effectuables sur une variables ou deux telles variables. La définition préalable de l'ensemble sous-jacent introduit une permutation arbitraire de ses éléments. Il y a 3! = 6 permutations possibles notées également {id = ( ), c0=(0,1,2), c1=(2,1,0), s0=(1,2), s1=(0,2), s2=(1,2)}qui correspondent aux opérations unaires sans perte d'information qui forment une structure. Ces opérations sont transformées par permutation préalable comme suit :

c0^-1 = c1
c1^-1 = c0
s0^-1 = s0
s1^-1 = s1
s2^-1 = s2

c0^-1 ° c0 ° c0 = c0
c0^-1 ° c1 ° c0 = c1
c0^-1 ° s0 ° c0 = s2
c0^-1 ° s1 ° c0 = s0
c0^-1 ° s2 ° c0 = c1

c0 : ({0,1,2}, c0, c1, s0, s1, s2) --> ({0,1,2}, c0, c1, s2, s0, s1)

Les deux permutations coïncident avec deux opérations unaires. La négation préalable n'affecte pas les méthodes {id, ¬} mais permutte les méthodes 0 et 1 :

Le type d'une variable décrit l'ensemble des valeurs possibles de la variable, ainsi que les opérations que l'on peut effectuer sur la variable.

La combinaison non booléenne de deux booléens x, y peut produire soit une variable à 4 états ou soit une variable à 3 états possibles.

Naturellement le couple (x,y) est une variable à 4 états. C'est semble-t-il la plus simple à concevoir {(0,0), (0,1), (1,0), (1,1)}. On la muni des deux opérations +, * pour construire la structure d'anneau de couples ((Z/2Z)^2, +, *). On a ainsi pourvu la variable à 4 états d'une structure, et pour enlever l'arbitraire de cette construction, on conçoit toute les permutations possibles parmis les 4 éléments . Il y a 4! = 24 permutation possibles. Mais la structure d'anneau de couples de booléens n'est pas rigide, elle contient un automorphisme (x,y)-->(y,x). Il faut diviser par 2. Il y a donc 12 façons possible de concevoir l'anneau de couples de booléens sur 4 éléments.

les autres variable à 4 état s'obtiennent en appliquant une bijection, et

Un n-uplet de varaibles booléennes

Un triplet de variables booléennes est caractérisé par les 2^3 probabilitées des 2^3 cas exhaustifs exclusifs correspondant au 2^3 sous ensemble de {0,1,2}:

On choisie de numéroter les 4 cas exclusifs exhaustifs par un entier n de tel sorte que sa décomposition en nombre binaire correspondent au couple de valeurs booléennes : n = 2^2*x2 + 2^1*x1 + . Cela constitue une bijection entre Z/2Z * Z/2Z --> Z/4Z. On a remplacé ainsi deux variables x et y dans Z/2Z par une variable n dans Z/4Z en choisissant x comme bit de poid fort et y comme bit de point faible.

La relation p0 + p1 + p2 + p3 = 1 nous informe qu'une valeur est redondante.

L'exclusivité et l'exhaustivité entraine que P(x) = p2 + p3 et que P(y) = p1 + p3.

La loi de probabilité d'un couple de variable (x,y) est donc exactement déterminé par 3 valeurs de probabilitées P(x), P(y), P(x et y), à partir desquel on peut calculer les probabilités des 4 cas exhaustifs exclusifs :

p3  =  P(x et y)
p2  =  P(x) - P(x et y)
p1  =  P(y) - P(x et y)
p0  =  1 - P(x) - P(y) + P(x et y)

Seuil de probabilité éxigé.