Partie 4 : méthode de Monte-Carlo.

Le jeu de GOOGOL

L'idée du jeu proposé afin de réaliser une optimisation en utilisant la méthode de Monte-Carlo a été trouvé dans les " Nouveaux divertissements mathématiques " de Martin Gardner (éd. Dunod, 1964). Le jeu est décrit sous le nom de "Jeu de GOOGOL" ; pour Gardner, " la stratégie consiste à éliminer un certain nombre de billets et à retenir ensuite dans la série le premier nombre qui sera supérieur au plus grand des nombres rejetés au départ. Reste à trouver la formule qui nous dira combien de billets rejeter a priori en fonction du nombre total de billets ". C'est sur ce dernier point que portait la question du challenge.

Nous avions évoqué la construction d'un preuve établissant que la stratégie décrite était bien la meilleure et la possibilité d'établir mathématiquement cette fois, le nombre de billets à rejeter.

Voici notre contribution à la recherche de ces résultats. Comme convenu dans l'énoncé de la question du challenge, nous supposons que le nombre n est "suffisamment grand" pour justifier l'approximation mathématique

1. Premier acte.

Devant la file des cartons retournés, le " premier acte " consiste en l'opération suivante :

1.1. soit on ne fait rien ;

1.2. soit on retourne d'un bloc k cartons (avec pour "intention" de continuer au moins une fois ; ceci est une commodité pour décrire le jeu en deux actes comme on le fait ici ; une autre description est possible et elle est bien entendu équivalente).

Attention : Comme les valeurs portées sur les cartons sont aléatoires, on ne peut évoquer l'idée que le nombre k ait une quelconque dépendance vis à vis des valeurs portées sur les cartons.

Quand au nombre k, ce peut être, pour n fixé :

1.2.1. toujours la même valeur ;

1.2.2. une valeur variable ; mais la cohérence exige alors que k soit aléatoire ; plus précisément que tout nombre entre 1 et n soit également probable (Par définition, des événements sont équiprobables si aucun élément ne permet d'accorder la préférence à l'un d'entre eux).

Si on peut prouver qu'il existe un nombre k qui maximise strictement la probabilité de gagner, il est alors évident que l'action 1.2.2. ne peut être la bonne stratégie de départ.

2. Second acte.

Quelle est alors la bonne démarche, étant admis que l'on va encore retourner au moins un carton ? On va retourner des cartons et s'arrêter (on peut y être contraint s'il n'y a plus rien à retourner) ! Au moment de l'arrêt, deux situations sont possibles :

2.1. Le dernier carton retourné n'est pas le plus grand des retournés ; la partie est perdue ; mais on admettra aisément que ceci ne se produit que si l'on a tout retourné ! Et si on a tout retourné, la probabilité de gagner est 1/n.

2.2. Le dernier carton retourné est le plus grand des retournés ; supposons que son rang est s. Mais quand s'arrêter ? Deux possibilités se présentent :

2.2.1. On s'arrête systématiquement sur le premier (cas a), ou le deuxième (cas b), ou le troisième (cas c)... carton présentant la particularité d'être le plus grand des retournés ;

2.2.2. On s'arrête aléatoirement sur le premier, le deuxième ... carton qui est le plus grand des retournés ; le même type de raisonnement qu'en 1.2.2. permet d'éliminer cette solution.

3. Examen de l'hypothèse où l'on s'arrête sur le premier (2.2.1. a).

Quelle est la probabilité de gagner en suivant cette stratégie ?

Il faut en premier lieu que le plus grand nombre, ait son rang s dans l'intervalle [k+1 ; n]. Supposons que l'on ordonne l'intervalle [1 ; s-1] ; on obtient alors la suite ordonnée décroisante des valeurs de l'intervalle (S1, S2, S3,... , S (s-1) ) ; il faut, selon cette nouvelle notation, en second lieu que S1 ait son rang dans l'intervalle [1 ; k].

La probabilité que le plus grand élément soit de rang s est 1/n ; la probabilité que S1 ait son rang dans l'intervalle [1 ; k] est k/(s-1).

Comme s peut varier de k+1 à n, la probabilité de gagner est :

On peut remarquer que la probabilité est supérieure à 1/n. Et que cette valeur est celle que l'on obtiendrait à partir de la situation 1.1. qui est donc à rejeter.

4. Examen du cas 2.2.1. b (arrêt sur le deuxième).

En reprenant la notation du paragraphe précédent, on peut dire que si le plus grand élément S1 a le rang s, il faut que S2 ait un rang dans l'intervalle [1 ; k] et S1 dans l'intervalle [k+1 ; s-1]. On peut donc dire qu'il y a deux conditions à remplir : la première condition a la probabilité k/(s-1), la même que S1 ait son rang dans l'intervalle [1 ; k] dans la situation du paragraphe 3. La satisfaction successive des deux conditions va avoir une probabilité inférieure à k/(s-1) [elle serait en fait k(s-k-1) / (s-1)(s-2)] ; chacun des termes de la somme obtenue dans cette situation est inférieur à celui que l'on a obtenu dans la situation précédente. On peut remarquer que ce raisonnement peut être étendu à un arrêt au troisième, au quatrième...

La conclusion est que si l'on optimise la somme du paragraphe 3 (arrêt sur le premier) on obtient bien la meilleure stratégie au jeu de GOOGOL ! C'est cette hypothèse que l'on demandait d'admettre.

5. Optimisation : méthode mathématique.

La probabilité de gagner peut encore d'écrire de façon plus condensée :

Comme on le voit en math de terminale, le crochet peut être assez finement approché par ln (n/k) (ln = logarithme népérien) ; c'est une approximation par excès, avec une erreur inférieure à (1/k - 1/n). Ceci montre que la variable significative est k/n (tout au moins tant que l'approximation est valable : n assez grand, -c'est l'hypothèse- et assez différent de k, ce qui se vérifie).

On peut alors poser x = k/n. Reste à chercher le maximum de la fonction y= x ln (1/x).

* calcul des dérivées :

* tableau de variation :

* conclusion

On en déduit qu'il y a une seule stratégie optimale ; il faut prendre k aussi voisin que possible de n/e ; la probabilité de gagner et alors de 1/e

* en pratique

le nombre e vaut environ 2,72 ; et donc son inverse environ 0,37 ; on voit que la probabilité de gagner est supérieure à une chance sur trois !

On peut aller un peu plus loin en étudiant la fonction y au voisinage e son maximum ( la monotonie de y" et sa faible valeur y incitent) :


x


0,20


0,25


0,30


0,35


0,40


0,45


y


0,32


0,34


0,36


0,37


0,37


0,36

On voit que la fonction présente une très faible variation au voisinage de son maximum ; ce qui signifie que la valeur retenue pour k/n n'est pas très "sensible". En pratique, cela signifie qu'en prenant k égal au tiers de n, on ne gaspille pas ses chances de gain !

 

 

La simulation.

1. Méthode 1.

* La première idée qui vient à l'esprit est de coller le plus possible à la réalité : On peut représenter les cartons par un tableau à 100 éléments, et remplir aléatoirement ce tableau ; il n'y a là aucune difficulté, étant donné que tous les systèmes de programmation ont un générateur de nombres pseudo-aléatoires qui donne à chaque sollicitation un nombre à virgule (définir le type de tableau en conséquence) de l'intervalle [0 ; 1[ sur un mode équiprobable, avec la précision autorisée par le système (8 décimales ou plus) par une fonction appelée en général random.

* Le jeu stipule que tous les nombres doivent être différents ; en fait, il est peu probable que deux nombres soient égaux sur 100 tirages ; et la seule difficulté qui peut se présenter est que la valeur maximale soit doublée. La seconde étape peut donc se réduire à chercher la position s du nombre maximal du tableau ; au cas où celui-ci serait représenté deux fois ou plus, le bon sens consiste simplement à ignorer l'essai et recommencer le remplissage du tableau !

* Il s'agit alors de chercher le rang r du plus grand élément de l'intervalle [1 ; s-1].

* On suppose construit un deuxième tableau, de 100 entiers initialisés à 0 ; c'est le tableau des essais. La valeur k (avec la signification donnée ci-dessus) balaie le tableau ; on gagne si r, k, s sont dans cet ordre ; on perd sinon. Il suffit alors de consigner dans le tableau les gains en incrémentant les éléments dont le rang est entre r et s-1.

* si on répète 1000 (ou 10000 fois) le processus précédent, on obtient une statistique des parties gagnantes ; il suffit alors de définir le maximum du tableau et d'en déduire en divisant par le nombre des essais l'optimum de k/n et la probabilité qui lui est associée.

 

2. Méthode 2.

* On peut décoller un peu de la modélisation physique en remarquant que la probabilité que le maximum absolu ait le rang s vaut 1/n, et la probabilité que le maximum de l'intervalle [1 ; s-1] ait le rang r est 1/(s-1).

* On peut dont simuler les résultats pour un tirage en définissant s à partir de la partie entière de 100 * random ; puis la place r du maximum de l'intervalle [1 ; s-1] par le même procédé. On incrémente le tableau des essais comme précédemment.

* Le reste du processus est similaire. Il est évident que cette seconde méthode est plus rapide et plus simple à mettre en Âœuvre (elle se prête bien à un calcul sur tableur).

3. Le logiciel proposé.

Nous avions réalisé la simulation selon les deux méthodes ; le résultat compilé en était donné dans le logiciel d'accompagnement. Comme pour les autres exercices comportant de la programmation, nous avons donné la source en Pascal (Delphi; source d'extension .pas) en tant que correction (la translation dans n'importe quel langage procédural est immédiate). Il n'y a pas à s'attarder sur l'interface graphique, qui n'était pas demandée.

 

téléchargement :