Écart max

Bonjour,

jeancreatif a écrit:

Bonsoir Alea, tu m'as convaincu de me mettre à la programmation.

Que choisir de moins "prise de tête" ? Python ou ton Julia ?

Je te conseille le langage Wolfram (Mathematica), puissant, rapide, très compact et plus simple à comprendre que nombre d'autres langages (mais tout est relatif).

Si j'ai bien compris, on effectue 20 lancés d'une pièce de monnaie et on compte le nombre de "pile" consécutifs obtenus, qui peut se situer entre 1 et 20. On répète cette série de lancés un grand nombre de fois. Le résultat final est une liste de 20 nombres représentant le nombre total de fois qu'on a obtenu 1, 2, 3, ..., 20 "pile" consécutifs.

Ça revient à effectuer 20 tirages pseudo-aléatoires de 0 et de 1, en admettant que 0 = pile. Donc pour commencer je crée un liste de 20 zéros :

res=ConstantArray[0, 20]

dont j'incrémenterai chaque terme au fur et à mesure des résultats, sachant que le premier 0 est à l'indice 1 de cette liste. Par exemple, si après 20 lancés j'ai obtenu 3 zéros consécutifs, je ferai res3++. Pour simuler les 20 tirages je crée ensuite une liste de vingt 0 et 1 tirés aléatoirement :

RandomInteger[1, 20]

RandomInteger[k, 20] produit un entier pseudo-aléatoire de 0 à k. Supposons que cette liste soit {0,1,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0}, dont le plus grand nombre de zéros consécutifs est 4. Pour obtenir ce nombre je pose

r=Max@SequenceCases[{0,1,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0}, {p:Repeated[0]}:>Length[{p}]]

SequenceCases[...] renvoie {1, 3, 4, 2, 1}, qui correspond aux nombres de 0 consécutifs rencontrés dans cette liste, et dont Max prélève la valeur maximale, soit r = 4. Il ne reste plus qu'à incrémenter l'indice correspondant de la liste res : res4++. Voici la fonction consec0 (0 consécutifs) où nbrSer est le nombre de séries de "lancés de la pièce", et lanc le nombre de lancés effectués au cours de chaque série (20 par défaut) :



Résultats de consec0[10^6, 50] : {27, 17226, 155830, 275549, 237068, 148912, 81760, 42168, 21112, 10368, 5039, 2491, 1206, 634, 320, 147, 67, 35, 24, 7, 5, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

Graphe des 24 premiers totaux (jusqu'au 1) :



Je suppose qu'on pourrait augmenter le nombre de séries de lancer sans voir la forme du graphe changer.

Une variante, beaucoup plus rapide (20 s contre 30 mn pour 10^6 séries de lancés), consiste à prendre en compte pour chaque série la séquence de chiffres identiques la plus longue, qu'elle soit composée de 0 ou de 1 :



Je reprends l'exemple de RandomInteger[1, 20] = {0,1,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0} :

Split[{0,1,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0}] = {{0}, {1, 1, 1}, {0, 0, 0}, {1, 1}, {0, 0, 0, 0}, {1, 1}, {0, 0}, {1, 1}, {0}}

Length /@ Split[{0,1,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0}] = {1, 3, 3, 2, 4, 2, 2, 2, 1}, la longueur de chaque sous-liste. Puis Max[...] renvoie bien sûr 4, qu'il s'agisse d'une séquence de 0 ou de 1. Vu la rapidité de ce nouvel algorithme j'ai testé

consec01[10^8, 50] = {0, 3688, 1872734, 16032503, 27684193, 23519355, 14691106, 8021712, 4124500, 2058518, 1017753, 498277, 243790, 118477, 58254, 28382, 13795, 6576, 3298, 1610, 752, 373, 192, 82, 47, 22, 7, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

Alors que précédemment la plus longue séquence de chiffres identiques était majoritairement de longueur 4, cette fois-ci elle est de longueur 5, mais le graphe a exactement la même forme (29 premiers totaux, jusqu'au 1) :



On notera que sur 50 "lancés" il y a toujours au moins deux 0 ou deux 1 consécutifs, puisqu'il n'existe aucune séquence de longueur 1.

Bref, rien de nouveau, c'était juste pour montrer la simplicité du langage Wolfram par rapport à Python, Julia et autres joyeusetés.

EDIT : tout bien réfléchi, je pense que le décalage de la longueur majoritaire d'une séquence de chiffres identiques, de 4 dans le premier exemple à 5 dans le second, est dû au fait que j'ai effectué 10^6 séries de 50 "lancés" dans le premier cas, contre 10^8 dans le second. Vu qu'il a fallu 30 mn pour obtenir le premier résultat, si je passais de 10^6 à 10^8 il faudrait 100 fois plus de temps, soit 50 heures. Je ne vais donc pas m'amuser à vérifier mes soupçons. Quoi qu'il en soit, il se pourrait que prendre en compte uniquement les 0 et prendre en compte les 0 et les 1 indifféremment, revienne exactement au même. Ce qui compte en effet c'est la plus longue séquence de chiffres identiques obtenue, et elle ne varie pas avec la nature desdits chiffres puisqu'en comptant les "pile" on obtient la même chose qu'en comptant les "face".

Sylviel a écrit:

@Wilfrid : c'est sans doute une question d'habitude / goût mais je trouve le code Julia nettement plus clair que le code Mathematica.

Quelqu'un aurait-il la bonté de m'expliquer pourquoi les séquences de 4 chiffres identiques sont les plus fréquentes lorsqu'on ne prend en compte que les 0, et qu'elles sont de 5 chiffres lorsqu'on ne différencie pas les 0 et les 1, ce qui paraît totalement contrintuitif ?

En attendant, et bien que ce soit hors sujet, il me semble important que ceux qui envisagent de se mettre à la programmation fassent la différence entre un langage procédural (Wolfram) et un langage séquentiel (les autres). Il ne faut pas voir le langage Wolfram comme un langage de programmation au sens habituel du terme, mais comme une boîte de Lego. C'est un vaste ensemble de procédures (routines, fonctions) dont on combine un certain nombre pour obtenir le résultat recherché. Un programme en langage Wolfram est plus simple à mettre en œuvre qu'un programme séquentiel ordinaire puisqu'on ne se préoccupe pas de savoir comment parvenir à tel ou tel résultat intermédiaire : on se focalise uniquement sur l'objectif à atteindre, tout comme comme on le fait pour construire un objet quelconque à l'aide des briques d'une boîte de Lego. Il faut juste se familiariser avec quelques subtilités syntaxiques (comme la séquence "/@" rencontrée ci-dessus).

Pourquoi réinventer la roue à chaque fois qu'on se lance dans l'écriture d'un programme ? Telle est la philosophie de nombre de programmeurs, qui se constituent au fil du temps une bibliothèque de routines spécifiques à leurs besoins, qu'il réutilisent encore et encore. Chez Wolfram Research il y a des gens hautement qualifiés qui ont déjà constitué cette bibliothèque, destinée aux scientifiques et en particulier, bien évidemment, aux mathématiciens.

Voici un exemple particulièrement significatif. Je reprends la liste {0,1,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0} qu'il faut séparer en morceaux composés de chiffres identiques pour ensuite déterminer lequel est le plus long (sans différenciation des séquences de 0 et de 1). Pour ça j'utiliserai le langage de script PHP, parce qu'il se lit facilement.

[size=large]PHP[/size]

<?php
	$arr = [0,1,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0];
	// conversion du tableau (array) en chaine de caractères
	$chn = implode("", $arr);  // on n'insère rien entre les caractères
	$lg = strlen($chn)-1;  // longueur de la chaine - 1
	// on parcourt la chaine pour détecter tout changement de caractère (chiffre)
	$i = 0;
	while ($i < $lg) {
		if ($chn[$i+1] != $chn[$i]) {
			// le caractère à la position $i+1 est différent de celui à la position $i
			// on insère un espace entre les deux, donc à la position $i+1
			$chn = substr_replace($chn, " ", $i+1, 0);  // 0 signifie insertion (pas remplacement)
			// on incrémente le pointeur pour le placer sur l'espace
			// et on n'oublie pas d'incrémenter la longueur de la chaine
			$i++; $lg++
		}
		$i++
	}
	// création d'un tableau contenant les morceaux séparés par un espace
	$res = explode(" ", $chn);
	$lg = count($res);  // nombre d'éléments du tableau
	$plsq = 0;  // plus longue séquence de chiffres identiques
	for ($i=0; $i < $lg; $i++) {
		$k = strlen($res[$i]);  // longueur du morceau
		if ($k > $plsq) $plsq = $k
	}
	// afficher le résultat
	echo $plsq
?>

Avec du temps devant soi on pourrait trouver d'autres manières de procéder, qu'elles soient plus simples ou plus compliquées.

[size=large]Mathematica[/size]

plsq = Max[Length /@ Split[{0,1,1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0}]]

Pour les explications voir mon second précédent message.

Pourquoi s'emmerder à concevoir un algorithme et taper 28 lignes de code que quelqu'un devra lire jusqu'au bout pour comprendre son fonctionnement – et éventuellement chercher à faire mieux –, alors qu'on peut se contenter d'une seule ligne déjà dans sa forme la plus aboutie et dont la finalité apparaît immédiatement pour peu qu'on ait quelques bases en langage Wolfram ?

Il est évident qu'en interne Mathematica se livre à un tas de calculs peut-être semblables à ceux que j'ai codés en PHP, mais c'est le cadet de nos soucis ! Je suppose par ailleurs qu'il met à profit le mécanisme de type Lego que ses concepteurs ont créé, afin d'éviter toute duplication de code. C'est probablement ce qu'entend Stephen Wolfram lorsqu'il dit que Mathematica est complètement optimisé.

Je précise pour terminer que je n'ai pas d'actions chez Wolfram Research. Je suis seulement persuadé que le concept de programmation va évoluer au fil du temps et que le langage Wolfram est le prélude à changement radical. Il suffit d'ailleurs de le comparer au langage proposé par Maple pour mesurer l'évolution du concept en question sur les 30 dernières années.

@Sylviel,

Personne ne va se livrer à de savants calculs avec Php, c'est un langage de script côté serveur utilisé uniquement pour la programmation de sites Web (notamment l'accès aux bases de données). Je l'ai privilégié pour sa simplicité parce que je m'adressais à ceux qui ne connaissent rien à la programmation.

Tu as raison, convertir une liste en chaine de caractères pour faire du comptage n'est pas l'idéal, mais je n'allais pas perdre mon temps à chercher une solution qui de toute façon n'aurait servi strictement à rien. Mon but était uniquement de comparer les langages séquentiel et procédural (et je n'ai pas manqué de préciser qu'on pouvait faire mieux).

Superbes exemples en Python, vraiment, j'adore ce genre de solution ! Effectivement, tous les langages de programmation proposent des bibliothèques de fonctions qu'il suffit d'installer (avec plus ou moins de facilité). Dans Mathematica le concept de bibliothèque est cependant au cœur du système, on ne peut pas le contourner (on peut même installer des bibliothèques supplémentaires pour faciliter certains calculs particulièrement ciblés). Enfin, de la même manière que lorsque tu construis un objet à l'aide de briques de Lego tu n'as pas besoin d'outils supplémentaires ni de connaissances en bricolage, lorsque tu "programmes" en langage Wolfram tu n'as besoin que de connaissances rudimentaires en programmation, ce qui selon moi est déjà une fameuse évolution, qui va dans le sens où "programmer" une machine deviendra un jour accessible à tout le monde (des tas de gens font de la recherche dans ce domaine. On trouve déjà des petits robots à usage ludique qu'une appli permet de programmer succinctement à l'aide d'une interface simple et intuitive).

Par programmation on entend la manière dont l'homme communique ses instructions aux machines, indépendamment du langage utilisé. A ce titre il est tout à fait envisageable (et j'en suis même persuadé) qu'un autre type de communication soit possible et se mette progressivement en place. Imaginons par exemple une sorte de clavier muni de plusieurs grosses touches : l'ordre dans lequel on en presserait quelques unes – ce qui permettrait un grand nombre de combinaisons –, donnerait instruction à la machine de faire ceci ou cela, sans qu'on ait à se préoccuper de fastidieux détails. Un programme serait alors constitué de séquences de touches, qui formeraient un langage.

@lourran,

C'est bon, on vient de m'installer la lumière au dernier étage. Plus la série de lancés d'une pièce de monnaie est longue et plus le nombre de "pile" consécutifs a des chances d'être grand, d'où l'apparition de séquences majoritaires de longueur 4, 5, 6, ... au fur et à mesure qu'on augmente le nombre de lancés. Donc oui, c'est assez intuitif.

Ce qui me fascine néanmoins est qu'on soit obligés de passer par la simulation pour estimer l'ordre de grandeur desdites longueurs.

@jeancreatif,

Ce n'est pas un langage de programmation mais un outil d'aide à la conception d'un programme, qui représente sa structure, les données à traiter, les méthodes à mettre en oeuvre, le résultat à afficher, bref, une représentation du programme final qui reste à écrire dans un langage quelconque en se basant sur ce modèle. Par exemple, si tu tapes $\text{Afficher}\:\: W[ k ]$ dans Phyton tu auras droit à un message d'erreur, parce que Python ne comprend pas le mot Afficher. Mais si tu tapes print(W[k]) tout se passera bien. "Afficher" signifie seulement que tu dois utiliser l'instruction de sortie correspondante du langage que tu utilises pour visualiser le résultat du calcul, sur ton écran ou autre.

jeancreatif a écrit:

Je suppose que tu dirais qu'il est totalement contre intuitif de fabriquer le mot 0011 plus vite que le mot 1111 ?

Je ne suis pas certain que c'est ce que je dirais, à moins que tu ne m'expliques de quoi tu parles.

Le diagramme ci-dessous est issu du blog de Wolfram Research, à cette adresse. Il représente les relations entre les 6 séquences toujours gagnantes : PFF, FFP, FPF, PFP, PPF et FPP.


Supposons que je demande à mon adversaire de choisir une des 6 séquences et qu'il opte pour FFP (angle supérieur droit). Mon choix se portera alors sur PFF parce que sa probabilité de gain contre FFP est de 3/4. S'il choisit PFF pas de problème, je prendrai pour ma part PPF (angle inférieur gauche), dont la probabilité de gain contre PFF est de 2/3.

Quel que soit le choix de mon adversaire je sortirai toujours vainqueur de la compétition !

jeancreatif a écrit:

J'aimerais bien une démonstration de l'inutilité de choisir une façon de miser plutôt qu'une autre ; [...] Et bien tout cela est voué à l'échec.

Il y a peut-être une explication à ça :

1. Dans une série infinie de lancers toutes les combinaisons de P et de F de longueur donnée sont équiprobables.
   $\to$ RAS
2. Dans le jeu de pile ou face le nombre de lancers est par nature fini.
   $\to$ Paradoxe de Penney

Il n'y a de paradoxe que de notre point de vue, à notre échelle. Quelle que soit la manière dont on considère le problème un de ses aspects nous glissera toujours entre les doigts, parce qu'on ne peut pas expliquer/démontrer quelque chose qui fondamentalement n'existe pas.

@jeancreatif,

Je reformule : le paradoxe de Penney énonce ceci : "il est possible de gagner au jeu de pile ou face alors qu'en toute logique on ne le devrait pas". Le "en toute logique" fait référence à une série infinie de lancers, dont intuitivement on sait très bien qu'elle interdit tout gain à ce jeu. Si on admet que dans la vraie vie il est impossible de procéder à une série infinie de lancers, alors il n'y a tout simplement plus de paradoxe. C'est donc nous et nous seuls qui le créons, et le résultat de cette création n'a plus rien à voir avec les probabilités, c'est juste de la combinatoire.

Morale de l'histoire : si tu cherches une explication probabiliste à ce problème tu ne la trouveras pas.

Deux joueurs A et B s'affrontent. Le choix d'une séquence de longueur 3 (et uniquement dans ce cas) est laissé à A. Quelle séquence B doit-il choisir pour l'emporter sur A ?

Si A choisit $a_1\,a_2\,a_3$ alors B doit choisir $\dfrac{1}{a_2}\,a_1\,a_2$
où $\dfrac{1}{a_2}$ signifie bien sûr P si F et F si P.

Existe-t-il un algorithme similaire applicable à des séquences plus longues, voire un algorithme universel ?

Source (en anglais)

@lourran,

Pourrais-tu fournir un exemple avec B=FFPP gagnant contre A=PPPP, éventuellement sans faire intervenir les probabilités de gain de B (qu'on peut toujours calculer ultérieurement) ? Ce dont je parlais est d'un algorithme permettant de permuter les lettres de A pour obtenir la séquence gagnante de B. Les chances qu'il a de gagner sont sans importance puisqu'elles dépendent du choix de A, ce qui veut dire que B n'a pas le choix de ses gains (à condition bien sûr qu'il n'existe qu'une seule séquence gagnante).