Comment construire une suite finie aléatoire?

Bonjour tout le monde,

Sujet qui va sans doute faire un bide, mais selon le consensus plus ou moins établi parmi les mathématiciens depuis les travaux sur la théorie de la complexité, une suite aléatoire de nombres est une suite qu'il est impossible de compresser, c'est à dire que, pour une séquence numérique finie, il doit être impossible de stocker la même information dans un volume plus petit de données, et pour une séquence infinie qu'il ne doit pas exister de règle de construction permettant de déduire les nombres suivants depuis les nombres déjà existants dans la suite numérique.

La question est la suivante : sachant qu'il n'existe pas de compresseur sans perte universel, existe-t-il toujours un algorithme particulier (bien que différent selon le fichier) permettant de compresser sans perte une suite finie de chiffres (càd n'importe quel fichier)? A défaut, est-il possible de trouver une logique cachée ou un ordre spécial dans chaque suite finie de chiffres? Notons bien que la présence d'une logique particulière dans une suite numérique finie ou d'un ordre quelconque est nécessaire mais non suffisante à une compression sans perte efficace, puisqu'au delà du contenu compressé il faudra également stocker la méthode ou le programme permettant de recalculer le fichier de départ, ce qui pourrait bien se faire à perte.

Le codage de huffmann n'est donc pas forcément une solution : non seulement il ne peut pas compresser les suites où les chiffres sont équiprobables, mais pour des suites trop courtes nous pourrions supposer qu'il sera plus lourd de stocker le fichier compressé plus l'arbre et le programme qui permettent de reconstituer le fichier d'origine. A priori j'arrive de proche en proche à la déduction que parfois une suite finie pourra bien être aléatoire au sens où elle sera parfaitement incompressible par tout algorithme envisageable, puisqu'alors il serait possible de compresser indéfiniment le résultat avec différents algorithmes jusqu'à n'obtenir qu'un seul chiffre, ce qui me paraît absurde.

Mais comme l'absence d'ordre dans une suite numérique est impossible à prouver, j'ai l'impression de me retrouver avec un objet clairement défini mathématiquement tout en étant fini, sans pouvoir toutefois en exhiber un seul! Encore faudrait-il toutefois définir ce qu'on appelle un ordre dans une suite, mais une absence d'ordre me paraît impossible à démontrer sur une suite finie. En bref, si nous supposons qu'il existe bien des suites finies aléatoires, existe-t-il toujours une suite finie aléatoire pour une longueur fixée d'avance et comment s'y prendre pour en construire une? S'il n'existe aucune méthode un tel nombre n'existera pas, mais s'il en existe donc forcément une, c'est que la méthode permettant de le recalculer doit être trop laborieuse.

Quelle pourrait donc être une telle méthode? Faut-il considérer qu'aucune suite finie n'est aléatoire ou existe-t-il vraiment des suites finies aléatoires mais serait-il impossible de prouver lesquelles le sont?

Salut,

On en avait déjà discuté, tu avais ouvert un sujet similaire.

Cordialement.

De mémoire ma réponse :

C'est que pour une suite finie (humainement lisable de quelquels milliers de bits) la complexité de Kolmogrorv n'est pas une bonne estimation de la complexité, en effet elle dépend du langage utilisé pour compresser, imagine que dans le langage que tu utilises la suite est déjà stocké et s'appelle la Quasi-suite, et alors tu auras artificiellement une complexité basse.

En résumé il n'existe pas de bonne estimation de la complexité pour des suites humaines accessibles, la complexité de Kolmogrov est bien quand la suite en taille tend vers l'infini.

Cordialement.

Salut,
déjà, il faut lever les ambiguïtés que l’on peut relever dans ton post.
Tu évoques à plusieurs reprises deux notions : celle  de compression et celle plus profonde de suite « aléatoire »
Pour ce qui est de la compression, déjà, tu t’embrouilles un peu. Il existe des algorithmes sans perte aucune. Et c’est heureux car sinon, plus personne n’aurait jamais l’idée de compresser un fichier. Des exceptions à la règle, existent bien sûr, mais elles ne deviennent tolérables que quand le fichier à compresser est un fichier, qui justement accepte d’être encore lisible après décompression même en cas de perte d'information, on peut citer le très classique MP3 qui, procédant par échantillonnage, se permet de réduire la bande passante d’un fichier audio. Ou celui du non moins classique JPEG qui fait la même chose avec des fichiers graphiques. Dans le premier cas, le résultat final serait équivalent à ce qui se passe quand tu écoutes un morceau de musique à un concert, et quand ensuite tu écoutes l’enregistrement sur différents système audio de qualités différentes. Idem pour une image qui viendrait d’un modèle photographié avec appareil photo de très haut de gamme et celle que nous rendrait un appareil photo du genre « jetable ».
Pour le reste, comme par exemple la compression d’un fichier « texte » tout bête, aucune erreur après décompression ne peut être tolérée : le fichier « décompressé » doit être absolument identique à l’original. En général, on comprime les attributs du fichier, par exemple la définition des polices utilisées, ou celle de leur propriétés ( bold, italic, size et autres…) Et cela peut suffire pour gagner beaucoup sur la taille du fichier « compressé »
Donc, on passe sur cette notion de « compression » pour rester clair.
Il reste donc celle de la définition d’un fichier «aléatoire » et plus particulièrement le sens que l’on donne à ce mot, aléatoire.
Est-ce de cela dont tu souhaites parler ?
Je te dis cela parce que sinon tu vas te trouver seul avec des émules de contrexemple qui vont faire du vent, sans jamais pouvoir te donner des exemples concrets. Il est en effet notoirement connu que seuls ceux maitrisent bien un sujet peuvent en en parler …. et se faire comprendre.

il y a 36 minutes, azad2B a dit :

Je te dis cela parce que sinon tu vas te trouver seul avec des émules de contrexemple qui vont faire du vent, sans jamais pouvoir te donner des exemples concrets. Il est en effet notoirement connu que seuls ceux maitrisent bien un sujet peuvent en en parler …. et se faire comprendre.

Et toi en tempête dans un verre d'eau tu t'y connais.

Pour revenir au sujet, la notion d'aléatoire définie à partir de la complexité est une notion "classique", en effet une suite aléatiore est une suite dont la complexité est au moins aussi grande que la suite elle même.

Tu sais tu devrais, apprendre à dire une phrase plus souvent : "je ne sais pas". 

Le problème est dans la définition de la complexité qui est toujours à une constante prés...

PS : tu sais écrire un post entier, sans avoir à critiquer un tel ou un tel... pour l'instant je ne t'ai jamais vu réaliser ce qui pour toi relève de la prouesse...

C'est la réponse de Quasi-Modo qui m'intéresse. Désolé. Encore une fois, tu embrayes, sans savoir quel est le sens exact de la question posée. 

il y a 9 minutes, azad2B a dit :

C'est la réponse de Quasi-Modo qui m'intéresse.

Alors ne me site pas dans ton message, tu le sauras pour une prochaine fois.

Tchuss.

Le débat commence à devenir intéressant !

Je trouve remarquables les exemples de "compressibilité ou de non compressibilité de fichiers donnés par azad2B. 

Faire une suite d'éléments totalement indépendants et donc imprévisible implique bien qu'on ne puisse pas lui enlever un iota sous peine de la rendre fausse. Elle est donc "incompressible".

il y a 45 minutes, Répy a dit :

Faire une suite d'éléments totalement indépendants et donc imprévisible implique bien qu'on ne puisse pas lui enlever un iota sous peine de la rendre fausse. Elle est donc "incompressible".

Tout à fait, et c'est cela qui est remarquable. Il existe des algorithmes qui savent déceler dans une suite dont les éléments semblent aléatoires, mais qui en réalité cache un ordre dont la logique n'est pas connue, l' élément "incongru" qui mérite attention. Un peu comme si dans le relevé des températures journalières prises à Taïti on ne trouvait que des nombres entre 18 et 23 degrés tout au long de l'année et qu'un -12°C apparaissait un (triste) jour. Il y aurait de quoi perturber le plus calme des météorologue.

Mais j'avoue que le savoir qu'implique l'écriture d'un tel algorithme me dépasse énormément.

il y a 22 minutes, azad2B a dit :

 

Tout à fait, et c'est cela qui est remarquable. Il existe des algorithmes qui savent déceler dans une suite dont les éléments semblent aléatoires, mais qui en réalité cache un ordre dont la logique n'est pas connue, l' élément "incongru" qui mérite attention. Un peu comme si dans le relevé des températures journalières prises à Taïti on ne trouvait que des nombres entre 18 et 23 degrés tout au long de l'année et qu'un -12°C apparaissait un (triste) jour. Il y aurait de quoi perturber le plus calme des météorologue.

Mais j'avoue que le savoir qu'implique l'écriture d'un tel algorithme me dépasse énormément.

Cet exemple de température négative à Tahiti est remarquable puisqu'il a été déjà utilisé pour faire foirer des lancements de fusée et autres opérations militaires. Ce genre d'anomalie météo grossière sert de signal déclencheur dans des procédures de sabotages de tous ordres. Les exécutants en recevant ce signal savent qu'ils peuvent passer à l'action. C'est comme le poème de Verlaine (les sanglots longs des violons....) suivis la nuit du 5 au 6 juin 1944 (...bercent mon cœur d'une langueur monotone !) et là les résistants savaient qu'il fallait saboter l'occupation allemande.

Et c'est ce que recherchent encore les militaires qui veulent contrer le nord coréen.

Incroyable, je croyais sortir cet exemple du néant, mais visiblement j'avais dû enregistrer la chose dans mon subconscient après en avoir pris connaissance. Comme quoi, ta tête c'est une sacrée fichue machine ! Dommage qu'on ne la maîtrise pas soi-même parfaitement. Quoique ... c'est p'tet un bien finalement ?

Il y a 2 heures, Répy a dit :

Cet exemple de température négative à Tahiti est remarquable puisqu'il a été déjà utilisé pour faire foirer des lancements de fusée et autres opérations militaires. Ce genre d'anomalie météo grossière sert de signal déclencheur dans des procédures de sabotages de tous ordres. Les exécutants en recevant ce signal savent qu'ils peuvent passer à l'action. C'est comme le poème de Verlaine (les sanglots longs des violons....) suivis la nuit du 5 au 6 juin 1944 (...bercent mon cœur d'une langueur monotone !) et là les résistants savaient qu'il fallait saboter l'occupation allemande.

Et c'est ce que recherchent encore les militaires qui veulent contrer le nord coréen.

L'ensemble des outils fonts l'instrument vérité, de la paix. L'ensemble des armes font l'instrument de torture. (idiome instrumental avertisseur).

Il y a 18 heures, azad2B a dit :

Tu évoques à plusieurs reprises deux notions : celle  de compression et celle plus profonde de suite « aléatoire »
Pour ce qui est de la compression, déjà, tu t’embrouilles un peu. Il existe des algorithmes sans perte aucune. Et c’est heureux car sinon, plus personne n’aurait jamais l’idée de compresser un fichier. Des exceptions à la règle, existent bien sûr, mais elles ne deviennent tolérables que quand le fichier à compresser est un fichier, qui justement accepte d’être encore lisible après décompression même en cas de perte d'information, on peut citer le très classique MP3 qui, procédant par échantillonnage, se permet de réduire la bande passante d’un fichier audio. Ou celui du non moins classique JPEG qui fait la même chose avec des fichiers graphiques. Dans le premier cas, le résultat final serait équivalent à ce qui se passe quand tu écoutes un morceau de musique à un concert, et quand ensuite tu écoutes l’enregistrement sur différents système audio de qualités différentes. Idem pour une image qui viendrait d’un modèle photographié avec appareil photo de très haut de gamme et celle que nous rendrait un appareil photo du genre « jetable ».
Pour le reste, comme par exemple la compression d’un fichier « texte » tout bête, aucune erreur après décompression ne peut être tolérée : le fichier « décompressé » doit être absolument identique à l’original. En général, on comprime les attributs du fichier, par exemple la définition des polices utilisées, ou celle de leur propriétés ( bold, italic, size et autres…) Et cela peut suffire pour gagner beaucoup sur la taille du fichier « compressé »
Donc, on passe sur cette notion de « compression » pour rester clair.
Il reste donc celle de la définition d’un fichier «aléatoire » et plus particulièrement le sens que l’on donne à ce mot, aléatoire.
Est-ce de cela dont tu souhaites parler ?

Salut,

Merci pour ta réponse. Ce que tu affirmes sur la compression me paraît juste je ne comprends seulement pas pourquoi tu me réponds ça puisque je le sais déjà et n'ai pas dis le contraire

Bien entendu qu'il existe des algorithmes de compression sans perte, le codage de Huffman que j'évoque étant par ailleurs classé parmi ceux-ci, l'astuce étant de coder les informations sur un nombre de bits variable au fonction de la fréquence d'apparition de chaque caractère : par exemple en français si le e apparaît le plus souvent il sera codé sur 1 bit, etc ... tandis que plus un caractère sera fréquent dans la suite à compresser, moins il y aura de bits pour le coder ... 

Mais il n'y a pas d'algorithme de compression sans perte universel au sens où si un algorithme de compression sans perte réduit la taille d'un fichier alors forcément il allongera la taille d'un autre  

A propos de l'aléatoire je la relie précisément à la compression, c'est à dire qu'une suite aléatoire est une suite qu'on ne peut pas compresser, ce qui est plus ou moins la définition admise aujourd'hui.

D'où ma question finale : peut-on considérer qu'il existe mathématiquement parlant des suites aléatoires finies et comment pourrait-on en exhiber une? Finalement je pense avoir ma réponse : c'est semble-t-il impossible puisque la complexité de Kolmogorov est non calculable, c'est à dire qu'il n'existe pas de programme informatique qui prenne un fichier et annonce si il est encore possible de le compresser ou non.

Il y a 19 heures, contrexemple a dit :

De mémoire ma réponse :

C'est que pour une suite finie (humainement lisable de quelquels milliers de bits) la complexité de Kolmogrorv n'est pas une bonne estimation de la complexité, en effet elle dépend du langage utilisé pour compresser, imagine que dans le langage que tu utilises la suite est déjà stocké et s'appelle la Quasi-suite, et alors tu auras artificiellement une complexité basse.

En résumé il n'existe pas de bonne estimation de la complexité pour des suites humaines accessibles, la complexité de Kolmogrov est bien quand la suite en taille tend vers l'infini.

Cordialement.

Salut,

Tu fais bien de parler de la complexité de Kolmogorov puisqu'elle contient la réponse.

Cependant la complexité de Kolmogorov est bel et bien définie sur des objets de taille finie, d'ailleurs il n'aurait aucun sens de travailler sur des objets de taille infinie en informatique puisque les mémoires sont limitées

Il y a 19 heures, contrexemple a dit :

Salut,

 

On en avait déjà discuté, tu avais ouvert un sujet similaire.

 

Cordialement.

Tu as raison en plus, je commence à m'inquiéter pour mon Alzheimer

Citation

Raisonnement Empirique : A est EC si avec 10 exemples et pas de contre-exemples connus

Je voulais juste te préciser que ce raisonnement serait faux dans le cas de conjectures qui se révèlent fausses mais vérifiées pour de nombreux cas

Sinon je viens de lire dans un cours de normalsup que la complexité de Kolmogorov peut être approchée à l'aide d'une limite qui tend vers l'infini (ce qui explique qu'elle ne soit pas calculable!). Donc mathématiquement il est peut-être possible de l'évaluer pour une suite finie, il faut que je me renseigne davantage.

source

Dans la source nous voyons bien que la complexité de Kolmogorov est définie sur des mots de longueur finie.

Cependant il semblerait que la complexité de Kolmogorov soit uniquement définie à un c près (et sur une machine donnée), mais nous pourrions dans notre cas prendre c=0 je pense et supposer que nous avons la machine optimale. Selon ce cours 99% des mots de longueur finie sont c-incompressibles (si on choisit bien son c je suppose) et il existe toujours des mots c-incompressibles de longueur n pour tout n.

Donc pour toute longueur n il existe indubitablement une suite finie aléatoire!

Après pour ce qui est d'en exhiber une c'est une autre paire de manche ptdr

Il y a 4 heures, Quasi-Modo a dit :

Cependant il semblerait que la complexité de Kolmogorov soit uniquement définie à un c près (et sur une machine donnée), mais nous pourrions dans notre cas prendre c=0 je pense et supposer que nous avons la machine optimale. Selon ce cours 99% des mots de longueur finie sont c-incompressibles (si on choisit bien son c je suppose) et il existe toujours des mots c-incompressibles de longueur n pour tout n.

Mais non, la complexité est définie à constante prés à cause du langage utilisé, il suffit que ta suite soit une constante du langage pour que la complexité avec ce langage soit basse, alors que pour un autre langage il pourrait en être autrement.

Pour résoudre cela, il faudrait fixé arbitrairement un langage à utiliser pour calculer la complexité...

Il y a 4 heures, Quasi-Modo a dit :

Je voulais juste te préciser que ce raisonnement serait faux dans le cas de conjectures qui se révèlent fausses mais vérifiées pour de nombreux cas

Non, car il suffit qu'il existe un contre-exemple connu, pour que cela ne soit pas le cas, c'est ce que l'on appelle le raisonnement empirique, raisonnement amplement utilisé en science, je te rappelle qu'un axiome n'est rien d'autre qu'une conjecture pour laquelle on parierait son bras...

PS : mais oui contrairement à la logique, avec le raisonnement empirique vrai un jour, n'est pas vrai toujours.

Pour un langage fixé, et une suite finie, le problème de savoir si cette suite est aléatoire ou non, est un problème calculable.

En effet il suffit d'énumérer tous les programmes possibles de tailles strictement plus petit que la suite (il y en a un nombre fini) et regarder s'il y en a qui génére la suite, si oui, elle n'est pas aléatoire, sinon elle est aléatoire.

Salut.
Je m’aperçois que je m’étais trompé sur le sens profond de la question posée.
Et c’est le mot « compression » utilisé, et que j’avais cru reconnaître comme étant un rapport entre la taille d’un fichier compressé et celle du fichier original, qui a provoqué mon erreur.
Votre discussion semble plus axée sur les critères permettants de d’affirmer qu’ une suite présente les caractères irréfutables d’un tirage aléatoire pur.
Cette discussion, implique donc la connaissance de techniques que je ne connais absolument pas et je vous prie de m’excuser de mon erreur et de mon intrusion dans le débat.
Amusez vous bien. Et pardonnez mon erreur. Merci.