Problème de Waldegrave

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
Vassillia

Re: Problème de Waldegrave

par Vassillia » 15 Aoû 2021, 01:20

C'est nettement plus raisonnable même si je ne comprends pas trop cette passion pour les chaines de Markov qui donnent des calculs pénibles à part l'envie d'exploiter des pauvres esclaves numériques. Pour vous convaincre de quitter le coté obscur de la force, je me motive à vous écrire la version de Bernoulli avec les joueurs ABCDE et je vous laisse en tirer quelque chose pour l’espérance si vous avez envie et si j'arrive à m'expliquer clairement

Soit proba joueur entrant de gagner le tournoi sachant que son adversaire a déjà gagné j parties
Le joueur E qui arrive en 5ème position a une proba de d'entrer contre D qui a gagné 1 partie ; une proba de d'entrer contre C qui a gagné 2 parties et une proba de d'entrer contre A ou B qui ont gagné 3 parties




Soit proba joueur sortant de gagner le tournoi sachant qu'il laisse son adversaire avec j parties gagnées
Si le joueur entre contre un adversaire qui a déjà gagné 3 parties, soit il gagne le tournoi (proba ), soit il va se faire virer tout de suite (proba ) et laisser son adversaire avec 4 parties gagnées, soit il va se faire virer au second tour (proba ), au troisième tour (proba ), au quatrième tour (proba ) et laisser son adversaire avec 1 partie gagnée





Si l'adversaire a 4 parties gagnées, c'est fichu pour le joueur qui sort
Si l'adversaire a 3 parties gagnées, lorsque le joueur sort, pour gagner le tournoi, il doit se passer 4 parties d'attente sans que le tournoi ne termine avant qu'il ne revienne. La seule condition possible est que l'adversaire perde la partie suivante (proba 1/2). Toute l'avance prise par l'adversaire est perdue dès la première partie d'attente. La configuration redevient équivalente au début où le joueur revient alors comme E.
Comme précédemment mais il y a une autre condition possible, l'adversaire peut perdre au bout de 2 parties (proba 1/2^2). Toute l'avance prise par l'adversaire est perdue à la deuxième partie d'attente. La configuration redevient équivalente au début où le joueur revient alors comme D


On résout le système de 13 équations (en rajoutant avec les 12 inconnues et ça passe. Le système s'arrange plutôt bien même si je ne détaille pas les calculs qui n'ont rien de passionnants.



lyceen95
Membre Irrationnel
Messages: 1377
Enregistré le: 15 Juin 2019, 01:42

Re: Problème de Waldegrave

par lyceen95 » 15 Aoû 2021, 08:57

On rejoint en fait ce que disait GBZM.
On ne s'intéresse en fait pas à l'identité des joueurs mais à leur position dans le processus. Si un joueur a gagné un duel, quelle est sa probabilité de gagner la partie ; si un joueur perd son duel, contre un joueur qui a donc duels gagnés, quelle est sa probabilité de gagner la partie.
GBZM envisageait (nécessairement) les autres situations : si un joueur est en ème position dans la file d'attente, alors qu'un autre joueur a victoires, quelle est sa probabilité de gagner la partie.
On a toutes ces variables, reliées entre elles par plein d'équations.

Vassillia

Re: Problème de Waldegrave

par Vassillia » 15 Aoû 2021, 12:25

Oui, j'avais compris, notons l'état où je vais participer à la ième partie à venir et un adversaire en est déjà à j victoires, notons l'état où j'en suis moi-même à k victoires
Les états proposés par GBZM sont donc avec les 2 états absorbants Gagné Perdu.
La démonstration de Bernoulli s'intéresse
- aux qui sont les probas de gagner à partir de l'état
- aux qui sont les probas de gagner à partir de l'état
- aux qui sont les probas de gagner à partir de l'état ou ou ou .
C'est un petit peu normal qu'on retombe sur les mêmes équations à la fin mais je trouve quand même les 2 démonstrations assez différentes.
Disons pour ne pas faire de jaloux que la matrice de GBZM est plus facile à écrire mais que le système de Bernoulli est plus facile à résoudre comme le travail est déjà commencé.
Mais tout cela ne nous donne pas (encore) une jolie démonstration pour le calcul de l'espérance de gain pour chacun des joueurs, je sais, je suis têtue

lyceen95
Membre Irrationnel
Messages: 1377
Enregistré le: 15 Juin 2019, 01:42

Re: Problème de Waldegrave

par lyceen95 » 16 Aoû 2021, 00:12

On a ces équations qui décrivent le modèle :
Code: Tout sélectionner
 2 A1=A2 +E1
2 A2=A3 +E1
2 A3=A4 +E1
2 E1=D1 +D2
2 E2=D1 +D3
2 E3=D1
2 D1=C1 +C2
2 D2=C1 +C3
2 D3=C1
2 C1=B1 +B2
2 C2=B1 +B3
2 C3=B1
2 B1=A1 +E2
2 B2=A1 +E3
2 B3=A1


Dans ces équations, A1 désigne la proba de gagner si on a gagné 1 duel , A2, la proba de gagner si on a gagné 2 duels ...
Bi : quelle est la proba de gagner si on est en train de jouer le duel contre le joueur A, et que ce joueur A a déjà gagné i duels.
Ci : Quelle est la proba de gagner si on est sur le siège C (prochain dans la file d'attente) et que A a déjà i duels gagnés.
etc etc
E3 est visiblement la pire des situations, A est sur le point de conclure, et en plus, on n'est pas près de rentrer en jeu.
J'ai laissé A4, mais A4=1

On peut éliminer les inconnues les unes après les autres ; d'abord les A3 B3 C3 D3 et E3 :
Code: Tout sélectionner
2 A1=A2 +E1
4 A2=A4 +3 E1
2 E1=D1 +D2
4 E2=2 D1 +C1
2 D1=C1 +C2
4 D2=2 C1 +B1
2 C1=B1 +B2
4 C2=2 B1 +A1
2 B1=A1 +E2
4 B2=2 A1 +D1


Puis on élimine A2 B2 C2 D2 et E2 :
Code: Tout sélectionner
8 A1=A4 +7 E1
8 E1=4 D1 +2 C1 +B1
8 D1=4 C1 +2 B1 +A1
8 C1=4 B1 +2 A1 +D1
8 B1=4 A1 +2 D1 +C1


Puis on élimine E1,


On élimine D1 :
Code: Tout sélectionner
121 A1= 16 A4 + 56 C1 + 28 B1
60 C1  = 34 B1 +17 A1
30 B1=  17 A1 + 8 C1


On élimine C1 :
Code: Tout sélectionner
1577 A1=240 A4 + 896 B1 
382 B1= 289 A1


On élimine B1 :
Code: Tout sélectionner
A1=45849/171735=0.266923


Et on remonte la chaine ...
Code: Tout sélectionner
B1=441592/2186759=0.20194
C1=(30 B1-17 A1)/8 = 0.1901
D1=(8B1-4A1-C1)/2=0.17889
E1=(4 D1 +2 C1 +B1)/8=0.16220


Et comme on veut (A1+E1)/2 ...
Code: Tout sélectionner
A0=0.21456


On retrouve bien le ratio 16/17 entre 2 termes consécutifs.

Vassillia

Re: Problème de Waldegrave

par Vassillia » 16 Aoû 2021, 00:34

Jolie résolution, je suis contente que le problème te plaise.
Je te propose un nouveau petit challenge pour promouvoir les chaines de Markov, essayer de calculer les probas pour n joueurs (ce qui permettrait de vérifier que je ne me suis pas loupée par la même occasion).

PS : tu viens de donner des valeurs exactes, tu es officiellement un vrai matheux maintenant même si je n'en ai jamais douté ;)

GaBuZoMeu
Habitué(e)
Messages: 4811
Enregistré le: 05 Mai 2019, 11:07

Re: Problème de Waldegrave

par GaBuZoMeu » 16 Aoû 2021, 19:55

Bonsoir,

Si tu utilises, Sage, je peux mettre ici le code qui fonctionne pour tout nombre de joueurs (enfin, ça répond pratiquement sans délai pour 10, par exemple, mais ça rame pour 100).
Pour les espérances de gain, j'ai un souci avec l'approche chaîne de Markov absorbante. Je ne sais pas obtenir l'espérance du nombre de parties de la poulle, sachant qu'un joueur donné gagne.

Vassillia

Re: Problème de Waldegrave

par Vassillia » 16 Aoû 2021, 23:47

Si tu as écrit un code, je pense que ce serait dommage de ne pas le mettre, je peux toujours me débrouiller avec un compilateur en ligne. Ce n'est pas parceque je préfère une formule générale facilement démontrable (qui a dit que j'étais exigeante :]) qu'il faut m'écouter, c'est très bien aussi les programmes informatiques.

Même si tu obtiens l’espérance du nombre de parties de la poulle sachant qu'un joueur donné gagne, cela ne répond pas directement la réponse. Je prends un cas basique à 4 joueurs sachant que A gagne au bout de 13 parties, les joueurs gagnants sont en majuscules.
1er hypothèse (Ab)(Ac)(aD)(Bd)(Cb)(Ac)(Ad)(aB)(bC)(cD)(Ad)(Ab)(Ac) => gain=14-3
2ème hypothèse (aB)(bC)(cD)(aD)(Bd)(Cb)(Ac)(aD)(Bd)(Cb)(Ac)(Ad)(Ab) => gain=14-4
J'imagine qu'on peut peut-être s'en sortir en distinguant les cas par la suite mais je suis trop fatiguée pour y réfléchir (la pré-rentrée a commencé, je vais avoir 15 jours assez intenses m'enfin ça fait plaisir de revoir les étudiants :D)

GaBuZoMeu
Habitué(e)
Messages: 4811
Enregistré le: 05 Mai 2019, 11:07

Re: Problème de Waldegrave

par GaBuZoMeu » 17 Aoû 2021, 11:53

Ça ne me donne pas directement l'espérance de gain, mais j'ai déjà l'autre information : l'espérance du nombre d'écus mis au pot par tel joueur pendant la partie.
Et en ramassant les reines-claudes, j'ai compris comment obtenir très facilement l'information qui me manquait, l'espérance du nombre de parties sachant que tel joueur a gagné.
Je vais pouvoir compléter mon code pour donner des réponses complètes. Mais là, tout de suite, je descends en ville au bazar acheter des joints pour fermer les bocaux de prunes. Les retraités n'ont pas à préparer la rentrée, immense avantage !

Vassillia

Re: Problème de Waldegrave

par Vassillia » 17 Aoû 2021, 13:29

Ah j'avoue que c'est une bonne raison, le plaisir de manger des reines-claudes directement sous le prunier mérite largement que tu fasses durer le suspens.

GaBuZoMeu
Habitué(e)
Messages: 4811
Enregistré le: 05 Mai 2019, 11:07

Re: Problème de Waldegrave

par GaBuZoMeu » 17 Aoû 2021, 19:11

Voici le code SageMath :
Code: Tout sélectionner
# Construction de la matrice de transition en fonction du nombre n de joueurs.
# Il y a n * (n-2) états codés par la position du joueur notée i (commençant à 0
# pour le sortant et terminant à n-1 pour le leader) et par le nombre de parties
# gagnées par le leader (c'est j+1 pour j de 0 à n-3), plus deux états absorbants :
# le joueur gagne, un autre gagne.

def MatriceTransition(n) :
    P=zero_matrix(QQ,n*(n-2)+2,n*(n-2)+2)
    # depuis un état où le joueur n'est pas entré dans le jeu
    for i in range(n-2) :
        for j in range(n-3) :
            P[j+(n-2)*i,j+1+(n-2)*(i+1)]=1/2 ; P[j+(n-2)*i,(n-2)*(i+1)]=1/2
        P[n-3+(n-2)*i,(n-2)*n+1]=1/2 ; P[n-3+(n-2)*i,(n-2)*(i+1)]=1/2
    # depuis un état entrant (i=n-2)
    for j in range(n-3) :
        P[j+(n-2)*(n-2),(n-2)*(n-1)]=1/2 ; P[j+(n-2)*(n-2),j+1]=1/2
    P[n-3+(n-2)*(n-2),(n-2)*n+1]=1/2 ; P[n-3+(n-2)*(n-2),(n-2)*(n-1)]=1/2
    # depuis un état de leader (i=n-1)
    for j in range(n-3) :
        P[j+(n-2)*(n-1),j+1+(n-2)*(n-1)]=1/2 ; P[j+(n-2)*(n-1),0]=1/2
    P[n-3+(n-2)*(n-1),n*(n-2)]=1/2 ; P[n-3+(n-2)*(n-1),0]=1/2
    # états absorbants
    P[(n-2)*n,(n-2)*n]=1 ; P[(n-2)*n+1,(n-2)*n+1]=1
    # sortie
    return P

Code: Tout sélectionner
def Poulle(n) :
    print("Poulle à {} joueurs".format(n))
    P=MatriceTransition(n)
    Q=P.submatrix(0,0,n*(n-2),n*(n-2))
    R=P.submatrix(0,n*(n-2),n*(n-2),2)
    I=identity_matrix(QQ,n*(n-2))
    # calcul de la matrice fondamentale
    N=(I-Q)^(-1)
    # espérance du nombre de parties de la poulle (y compris la partie initiale)
    nbpar=sum(N[0,i] for i in range(n*(n-2)))+1
    print("Espérance du nombre de parties de la poulle : {} parties".format(nbpar))
   
    # les états de départ (juste après la partie initiale)
    # correspondent aux lignes i*(n-2) pour i de 0 à n-1
    # i=0 pour le sortant de la partie initiale,
    # i=n-1 pour le gagnant de cette partie
   
    # probabilités de gagner
    B=N*R
    pg=[B[i*(n-2),0] for i in range(n)]
    prob=pg[1:n-1]+2*[(pg[0]+pg[n-1])/2]
    print("Probabilités de gagner pour chaque joueur (en commençant par le dernier) :\n"
          ,prob)
    print("soit environ",[round(p,3) for p in prob])
   
    # espérances de gain
    C=N*B
    # espérances du nombre d'écus mis au pot
    ec = [sum(N[i*(n-2),j+(n-2)*(n-2)] for j in range(n-2)) for i in range(n)]
    ec[0]+=1 ; ec[n-1]+=1
    ecot=ec[1:n-1]+2*[(ec[0]+ec[n-1])/2]
    print("Espérances du nombre d'écus mis au pot pour chaque joueur :\n",ecot)
    print("soit environ",[round(e,3) for e in ecot])
    # espérances du magot remporté en cas de victoire
    mag=[C[i*(n-2),0]/pg[i] + 2 for i in range(n)]
    magot=mag[1:n-1]+2*[(mag[0]+mag[n-1])/2]
    print("Espérances du magot récolté en cas de victoire ;\n", magot)
    print("soit environ",[round(m,3) for m in magot])
    # espérances de gain
    ga=[mag[i]*pg[i]-ec[i] for i in range(n)]
    gain=ga[1:n-1]+2*[(ga[0]+ga[n-1])/2]
    print("Espérances du gain :\n", gain)
    print("soit environ",[round(g,3) for g in gain])
   

GaBuZoMeu
Habitué(e)
Messages: 4811
Enregistré le: 05 Mai 2019, 11:07

Re: Problème de Waldegrave

par GaBuZoMeu » 17 Aoû 2021, 19:12

De petits exemples :

Code: Tout sélectionner
Poulle(3)

Poulle à 3 joueurs
Espérance du nombre de parties de la poulle : 3 parties
Probabilités de gagner pour chaque joueur (en commençant par le dernier) :
[2/7, 5/14, 5/14]
soit environ [0.286, 0.357, 0.357]
Espérances du nombre d'écus mis au pot pour chaque joueur :
[8/7, 10/7, 10/7]
soit environ [1.143, 1.429, 1.429]
Espérances du magot récolté en cas de victoire ;
[31/7, 31/7, 31/7]
soit environ [4.429, 4.429, 4.429]
Espérances du gain :
[6/49, -3/49, -3/49]
soit environ [0.122, -0.061, -0.061]


Code: Tout sélectionner
Poulle(5)

Poulle à 5 joueurs
Espérance du nombre de parties de la poulle : 15 parties
Probabilités de gagner pour chaque joueur (en commençant par le dernier) :
[2048/11449, 2176/11449, 2312/11449, 4913/22898, 4913/22898]
soit environ [0.179, 0.19, 0.202, 0.215, 0.215]
Espérances du nombre d'écus mis au pot pour chaque joueur :
[32768/11449, 34816/11449, 36992/11449, 39304/11449, 39304/11449]
soit environ [2.862, 3.041, 3.231, 3.433, 3.433]
Espérances du magot récolté en cas de victoire ;
[199655/11449, 3245298/194633, 3096461/194633, 21412149678/1353603821, 21412149678/1353603821]
soit environ [17.439, 16.674, 15.909, 15.819, 15.819]
Espérances du gain :
[33732608/131079601, 16789760/131079601, -2402712/131079601, -24059828/131079601, -24059828/131079601]
soit environ [0.257, 0.128, -0.018, -0.184, -0.184]

GaBuZoMeu
Habitué(e)
Messages: 4811
Enregistré le: 05 Mai 2019, 11:07

Re: Problème de Waldegrave

par GaBuZoMeu » 17 Aoû 2021, 19:14

Et un plus gros :

Code: Tout sélectionner
Poulle(10)

Poulle à 10 joueurs
Espérance du nombre de parties de la poulle : 511 parties
Probabilités de gagner pour chaque joueur (en commençant par le dernier) :
[2361183241434822606848/23815758613997334565121, 2365794927453249994752/23815758613997334565121, 2370415620670932123648/23815758613997334565121, 2375045338680055037952/23815758613997334565121, 2379684099107164520448/23815758613997334565121, 2384331919613233201152/23815758613997334565121, 2388988817893727797248/23815758613997334565121, 2393654811678676484352/23815758613997334565121, 4796659837465472798721/47631517227994669130242, 4796659837465472798721/47631517227994669130242]
soit environ [0.099, 0.099, 0.1, 0.1, 0.1, 0.1, 0.1, 0.101, 0.101, 0.101]
Espérances du nombre d'écus mis au pot pour chaque joueur :
[1208925819614629174706176/23815758613997334565121, 1211287002856063997313024/23815758613997334565121, 1213652797783517247307776/23815758613997334565121, 1216023213404188179431424/23815758613997334565121, 1218398258742868234469376/23815758613997334565121, 1220777942841975398989824/23815758613997334565121, 1223162274761588632190976/23815758613997334565121, 1225551263579482359988224/23815758613997334565121, 1227944918391161036472576/23815758613997334565121, 1227944918391161036472576/23815758613997334565121]
soit environ [50.762, 50.861, 50.96, 51.06, 51.159, 51.259, 51.359, 51.46, 51.56, 51.56]
Espérances du magot récolté en cas de victoire ;
[12296958890966939706612160/23815758613997334565121, 699592974302731712541246344/1357498240997848070211897, 698259291820347861805599568/1357498240997848070211897, 232308536445988003689984264/452499413665949356737299, 695591926855580160334306016/1357498240997848070211897, 694258244373196309598659240/1357498240997848070211897, 230974853963604152954337488/452499413665949356737299, 691590879408428608127365688/1357498240997848070211897, 272089334135533158011137664606806685706778157638566481651511979273/534945636505321335102052215533608318320641459281683149454546430, 272089334135533158011137664606806685706778157638566481651511979273/534945636505321335102052215533608318320641459281683149454546430]
soit environ [516.337, 515.355, 514.372, 513.39, 512.407, 511.425, 510.442, 509.46, 508.63, 508.63]
Espérances du gain :
[243887751793187426704427305365348539783184384/567190358360188242288640806509131094189744641, 189009371345128276331250172348126121038970880/567190358360188242288640806509131094189744641, 133915691865504010001160663646108318439571456/567190358360188242288640806509131094189744641, 78606081686880413619655357111284064592068608/567190358360188242288640806509131094189744641, 23079907495672985196582581572571466383228928/567190358360188242288640806509131094189744641, -32663465671873719681869093263888755210584064/567190358360188242288640806509131094189744641, -88624674433716168497930368539855918936883200/567190358360188242288640806509131094189744641, -144804357066051380046947442448594866441947136/567190358360188242288640806509131094189744641, -201203153507365921813164587895549484823804928/567190358360188242288640806509131094189744641, -201203153507365921813164587895549484823804928/567190358360188242288640806509131094189744641]
soit environ [0.43, 0.333, 0.236, 0.139, 0.041, -0.058, -0.156, -0.255, -0.355, -0.355]

Vassillia

Re: Problème de Waldegrave

par Vassillia » 17 Aoû 2021, 22:15

Je me suis remise aux chaines de Markov pour l'occasion (merci pour les commentaires dans le code sinon j'y serai encore) et quand même le coup du c'est très joli je trouve :D

J'ai un peu regardé tes valeurs pour et sur les probabilités de gain par joueur, on a bien
pour avec et
Mais surtout il semble que la relation de récurrence sur les espérances de gain par joueur soit la suivante :
pour avec et

Pourquoi ? Alors là mystère, il y a surement une démonstration sympa mais à ce stade je ne vois pas, je suis déjà bien contente d'avoir une relation.

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 10 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite