Suite aléatoire

Cette suite est-elle aléatoire ?

En mathématiques, une suite aléatoire, ou suite infinie aléatoire, est une suite de nombres 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).

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

• une suite aléatoire ne doit posséder aucune régularité « exceptionnelle et effectivement testable » (Martin-Löf 1966^[2])
• une suite aléatoire doit posséder un « contenu informationnel incompressible ». (Levin 1974^[3], 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 (Schnorr (en) 1971^[4]).

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

L'ensemble des suites aléatoires peut être mis en relation bijective avec l'ensemble des nombres dont le développement numérique 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 notation 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^[5], de la biologie^[6] 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)^[7].

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₀ de la suite, puis le symbole suivant le a₁ 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. 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.

A 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, Emile Borel a proposé un paradoxe selon lequel la définition du hasard est par nature impossible.

En effet, si 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 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^[8].

Les définitions formelles actuelles du concept de suite aléatoire "résolvent" le 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.

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 [0,1] des réels. De plus, l'ensemble des suites défini par des bits consécutifs définis (pattern), ou indéfinis, correspondent à des 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 le segment $]{\scriptstyle\frac12},1]$. Les intervalles correspondant à l'ensemble des suites dont le premier bit indéfini, les deux bits suivants '01', et le reste indéfini ('X01XXXXXX...') sont les segments $]{\scriptstyle\frac14},{\scriptstyle\frac12}]$ et $]{\scriptstyle\frac34},1]$, etc..

Le principe de la définition est de construire (récursivement) une liste infinie d'ensembles A₀,A₁,..,A_m,... de suites (donc chaque A_i correspond à un ensemble de segments), qui vont définir une (ou plusieurs) « propriété exceptionnelle ». La mesure totale des segments de A_i doit être majorée par 1 / 2ⁱ, 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 que 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 totale 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^[9].

« 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^[10]. »

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 s'il existe une constante c telle que, quel que soit n, $H(s^n) \geq n - c$ (sⁿ désigne les n premiers symboles d'une suite s, et H(s) la complexité de Chaitin-Levin)^[11]. Il a été démontré récemment par Chaitin que cette définition est équivalente à dire que $\lim_{n \to \infty} H(s^n) - n = +\infty$.

Définition au sens de Schnorr

La définition est fondée sur la théories 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 soient fondées 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 adressent quelque chose de « fondamental » concernant cette notion.

De plus, ces définitions possèdent une certaine « robustesse » (elle restent valables et équivalentes même si 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^[1].

Toutefois, comparativement à d'autres thèses fondamentales du même domaine (comme par exemple 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^[1].

Certains mathématiciens, comme Schnorr lui-même, pense que les définitions de type Martin-Löf sont trop strictes et imposent trop de conditions aux suites aléatoires. Selon Schnorr^[12], 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éatoire 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 >= à 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 n'est souvent pas vraie).

• 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écursivement énumérable).
• 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 mais de mesure nulle dans $\mathbb{R}$ et dense dans $\mathbb{R}$.

Voir aussi

• Complexité de Kolmogorov
• Théorie algorithmique de l'information
• Générateur de nombres aléatoires

Notes et références

1. ↑ ^{a, b et c} Jean-Paul Delahaye, Information, complexité et hasard, 1999, Hermes
2. ↑ (en) Martin-Löf, P., « The definition of random sequences », dans Information and Control, vol. 9, 1966, p. 602–619 [lien DOI] 
3. ↑ (en) Levin, L., « On the notion of a random sequence », dans Soviet Mathematics Doklady, vol. 14, 1973, p. 1413–1416 
4. ↑ (en) Schnorr, C. P., « A unified approach to the definition of a random sequence », dans Mathematical Systems Theory, vol. 5, n^o 3, 1971, p. 246–258 [lien DOI] 
5. ↑ (en) Karl Svozil, Randomness & Undecidability in Physics, World Scientific, 1993 [1]
6. ↑ (en) G. Chaitin, Toward a Mathematical Definition of Life, [2] [PDF]
7. ↑ Ville, J., Étude critique de la notion de collectif, Paris, Gauthier-Villars 
8. ↑ cité dans G. Chaitin, Hasard et complexité en mathématiques, Flammarion, 2009
9. ↑ Il s'agit du théorème d'invariance
10. ↑ (en) Chaitin G.J., On the Lenght of Programs for Computing Finite Binary Sequence, J.A.C.M. 13, 547-569
11. ↑ Ce qui n'est pas nécessairement vrai avec la complexité de Kolmogorov K(s), car on peut montrer que toute pour suite s il existe une infinité de n tels que $\scriptstyle{K(s^n) \leq n - log(n) + c}$.
12. ↑ (en) Schnorr C.P., A survey of the Theory of Random Sequence in Basic Problems in Methodology and Linguistics Butts Hintikka Ed. 1977