Jouons aux proba

Good morning zebras
Voici une énigme dont on dit qu'elle est difficile mais ça reste à prouver :
Un chat et une souris décide de jouer à pile ou face. Mais ils se disent que ce n'est pas très intéressant comme jeu donc ils compliquent un peu la règle.
Chacun choisit une combinaison de trois résultats (ex. Pile, pile, face). Ils lancent la pièce plusieurs fois, le premier qui voie sa combinaison apparaître dans les trois derniers lancers gagne. Ils ne peuvent pas choisir la même combinaison.
Le chat, étant plus fort décide de choisir sa combinaison en premier, et la souris étant intelligente le laisse faire.

Existe-t-il une stratégie pour maximiser l'espérance du gain d'un des deux joueurs ?


Le hic avec cette énigme c'est qu'il n y a pas sa réponse sur le net, enfin après recherche bâclée, j'ai bien une théorie quant à la réponse mais je préfère avoir vos avis avisés ( ou pas ) pour trouver une solution tangible
à vous les studios

aucune startegie

J'espérais que quelqu'un propose une solu
Bon, voila comment j'analyse la situation, l'énoncé dit que la souris plus faible choisit en second, vu comme ça on a l'impression que le chat a un avantage, mais c'est tout le contraire, chose qui est crédité par le fait que la souris qualifiée comme intelligente y agrée, donc je pars du principe que le fait d'être le second est un avantage, partons de ce postulat, voici comment je vois les choses, l'avantage que conférera le fait d'être le second à la souris ne durera que pendant le premier lancé car après les chances seront égales, donc la souris attend que le chat choisit, elle n'aura besoin que de connaitre la combinaison que donnera le chat pour avoir l'avantage, je m'explique, disons que le chat choisit la combinaison suivante Pile, Face et Face, comme la souris ne peut choisir la même combinaison, il peut considérer qu'il va gagner en niant la possibilité que la combinaison du chat va gagner vue qu'il ne peut l'utiliser et donc l'exclure des 8 combinaisons possibles, en d'autres mot, pour la souris il n'existe que 7 possibilités, 3 combinaisons qui commencent par Pile et 4 combinaisons qui commencent par Face, ce qui fait qu’alors le chat a une probabilité de 12.5% de chance de gagner, la souris aura quant à elle 18.65% de chance de gagner et ainsi elle aura optimisé sa chance de gagner à son paroxysme théorique, donc si le chat commence par Pile Face Face, la souris n'aura qu'à choisir la combinaison suivante Face Pile Pile, mais cette avantage hypothétique n’aura d’intérêt que le premier lancé, pour expliquer mon principe je vais vous faire une image, imaginez un univers qui se crée à minuit, imaginez maintenant un autre univers qui se crée à minuit et quart en prenant comme reperds le notre, disons que ces 2 univers tendent vers l'infini, disons aussi qu'il y a exactement les même paramètres dans les 2 univers, un évènement X a plus de chance de se produire dans le premier univers qui s'est crée, mais après un quart d'heure de sa création, si l'évènement X ne se produit pas, et ce tendant vers l'infini, ils auront la même probabilité de la réalisation de l'évènement X, mais le premier univers aura toujours l'avantage en théorie car il aurait pu s y produire l'évènement, même s'il ne s'est pas produit, la probabilité dans le premier est plus grande en théorie, c'est exactement la même chose ici

Je tiens avec Bullbao : rien à faire, c'est simplement du hasard équiprobable. Toutes les stratégies sont équivalentes EDIT: si on s'en tient aux trois premiers lancers.

Phtos, dans ton analyse, le postulat est infondé, et ensuite, ton pourcentage néglige le fait que le chat peut gagner, quand bien même la souris ne pourrait-elle pas choisir la même combinaison. Quoi qu'elle choisisse, elle aura toujours sa chance sur 8 de gagner « du premier coup » (après trois lancers), comme le chat. Elle aurait l'avantage, et une chance sur 7 de gagner après seulement trois lancers si après le choix du chat, une fée malicieuse passait et annonçait « Hahaha, quel mauvais choix, je vous garantit que ça n'arrivera pas du premier coup ! ».

Salut! C'est une énigme intéressante.

Les 8 combinaisons sont dans l'absolu équiprobables. L'avantage de la souris ne vient pas du fait que son choix restreint augmente artificiellement la probabilité que sa combinaison apparaisse. Plutôt, ça lui permet de choisir une combinaison qui a plus de chance de précéder celle du chat. Je pense qu’elle a intérêt à choisir une combinaison dont la fin recoupe le début de celle du chat, sans que l’inverse soit vrai (par exemple « Face Face Pile » si le chat choisit « Face Pile Face ») .

Le cas le plus simple à vérifier est celui ou le chat choisit « Pile Pile Pile » (ou « Face Face Face », c’est symétrique) ; la souris en choisissant « Face Pile Pile » ne le laisse gagner que si « Pile Pile Pile » apparait dès les trois premiers lancers ( soit 1/8 ).

Dans les autres cas par contre le calcul de probabilité me semble beaucoup moins évident. Si quelqu’un est motivé…

Et sinon, si on veut jouer au malin et répondre uniquement à la question: Oui, ayant un nombre fini de stratégies possibles, il y en a forcément (au moins) une qui maximise leur espérence de gain

Je suis s'accord avec MisceKaran. La souris peut choisir, en connaissant la combinaison du chat, une combinaison plus avantageuse, avec la méthode qu'il expose.

Mais le chat peut également chosir intelligement sa combinaison. Toutes les combinaisons ne sont pas équivalentes , même si on joue seul. Ce n'est pas forcément intuitif. Dès que l'on dépasse trois lancés, certaines séquences deviennent plus efficaces.

Le cas du dessus est le meilleur pour la souris. Non seulement elle bénéficie du fait que la séquence du chat ne peut apparaître sans la "fin" de la séquence de la souris, ce qui, intuitivement, donne plus de chances à la souris d'avoir "déjà gagné" avant que n'apparaisse la séquence du chat. Mais le chat a également choisi une des pires combinaisons (PPP, FFF), et la souris une des meilleures (FFP, PPF).

Commençons par prouver que, même si le chat et la souris jouaient seuls, la combinaison du chat est moins bonne que celle de la souris (dans le sens ou la souris tombe en moyenne plus tôt sur sa combinaison).

On peut représenter le processus par des chaînes de Markov à quatre états, qui sont pour le chat:

1. État initial
2. Pile
3. Pile Pile
4. Pile Pile Pile

Et pour la souris:

1. État initial
2. Face
3. Face Pile
4. Face Pile Pile

Bon, ça serait tellement mieux avec un dessin... on va faire avec, imaginez vous le graphe dans votre tête... et c'est ici que les sceptiques apercevront que les matrices de transitions ne sont pas les mêmes!

Pour le chat, la matrice Mc:

Code:

 0.5 | 0.5 | 0.5 |  0 
 0.5 |  0  |  0  |  0 
  0  | 0.5 |  0  |  0 
  0  |  0  | 0.5 |  1 


Pour la souris, la matrice Ms:

Code:

 0.5 |  0  |  0  |  0 
 0.5 | 0.5 | 0.5 |  0 
  0  | 0.5 |  0  |  0 
  0  |  0  | 0.5 |  1 

On peut voir déjà que pour les états 2 et 3 (colonnes 2 et 3), la souris ne "retombe pas" à l'état 1 en cas d'échec, mais uniquement à l'état 2, ce qui laisse penser que sa combinaison est meilleure, car il y a moins de "retours en arrière". Pour le dernier état j'ai mis 100% de transition vers lui même, parce que, quand on a gagné, bah, on a gagné, peu importe les tirages qui suivent après.

La probabilité d'avoir gagné est la probilité d'être dans l'état 4, donc la dernière composante du vecteur d'état. Le vecteur d'état initial est V_i = (1, 0, 0, 0).

Pour trois lancés, c'est à dire en calculant M_s³V_i et M_c³V_i on obtient respectivement (0.125, 1.5, 0.25, 0.125) et (0.5, 0.25, 0.125, 0.125). La dernière composante est la même, on retrouve bien la probabilité de victoire de 1/8 quelque soit la combinaison. Mais pour les lancés suivants, ce n'est plus valable. En effet on trouve pour M_s⁴V_i et M_s⁴ V_i respectivement (1/16, 7/16, 1/4, 1/4) et (7/16, 1/4, 1/8, 3/16). Donc la souris trouve sa combinaison au quatrième lancé (ou avant) à 25%, le chat seulement à 18.75%, et ce sans tenir compte du fait que l'un peut gagner avant l'autre. On sait que ça va tendre vers 1 lorsque le nombre de lancés augmente, et que la proba de la souris va rester supérieure à celle du chat. Mais j'ai peur qu'il ne faille se contenter de la formule matricielle M_s^NV_i pour avoir la probabilité exacte d'avoir gagné au tour N (si quelqu'un peut me contredire, qu'il n'hésite pas à donner une preuve, par récurrence j'imagine).

Bon, bon.

Maintenant, on va tenir compte du fait que la souris peut gagner avant le chat. Il faut donc incorporer les deux séquences dans une même chaine. Voici les nouveaux états:

1. État initial
2. Pile
3. Face
4. Pile Pile
5. Face Pile
6. Pile Pile Pile (le chat gagne)
7. Face Pile Pile (la souris gagne)

Et voici la nouvelle matrice de transitions, M, de dimension 7 cette fois (j'ai le graphe sous les yeux, ça commence à devenir bordelique ) :

Code:

  0  |  0  |  0  |  0  |  0  |  0  |  0 
 0.5 |  0  |  0  |  0  |  0  |  0  |  0 
 0.5 | 0.5 | 0.5 | 0.5 | 0.5 |  0  |  0 
  0  | 0.5 |  0  |  0  |  0  |  0  |  0
  0  |  0  | 0.5 |  0  |  0  |  0  |  0 
  0  |  0  |  0  | 0.5 |  0  |  1  |  0 
  0  |  0  |  0  |  0  | 0.5 |  0  |  1 

Même justifications que tout à l'heure, quand on a gagné, on ne sort pas de l'état etc...

La quatrième composante du vecteur d'état sera donc la probabilité de victoire du chat et la cinquième celle de la souris. Le vecteur d'état initial est (1, 0, 0, 0, 0, 0, 0).

On calcule M³V_i on trouve bien (0, 0, 0.5, 0, 0.25, 0.125, 0.125). C'est à dire qu'avec trois lancés, les deux participants on tout les deux 12.5% de chance d'avoir gagné. Mais dès M⁴V_i on trouve (0, 0, 0.375, 0, 0.25, 0.125, 0.25), c'est à dire que la souris a deux fois plus de chance d'avoir gagné que le chat.

Chose amusante, la probabilité de victoire du chat est toujours de 0.125, quelque soit le nombre de lancés (facile à prouver en utilisant la matrice). Me serais-je trompé dans le graphe ou dans l'écriture de la matrice?
Bref, si c'est juste, la probabilité de victoire de la souris est donc de 0.875.

Ouf...

Donc oui, sous réserve que la matrice soit juste, la méthode de MisceKaran offre un énorme avantage à la souris. Il faudrait confirmer avec une simulation, et faire le calcule pour les autres combinaisons, de type FPF ou PPF, pour vérifier si l'avantage de la souris est conservé dans ces autres cas. Un volontaire? Moi je fatigue...

Edit:
Dernières news:
Une simulation avec 10^6 essais me donne: 0.875623 pour la proba de victoire de la souris et 0.124377 pour le chat.

Edit2:
Bonus: la partie se termine en moyenne en 6.99382 coups.
Ça doit pouvoir se prouver que c'est 7.

Ah oui, tiens, belle démontration, korppi. Je m'étais arrêté à « l'avantage […] à la souris ne durera que pendant le premier lancé car après les chances seront égales », alors qu'en fait, c'est précisément après les premiers lancers que les choses deviennent intéressantes ^_^

Seul, « recycler ses échecs » serait la formule gagnante ?
Du coup, PFF serait meilleur que PFP, parce que si on se rate à la troisième étape, on ne revient pas autant en arrière ?
Les combinaisons seraient donc, de la moins bonne à la meilleure (modulo symétrie) : PPP < PFP < PFF < PPF ?

Et avec le chat, la souris aurait donc intérêt à recycler aussi les échecs du chat, dans la mesure du possible ?

La stratégie optimale pourrait-elle être :_?

• Si le chat choisit PPF ou FFP, choisir l'autre ;
  
• Sinon, celle des deux qui commence à l'opposé de la (2 ou 3)^e lettre de chat.

(Désolé, flemme de faire des calculs / simulations, surtout vu mon niveau en probas niveau Markov…)

Faut-il quelqu'un pour demontrer l'equiprobabilité de l'espérance par voie matricielle egalement? ou est-ce de la deconne?

A chaud sans trop réfléchir :


Le chat a intérêt a choisir une combinaison AAB, car dès qu'il y aura AA il sera sûr de gagner au bout d'un moment dès qu'un B sortira.

S'il choisit ABA, par exemple, un tirage AB puis B le fait repartir de zéro.

S'il choisit AAA, par exemple, un tirage AA puis B le fait également repartir de zéro.

Donc la meilleure stratégie pour le chat serait AAB.

Pour la souris :

- Si le chat a choisit AAA, la souris doit choisir BAA pour gagner avant le chat (pas besoin de démonstration je crois...). là la souris gagne à tous les coups sauf si le tout premier tirage est AAA.

- Si le chat a choisi ABA, mettons nous dans la position où il va presque gagner, donc disons que le deux derniers tirages soient AB.

donc les six derniers tirages peuvent être :

AAAAAB
ABAAAB (impossible le chat aurait déjà gagné)
BAAAAB
BBAAAB
XXABAB (impossible le chat aurait déjà gagné)
AABAAB (impossible le chat aurait déjà gagné)
ABBAAB
BABAAB (impossible le chat aurait déjà gagné)
BBBAAB
AABBAB
ABBBAB
BABBAB
BBBBAB

Il me semble que les meilleures solutions sont AAB ou BBA...

- Si le chat choisit AAB alors...

... bah, je n'ai pas le temps de finir, je dois me sauver... mais je crois que c'est une bonne piste. A confirmer.

Je reviendrai pour la fin...

Phtos le titan,ton problème ma fait penser à ce problème ci peut être que cela pourra t'aider ou au moins te donner une piste .en tous cas je trouve que ça ressemble un peu à ton problème . voici l'article : http://fr.wikipedia.org/wiki/Probl%C3%A8me_de_Monty_Hall

Salut tout le monde,

On demande un spécialiste des probabilités ? Me voici ! (Je suis chercheur en probas ).

Alors, pour l'énigme :

• Le premier point, qui a déjà été évoqué plus haut dans ce fil, est que paradoxalement deux combinaisons ne sont pas équivalentes, quand bien même elles sortent une fois sur huit en moyenne. L'explication vient :
  
  1. D'une part de ce que certaines combinaisons ont tendance à tomber « par paquets » (par exemple, la combinaison “PPP” peut facilement tomber deux fois de suite [il suffit qu'il y ait quatre ‘P’ d'affilée], alors qu'une combinaison comme “PPF” ne le peut pas — après “PPF” vient forcément “PFP” ou “PFF” ; il faut attendre le troisième lancer après pour avoir une chance d'avoir à nouveau “PPF”). Or puisque l'objectif est de voir sa séquence apparaitre en premier, il vaut mieux (en règle générale) choisir une combinaison qui tombe régulièrement qu'une combinaison qui tombe par blocs.
     
  2. D'autre part, de ce que certaines combinaisons ont tendance à tomber “juste avant” d'autres. Par exemple, “FPP” a tendance à tomber juste avant “PPF”, puisque dès qu'apparait la séquence “FPPF” on a ce phénomène. Ainsi “PPF” ne peut gagner que s'il n'a pas été précédé de ‘F’, ce qui divise tout de suite par deux ses chances... ! (en négligeant la probabilité que “PPF” tombe dès le début). De même, il est intéressant de jouer “PFP” contre “FPP”, et... intéressant de jouer “PPF” contre “FPP” ! Il ne s'agit plus ici de forces “absolues”, mais d'un critère d'adaptation à la séquence proposée par l'autre.
     
  Notez que le point ‘1.’ ci-dessus aurait tendance à avantager le chat, qui peut ainsi se réserver la combinaisons la plus forte “dans l'absolu” (à ceci près que cette combinaison n'est forcément pas unique : si “PPF” est “fort dans l'absolu”, par exemple, il suffit d'inverser ‘P’ et ‘F’ pour voir que “FFP” est “fort dans l'absolu” aussi !), tandis que le point ‘2.’ a tendance à avantager la souris, qui peut adapter sa réponse au choix du chat.
  
• Une fois qu'on a dit ça, il faut établir un tableau de 8 lignes par 8 colonnes qui donne la probabilité de gain de chacune des combinaisons face à chacune des autres. Ce n'est pas facile à calculer, car il faut plus ou moins faire du “cas par cas” (et même pour un seul cas ce n'est pas simple ; on est plus ou moins obligé de connaitre les chaines de Markov pour s'en sortir). Heureusement il y a déjà des gens qui ont calculé des formules générales pour résoudre la question (encore que je présume que c'est de la triche d'utiliser ces résultats... ). J'ai une référence sur le sujet (un article de Delahaye dans la revue de vulgarisation Pour La Science), mais il faut que je remette le grappin dessus...
  
• Ensuite, chacun des deux joueurs a évidemment une stratégie optimale. Pour la souris, il s'agira de donner la meilleure réponse compte tenu du choix du chat ; quant au chat, il devra faire le meilleur choix possible sachant que la souris y donnera ensuite la réponse optimale (puisqu'elle est très intelligente).

Bref, je n'ai pas encore la réponse précise, mais voici au moins l'argument général de la solution... Cela dit, attention : le calcul du tableau des duels entre combinaisons n'est pas simple du tout et repose lui-même sur des arguments théoriques ! Mais une chose à la fois ; chi va piano va sano

Salut à tous,
Sol♯

Tous les tirages sont indépendants.
L'hypothèse d'indépendance est forte en proba. Ceci est le cas ici (a moins que la piece soit truquée).
Il ne faut pas confondre la proba de sortie d'une combinaison avec le nombre optimal de tirage. L'indépendance implique que toutes les combinaisons ont la même probabilite de sortie. Par contre l'espérance de gagner dépend des conditions du jeu.

Le chat choisit XXF. Si je suis souris, je choisis : XXP. Ce n'est qu'a ce moment la que je maximise l'utilisation de l'information a ma disposition.

Simplement, au départ, l'espérance de gain du chat est plus important : il peut choisir parmi 8 combinaisons alors que la souris n'a que 7 choix possibles. En faisant, le choix que je décris, la souris rétablit le fait d'avoir autant de chance que le chat (50%).

L'indépendance implique que toutes les combinaisons ont la même probabilite de sortie

Arf, mais non!
Les résultats d'un lancé de la pièce sont certes indépendants et équiprobables.
Mais les apparitions des différentes séquences après un lancer de pièce ne sont ni indépendantes ni équiprobables.

Il suffit de regarder:
On vient de tirer FFP, quelles sont les probabilités d'apparition des autres séquences au lancé suivant?
FFP: 1/2
FPF: 1/2
Les autres: 0

D'ou vient ton FFP ?
C'est une information d'une réalisation.
Il faut se situer au moment du pari..pas après. Les proba ne sont pas toujours intuitifs.
Et nous parlons d'espérance de gain ici, au moment du pari ? Oui ou non ?

Bon, je vais vous laisser...jouer
L'espérance et la proba sont deux notions différentes.
Il ne faut pas laisser influencer par un cas spécifique car le raisonnement sera erroné.

... Et voilà le résultat des calculs ! J'espère ne pas m'être trompé... Le « cas par cas » était horriblement long, alors j'ai paresseursement utilisé directement la formule de Conway, dont voici les références : Pour La Science no 409 (nov. 2011), « Les surprises du jeu de pile ou face », par J-P. Delahaye, pp. 146–151 (et plus précisément l'encadré ‘4.’ p. 151). Pour que ma solution soit complète, il faudrait donc y adjoindre une démonstration de la formule de Conway, ce que j'ai bien trop la flemme de faire...

J'ai présenté les résultats sous forme de tableau. L'intersection de la ligne “PPP” avec la colonne “PFP”, par exemple, signifie « probabilité que, si le chat a choisi “PPP”, la souris gagne en choisissant “PFP” » (ce sont des arrondis).


___ PPP PPF PFP PFF FPP FPF FFP FFF
PPP s/o 50% 60% 60% 88% 58% 67% 50%
PPF 50% s/o 33% 33% 80% 37% 50% 33%
PFP 40% 67% s/o 50% 50% 50% 63% 42%
PFF 40% 67% 50% s/o 50% 50% 20% 12%
FPP 12% 20% 50% 50% s/o 50% 67% 40%
FPF 42% 63% 50% 50% 50% s/o 67% 40%
FFP 33% 50% 37% 80% 33% 33% s/o 50%
FFF 50% 67% 58% 88% 60% 60% 50% s/o


J'ai mis en gras la meilleure réponse possible de la souris face à chaque choix du chat. On voit donc que si le chat choisit “PPP” ou “PPF”, la souris doit répondre par “FPP” ; s'il choisit “PFP” ou “PFF”, elle doit répondre par “PPF” ; s'il choisit “FPP” ou “FPF”, elle doit répondre par “FFP” ; et s'il choisit “FFP” ou “FFF”, elle doit répondre par “PFF”. En choisissant une telle stratégie, la souris est assurée de gagner dans au moins 67% des cas, quel que soit le choix du chat. Quant au chat, s'il veut éviter une défaite plus humiliante encore, il doit choisir “PFP”, “PFF”, “FPP” ou “FPF”.

Pour l'explication du calcul de ces probabilités, je vous renvoie à l'article de Delahaye cité ci-dessus (que je peux envoyer par MP à ceux qui le souhaitent). L'article ne démontre pas la formule de Conway, mais présente la méthode du graphe d'états et explique grossièrement comment utiliser cette méthode pour résoudre les problèmes au cas par cas.

Bon après-midi,
Sol♯

Soleil:

On ne s'est pas bien compris, j'aurais dû mieux te lire.

Je crois que tu parles de la probabilité d'apparition moyenne d'une combinaison lorsque l'on lance une pièce, sur un nombre infini de tirages.

Je parle de la probabilité d'apparition d'une combinaison lors d'une partie, qui s'arrête après un nombre fini de lancés, lorsque l'une des deux combinaisons tombe.

Sol#: Merci pour le tableau

Sol# a écrit:Pour l'explication du calcul de ces probabilités, je vous renvoie à l'article de Delahaye cité ci-dessus.

Ah ben tiens, je viens de m'apercevoir que l'article en question est disponible aun ze ouèbe...
http://www.lifl.fr/~delahaye/pls/213.pdf

Sol♯