stratégie optimale d'arrêt d'un jeu

freddy · 30-06-2009 19:36:28

Hellu tutti,

un de mes copains vient de me transmettre le problème suivant :

On peut jeter un dé, parfaitement équilibré, 5 fois au maximum.

On peut s'arrêter quand on veut.

Quand on s'est arrété de jouer, on gagne une somme égale à une multiple du numéro sorti lors du dernier jet.

A quel moment faut il s'arréter de jouer ?

freddy · 30-06-2009 22:10:51

Re,

bon, a priori, on voit bien que si on sort un 6, il faut s'arrêter car on ne pourra pas améliorer le résultat.

Symétriquement, si on tire un 1, il faut continuer, sans remord, sauf si c'est la fin du jeu.

Ensuite ...

nerosson · 01-07-2009 12:39:38

Bonjour, Freddy, heureux de te retrouver. D'habitude, j'ai toujours une vacherie en réserve à ton intention, mais là, je suis pris de court...
Venons en à ta question :
Si on sort un deux, on a quatres chances sur six de faire mieux la prochaine fois : il faut rejouer.
Si on sort un trois, on a trois chances sur six de faire mieux la prochaine fois et une chance sur six de faire aussi bien : il faut rejouer.
Si on sort un quatre, on a deux chances sur six de faire mieux, et une de faire aussi bien, et trois chances sur six de faire moins bien.
Si on suit la même logique que précédemment, on devrait arrêter. Mais en fait ça n'est pas si simple. Ce que je dis est vrai si on en est à son quatrième lancer, on n'en a plus qu'un et je crois que ma conclusion est bonne. Mais si on en est à son troisième lancer, le raisonnement doit être infléchi par le fait qu'on dispose encore de deux lancers et non d'un. Donc, dans ce dernier cas, je rejouerais.A fortiori, si j'en étais à mon premier ou deuxième lancer.
Ce raisonnement du nombre des lancers restants n'est pas susceptible d'influencer les trois cas envisagés au début, puisque, même si on en est à l'avant-dernier lancer, on rejoue.
Il y a donc deux cas où ma réponse est incomplète, ce sont les cas ou on sort un quatre ou un cinq, car la décision est influencée par le nombre de lancers encore disponibles.
Je laisse à ces savants matheux qui poussent comme le chiendent sur ce site le soin de parachever la réponse.
Amitiés,Freddy.

freddy · 01-07-2009 13:41:22

Ahhh, mon bon ami nerosson qui sort de la torpeur estivale l'esprit vif comme un jouvenceau !

Bon, tu as ouvert la piste que j'entrevoyais au déjeuner.

On définit la variable aléatoire G = X - F, avec F le numéro sorti et X les numéros qu'on peut avoir si on procède à un nouveau tirage. ON notera queles tirage sont indépendants !

On peut se donner comme règle de décision : je continue à jouer si E(G) >0, sinon j'arrète.

Avant de jouer la première fois, [tex] E(G) = \sum_{k=1}^6 \frac{k}{6} = 3,5 [/tex]

On a tout intérêt à jouer , puisqu'on ne peut que gagner.

Soit F le numéro obtenu au précédent tirage, on calcule alors [tex] E(G) = \sum_{k=1}^6 \frac{k-F}{6} = 3,5 - F[/tex]

Conclusion : on s'arrète dès qu'on a obtenu 4 ou plus.

Et au pire, au dernier tirage, on gagne sûrement F > 0

Qu'en pensez vous, les bibm@theux ?

Et toi, ami nerosson ?

Dernière modification par freddy (01-07-2009 14:22:23)

nerosson · 01-07-2009 16:07:38

J'en pense que tous ces agrégés de maths me donnent des boutons ! ! !
Cela dit, ta conclusion me laisse un peu réticent.
Comme je l'ai dit, si c'est au quatrième essai que j'obtiens 4, j'arrête les frais. Mais si c'est au premier lancer que je fais quatre, je me dis "j'ai encore quatre essais possibles pour faire un cinq ou un six, je rejoue". J'admets qu'il y a là une réaction intuitive. Une démonstration mathématique dépasse les capacités d'un vieux schnock qui a quitté le collège il y a 65 ans. C'est pourquoi je repose le problème un peu différemment à tous ces bibmatheux de haut vol :
Si, ayant fait quatre au premier lancer, et ayant la possibilité de faire encore quatre lancers (ou moins), combien de chances ai-je d'avoir eu raison, autrement dit de pouvoir arrêter sur un cinq ou un six ?
Allez, Yoshi, freddy et consorts, qui avez encore du lait derrière les oreilles, en piste ! ! !

Dernière modification par nerosson (01-07-2009 16:31:13)

freddy · 01-07-2009 16:51:45

Re,

tu as raison, ami nerosson, après réflexion et entretien avec moi-même, la solution proposée n'est correcte que si j'ai droit à deux tirages seulement. Je regadre la suite dès que ...

A plutarque

yoshi · 01-07-2009 18:09:10

Salut,

Si je fais un arbre, après le 1er jet, j'ai droit à 6^4 = 1296 possibilités de résultat...
Il me suffirait de relever toutes les branches contenant au moins un 5 ou un 6, puis de comptabiliser les jets 'positifs' et de faire un ratio, non ?

Mais c'est trop pour moi, pour ce soir, après le travail pour nerosson, j'ai plus envie de faire fonctionner mon cerveau...
D'autant qu'il doit bien exister une formule qui permette sur 4 jets consécutifs de savoir combien de tirages positifs sont possibles....
Ah bah...
Allez un petit coup de Python : j'ai 1040 possibilités...
soit 1040/1296, 80,2 % de chances de faire 5 ou 6 (ou les deux) dans les 4 jets suivants...

Ca me paraît beaucoup...

Freddy, ôte-moi d'un doute, que j'aie fait 1, 2, 3, 4, 5 ou 6 au 1er jet, ça n'influe absolument pas sur les jets suivants, j'entends mathématiquement parlant pour chercher 5 ou 6 ?
Mais c'est clair que dans l'optique du gain, ce n'est pas la même chose.
Si je veux absolument tenter d'avoir un 6 dans les 4 jets suivants, je n'ai plus que 671 solutions soit encore 52,4 % de chances d'être exaucé...
Là, sauf pour un joueur invétéré, j'estime que le jeu n'en vaudrait pas la chance... Si 100 % des gagnants on tenté leur chance, c'est bien connu, hélas 100 % des perdants aussi...

@+

freddy · 02-07-2009 00:35:53

Re,

oui Yoshi, les tirages sont indépendants => [tex] Prob(B=k/A=j) = \frac{Prob(B=k)\times Prob(A=j)}{Prob(A=j)} = Prob(B=k) [/tex]

Sinon, la Prob d'avoir au moins un 6 dans les 4 tirages = 1 - Proba de n'avoir aucun 6 dans les 4 tirages =

[tex] 1 - (\frac{5}{6})^4 = 0,5177 [/tex]

nerosson · 02-07-2009 12:35:27

Salut,
Yoshi a dit :
"80,2 % de chances de faire 5 ou 6 (ou les deux) dans les 4 jets suivants..."
C'est là que se trouve la réponse à ma question, telle que je l'avais formulée.
Mon pif ne m'avait pas trompé.
Merci et salut à tous les deux.
P.S. si on veut prolonger le jeu et houspiller un peu tous ces bibmatheux, on peut reformuler le problème comme suit :
On a vu que :
a - si on a quatre après le premier lancer, on a raison de continuer,
b - si on a quatre au quatrième lancer, on a raison de ne pas continuer.
question : à partir de combien de lancers, est-il plus sage de se contenter de quatre ?
Ca, c'est pour em...quiquiner Freddy. J'adore. Pour Yoshi, je l'enquiquine aussi, mais en liaison directe....

freddy · 02-07-2009 18:42:33

Re,

bon, je pense avoir trouvé la bonne manière de modéliser le problème, qui rend d'ailleurs hommage à la perspicacité de nerosson et la ténacité de yoshi (ou bien l'inverse).

On considère n jets possibles. On a effectué le premier jet et on a obtenu F.

L'événement à probabiliser est " Sachant que j'ai obtenu F au premier tirage, quelle est la proba que j'obtienne au moins une fois dans les (n-1) jets suivants F ou plus". On a :

[tex] Prob(n-1, F) = 1 - (\frac{F-1}{6})^{n-1}[/tex]

Il reste à fixer le seuil de décicion. Si on décide de s'arréter si cette proba est strictement inférieure à 60 %, on a alors :

Si F = 6 , arrêt immédiat du jeu ;
avec deux jets : arrêt à 4 et plus ;
avec trois jets : arrêt à 5 et plus ;
avec quatres jets : quel que soit F (différent de 6), on continue la partie.

A chaque tour, le nombre de jets restants nous indique à quelle valeur de F s'arrêter.

PENTIMENTUM

mon critère est trop subjectif, il faut que je trouve un critère plus "robuste" pour savoir quand vraiment s'arrêter.

Dernière modification par freddy (06-07-2009 16:20:52)

vbnul · 04-07-2009 19:39:21

Ici on a 5 va iid tirant entre 1 et 6, la va aléatoire qui me semble intéressante à étudier serai :

[tex]X_{i+1}\geq X_i \text{ ou } X_{i+2}\geq X_i \text{ ou ...}/X_i[/tex]

En inversant l'évènement (1-P(…)) on pourrait peut être simplifier…

freddy · 05-07-2009 21:45:20

vbnul a écrit :

Ici on a 5 va iid tirant entre 1 et 6, la va aléatoire qui me semble intéressante à étudier serait :
[tex]X_{i+1}\geq X_i \text{ ou } X_{i+2}\geq X_i \text{ ou ...}/X_i[/tex]
En inversant l'évènement (1-P(…)) on pourrait peut être simplifier…

Hi,

oui, je pense que c'est un bon début, mais cela ne règle pas le problème de la construction d'un critère simple et objectif.

freddy · 06-07-2009 17:43:37

Hello everybody,

je reprends du début. On suppose qu'on gagne un multiple de 10.000 euros, pour mettre un peu de piment à la sauce.

Le jeu proposé ne connait pas de perdant, comme ils disent à la foire du trône sur la pelouse de Reuilly !

Je peux jeter au maximum 5 fois un dé parfaitement équilibré.

Au début, je joue et espère gagner 3.500 euros. Le 1 sort, c'est sûr, je rejoue si je peux. Le 6 sort, c'est le gain maximal, je quitte le jeu, quel que soit le nombre de tirage restant.

J'ai joué et j'ai sorti 4. Dois je poursuivre ? Tout dépend du nombre de jeux restant.

H_1 : c'est le dernier tirage. Je peux donc soit rejouer et espérer gagner 35.000 euros, ou bien avoir sûrement 40.000 euros > 35.000 euros. Il est raisonnable de s'arrêter, alors que si j'avais eu moins de 4, il est rationnel de continuer.

H_2 il reste 2 tirages. je rejoue car, soit j'obtiens 4, 5 ou 6, ou bien j'obtiens 1, 2 ou 3 et je rejoue avec gain espéré de 35.000 euros.

Donc, sous H_2, je continue si j'ai 4 ou moins et j'espère gagner : (4+5+6)/6 + 50%*3.5 = 4.25*10.000 euros > 40.000 euros

Supposons que le premier tirage m'ait donné 5 . Faut il continuer sous H_2 ?

L'espérance de gain devient : (5+6)/6+ 2/3*3.5=41.667 euros < 50.000 euros.

Donc réponse : si j'ai eu 5 au premier tirage, je stoppe !

On établit, sauf erreur de ma part, qu'il en est de même s'il reste 2,3 ou 4 tirages.

++

Dernière modification par freddy (06-07-2009 23:07:53)

grine · 12-07-2009 10:28:17

Bonjour,

Au pire, acheter "Pour la Science" de ce mois-ci, il y a tout ce qu'il faut en ce qui concerne les stratégies optimales d'arrêt.

Tchô
Grine

freddy · 12-07-2009 11:09:00

Salut grine,

exact, c'est ce que j'avais indiqué sur un autre sujet, j'avais trouvé la source des pbs que m'avait posés mon collègue de travail (on pense d'ailleurs qu'au moins une réponse indiquée est inexacte).

Tu auras remarqué, si tu as bien lu, que le contenu est plus journalistique que scientifique :présentation assez pauvre de la problématique soulevée, aucune démonstration des stratégies optimales décrites, raccourcis saisissants, analyses approximatives des notions des jeux à informations complètes ou non, ... un bon boulot d'investigation qui suppose soit qu'on est spécialiste des questions, soit qu'on se contente des idée véhiculées sans chercher à comprendre un minimum.

D'où les sujets ouverts que j'ai ouvert ici, "pour l'honneur ...".

Une bonne journée

Dernière modification par freddy (12-07-2009 12:32:18)

ISO · 03-08-2009 17:38:48

Le problème est bien connu :
Il faut partir du dernier jet du dé (le 5ème).
Si on arrive jusqu’au dernier jet on tirera alors une valeur entre 1 et 6 soit en moyenne 3,5
(1+2+3+4+5+6)/6
Il faudra donc s’arrêter au 4ème jet si on n'espère pas faire mieux en moyenne au 5ème c'est à dire si on tire 4 ou 5 ou 6 soit en moyenne 5.
Au 3ème jet arrêt si on tire 5 ou 6 moyenne 5,5
Arrêt si on tire 6 au 2ème ou au 1èr jet.
L’espérance de gain sera un peu supérieure à 5.

freddy · 04-08-2009 09:55:45

Salut,

Ouaip, c'est ce qu'on appelle de l'analyse rétrograde, "la descente et la remontée de l'arbre de décision" décrite dans le principe de Belman d'optimisation dynamique (Voir Luce & Raïffa "Théorie de la décision" 1969 ?)

Merci de cette simplissime et très élégante démonstration.

Bb

Dernière modification par freddy (04-08-2009 21:24:04)

ISO · 04-08-2009 15:27:30

Hélas, j’ai simplifié outrageusement le raisonnement dans mon message précédent ce qui m’a conduit à des conclusions fausses.
En effet :

L’espérance de gain avant le dernier tirage est bien de 7/2 = 3,5 donc il ne faut s’arrêter au 4ème tirage que si l’on tire 4, 5, ou 6 donc une probabilité de tirer ces 3 chiffres de ½ et un gain de (4+5+6)/3=5
Mais avant le 4éme tirage l’espérance de gain est :
(espérance de gain du 4ème tirage)*(probabilité de réussite du 4ème tirage) + (probabilité d’échec du 4ème tirage)*(espérance de gain du 5ème tirage) soit
5*1/2+7/2*1/2= 17/4= 4,25
Donc le 3ème tirage doit être supérieur à 4,25 soit 5 ou 6 c'est-à-dire une probabilité de 2/6 et une espérance de gain de 11/2 ; à la fin du 2ème tirage l’espérance de gain sera donc : 11/2*2/6+17/4*4/6 = 14/3= 4,78
Donc le 2ème tirage devra être supérieur à 4,78 soit 5 ou 6 avec une espérance de gain de 11/2
Probabilité à la fin du 1er tirage :14/3*4/6+11/2*2/6 =89/18 =4,94
Le 1er tirage devra donc retenir 5 ou 6 pour une espérance de gain de 11/2
L’espérance de gain moyenne pour le jeu sera : 11/2*2/6+89/18*4/6 =277/54=5,129

Conclusion
1er tirage s’arrêter si 5 ou 6
2ème tirage s’arrêter si 5 ou 6
3ème tirage s’arrêter si 5 ou 6
4ème tirage s’arrêter si 4, 5 ou 6

Gain moyen 5,129
(Cette fois je crois que c'est juste - j'ai fait une simulation avec Mathematica; on ne se méfie jamais assez avec les probabilités)

Forum de mathématiques - Bibm@th.net

#1 30-06-2009 19:36:28

stratégie optimale d'arrêt d'un jeu

#2 30-06-2009 22:10:51

Re : stratégie optimale d'arrêt d'un jeu

#3 01-07-2009 12:39:38

Re : stratégie optimale d'arrêt d'un jeu

#4 01-07-2009 13:41:22

Re : stratégie optimale d'arrêt d'un jeu

#5 01-07-2009 16:07:38

Re : stratégie optimale d'arrêt d'un jeu

#6 01-07-2009 16:51:45

Re : stratégie optimale d'arrêt d'un jeu

#7 01-07-2009 18:09:10

Re : stratégie optimale d'arrêt d'un jeu

#8 02-07-2009 00:35:53

Re : stratégie optimale d'arrêt d'un jeu

#9 02-07-2009 12:35:27

Re : stratégie optimale d'arrêt d'un jeu

#10 02-07-2009 18:42:33

Re : stratégie optimale d'arrêt d'un jeu

#11 04-07-2009 19:39:21

Re : stratégie optimale d'arrêt d'un jeu

#12 05-07-2009 21:45:20

Re : stratégie optimale d'arrêt d'un jeu

#13 06-07-2009 17:43:37

Re : stratégie optimale d'arrêt d'un jeu

#14 12-07-2009 10:28:17

Re : stratégie optimale d'arrêt d'un jeu

#15 12-07-2009 11:09:00

Re : stratégie optimale d'arrêt d'un jeu

#16 03-08-2009 17:38:48

Re : stratégie optimale d'arrêt d'un jeu

#17 04-08-2009 09:55:45

Re : stratégie optimale d'arrêt d'un jeu

#18 04-08-2009 15:27:30

Re : stratégie optimale d'arrêt d'un jeu

Pied de page des forums