suite aléatoire

On lance une pièce seize fois et l'on note 0 pour pile, 1 pour face : 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0. La suite paraît désordonnée. Pourtant, ce court relevé ne prouve pas qu'elle est aléatoire : une règle cachée pourrait produire exactement les mêmes termes.

Pour une suite infinie, l'idée rigoureuse consiste donc à demander si une procédure de calcul peut y déceler une régularité exceptionnelle. Plusieurs définitions précisent ce que signifie « déceler », notamment celles de Martin-Löf et de Schnorr.

Une suite aléatoire, au sens algorithmique, est généralement une suite infinie de symboles prise dans un alphabet fini, souvent les chiffres binaires 0 et 1. L'absence de motif visible n'est qu'une intuition : la définition doit préciser quels procédés de détection sont autorisés et quelle mesure de probabilité est choisie. Pour la mesure uniforme sur les suites binaires, un test de Martin-Löf est une famille (U_m) uniformément effectivement ouverte telle que μ(U_m) ≤ 2^−m. Une suite est aléatoire au sens de Martin-Löf lorsqu'elle n'appartient à l'intersection des U_m d'aucun de ces tests.

La même classe peut se décrire par l'incompressibilité de Levin et Chaitin. Lorsque les programmes servant de descriptions sont autodélimités, le préfixe formé des n premiers termes ne doit, pour aucune longueur n, posséder une description sensiblement plus courte que n, à une constante fixe près. La définition de Schnorr impose une effectivité plus stricte au contrôle des probabilités des tests. Les martingales offrent une autre langue : elles modélisent des stratégies de pari qui tentent d'exploiter les termes successifs.

Ces contributions portent sur des critères distincts. Émile Borel a étudié la normalité et les fréquences des blocs ; Richard von Mises, les collectifs et les règles de sélection, précisées ensuite par Alonzo Church ; Jean Ville, les stratégies de pari et les limites de cette approche. Kolmogorov a ouvert la voie de la complexité descriptive, tandis que Martin-Löf a formulé les tests effectifs et que Schnorr en a proposé une variante. Leonid Levin et Gregory Chaitin ont développé, par des travaux distincts, les liens entre hasard et incompressibilité. Ces notions relèvent de la calculabilité : elles qualifient une suite mathématique infinie, pas seulement le procédé physique qui aurait produit un échantillon fini.

Cinq éléments structurent la notion. L'alphabet fixe les symboles possibles, par exemple 0 et 1. La suite infinie ordonne ces symboles ; chacun de ses préfixes donne une observation finie. La mesure de probabilité, calculable dans le cadre usuel, fixe la probabilité des ensembles de suites ; dans le cas binaire standard, c'est la mesure uniforme. La classe de procédés effectifs précise ce qu'un algorithme peut détecter. Le critère de succès décide quand une détection est trop exceptionnelle, quand une compression est trop forte ou quand une stratégie de pari s'enrichit sans borne.

Le critère n'a de sens qu'avec la mesure et la classe de procédés choisies, et chaque préfixe dépend de la même suite infinie. Ces données permettent de formuler un test de Martin-Löf, une condition d'incompressibilité ou un critère par martingales. La manière d'afficher les 0 et les 1 ne fait pas partie de la structure.

Reprenons le préfixe observé lors de seize lancers : 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0.
1. Les données sont seize termes, avec 0 pour pile et 1 pour face.
2. Le comptage donne huit 0 et huit 1 : les deux fréquences valent donc 8/16, soit exactement 1/2.
3. Parmi les quinze paires qui se chevauchent, on compte deux fois 00, cinq fois 01, cinq fois 10 et trois fois 11.
4. En ajoutant +1 après un 1 et −1 après un 0, l'écart cumulé revient à 0 au seizième terme. Le tracé matérialise ce contrôle.
5. Ces résultats sont compatibles avec des lancers équilibrés, mais ils ne certifient pas le hasard algorithmique. Un algorithme déterministe peut fabriquer ce même préfixe. Le contrôle est refaisable en recomptant les seize symboles et les quinze paires.

Devant une liste finie de 0 et de 1, on recherche d'abord des déséquilibres ou des motifs simples. Ces contrôles signalent certaines régularités, mais leur réussite ne transforme pas l'échantillon en preuve de hasard.

Pour étudier une suite infinie comme objet mathématique, on choisit ensuite une notion précise. Les tests de Martin-Löf conviennent au hasard algorithmique le plus usuel ; le cadre de Schnorr convient lorsqu'on exige un contrôle calculable plus fin du test.

Si la question porte sur la possibilité de décrire les préfixes, on emploie la complexité de Kolmogorov. Si elle porte sur une stratégie exploitant les termes successifs, on adopte le langage des martingales. Le choix dépend donc du critère observable étudié.

Suite pseudo-aléatoire. Elle est produite par un algorithme à partir d'un état initial. Deux exécutions avec le même algorithme et le même état reproduisent la même suite ; une suite aléatoire au sens de Martin-Löf ne peut pas être entièrement calculable.

Nombre normal. Dans son écriture dans une base donnée, chaque bloc fini apparaît avec la fréquence attendue. Ce critère de fréquence est moins exigeant que le hasard algorithmique : une écriture peut être normale tout en étant calculable.

Variable aléatoire. C'est une fonction mesurable définie sur un espace probabilisé, à valeurs dans un espace mesurable. Elle associe une valeur à chaque résultat, tandis qu'une suite aléatoire algorithmique est un objet infini dont on examine les régularités effectives.

Préfixe fini. Même un milliard de termes ne suffit pas à établir qu'une suite infinie est aléatoire au sens de Martin-Löf. Le symptôme trompeur est une batterie de tests tous réussis ; il faut conclure seulement que ce préfixe n'a pas révélé les régularités recherchées.

Fréquences équilibrées. Obtenir autant de 0 que de 1, comme huit contre huit dans l'exemple, ne suffit pas. Une règle calculable peut imposer cet équilibre. Il faut examiner une famille entière de tests effectifs, pas un seul indicateur.

Définition non précisée. Dire seulement « aucune régularité » masque la classe des procédés autorisés. Une suite peut satisfaire une notion de hasard et échouer à une notion plus forte. Il faut annoncer explicitement Martin-Löf, Schnorr, Levin-Chaitin ou le critère par martingales employé.

Complexité de Kolmogorov — Elle précise comment mesurer la longueur de la plus courte description algorithmique d'un préfixe.

Martingale — Elle donne le modèle mathématique des stratégies de pari utilisées pour détecter une régularité exploitable.

Nombre normal — Il permet de comparer l'équilibre des fréquences avec l'exigence plus forte du hasard algorithmique.

Algorithme — Il éclaire le sens de « procédure effective », central dans les définitions modernes d'une suite aléatoire.