Peut-on simuler le hasard ?

[Schrodies-cat]

Je prendrais le cas d'une suite de bits aléatoires (ou pas).
On peut dire que cette suite est aléatoire si il est impossible, connaissant les n premiers bits de cette suite, de prédire le n+1ième bit de cette suite avec une probabilité supérieure à 1/2.
Par des méthodes classique (réciproque de la fonction de répartition de la loi de la variable qu'on veut simuler etc), il est possible à partir de la de simuler n'importe quelle variable aléatoire.
Dans la pratique, on peut souvent se contenter de suites pseudo aléatoires, c'est à dire pour les quelles il est seulement difficile de prédire le bit suivant avec une probabilité supérieure à 1/2.
Dans la pratique, ce qu'on exige d'une suite pseudo aléatoire dépend des applications.
A priori, pour des application du type résolution d'un problème d'analyse numérique par une méthode de Monte-Carlo ne demande pas une suite très robuste et on peut se contenter des générateurs de suites pseudo aléatoires classiques, initialisés éventuellement avec la date et l'heure.
Pour la génération de clefs de cryptographie, il y a de sérieuses contraintes de sécurité.
Utiliser la date et l'heure comme racine d'une générateur pseudo aléatoire permettrait de déterminer la suite pseudo aléatoir en un nombre limité d'essais.
Les logiciels de cryptographie utilisent souvent une vaste combinaison d'octets présents sur le disque dur de l'ordinateur pour déterminer un nombre pseudo aléatoire. étant donné la pagaille qui règne dans nos ordinateurs, et le fait que divers logiciels modifient sans cesse le contenu du disque dur, cela peut sembler pertinent.

Pour avoir un hasard d'origine physique, je propose, plutôt qu'utiliser des éléments radioactifs, ce qui pose des problèmes de sécurité et de pollution, ou des circuits faisant intervenir des phénomènes quantiques, comme le proposent certains, je propose tout simplement d'utiliser le bruit thermique produit par les composants électroniques (bruit de souffle) en le numérisant et en gardant les bits de poids faible.
Cette méthode me parait robuste et ne fait appel qu'à des composants classiques.
-----

[Garion]

Mon raisonnement tient, sauf je j'ai commis une grosse bourde : dans un fichier texte il ne faut pas raisonner sur la valeur en bits des nombres, mais sur la valeur en bits des octets de la table ASCII ou ANSI.

Comme j'aime bien l'expérimentation, je viens de faire un petit logiciel pour convertir le premier million de décimales de pi (que j'ai pu trouver sur le net en texte) en binaire.
Cela m'a donné un fichier de 415 242 octets, je l'ai converti en zip (415 482 octets) puis en 7z (415 389 octets).
Bref, les deux compacteurs n'ont pas réussi à compresser quoi que ce soit. Ça vaut ce que ça vaut.

[JPL]

Je dis

[obi76]

Ce n'est pas si simple. Les compresseurs utilisent en général une recherche de redondance des OCTETS, pas de succession de bit qui ne sont pas des multiples de 8... Cette conclusion me parait un peu rapide puisque les algos que tu as utilisés ne sont juste pas faits pour ça.

[Deedee81]

Salut,

Ce n'est pas si simple. Les compresseurs utilisent en général une recherche de redondance des OCTETS, pas de succession de bit qui ne sont pas des multiples de 8... Cette conclusion me parait un peu rapide puisque les algos que tu as utilisés ne sont juste pas faits pour ça.

De plus, ils ne sont pas infiniment performants.
A une époque j'avais travaillé sur la compression de donnée et j'avais trouvé (dans un livre) la méthode de compression arithmétique (on utilise plus souvent la méthode par dictionnaire) : ultraperformante pour ce qui de la compression (on peut tendre vers la compression maximale) mais épouvantable pour ce qui est de la vitesse (d'où le fait qu'elle soit peut utilisée).
Faudrait trouver ça (je n'ai malheureusement plus accès au code, ayant changé d'employeur depuis longtemps).

Un lien (que je n'ai pas lu) :
https://fr.wikipedia.org/wiki/Codage_arithm%C3%A9tique

[Schrodies-cat]

(...) (on peut tendre vers la compression maximale) (...)

Là, je me demande si des résultats d' incalculabilité, si on définit la compression maximale à l'aide de la complexité de Kolmogorov, ne contredisent pas votre affirmation.

[Deedee81]

Là, je me demande si des résultats d' incalculabilité, si on définit la compression maximale à l'aide de la complexité de Kolmogorov, ne contredisent pas votre affirmation.

Pas nécessairement car on peut s'approcher de la compression maximale.... sans jamais l'atteindre.
Et les algorithmes de compression "presque" maximale peuvent être parfaitement calculable.

Ceci dit, cette efficacité des algorithmes était citée dans le livre (d'un collègue) mais je n'ai pas étudié la démonstration.

[invite73192618]

Selon vous, peut-on simuler le hasard ?

En termes algorithmiques, la meilleure façon d'exprimer cela est : est-ce qu'il existe des one-way functions, c'est-à-dire des méthodes pratiques pour générer des suites de nombres qu'il sera très difficile de différencier d'une suite aléatoire. Il n'y a pas de garantie mathématique que cela existe (si on en avait, cela résolverait automatiquement la question P?NP), mais disons que la très grande majorité des mathématiciens pensent que oui.*

Pour Pi on parle d'aléatoire notamment parce qu'on pense qu'il est équirépartit (ce n'est pas prouvé), mais surtout parce que l'information sur un nombre quelconque de décimales n'apporte pas d'information pour calculer une autre décimale (ça c'est prouvé, car il existe un algorithme pour trouver directement une décimale quelconque sans calculer les décimales précédentes). En revanche ce n'est pas aléatoire au sens de Kolgomorov du plus petit programme possible. Ainsi, en prenant l'exemple de la suite de JPL, la façon la plus courte de mémoriser les 12800 nombres de la suite est de simplement mémoriser un programme qui sort les 12800 premières décimales de Pi, ce qui est beaucoup plus court que de mémoriser les décimales directement.

Pour le comportement des compresseurs usuels sur cette suite, il faut savoir qu'aucun compresseur ne marche avec toutes les suites (il y a même des théorèmes qui l'interdisent). Quand un compresseur est appliquée à n suites aléatoires, moins de la moitié des suites diminue de taille, et pour chaque suite dont la taille diminue il y a une suite dont la taille augmente. Le truc, c'est que généralement nous n'utilisons pas les compresseurs sur des suites aléatoires, mais sur des suites (du texte en langage humain, des images naturelles, etc...) qui ont certaines propriétés non aléatoires (on peut sans avoir vu les fichiers prédire qu'il y a plus de "e" que de "x", plus de ligne droites et de zones homogènes que le hasard, etc). Ce sont ces propriétés qui permettent aux compresseurs de marcher en pratique, même si on des garanties mathématiques que les compresseurs ne marchent pas dans le cas général.

*n'étant pas mathématicien, je me permet de croire avoir peut-être démontré le contraire
** bien sur, c'est probablement une erreur dans ma démo

[Garion]

Ce n'est pas si simple. Les compresseurs utilisent en général une recherche de redondance des OCTETS, pas de succession de bit qui ne sont pas des multiples de 8... Cette conclusion me parait un peu rapide puisque les algos que tu as utilisés ne sont juste pas faits pour ça.

Tu as raison, c'est pour ça que j'ai ajouté à la fin "Ça vaut, ce que ça vaut".

Toutefois, il y a quelque chose d’intéressant dans ces expériences, les compressions faites sur des fichiers textes (dont au niveau de l'octet) n'ont pas donné de meilleurs résultats qu'un stockage optimal en binaire. Les outils de compression n'ont pas trouvé de séquences significativement plus probables que d'autres.