Section : Simulation, modèles et réalité
Précédent : Suites uniformes
Suivant : Variables aléatoires

Complexité et hasard

Parmi les différentes formalisations du hasard qui ont pu être proposées, la notion de suite uniforme est la seule utilisable en pratique : elle est la seule que l'on puisse tester pour un générateur donné et elle suffit à justifier toutes les applications de la fonction Random. Une "vraie" suite aléatoire doit être uniforme. Mais peut-on considérer comme aléatoire toute suite uniforme ? Nous allons voir que non, malheureusement.

Comme l'ordinateur ne peut donner que des approximations décimales des réels, il suffirait de savoir construire une suite aléatoire de chiffres entre 0 et $9$, pour en déduire des réels au hasard dans $[0,1]$, approchés à la $k$-ème décimale, en considérant des $k$-uplets consécutifs de chiffres de la suite initiale. La même remarque vaut bien sûr en base 2. Il suffirait donc de savoir définir ce qu'est une suite de bits au hasard.

Limitons-nous donc aux suites de bits dans $\{0,1\}$. On attend d'une telle suite qu'elle soit le résultat typique d'une suite de tirages de Pile ou Face. Voici trois séquences particulières :

$$0 \,0 \,0 \,0 \,0 \,0 \,0 \,0 \,0 \,0 \,0 \,0 \,0 \,0 \,0 \,0$$

$$0 \,1 \,0 \,1 \,0 \,1 \,0 \,1 \,0 \,1 \,0 \,1 \,0 \,1 \,0 \,1$$

$$0 \,1 \,1 \,0 \,1 \,0 \,0 \,0 \,1 \,1 \,0 \,1 \,1 \,1 \,0 \,0$$

La troisième a meilleur aspect que les deux premières. Elle a pourtant exactement la même probabilité de sortir telle quelle à Pile ou Face  : $1/2^{16}$. Parmi les $1000$-uplets de bits, tous ont a priori la même probabilité de sortir : $1/2^{1000}$. Toute suite aléatoire de bits doit contenir nécessairement une infinité de fois $1000$ zéros à la suite. Accepterions-nous qu'un générateur de bits retourne ne serait-ce que $100$ zéros à la suite ? Cela paraît peu vraisemblable.

Sur les $3$ exemples ci-dessus, nous écarterions le premier car il semble violer la 1-uniformité. Nous écarterions le second au nom de la 2-uniformité. Mais que dire alors de la suite concaténée de tous les entiers en base 2 (suite de Champernowne) ?

$$0 \,1 \underbrace{1 \,0}_2 \underbrace{1 \,1}_3 \underbrace{1 \,... ...}_{11} \underbrace{1 \,1 \,0 \,0}_{12}\underbrace{1 \,1 \,0 \,1}_{13} \,\ldots$$

On montre qu'elle est $\infty$-uniforme. Mais comment qualifier d'aléatoire une suite aussi parfaitement prévisible ?

La définition la plus intuitive du hasard, celle des dictionnaires, n'a aucun rapport avec l'uniformité. Est aléatoire ce qui est imprévisible. Une suite serait donc aléatoire si on ne pouvait pas prévoir son $(n\!+\!1)$-ème terme connaissant les $n$ premiers. La suite

$$0 \,1 \,0 \,1 \,0 \,1 \,0 \,1 \,\ldots \,0 \,1 \,\ldots$$

n'est pas aléatoire car sans avoir écrit les $999$ premiers termes on sait que le $1000$-ème sera "1" et le suivant "0". La suite

$$0 \,1 \,1 \,0 \,1 \,0 \,1 \,1 \,1 \,0 \,0 \,1 \,0 \,1$$

en revanche, ne semble pas présenter de régularité, de configuration qui permettrait d'en prévoir les termes suivants. Une suite est donc aléatoire si elle n'a pas de règle de construction simple.

On peut voir une règle de construction comme un moyen de compresser une suite en un algorithme qui l'engendre.

Exemple :

Répéter $n$ fois
écrire 0 puis 1
finRépéter

Traduit en chaîne de bits, la seule chose qui dépend de $n$ dans cet algorithme est le test. La longueur de la chaîne de bits sera $\log_2n+$constante, pour engendrer à l'exécution une chaîne de longueur $2n$ ($\log_2n$ est le nombre de bits nécessaires pour écrire $n$, à 1 près).

Notons $X^*$ l'ensemble de toutes les chaînes de bits de longueur finie. Si $x\in X^*$, sa longueur (nombre de bits) sera notée $l(x)$. Un algorithme est une application de $X^*$ dans lui-même.

$X^*$	$\stackrel{\Phi}{\longrightarrow}$	$X^*$
$y$	$\longrightarrow$	$x$
input		output

Soit $\tau (\phi)$ la taille du codage de $\phi$ exprimée en bits (hors input).

Définition 2.4   On appelle complexité de $x$ relative à $\phi$ l'entier :

$$K_\phi (x) =\inf \,\{ \,l(y), \,\phi (y)=x \,\}+\tau (\phi)\; (=+\infty$$ si $$x\not\in\phi (X^*)) \;.$$

En d'autres termes $K_{\phi}(x)$ est une mesure de la taille de l'information qu'il faut donner à l'algorithme $\phi$ pour produire $x$. Dans l'exemple ci-dessus, une chaîne de $\log_2n$ bits suffisait à produire la chaîne de longueur $2n$

$$\underbrace{0 \,1 \,0 \,1 \,\cdots \cdots \,0 \,1}_{\mbox{$n$ fois}} \;.$$

Définition 2.5   On appelle complexité de $x$ l'entier :

$$K(x)= \inf\limits_\phi K_\phi (x) \;.$$

$K(x)$ est la quantité minimale d'information nécessaire pour produire $x$.

Remarque : Bien que ceci n'ait pas la prétention d'être un cours de complexité, on doit tout de même signaler que les définitions ci-dessus n'ont de sens que si on restreint quelque peu la notion d'algorithme. Si on en reste aux applications quelconques de $X^*$ dans $X^*$, on se heurte à des paradoxes du type de celui de R. Berry  :

"Le plus petit nombre qu'on ne puisse pas définir en moins de $20$ mots".

Le bon cadre est celui des fonctions récursives, calculables par machines de Turing.

Pour engendrer une suite donnée de $n$ bits, l'algorithme brutal consiste à les écrire tous les uns après les autres. Il correspond à l'application identique $I$ de $X^*$ dans lui-même. Relativement à cet algorithme la complexité de toute suite de $n$ bits est $n$. Donc la complexité de toute suite est majorée par sa longueur :

$$\forall x\; K_{I}(x)=l(x) \Longrightarrow K(x)\leq l(x) \;.$$

Dire qu'une suite est aléatoire, c'est dire qu'on ne peut pas faire mieux que l'algorithme brutal pour l'engendrer.

Définition 2.6   Soit $x=(x_n)_{n\in\mathbb{N}^*}$ une suite de bits. Elle est dite aléatoire si il existe une constante $c$ telle que pour tout $n$ :

$$\exists c\;\forall n\; K((x_1,\ldots ,x_n))\geq n-c \;.$$

D'après la proposition suivante, la plupart des suites sont aléatoires.

Proposition 2.7   Le cardinal de l'ensemble des suites de bits de longueur $n$ dont la complexité est minorée par $n\!-\!c$ est au moins :

$$2^n(1-2^{-c}) \;.$$

Démonstration  :Parmi les inputs susceptibles d'engendrer les suites de longueur $n$, seuls ceux dont la longueur est inférieure à $(n-c)$ nous intéressent. Il y en a au plus :

$$2^0+2^1+\cdots +2^{n-c-1} =2^{n-c}-1 \;.$$

Chaque couple (input+algorithme) engendre au plus une suite de longueur $n$. Il y a donc au plus $2^{n-c}$ suites de longueur $n$ dont la complexité est inférieure à $n-c$.
$\square$

Concrètement, parmi toutes les suites de longueur $n$, une proportion de $1/2^{10}\simeq 10^{-3}$ d'entre elles seulement sont de complexité $<n-10$.

Il devrait donc être facile de trouver des suites aléatoires puisque la plupart d'entre elles le sont. Paradoxement, le problème de démontrer qu'une suite particulière est aléatoire est indécidable en général.

Section : Simulation, modèles et réalité
Précédent : Suites uniformes
Suivant : Variables aléatoires