Qualité aléatoire

[Médiat]

Est-ce que “est aleatoire ce qui est incompressible” répond à cette demande de définition?

Je ne suis pas spécialiste du sujet, mais il me semble avoir vu quelque chose comme cela dans le cadre de la complexité de Kolmogorov.
-----

[Verdurin]

Je ne suis pas spécialiste du sujet, mais il me semble avoir vu quelque chose comme cela dans le cadre de la complexité de Kolmogorov.

Sauf que l'on peut avoir des suites aléatoires ayant une complexité de Kolmogorov faible. C'est juste improbable, pas impossible.
Et que si on donne la liste des 10 000 premiers bits après la virgule de l'écriture binaire de ln(42) ou de sin(42) il sera très difficile de voir que la complexité de Kolmogorov est très petite.

[Médiat]

Et ?

Cela empêche les gens qui se posent la question d'avoir des idées ?

[invite73192618]

Sauf que l'on peut avoir des suites aléatoires ayant une complexité de Kolmogorov faible. C'est juste improbable, pas impossible.

Non, contresens. Par exemple, tu peux trouver un emplacement quelque part dans les décimales de pi qui encode un dictionnaire français-anglais. Cela ne veut pas dire que ce dictionnaire est lui-même aléatoire.

[Médiat]

tu peux trouver un emplacement quelque part dans les décimales de pi qui encode un dictionnaire français-anglais.

Si pi est univers

[Verdurin]

Et ?

Cela empêche les gens qui se posent la question d'avoir des idées ?

Non.
C'est juste difficile.

[invite73192618]

Si pi est univers

Oui, j’aurais du ajouter “probablement”... au risque d’ajouter une couche de confusion! ... disons d’un nombre univers quelconque. (Distribution laissée en exercice )

[Verdurin]

Non, contresens. Par exemple, tu peux trouver un emplacement quelque part dans les décimales de pi qui encode un dictionnaire français-anglais. Cela ne veut pas dire que ce dictionnaire est lui-même aléatoire.

Juste comme çà :
les décimales de pi ne sont pas aléatoires et leur complexité de Kolmogorov est faible. Je ne vois pas ce qu'elles viennent faire ici.
On peut très bien écrire un nombre univers dont les décimales sont très faciles à calculer.
Par exemple : 0,1234567891011121314 . . .
J'ai la nette impression que tu ignores le problème de départ.

[edit]
Et de toutes façons le problème porte sur des suites finies : ce sont les seules dont on connaît tous les termes.

[gg0]

Bonjour Minushabens.

"Si une telle suite (disons de nombres entiers entre 0 et 2^64) ne dépend pas d'entrées extérieures ...". les suites produites par JulesMhz sont justement produites par un élément extérieur (générateur quantique). Si le système est construit correctement, le caractère aléatoire est justifié par la théorie quantique et ses présupposés : D'après cette théorie (et ses nombreuses vérifications), la suite est parfaitement aléatoire.

Cordialement.

[LeMulet]

Si le système est construit correctement, le caractère aléatoire est justifié par la théorie quantique et ses présupposés : D'après cette théorie (et ses nombreuses vérifications), la suite est parfaitement aléatoire.

D'accord, mais ce n'est pas suffisant.
Tout comme on sait qu'une balance doit obéir aux lois qui permettent sa fiabilité, il est néanmoins nécessaire d'en "faire la preuve" de manière expérimentale.

D'autre part, il faut bien comprendre (je ne fais probablement que vous le rappeler, mais ça mange pas de pain) qu'il ne s’agit pas alors d'une preuve basée sur un raisonnement binaire, mais une présomption de preuve, basée sur un niveau de confiance.

Par exemple, si je sors (malencontreusement ) la suite 0000000000000000000000000000, rien ne permet d'affirmer avec certitude qu'il ne s'agit pas d'une "suite aléatoire".
Mais si un test (du chi deux par exemple, comme proposé) affirme qu'on a 0.001 % de chance que cette suite soit aléatoire, on prend ce que fournit le test et on conclu que cette suite n'est pas issue d'une tirage aléatoire (si on se pose encore des questions après, il ne sert à rien...).

En dehors des mathématiques, c'est à dire dans les sciences, les "tests" ayant un niveau de confiance très élevé, ont valeur de certitude (jusqu'à preuve du contraire).

Maintenant, pour ce qui concerne ces histoires de longueur des séries, je ne vois pas vraiment l’intérêt d'en faire l'étude.
(Ce serait comme faire de la numérologie...)
La seule chose à vérifier, à mon avis, (avec un niveau de confiance défini), c'est l'indépendance des tirages et l'égalité des occurrences.

[invite73192618]

Par exemple, si je sors (malencontreusement ) la suite 0000000000000000000000000000, rien ne permet d'affirmer avec certitude qu'il ne s'agit pas d'une "suite aléatoire".

Meme remarque que Verdurin (et gg0): la definition de Kolmogorov permet de prouver que cette suite n’est *pas* aleatoire (preuve: “30 zeros” est plus court que “00000000000000000000000000000 0”). Bref, vous confondez “suite aléatoire” avec “suite produite par 7n processus aléatoire”. Le second est une interprétation physique indémontrable (mais refutable), le premier est une definition mathématique prouvable (pas nécessairement facilement).

[gg0]

Jiav,

rapidement : La notion que tu utilises pour "aléatoire" n'est pas une définition de l'aléatoire des probabilités, seulement d'une façon de choisir des suites d'une façon "inattendue" pour nous. Et d'ailleurs, ça n'a pas de sens pour les suites courtes ("1" serait une suite aléatoire, "11" aussi) et une grande quantité de tirages aléatoires courant (quand on jette 3 dés par exemple) sont rejetés par cette définition.
Donc c'est une notion théorique de complexité algorithmique, très intéressante, mais qui ne correspond pas à la question initiale.

Cordialement.

[minushabens]

Mais la définition probabiliste d'une suite aléatoire n'est pas très bien caractérisée non plus. Par exemple je peux définir une variable aléatoire X(0) qui suit la loi de Bernoulli de paramètre p : X(0) vaut 0 avec la probabilité 1-p et 1 avec la probabilité p. Ensuite, pour n>0 je définis X(n)=X(0). Ce processus est bien un processus aléatoire, il est stationnaire, markovien, évidemment pas ergodique. Donc on ne peut jamais dire qu'une suite n'est pas (la réalisation d'un processus) aléatoire au sens probabiliste.

[gg0]

Ce qui est bien défini, c'est une suite de variables i i d (indépendantes et identiquement distribuées) et c'est ce qu'on cherche pour un simulateur de suites aléatoires. Après, si on veut simuler un processus, on se sert des suites aléatoires obtenues.

Cordialement.

[invite73192618]

rapidement : La notion que tu utilises pour "aléatoire" n'est pas une définition de l'aléatoire des probabilités.

Certes, puisque CK est bien postérieur à la théorie des probabilités. Néanmoins il me semble que c’est la définition actuellement standard, non? Dit autrement, est-ce que tu considères les décimales de pi comme aléatoires (car iid) ou comme non aléatoires (car CK faible)?

[gg0]

Non, les décimales de Pi ne sont pas aléatoires, elles sont parfaitement déterminées. La suite des décimales de Pi n'est absolument pas iid.

L'aléatoire des probabilités n'est pas tout l'aléatoire, c'est seulement l'aléatoire "réglé", celui qu'on peut ramener à des règles (justement, celles des probabilités). L'aléatoire des événements uniques, par exemple, ne fait pas partie des probabilités.

Cordialement.

[Médiat]

Néanmoins il me semble que c’est la définition actuellement standard, non?

Non, Levin et Chaitin ont fait évoluer les idées.

[invite73192618]

Non, les décimales de Pi ne sont pas aléatoires, elles sont parfaitement déterminées. La suite des décimales de Pi n'est absolument pas iid.

L'aléatoire des probabilités n'est pas tout l'aléatoire, c'est seulement l'aléatoire "réglé", celui qu'on peut ramener à des règles (justement, celles des probabilités). L'aléatoire des événements uniques, par exemple, ne fait pas partie des probabilités.

Quelle est la règle que tu utilises pour dire qu'une suite est ou non iid?

Non, Levin et Chaitin ont fait évoluer les idées.

Quelle est la définition d'aléatoire que tu considérerais actuelle? Si tu pouvais aussi préciser l'impact de Levin et Chaitin sur l'évolution de cette définition, ce serait du bonbon.

[Médiat]

Je ne les ai plus sous la main ; il y a aussi Martin-Löf

[LeMulet]

Si tu pouvais aussi préciser l'impact de Levin et Chaitin sur l'évolution de cette définition, ce serait du bonbon.

Pour Chaitin :

Randomness and Mathematical Proof

Scientific American 232, o. 5 (May 1975), pp. 47#52 by Gregory J. Chaitin.

Although randomness can be precisely defined and can even be measured, a given number cannot be
proved to be random.

This enigma establishes a limit to what is possible in mathematics

http://www.owlnet.rice.edu/~km9/Rand...thematical.pdf

[gg0]

Je n'ai pas besoin d'une règle pour dire qu'une suite déterministe n'est pas iid. Il n'y a rien d'aléatoire dans les décimales de Pi.

Tu sembles mélanger la difficulté à obtenir des nombres et le fait qu'ils soient aléatoires, éventuellement à confondre inconnu et aléatoire. Le triplet composé des trois résultats de trois jets successifs qu'on va faire avec un dé est aléatoire, mais très simple. Le 123456789123456789123456789-ième chiffre après la virgule de Pi est difficile à déterminer (inconnu par moi), mais n'est absolument pas aléatoire. De la même façon, ton nom m'est inconnu, mais n'a rien d'aléatoire.

Cordialement.

NB : Si la suite des décimales de Pi était une suite iid, elle varierait avec les tirages

[invite73192618]

Je ne les ai plus sous la main

Too bad. Est-ce que le lien de LeMulet correspond à ce que tu avais en tête?

Pour Chaitin

Merci mais.....

Clearly a more sensible definition of randomness is required, one that does not contradict the intuitive
concept of a ``patternless'' number. Such a definition has been devised only in the past 10 years.
(...)
This definition was independently proposed about 1965 by A. N. Kolmogorov of the Academy of Science of
the U.S.S.R. and by me

...il parle donc bien de la complexité de Kolmogorov là. Je ne savais pas qu'il l'avait découvert indépendamment (du moins, selon lui!). La question concernait s'il avait fait évoluer la définition d'aléatoire depuis Kolmogorov (lui ou Levin).

Je n'ai pas besoin d'une règle pour dire qu'une suite déterministe n'est pas iid.

Moi, oui. Est-ce que tu peux tenter de formaliser le critère que tu utilises (pour dire si c'est iid) en proposant une règle empirique?

[Médiat]

Dans le texte en référence il est bien écrit :

The original formulations have been improved

Voir aussi "la mesure de Levin", "la profondeur de Bennet"


Ce document me semble très bien : https://tel.archives-ouvertes.fr/tel-00839374/document

Plus court : https://interstices.info/complexite-...-informatique/

[gg0]

Tu veux une règle pour déterminer si une suite déterministe est aléatoire ?

Ce n'est pas parce que des mathématiciens on décidé d'appeler "aléatoires" des suites de complexité (de Kolmogoroff) suffisantes pour ne pas être réductibles par un programme qu'ils ont défini ce que les probabilistes appellent des suites iid. D'ailleurs, il me semble qu'au début on les appelait "algorithmiquement aléatoires".
Il faut se méfier des usages de mots par une partie des mathématiciens qui spécialisent un mot plus général pour leur usage particulier. Pour caricaturer, je ne joue pas à la pétanque avec les boules de la topologie.

Cordialement.

[gg0]

Pour éclaircir les choses : Ce qui est parfaitement connu n'est pas aléatoire. Une fois obtenue, une suite de Pile ou Face obtenue avec une pièce n'est plus aléatoire, il n'y a plus rien de hasardeux. C'est le tirage de la suite qui est aléatoire. La suite PPFPFPFFPFFFFFPFPFPP est parfaitement connue, le hasard n'intervient pas. L'appeler "aléatoire" alors que c'est le résultat d'un choix de ma part (ou d'un tirage à Pile ou Face, peu importe), est une déformation de la notion d'aléatoire. Se poser la question "est-elle iid" n'a pas de sens, tout au plus, "pourrait-elle être le résultat d'un tirage iid ?" a un sens, mais la réponse est oui pour n'importe quelle suite de P et de F. Comme toutes les autres, elle a une chance sur 1048576 d'avoir été obtenue.

Cordialement.

[invite73192618]

@Médiat: merci, je vais prendre le temps de lire ça avant de te revenir.

Tu veux une règle pour déterminer si une suite déterministe est aléatoire ?

Plus exactement, je veux une règle pour savoir ce que tu appelles suite iid.

C'est le tirage de la suite qui est aléatoire. [la suite elle-même, l]'appeler "aléatoire" alors que c'est le résultat d'un choix de ma part (ou d'un tirage à Pile ou Face, peu importe), est une déformation de la notion d'aléatoire.

Tiens, tu ne trouves pas un certain air de famille avec?

Bref, vous confondez “suite aléatoire” avec “suite produite par 7n processus aléatoire”.

[gg0]

Effectivement,

il y a un air de famille, ce qui fait que je ne te comprends plus tout à fait. Si on avait continué de parler de la question initiale, on aurait évité ces approximations de vocabulaire. Mais comme tu semblais refuser les explications que je produisais (rigueur de vocabulaire ? Pinaillage ?), j'ai été obligé de continuer.

A noter : On utilise depuis plus de 70 ans des "suites de nombres aléatoires" qui sont des suites de nombres obtenus par tirage supposé aléatoire (iid).

[invite73192618]

"la profondeur de Bennet"

Merci pour les docs, oui c'est vrai que c'est une évolution intéressante. Pas certain de comment intégrer cette notion dans une réponse à la question de départ.

il y a un air de famille, ce qui fait que je ne te comprends plus tout à fait.

Ma grille de lecture:
Pour toi (et Verdurin, si je le comprend bien), "suite aléatoire" est un raccourci pour "suite produite par un processus iid" et il n'y a juste pas de sens à parler d'une suite qui serait elle-même aléatoire.
Pour moi (et Médiat, si je le comprend bien), "suite aléatoire" est une propriété de la suite qui indique sa non compressibilité (qu'on la mesure par sa complexité de Kolmogorov ou par des mesures plus sophistiquées -pun intended)

Si on avait continué de parler de la question initiale

La question de départ est de savoir comment tester si les suites produites par un générateur physique sont ou non aléatoires. La première définition conduit à répondre qu'on le saura jamais. La seconde définition conduit à la mesurer.

[gg0]

D'accord, Jiav,

mais qu'est-ce qu'on mesure ? Pas le fait qu'elle soit produite par un processus aléatoire uniforme (par définition, toutes les suites de longueur n sont possibles, chacune avec la même probabilité). Seulement qu'elle fasse partie de l'ensemble des suites difficiles à produire, qui n'ont pas plus de probabilité d'être produites, chacune, que celles qui sont facile à produire.
Donc une intéressante discussion sur la complexité algorithmique, mais qui a dévié du sujet initial.

"La première définition conduit à répondre qu'on le saura jamais." Très exactement, il n'y a pas de preuve mathématique, seulement des tests probabilistes. Par contre, c'est bien le problème de JulesMhz.

Cordialement.