Suite aléatoire

En mathématiques, une suite aléatoire, ou suite infinie aléatoire, est une suite de symboles d'un alphabet ne possédant aucune structure, régularité, ou règle de prédiction identifiable. Une telle suite correspond à la notion intuitive de nombres tirés au hasard. La caractérisation mathématique de cette notion est extrêmement difficile, et a fait l'objet d'études et de débats tout au long du XX^e siècle. Une première tentative de définition mathématique (insatisfaisante) a été réalisée en 1919 par Richard von Mises. Ce fut l'avènement de la théorie de la calculabilité, dans les années 1930, et de la théorie algorithmique de l'information qui permit d'aboutir dans les années 1970 — au terme d'une succession de travaux menés notamment par Andreï Kolmogorov, Gregory Chaitin, et Per Martin-Löf — à des définitions faisant aujourd'hui consensus (bien que toujours non tout à fait unanime).

Cette suite est-elle aléatoire ?

Les définitions actuellement acceptées (démontrées équivalentes) du caractère aléatoire d'une suite sont les suivantes :

• une suite aléatoire ne doit posséder aucune régularité « exceptionnelle et effectivement testable » (Martin-Löf 1966) ;
• une suite aléatoire doit posséder un « contenu informationnel incompressible » (Levin 1974, Chaitin 1975) ;
• une suite aléatoire doit être imprévisible, c'est-à-dire qu'aucune « stratégie effective » ne peut mener à un « gain infini » si l'on « parie » sur les termes de la suite (Claus-Peter Schnorr 1971).

Chacun des termes employés dans les définitions ci-dessus possède une définition mathématique rigoureuse.

L'ensemble des suites aléatoires sur un alphabet quelconque peut être représenté par celles n'utilisant que les chiffres « 0 » ou « 1 » qui peuvent elles-mêmes être mises en relation bijective avec l'ensemble des nombres réels dont le développement numérique écrit en notation binaire est constitué de chiffres « aléatoires ». De fait, la quasi-totalité des études et définitions mathématiques concernant les suites aléatoires sont effectuées en utilisant la traduction de la suite en un nombre réel, compris entre 0 et 1, écrit en binaire, donnant ainsi une simple suite de 0 et de 1.

Bien que très fructueuses sur le plan théorique, et menant à d'intéressants corollaires et propriétés, ces définitions sont en fait peu applicables en pratique pour tester le caractère aléatoire d'une véritable suite. Malgré tout, ces définitions commencent à trouver des applications théoriques dans les domaines de la physique, de la biologie ou de la philosophie.

Problématique et historique

L'histoire de la formalisation mathématique de cette notion permet de comprendre les problèmes et les subtilités qui interviennent quand il s'agit de définir la notion d'aléatoire.

Tout d'abord, une définition d'une suite aléatoire ne doit pas être trop stricte (aboutissant à une notion vide), ou au contraire trop laxiste, intégrant des suites qui ne sont pas — à l'évidence — aléatoires. Ensuite, la définition doit être précise et ne laisser aucune notion non rigoureusement définie intervenir (même indirectement) dans la définition.

La première tentative de définition, en 1919 par Richard von Mises, péchait sur les deux points. Selon von Mises, une suite constituée de 0 et de 1 est aléatoire si et seulement si toute sous-suite extraite « selon des moyens raisonnables » (ce qu'il appelait des « collectifs ») présente autant de 0 que de 1. Von Mises ne réussit jamais à mathématiser rigoureusement la notion de « moyen raisonnable » pour extraire une sous-suite. De plus, en 1939, Jean Ville démontra qu'aucune suite ne répond à la définition de von Mises (notion vide).

Karl Popper, en 1935, essaya de partir sur une idée semblable à celle de von Mises, mais plus précisément définie. L'idée est d'extraire une sous-suite d'une suite donnée $s_{i}$ à partir une autre suite quelconque $a_{i}$. On extrait de la suite $s_{i}$ le symbole suivant le premier $a_{0}$ de la suite, puis le symbole suivant le $a_{1}$ suivant, etc. Une suite est dite aléatoire si quelle que soit la suite $a_{i}$, les fréquences de 0 et de 1 sont égales dans les sous-suites extraites. A l'inverse de la définition de von Mises, cette définition fut prouvée trop faible, toujours par Jean Ville, qui fournit des contre-exemples de suites visiblement non aléatoires répondant à cette définition.

En 1940, le mathématicien Alonzo Church mit à profit la théorie de la calculabilité (dont il est un des pères) pour préciser la définition de von Mises. Il définit la notion de « moyen raisonnable » par « peut être extraite par une fonction récursive ». Cette définition échoua également, car il s'avère que les sous-suites définies ainsi sont dénombrables. Or, Jean Ville a démontré, toujours en 1939, que si l'ensemble des sous-suites dans une définition de type von Mises est dénombrable, alors il existe des suites qui répondent à la définition, mais qui comportent plus de 1 que de 0 dans tout début de suite.

À ce point, la communauté des mathématiciens, Jean Ville et Émile Borel en tête, doutait qu'il fût jamais possible de trouver une définition satisfaisante à la notion de suite aléatoire (voir Paradoxe du hasard indéfinissable).

En 1965, Kolmogorov proposa une définition fondée sur la notion de complexité qui allait s'avérer fructueuse, mais encore insuffisante en l'état : est aléatoire tout suite infinie dont la complexité de Kolmogorov est maximale. Il manquait seulement la notion de programme auto-délimité (voir la définition de Levin-Chaitin) pour aboutir à une définition correcte. En l'état, cette définition menait de nouveau à une notion vide.

C'est à partir de 1966, avec la proposition de Per Martin-Löf, et avec le raffinement de la proposition de Kolmogorov par Gregory Chaitin et Leonid Levin, que des définitions solides commencent à apparaître.

Paradoxe du hasard indéfinissable

Au moment, avant la Seconde Guerre mondiale, où la communauté scientifique ne croyait plus en la possibilité d'une définition formelle d'une suite aléatoire, Émile Borel a proposé un paradoxe selon lequel la définition du hasard est par nature impossible.

En effet, si l'on conçoit intuitivement une suite aléatoire comme une suite ne possédant absolument aucune caractéristique particulière, alors le simple fait de définir une suite aléatoire donne une caractéristique aux suites répondant à la définition, qui est le fait d'être « aléatoire ». Donc le simple fait de définir l'aléatoire est paradoxal par rapport à sa définition intuitive.

Borel exhibe donc une sorte de hiérarchie nécessaire, et infinie, de définition de l'aléatoire. Si l'on propose une définition D0 de l'aléatoire, alors une autre définition D1 devient nécessaire, excluant les suites définies comme aléatoires par D0 et ainsi de suite.

Les définitions formelles actuelles du concept de suite aléatoire "résolvent" ce paradoxe de Borel en s'arrêtant volontairement à un certain niveau dans la hiérarchie, sur lequel les mathématiciens se sont accordés pour dire qu'il correspond à une définition raisonnable de ce concept, même si le paradoxe de Borel reste valable dans l'absolu.^{[réf. souhaitée]}

Définitions mathématiques

Définition au sens de Martin-Löf

Une suite est aléatoire au sens de Martin-Löf si elle ne possède aucune propriété « exceptionnelle et effectivement vérifiable », c'est-à-dire une propriété pouvant être vérifiée par une fonction récursive, au sens de la théorie de la calculabilité (autrement dit un algorithme).

La définition de Martin-Löf utilise la bijection suite ↔ réel. Par conséquent, un ensemble de suites correspond à un ensemble de points sur le segment réel [0, 1]. De plus, les ensembles de suites contenant des séquences de bits définies (pattern) correspondent à des réunions d'intervalles sur ce segment. Ces intervalles sont tous de la forme [i, j] avec i et j de la forme $p/2^{q}$, p et q étant des entiers naturels. Par exemple, l'ensemble des suites commençant par '1' ('1XXXXXX...') est l'intervalle $]1/2,1]$. L'ensemble des suites dont le premier bit indéfini, les deux bits suivants '01', et le reste indéfini ('X01XXXXXX...') est la réunion des intervalles $]1/8,1/4]$ et $]5/8,6/8]$, etc.

Le principe de la définition est de construire (récursivement) une liste infinie d'ensembles $A_{0},A_{1},\dots ,A_{m},\dots$ de suites (donc chaque $A_{i}$ correspond à une réunion d'intervalles), qui vont définir une (ou plusieurs) « propriété exceptionnelle ». La mesure de $A_{i}$ doit être majorée par $1/2^{i}$, et $A_{i}$ doit être un sous-ensemble de $A_{i-1}$. La suite des ensembles $A_{i}$ doit être récursivement énumérable. On dit qu'une suite possède une propriété exceptionnelle et effectivement vérifiable, définie par $A_{m}$ pour un niveau m, si la suite appartient à l'ensemble $A_{m}$.

Par définition, la mesure de $A_{m}$ tend vers 0 quand m tend vers l'infini, ce qui justifie le terme « exceptionnel » pour cette propriété. Le terme « effectivement vérifiable » provient de la définition récursive de $A_{m}$ qui assure que l'appartenance à $A_{m}$ est « effectivement » testable par une machine de Turing, en un temps fini pour m fini (m est généralement fonction du nombre d'éléments à tester dans la suite).

Par définition, une suite qui n'appartient à aucun ensemble $A_{m},B_{m},...$ constructible selon le procédé ci-dessus, et donc qui ne possède aucune « propriété exceptionnelle et effectivement vérifiable », est une suite aléatoire au sens de Martin-Löf (dite parfois ML-aléatoire).

On démontre qu'il existe une liste récursive d'ensembles particulière $U_{m}$ qui teste à elle seule l'ensemble de toutes les propriétés exceptionnelles définissables au sens de Martin-Löf. Il s'agit d'un test universel d'aléatoirité.

Définition au sens de Levin/Chaitin

La théorie algorithmique de l'information, développée par Ray Solomonoff et Andreï Kolmogorov dans les années 1960, a rendu possible de définir, de manière absolue, la notion de contenu en information d'une suite : il s'agit de la complexité de Kolmogorov. Cette mesure est définie comme étant la longueur du plus petit programme nécessaire pour engendrer la suite. Il est démontré que cette mesure ne dépend pas fondamentalement de la machine utilisée pour coder et exécuter le programme, à une constante additive près, ce qui justifie son caractère absolu.

« Sur la base de ces considérations, il peut apparaître naturel de définir une suite sans régularité, ou suite finie aléatoire, comme une suite qui pour être calculée demande en gros un programme aussi long qu'elle même. »

En effet, la suite '01010101...', qui est visiblement non aléatoire est descriptible en peu de mots : « répéter 01 à l'infini » (ce qui est l'équivalent d'un programme), alors que la suite '0110100101111001...' n'est descriptible qu'avec le programme : « écrire '0110100101111001...' » qui est un programme au moins aussi long que la suite elle-même.

La complexité de Kolmogorov n'était toutefois pas tout à fait suffisante pour définir rigoureusement une suite aléatoire. Le problème est que la complexité de Kolmogorov est fondée sur des programmes non auto-délimités (c'est-à-dire que la fin du programme n'est pas provoquée par une instruction du programme). Dans ce cas, il est possible par exemple de concaténer deux programmes, ce qui rend le poids d'un programme non univoque.

La définition de Chaitin-Levin utilise la complexité de Kolmogorov où il est spécifié que les programmes doivent être auto-délimités. Cette complexité est nommée complexité de Chaitin-Levin.

Une suite est aléatoire au sens de Chaitin-Levin si et seulement si la suite $\left(H(s^{n})-n\right)$ est minorée ($s^{n}$ désigne les n premiers symboles d'une suite s, et $H(s)$ la complexité de Chaitin-Levin). Chaitin a démontré récemment que cette définition est équivalente à : $\lim _{n\to \infty }H(s^{n})-n=+\infty$.

Définition au sens de Schnorr

La définition est fondée sur la théorie des martingales. L'idée est de définir une suite aléatoire comme une suite sur laquelle aucune martingale ne peut être gagnante.

Cette idée avait déjà été exploitée par Jean Ville en 1939, mais il n'utilisait pas la notion de calculabilité pour définir une martingale. Sans précautions sur la calculabilité de la martingale, cette définition mène à exclure toutes les suites possibles et aboutit à une notion vide.

Le mathématicien allemand Claus-Peter Schnorr (en) reprit cette idée en 1971 en posant des conditions précises sur la calculabilité de la martingale. En fonction de ces conditions, on aboutit à des définitions plus ou moins fortes (mais non vides) de la notion de suite aléatoire. Parmi ces possibilités, l'une produit exactement à la même classe de suites aléatoires que la définition de Martin-Löf, ou de Levin-Chaitin.

Justifications et doutes résiduels concernant ces définitions

Le fait que chacune des trois définitions soit fondée sur des idées intuitivement en rapport avec la notion de suite aléatoire, et surtout qu'elles se soient révélées mathématiquement équivalentes alors qu'elles sont fondées sur des idées différentes, et imaginées indépendamment les unes des autres, mène à penser que ces définitions touchent à quelque chose de « fondamental » concernant cette notion.

De plus, ces définitions possèdent une certaine « robustesse » (elles restent valables et équivalentes même si l'on modifie certains éléments non fondamentaux de leur définition), une fécondité mathématique, et une pérennité dans le temps que l'on attend de définitions fondamentalement justes.

Toutefois, comparativement à d'autres thèses fondamentales du même domaine (ex. : la thèse de Church), et sur ces mêmes critères, les définitions d'une suite aléatoire apparaissent moins bien fondées.

Certains mathématiciens, comme Schnorr lui-même, pensent que les définitions de type Martin-Löf sont trop strictes et imposent trop de conditions aux suites aléatoires. Selon Schnorr, seules les propriétés « qui peuvent être testées à l'aide d'expériences statistiques réelles », qui ont « un sens physique », devraient être prises en compte. Cela revient à remplacer, dans la définition de Martin-Löf, la condition que la suite des $A_{i}$ soit récursivement énumérable, par la condition que les ensembles $A_{i}$ soient des ensembles récursifs. Avec cette définition, certaines suites qui sont non aléatoires au sens de Martin-Löf sont définies comme aléatoires, car on ne pourra jamais mettre en évidence en pratique leur caractère calculable, même si elles sont calculables en théorie.

Aléatoire et incompressibilité

La définition de Levin/Chaitin est totalement équivalente à dire qu'une suite aléatoire est une suite incompressible (au sens de compression de données informatiques), ce qui se peut comprendre au sens intuitif qu'aucun terme n'est déductible des précédents et n'est redondant.

Pour une suite finie, l'incompressibilité s'exprime informellement par l'égalité de taille (en octets par exemple) de la suite et du plus petit algorithme permettant de l'engendrer. Pour une suite infinie comme le sont les décimales d'un nombre réel, l'aspect aléatoire/incompressible s'exprimera plus rigoureusement par : Il existe une constante C, telle que pour tout entier n, la taille du plus petit programme engendrant les n premiers octets de la suite est supérieure ou égale à n – C octets, C étant une constante mathématique dépendant du langage informatique (Fortran, C, Java, etc.) ou logique (codage particulier des machines de Turing, etc.) considéré.

Ces critères sont une traduction directe de la complexité de Levin/Chaitin.

Propriétés des suites aléatoires

Les suites aléatoires, telles que définies ci-dessus, possèdent un certain nombre de propriétés démontrées (attention : la réciproque des propriétés ci-dessous est souvent fausse) :

• un nombre réel au développement numérique aléatoire est normal en toute base et transcendant ;
• une suite aléatoire ne peut être décrite ou générée par un algorithme (elle n'est pas récursive) ;
• une suite aléatoire satisfait les critères de Von Mises et Popper (voir section "historique"), c'est-à-dire que toute sous-suite extraite de manière effective possède la propriété de convergence des fréquences ;
• les nombres réels dont le développement numérique est non aléatoire forment eux aussi un ensemble non dénombrable et dense dans $\mathbb {R}$, mais de mesure nulle.

En pratique : caractère aléatoire d'une suite de symboles

Beaucoup de suites comportent des symboles (nombres, mais aussi lettres, mots, pixels, résultats d'un tirage au sort, etc.) ayant des probabilités et des contraintes d'apparition, tout en s’écartant de l’idéal des définitions vues précédemment.

Ainsi, une suite où il n’y aurait pas équiprobabilités entre ses symboles peut être vue comme défectueuse en cryptanalyse. Les codes de César ou de Vigenère sont déchiffrables grâce à cette caractéristique qui dévoile une faille. Dans un autre domaine, une telle suite serait vue comme « compressible », par exemple « zippable » avec un taux de compression appréciable. Une source avec contraintes voit les probabilités de ses symboles changer au fur et à mesure que ses contraintes sont connues : son entropie (et donc le caractère aléatoire) de cette source diminue et ainsi s’écarte notablement d’un hasard complet.

Une source de symboles binaires pseudo aléatoires n’a rien d’aléatoire, au moins pour le concepteur, car le comportement de celle-ci est prédéterminé dans un câblage électronique. Paradoxalement, surtout si la longueur de la séquence pseudo aléatoire est longue, la source est suffisamment ergodique (dans le sens particulier où chaque sous-suite possible de longueur $\ell$ a une probabilité d’apparition voisine de $1/2^{\ell }$) et est considérée comme utile pour son emploi lors de tests.

Le caractère peu ou très aléatoire d’une suite de symboles dépend du contexte (cryptographie, compression de données, tests et autres) et explique la multiplicité des approches pour définir un hasard parfait.

Les suites aléatoire de nombres utilisées couramment dans les simulations sur ordinateur (méthode de Monte Carlo) ne satisfont qu'approximativement ces propriétés ; ce sont des suites pseudo-aléatoires, générées par des algorithmes déterministes.

Article connexe

Générateur de nombres aléatoires