David Madore's WebLog: Qu'est-ce qu'un nombre aléatoire ?

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #1542 [older|newer] / Entrée #1542 [précédente|suivante]:

(jeudi)

Qu'est-ce qu'un nombre aléatoire ?

Voici une question un peu provocante : qu'est-ce qu'un nombre aléatoire ? Pour un probabiliste, elle n'a pas de sens : un nombre n'est pas aléatoire (le nombre π, par exemple, ça n'a pas de sens de dire qu'il est aléatoire), ce qui a un sens, c'est de tirer aléatoirement un nombre, disons, dans l'intervalle [0;1]. Pourtant, il y a des branches des mathématiques où cela a bien un sens, de façon absolue, de dire qu'un nombre réel bien défini est — ou n'est pas — aléatoire (et, pour gâcher le suspens, le nombre π n'est pas aléatoire, en aucun sens qu'on sache définir à ma connaissance, ce qui est bien dommage parce que ça permettrait de prouver plein de choses merveilleuses à son sujet, mais c'est tout à fait intuitif parce qu'on arrive à le calculer — donc il n'est certainement pas tiré au hasard !). Je vais tâcher d'expliquer simplement de quoi il retourne, sans entrer dans trop de technicité mais en donnant tout de même des définitions complètes. L'idée qu'on cherche à développer est que :

L'aléatoire est ce qu'on ne peut prévoir (de façon non triviale) par le calcul.

Plutôt que de travailler sur des nombres réels, je travaillerai sur des suites infinies de 0 et de 1, ce qui est presque pareil (comme aucun rationnel dyadique, ou aucun rationnel tout court, d'ailleurs, n'est aléatoire en aucun sens, on peut considérer qu'une suite infinie de 0 et de 1 est la même chose que le nombre réel entre 0 et 1 qui a cette écriture binaire). Appelons Ξ (j'allais l'appeler 𝔠, mais je pense que si je fais ça beaucoup de gens ne vont rien voir d'utile) l'ensemble des suites infinies de 0 et de 1. On aura besoin de la notion d'ouvert de Ξ: un ensemble U de suites est dit ouvert lorsque c'est une réunion d'ensembles de la forme toutes les suites commençant par <un nombre fini de symboles> ; ou, de façon équivalente, lorsque pour toute suite de U il existe un rang à partir duquel on peut modifier n'importe comment la suite et rester dans U. Autrement dit, l'ensemble de toutes les suites commençant par 0, ou par 01101001, ou par 11111111, sont des ouverts, ainsi que n'importe quelle réunion — même infinie — de telles choses (par exemple, l'ensemble des suites commençant par 0 ou 11 ou 100 ou 1011 ou…), et ce sont là tous les ouverts de Ξ. (La notion d'ouvert de Ξ ne coïncide pas avec la notion plus habituelle d'ouvert de [0;1], par exemple parce que Ξ n'est pas connexe, mais la différence n'est pas importante pour ce que je vais dire.)

On dira qu'un ouvert (ou, d'ailleurs, n'importe quel ensemble) est dense lorsque son complémentaire (i.e., l'ensemble des suites qui ne sont pas dedans) ne contient aucun ouvert autre que ∅ (le vide, qui est un ouvert). Voici un exemple d'ouvert dense : l'ensemble de toutes les suites sauf la suite 000000… (ou sauf n'importe quelle suite donnée, d'ailleurs) : il est facile de vérifier que c'est un ouvert (c'est l'ensemble des suites commençant par 1, ou par 01, ou par 001, ou par 0001, autc.), et il est encore plus facile de se convaincre que son complémentaire (qui ne contient qu'une seule suite, la suite nulle) ne contient aucun ouvert non vide. L'idée est qu'un ouvert dense contient « quasiment toutes » les suites ; mais ça, ça va servir à définir les suites génériques, qui ne sont pas pareilles que les suites aléatoires.

Pour définir ce que c'est qu'une suite aléatoire j'ai besoin d'une autre notion, celle de mesure d'un ouvert (moralement, la probabilité qu'une suite de 0 et de 1 tirés au hasard indépendamment avec probabilité ½ pour chacun, tombe dans l'ouvert). J'ai dit qu'un ouvert pouvait s'écrire comme une réunion de machins qui sont toutes les suites commençant par <bla bla bla>, où <bla bla bla> ne comporte qu'un nombre fini de 0 et de 1 (on appelle de tels machins des ouverts élémentaires) : avec un petit peu d'efforts on peut s'arranger pour que la réunion soit disjointe (il suffit de retirer ce qui est redondant dans la description : l'ensemble des suites commençant par 0 ou 01, c'est juste l'ensemble des suites commençant par 0). On attribue à chacun de ces ouverts élémentaires une mesure qui est ½n (un demi puissance n) avec n le nombre de symboles imposés au début, et on ajoute toutes ces mesures pour calculer la mesure de la réunion disjointe. Par exemple, l'ouvert des suites commençant soit par 0 soit par 111, a pour mesure 5/8 (= 1/2 + 1/8) ; l'ensemble des suites autres que la suite 000000… (j'ai expliqué plus haut que c'était un ouvert) a pour mesure 1, comme l'ensemble Ξ de toutes les suites : un tel ouvert est dit de mesure pleine. Il s'avère qu'un ouvert de mesure pleine est forcément dense (pourquoi ?), mais la réciproque n'est pas vraie — si ça ne vous saute pas aux yeux, c'est sans doute normal, mais ça vaut le coup d'y réfléchir.

J'en viens à la notion de suite aléatoire et de suite générique. Mais avant ça j'aurai besoin d'une notion de calculabilité ; pourtant, je ne vais pas définir ce que c'est : ce qui est intéressant, c'est que pour chaque notion de calculabilité, je vais avoir une notion de suite aléatoire et de suite générique, qui sera d'autant plus contraignante que la notion de calculabilité est puissante. La notion la plus naturelle, c'est la calculabilité habituelle de Church-Turing (les fonctions récursives, qui sont en gros celles que peut calculer un ordinateur idéalisé), mais plein d'autres notions pourraient convenir : soit plus fortes (fonctions récursives sous un oracle quelconque, fonctions Σn de l'arithmétique, fonctions arithmétiques, fonctions hyperarithmétiques, fonctions analytiques-au-sens-de-la-calculabilité, fonctions constructibles-au-sens-de-l'univers-de-Gödel), soit plus faibles (fonctions primitives récursives, et sans doute même fonctions calculables en temps polynomial même si quand la calculabilité devient trop faible j'ai peur que les notions que je vais définir ne soient plus très bonnes).

Le but de ces fonctions calculables sera juste de pouvoir dire que certains ouverts de Ξ sont calculables : un ouvert calculable U sera juste un ouvert tel qu'une fonction calculable (donc un programme informatique idéalisé, si vous prenez la calculabilité au sens de Church-Turing) qui quand on lui présente un mot fini de 0 et de 1 décide si l'ouvert élémentaire des suites commençant par ce préfixe sera mis dans la réunion constituant U. Autrement dit, on lui demande veux-tu mettre dans l'ouvert toutes les suites commençant par 0 ?, veux-tu mettre dans l'ouvert toutes les suites commençant par 1 ?, veux-tu mettre dans l'ouvert toutes les suites commençant par 00 ?, etc., et elle prend à chaque fois une décision[#]. À titre d'exemple, tant que votre notion de calculabilité n'est pas démesurément faible, l'ensemble des suites qui ne sont pas la suite nulle — ensemble dont j'ai déjà dit que c'était un ouvert par ailleurs dense et de mesure pleine — est calculable, puisque c'est très facile de reconnaître les mots 1, 01, 001 et de répondre oui sur chacun d'entre eux. On peut aussi demander qu'une suite d'ouverts soit calculable : cela signifie que la fonction calculable prend en outre en entrée un entier (n) qui est le rang dans la suite. On définit enfin une suite décroissante calculable d'ouverts de Ξ : cela signifie simplement que la suite est décroissante pour l'inclusion (i.e., chaque ouvert est inclus dans tous les précédents), ou, si on préfère, quand la fonction calculable a décidé d'exclure un ouvert élémentaire d'un terme de la suite, elle exclut automatiquement de tous les suivants.

Quel est maintenant l'esprit de la définition ? Une suite aléatoire/générique est, en gros, une suite sur laquelle on ne puisse pas faire une prévision calculatoire non-triviale. Évidemment, on pourra toujours dire elle commence par 010100 (disons), puisque c'est une suite bien définie (je rappelle que je suis en train de définir une notion d'aléatoire qui s'applique pour une suite bien définie !) ; mais l'idée est qu'on ne peut pas faire une prévision vraiment intéressante.

Voici enfin les deux notions en question :

Une suite est dite générique lorsqu'elle appartient à tout ouvert dense calculable.

Une suite x est dite aléatoire lorsque pour toute suite décroissante calculable (Un) d'ouverts de Ξ telle que le n-ième soit de mesure au plus 1/n, la suite x n'appartient qu'à un nombre fini d'entre eux.

La définition d'une suite générique est sans doute plus simple à comprendre : si vous arrivez à faire une prévision calculable du type la suite n'est pas dans l'ouvert U que voici, alors cet ouvert ne peut pas être dense, c'est-à-dire qu'il y a quelque part un gros bout (toutes les suites commençant par un certain préfixe) qu'on a omis dans la prévision — qui n'a donc rien de remarquable (je peux bien faire la prévision la suite commence par 0101010, et il y a bien certaines suites aléatoires qui vont y coller). Dit autrement, un ouvert dense calculable contient toutes les suites génériques. Donc j'ai déjà prouvé que la suite 000000… n'est pas générique : il existe un ouvert dense (toutes les suites sauf elle !) qui est calculable et qui ne la contient pas.

La définition d'une suite aléatoire est un chouïa plus compliquée, parce que cette fois-ci on demande de faire des prévisions du type la suite est dans l'ouvert U que voici ; or on peut certainement faire des prévisions de ce style (de nouveau, je peux faire la prévision la suite commence par 0101010, et il y a bien certaines suites aléatoires qui vont y coller), on peut même certainement faire des prévisions aussi bonnes qu'on veut, mais le point important est qu'on ne peut pas le faire uniformément : si on a une suite décroissante calculable d'ouverts dont le n-ième a une mesure au plus 1/n[#2], son intersection ne contient aucune suite aléatoire. Ceci étant, on se convainc facilement que, par exemple, la suite nulle 000000… n'est pas aléatoire (de nouveau, dès que la notion de calculabilité n'est pas démesurément faible) : il suffit de considérer la suite décroissante d'ouverts donnée par les suites dont les n premiers termes sont nuls — cela donne une mesure de 1/2n.

J'ai donc prouvé que la suite nulle n'était ni aléatoire ni générique. C'est la moindre des choses. En fait, pour la même raison, n'importe quelle suite calculable au sens qu'on s'est fixé n'est ni aléatoire ni générique. En revanche, si je prends une suite aléatoire (resp. générique) et que je remplace un sur deux de ses chiffres par un 0, j'obtiens une suite qui n'est plus aléatoire (resp. générique) et qui n'est pourtant pas calculable : donc aléatoire et génériques ne sont pas synonymes de pas calculables — ils sont bien plus forts que ça.

Le fait qu'il existe des suites aléatoires et des suites génériques résulte, si la notion de calculabilité est dénombrable (i.e., s'il n'existe qu'une infinité dénombrable de fonctions calculables ℕ→ℕ, ce qui est le cas pour la calculabilité au sens de Church-Turing), résulte du théorème de Baire dans un cas (l'intersection de tous les ouverts denses calculables est non vide) et de l'additivité de la mesure dans l'autre (la réunion de toutes les intersections de suites décroissantes calculables d'ouverts dont la mesure tend vers zéro est de mesure nulle). Pour d'autres notions, cela peut être plus difficile ou impossible (si on déclare que toutes les fonctions ℕ→ℕ sont calculables, il n'y a plus aucun nombre aléatoire ou générique : pour un être omniscient, il n'y a pas de hasard).

Voici maintenant un résultat que j'ai toujours trouvé remarquable : on s'imagine que générique et aléatoire veulent tous les deux dire, de manière vague qu'on ne peut pas calculer de prévision aléatoire non triviale dessus ; pourtant, pour toute notion (un tant soit peu raisonnable) de calculabilité,

Aucune suite n'est simultanément générique et aléatoire.

La démonstration n'est pas compliquée ! Considérons, pour chaque n, l'ouvert Un de Ξ ainsi défini : il s'agit de l'ensemble des suites de 0 et de 1 qui commencent par k signes quelconques (pour un certain k fini) qui sont immédiatement suivis de 2k+n fois 0 (et ensuite n'importe quoi) : cette description montre immédiatement qu'il s'agit d'un ouvert, il est assez clair qu'il est calculable (il est très facile de reconnaître les mots formés de k signes quelconques puis 2k+n fois 0), et même, que la suite (Un) d'ouverts de Ξ est décroissante calculable. Maintenant, chacun des ouverts Un est dense (car vous aurez beau prescrire comme vous voudrez les N premiers termes d'une suite, vous n'éviterez jamais à qu'elle puisse être dans Un), et pourtant sa mesure est majorée par 1/2n ou quelque chose de ce goût-là (c'est une réponse à la question que j'avais posée plus haut : montrer qu'il existe des ouverts denses qui ne sont pas de mesure pleine). Du coup, une suite générique doit appartenir à chacun des Un, alors qu'une suite aléatoire ne peut appartenir qu'à un nombre fini d'entre eux. Cela empêche qu'une suite aléatoire soit générique.

Ce résultat est difficile à comprendre intuitivement : je pense que les suites génériques sont plus élusives que les suites aléatoires — elles donnent l'impression d'avoir des motifs dedans, ce qui est faux, bien sûr, mais elles ne se comportent pas du tout comme les suites aléatoires. Philosophiquement parlant, la suite de 0 et de 1 qu'on obtiendrait en tirant infiniment à pile ou face est assurément aléatoire, mais je ne sais pas d'où on pourrait sortir une suite générique : notre monde a l'air beaucoup plus naturellement orienté vers l'aléatoire que vers le générique[#3] — pourtant, mathématiquement, il existe une grande similarité entre ces deux notions (voir à ce sujet le livre d'Oxtoby fort justement intitulé Measure and Category).

Les suites (ou nombres réels) aléatoires et surtout génériques ont une grande importance en théorie des ensembles : par exemple, la façon dont Paul Cohen a montré l'indémontrabilité de l'hypothèse du continu c'est de fabriquer (par la technique du forcing) énormément de suites de 0 et de 1 (ou nombres réels) qui soient génériques (en fait, aléatoire marcherait aussi) en prenant pour notion de calculabilité la constructibilité au sens de l'univers de Gödel, qui est à peu près la plus forte qu'on puisse imaginer (très très grossièrement, c'est la puissance qu'aurait en quelque sorte un ordinateur capable de calculer directement sur les ensembles et sur des temps transfinis). À l'autre bout du spectre de la calculabilité, on pourrait placer la cryptographie, où la notion d'oracle aléatoire sert de modèle pour des preuves de sécurité de cryptosystèmes et où on est bien forcé de constater que ce n'est pas une notion si atteignable. Je me demande s'il y aurait lieu de considérer des oracles génériques (le terme a été utilisé, mais je crois que c'est pour quelque chose se très différent).

[#] Pour la calculabilité au sens de Church-Turing, on peut prendre l'absence de réponse, i.e., la non-terminaison du programme, comme une réponse négative, ou bien l'interdire, ça ne changera rien à la notion d'ouvert calculable.

[#2] Ça fait partie des choix pas forcément évidents à faire quand on prend une notion de calculabilité trop faible… déjà, pour la calculabilité au sens de Church-Turing, il faut se convaincre que le bon choix est bien d'imposer explicitement une vitesse de convergence et pas juste de dire la mesure de Un tend vers 0 : un des critères qui me poussent à faire ce choix, c'est que, si je ne me trompe pas, il permet alors avec l'oracle de l'arrêt des machines de Turing de construire un réel aléatoire (de même qu'on peut en construire un générique), ce qui ne serait pas possible si on demandait juste que la mesure tende vers zéro. Mais je ne suis pas totalement sûr de moi, et je le suis encore moins pour des notions de calculabilité très faibles comme la calculabilité en temps polynomial (où ça fait une différence de demander que la mesure soit bornée par 1/n ou 1/2n), et même pour la calculabilité de Church-Turing il faudrait calibrer les choses par rapport à une autre définition habituelle (mais à mon avis moins agréable) qui fait intervenir la complexité de Kolmogorov. Enfin bon, l'esprit est quand même raisonnable dans tous les cas, et pour les notions de calculabilité assez fortes (du genre être arithmétique), ça ne fait pas de différence.

[#3] Voici un autre fait digne d'intérêt : un nombre réel générique est un nombre de Liouville, c'est-à-dire qu'il s'approche très bien par les nombres rationnels, alors qu'un nombre réel aléatoire est approché par les rationnels exactement à l'ordre 2 (c'est-à-dire qu'il est à une distance d'un rationnel de l'ordre de la puissance −2 du dénominateur de celui-ci) ; or il se trouve que les nombres qui interviennent « naturellement » en analyse, en tout cas le nombre e, sont ou ont l'air d'être, approchés exactement à l'ordre 2. Du coup, en un sens qui semble malheureusement impossible à rendre précis, les décimales de e ou π sont plus proches d'être aléatoires que génériques (en vérité, elles ne sont ni l'un ni l'autre : il faudrait une notion furieusement faible de calculabilité pour que π soit aléatoire !).

↑Entry #1542 [older|newer] / ↑Entrée #1542 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées