Suite aléatoire

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[9].

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]}

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 ${\displaystyle p/2^{q}}$, p et q étant des entiers naturels. Par exemple, l'ensemble des suites commençant par '1' ('1XXXXXX...') est l'intervalle ${\displaystyle ]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 ${\displaystyle ]1/8,1/4]}$ et ${\displaystyle ]5/8,6/8]}$, etc.

Le principe de la définition est de construire (récursivement) une liste infinie d'ensembles ${\displaystyle A_{0},A_{1},\dots ,A_{m},\dots }$ de suites (donc chaque ${\displaystyle A_{i}}$ correspond à une réunion d'intervalles), qui vont définir une (ou plusieurs) « propriété exceptionnelle ». La mesure de ${\displaystyle A_{i}}$ doit être majorée par ${\displaystyle 1/2^{i}}$, et ${\displaystyle A_{i}}$ doit être un sous-ensemble de ${\displaystyle A_{i-1}}$. La suite des ensembles ${\displaystyle 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 ${\displaystyle A_{m}}$ pour un niveau m, si la suite appartient à l'ensemble ${\displaystyle A_{m}}$.

Par définition, la mesure de ${\displaystyle 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 ${\displaystyle A_{m}}$ qui assure que l'appartenance à ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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é.

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

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

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 ${\displaystyle \left(H(s^{n})-n\right)}$ est minorée (${\displaystyle s^{n}}$ désigne les n premiers symboles d'une suite s, et ${\displaystyle H(s)}$ la complexité de Chaitin-Levin)[12]. Chaitin a démontré récemment que cette définition est équivalente à : ${\displaystyle \lim _{n\to \infty }H(s^{n})-n=+\infty }$.

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.

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[1].

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[1].

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[13], 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 ${\displaystyle A_{i}}$ soit récursivement énumérable, par la condition que les ensembles ${\displaystyle 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.