Groupe de travail de l'équipe “Probabilités & Statistiques” de l'Institut Élie Cartan (Nancy)
27 juin 2013 : Rémi Peyre
Le nombre de Chaitin

Qu'est-ce qu'une suite de bits aléatoire ? C'est la question que cet exposé se propose d'aborder.

La théorie des probabilités classique appréhende la notion d'aléa à partir de celle de mesure : on peut dire qu'un objet aléatoire (par exemple une suite de bits indépendants et uniformes) a telle probabilité de vérifier telle propriété, mais on ne peut pas dire qu'un objet particulier soit aléatoire en tant que tel, puisque tous les objets ont la même probabilité — nulle — d'occurrence ! Du reste, à supposer qu'on disposerait, par quelque théorie que ce soit, d'un critère satisfaisant pour déclarer un objet particulier comme aléatoire, il semblerait absurde d'être alors capable de définir univoquement un tel objet : car comment pourrait-il être raisonnable de considérer comme aléatoire un objet parfaitement défini ?

Dans cet exposé, nous allons voir qu'il existe pourtant une définition de l'aléatoire qui répond de façon satisfaisante aux deux problématiques ci-dessus. Cette définition, qui repose sur des concepts de théorie de l'information que l'exposé présentera soigneusement, consiste à dire qu'une suite de bits est “aléatoire” si et seulement si elle est incompressible, càd. s'il n'est pas possible de générer N bits de cette suite à l'aide d'un programme lui-même de longueur substantiellement plus courte que N bits. Nous montrerons qu'avec une telle définition de l'aléa, une suite de bits “aléatoire” vérifie effectivement toutes les propriétés attendues, par exemple la loi du logarithme itéré ou la transcendance du nombre réel qu'elle définit.

L'acmé de l'exposé consistera en la définition du nombre Ω de Chaitin (qui se trouve incidemment être interprétable comme une... probabilité), qui est un exemple de nombre “aléatoire”... parfaitement défini ! Le paradoxe apparent à l'existence d'un tel objet viendra de ce que, certes, on peut définir Ω comme la limite d'une suite croissante majorée complètement explicite, mais qu'on ne peut pour autant prouver aucun résultat sur la valeur de Ω au-delà d'une certaine précision, de sorte que Ω reste inaccessible en pratique...

Références

Du plus accessible au plus approfondi :
  1. META MATH! (The Quest for Omega), par G. Chaitin ; arXiv:math/0404335 ou Pantheon Books éd. 2005. Traduction française : Hasard et Complexité en mathématiques (La Quête de Ω) ; Flammarion éd. 2009.
  2. Elements of Information Theory, par T. M. Cover & J. A. Thomas ; Wiley éd. 2006.
  3. An Introduction to Kolmogorov Complexity and Its Applications, par M. Li & P. Vitányi ; Springer éd. 1997.