Problème de Waldegrave

[Vassillia]

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]

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]

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]

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]

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]

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]

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 )

[GaBuZoMeu]

Ç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]

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]

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]

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]

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]

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

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.