Problème de Waldegrave

[Vassillia]

Bonjour à tous, je voulais vous proposer un extrait d'une lettre écrite par M.Montmort à M.Bernoulli en 1713


Je me demandais comment vous résoudriez le problème de nos jours si vous voulez bien vous y intéresser. Autant prendre directement 5 joueurs et traduire les questions par :
1. Calculer l’espérance de gain de chacun des 5 joueurs
2. Calculer les probabilités de gain de chacun des 5 joueurs
3. Calculer la durée moyenne de la poulle en nombre de parties

PS : je ne sais pas ce qu'est le tric-trac ou le piquet mais un pile ou face fera l'affaire.
L'ouvrage d'origine https://gallica.bnf.fr/ark:/12148/bpt6k110519q

[GaBuZoMeu]

Joli problème.

Pour la dernière question, on peut introduire les = expérance du nombre de parties restant à jouer avant la fin de la poule dans la situation où un joueur a gagné les dernières parties (et pas celle d'avant s'il y en a une), pour .
On a par exemple .

[Vassillia]

Merci de ton attention, parfaitement d'accord, du coup je finis le travail





Je ne détaille pas les calculs car il s'agit juste de résoudre un système linéaire
On trouve ; ; donc la durée moyenne vaut

Pour les premières questions, je ne te cache pas que la solution initiale de Bernoulli n'est pas évidente mais pour le moment je n'ai pas mieux à proposer. Ils étaient motivés à l'époque, ils ont échangés plusieurs lettres avant de s'en sortir et évidemment, ils n'avaient pas l'option simulation ordinateur.
Tu ferai comment toi si tu as le temps ?

[GaBuZoMeu]

Je ne suis pas d'accord avec ton .

[Vassillia]

Je ne comprends pas, avec 5 joueurs, si un joueur a gagné 4 parties de suite, ben c'est fini, non ?
Il vient de battre tous les adversaires.

Une manière équivalente de voir les choses différente de celle de Bernoulli mais avec laquelle je suis plus à l'aise, appelons les joueurs A,B,C,D et E :
A ou B ont la probabilité 1/8 de gagner à la fin des 4 premières parties
S'ils perdent contre C avec une probabilité 1/2 alors la durée moyenne se trouve prolongée de 1 partie
S'ils perdent contre D avec une probabilité 1/4 alors la durée moyenne se trouve prolongée de 2 parties
S'ils perdent contre E avec une probabilité 1/8 alors la durée moyenne se trouve prolongée de 3 parties

On trouve qui donne bien

[GaBuZoMeu]

Eh oui, suis-je bête ! 5 joueurs, ça fait 4 matchs consécutifs à gagner.

[Vassillia]

C'est surement parceque tu aimes les challenges, tu voulais faire encore plus de matchs
Tu peux utiliser cette envie sur les premières questions si le coeur t'en dit. Je pense que la résolution proposée par Bernoulli peut te plaire même si j'aimerai qu'on trouve mieux.

[GaBuZoMeu]

Pour la question 2) du problème originel (avec trois joueurs), j'ai bien envie de tenter un coup de chaîne de Markov absorbante. J'aurais 10 états dont 3 absorbants, et au bout du calcul je me rendrais compte qu'on doit pouvoir faire plus simple.

[GaBuZoMeu]

Je m'aperçois d'une petite ambiguïté.
Les joueur sont Alice, Bob, Charles, Djamila, Ernest
1er tour AB. A gagne, B sort. 2e tour AC. C gagne, A sort. 3e tour CD. D gagne, C sort. 4e tour DE. E gagne, D sort. Qui fait on rentrer ? A ou B ? Celui qui est sorti depuis le plus de temps, c'est B, non ?

[Vassillia]

Bonne question, d'après la démonstration que j'ai fini par comprendre, je peux en déduire que c'est B et plus généralement un joueur qui a perdu à la ième partie rentre à nouveau à la i+4ème partie.
Pas vraiment surprise que tu fasses apparaitre des chaines de Markov mais tu choisis quoi comme état ?

[Vassillia]

Je crois que j'ai compris ce que tu veux faire,
-1 état départ
-pour chaque couple de joueur tu subdivises en 2 états en fonction de qui gagne soit 6 états
-3 états absorbants en fonction de qui gagne 2 fois de suite
C'est ça ?
Effectivement, ça devrait le faire mais ça va devenir infernal dès qu'on va augmenter le nombre de joueurs

[GaBuZoMeu]

Je reviens sur le problème originel à trois personnes.
Deux branches :
12 initial - 13 - 32 - 21 - 13 etc.
12 initial - 23 - 31 - 12 - 23 etc
La probabilité que 3 gagne est donc .
Vérification : la probabilité que 1 gagne est
Dans le cas avec 5 personnes, la file d'attente des joueurs qui doivent rentrer me semble trop compliquée à gérer.

[lyceen95]

Pour le cas avec 5 personnes, il me semble qu'on trouve assez facilement une relation entre P(A) et P(E)
(A et E sont les 2 joueurs qui jouent le 1er duel, A est le gagnant de ce 1er duel, et E le perdant, P(A) et P(E) sont leurs probas de gagner).

J'ai fait les calculs dans la marge de mon papier... mais j'ai perdu mon papier.

Ensuite, je viens de me dire qu'on peut imaginer(c'est insuffisant, je sais, il serait bien de justifier) qu'on a une suite géométrique :
P(A)/P(B)=P(B)/P(C)=P(C)/P(D)=P(D)/P(E)
Et du coup, on a une équation du 4ème ou 5ème degré qui permet de conclure.

En nommant A le vainqueur du 1er duel, et E le perdant de ce duel, je pense que ça aide à bien modéliser le problème.

[Vassillia]

Je suis nettement plus enthousiaste déjà ! Pour 3 joueurs, on trouve donc et vous avez réussi à m’inspirer (enfin je crois même si cela gagnerait surement à être mieux rédigé)

Redémontrons le résultat de GaBuZoMeu :
Si 1 laisse sa place dans le 1er match pour jouer en dernier
- Il perd son avantage de jouer en premier qui va être donné au joueur 3 c'est à dire
- Lorsque 2 prend la place de 1 alors rien ne change pour lui donc
- Lorsque 3 prend la place de 2 alors il gagne donc

Mais alors pour individus, qu'est-ce qui se passe ?
Si 1 laisse sa place dans le 1er match pour jouer en dernier
- Il perd son avantage de jouer en premier qui va être réparti entre les joueurs 3,4 ... n c'est à dire
- Lorsque 2 prend la place de 1 alors rien ne change pour lui donc
- Lorsque 3 prend la place de 2 alors il gagne donc
- Lorsque 4 prend la place de 3 alors il gagne donc
...
- Lorsque n prend la place de n-1 alors il gagne donc

Si je ne me suis pas loupée, en tout cas c'est correct pour n=3, n=4 et n=5, on démontre donc que pour avec et

PS : Si vous êtes intéressés, je peux vous retranscrire la démonstration de Bernoulli pour n=5, elle vaut quand même le détour si vous n'êtes pas fâchés avec les systèmes d'équations ayant pas mal d'inconnues. En plus, elle a l'avantage d'être transposable assez facilement pour les espérances. C'est l'objectif suivant, on ne se décourage pas

[lyceen95]

Ce que j'avais griffonné sur mon papier ....
Après le 1er duel, A représente le vainqueur de ce 1er duel, B C D les 3 autres joueurs, dans l'ordre d'entrée en lice, et E, le perdant du 1er duel.
Cette position peut être symbolisée par A1BCDE : A a 1 victoire, et la file d'attente est composée de B,C,D,E dans cet ordre.
Après le 2ème duel, on peut avoir A2CDEB (proba=1/2) ou B1CDEA (proba=1/2)
Je ne détaille que la 1ère branche de l'arbre, tant que A gagne.
Après le 3ème duel, on peut avoir A3DEBC(proba =1/4) ou C1DEBA (proba=1/4)
Après le 4ème duel, on peut avoir A4EBCD(proba =1/8) ou D1EBCA (proba=1/8)
Mais la situation A4EBCD est en fait la situation A a 4 victoires, la partie est finie.

Les situations retenues sont donc :
Victoire de A, proba=1/8
D1EBCA : proba=1/8
C1DEBA : proba= 1/4
B1CDEA : proba= 1/2
Du pointde vue du joueur A, les 3 dernières situations sont strictement identiques. Il y a un adversaire qui a 1 victoire (contre A), et A est dernier dans la file d'attente.
Dans ces 3 configurations, A est exactement dans la situation de E au moment du début de la partie (après le duel A/E).
Donc P(A) = 1/8 + 7/8*P(E)

[Vassillia]

Oui d'accord mais attention car ici P(A) et P(E) ne désignent plus les probabilités de gagner pour les joueurs ayant joué ensemble dans le premier match ce qui sera la question finale.
P(A) et P(E) désigne les probabilités conditionnelles de gagner pour les joueurs ayant joué ensemble dans le premier match sachant le joueur qui a déjà gagné et sachant le joueur qui a déjà perdu.
Pour avoir suivi la démonstration de Bernoulli où il faut différencier les probabilités de gagner pour les joueurs et les probabilités en fonction de plusieurs conditionnements différents, on peut s'en sortir comme ça effectivement et je l'ai trouvé hyper intéressante mais il faut s'accrocher un peu quand même.
C'est pour ça que je ne vous la retranscrit que si vous avez envie de la lire.

[lyceen95]

Oui, on est bien d'accord, P(A) et P(E) ne nous intéressent pas directement ; ce qui nous intéresse, c'est la moyenne de ces 2 nombres.

J'ai finalement bâti la matrice de passage, on a 365 situations ( 120*3 situations du type A1BCDE, avec mes notations précédentes, et 5 situations A, B, C,D et E, pour symboliser les cas où la partie est finie).
La matrice 365x365 contient plein de 0, un peu de 1/2 et un peu de 1 sur les 5 dernières lignes.
J'ai calculé les puissances successives de cette matrice :
...
En fait, ça converge assez vite. est largement suffisant.
Partant de la position A1BCDE , on arrive à :
A : 26.6923%
B : 20.1939%
C : 19.0060%
D : 17.8880%
E : 16.2198%
Donc (A+E)/2 : 21.4560%
Et on constate effectivement le résultat que tu donnais (ratio 16/17 entre 2 valeurs consécutives)
On retrouve aussi le résultat : P(A) = (1+7*P(E)) /8

Rigoureusement, on pourrait ajouter une 366ème ligne et une 366ème colonne à notre matrice, celle codée A0EBCD ... c'est à dire celle avant le 1er duel, et obtiendrait directement le 21.4560%.

[Vassillia]

Tu as élevé au carré jusqu'à convergence une matrice carré de dimension 365
Je me doute que c'est informatisé mais quand même, je suis démotivée rien qu'à l'idée de le faire, tu gagnes indiscutablement la palme de la persévérance et merci pour ta vérification. J'aime bien les chaines de Markov mais pas à ce point là.
Reste à réfléchir à cette histoire d’espérance de gain pour les joueurs, comment s'en sortir sans trop de difficultés ?

[GaBuZoMeu]

En faisant mes longueurs de piscine, j'ai réalisé que ce problème de gestion des files d'attente est un faux problème. Il suffit en fait d'adopter le point de vue d'un seul joueur. En ce qui le concerne, il y a 3x5=15 états, plus deux états absorbants (je gagne, un autre gagne). Une matrice 17x17, c'est déjà plus raisonnable que 366x366
En plus, pas besoin d'itérer des puissances pour les chaînes de Markov absorbantes. Il suffira ici d'inverser une matrice 15x15. Bien sûr, il vaut mieux demander de l'aide à un esclave logiciel.

[lyceen95]

Prendre du recul est toujours une bonne source d'inspiration. Bien vu.

J'ai quand même continué à jouer avec mon programme, en modifiant un peu les règles du jeu.

Toujours 5 joueurs, mais dès qu'un joueur enchaine 3 victoires, il gagne. Du coup, le joueur censé entrer en dernier peut éventuellement perdre sans avoir l'occasion de jouer !
Résultats :
A et E : 22.89
B : 20.64
C : 18.81
D : 14.56

Et rebelote, toujours 5 joueurs, mais chacun doit enchainer 5 victoires pour gagner
A et E : 20.81
B : 20.08
C : 19.45
D : 18.85

Si je savais inverser une matrice, je serais un vrai matheux