[Proba] graphe, matrice de transition, etcsdc

[Olivier Miakinen]

Bonjour,

Je cherche à savoir comment résoudre certains problèmes de probabilité
dans lesquels 2 joueurs ou plus jouent jusqu'à ce que l'un d'entre eux
gagne. C'est un jeu où on part d'un état initial E0 et qui a un nombre fini
d'états possibles. À chaque coup, on passe d'un état à un autre avec une
certaine probabilité fixe ; par exemple, à partir de E1 on pourrait rester
en E1 avec probabilité 1/2, aller en E5 avec probabilité 1/3, ou revenir
en E0 avec probabilité 1/6. Certains états sont des états finaux, par
exemple F1 qui fait gagner le joueur 1, F2 qui fait gagner le joueur 2
et F3 qui fait gagner le joueur 3.

Je sais tracer le graphe des probabilités, et je sais aussi en faire une
matrice de transition. Mais ce que je ne sais pas, c'est :
− déterminer avec quelle probabilité ce sera le joueur n qui va gagner ;
− déterminer en combien de coups en moyenne il gagnera.

J'ai cherché (rapidement) des cours sur la toile, mais je ne suis pas
encore arrivé à quelque chose de concluant. Quelqu'un pourrait me donner
des pistes ?

Cordialement,

[efji]

Post by Olivier Miakinen
Bonjour,
Je cherche à savoir comment résoudre certains problèmes de probabilité
dans lesquels 2 joueurs ou plus jouent jusqu'à ce que l'un d'entre eux
gagne. C'est un jeu où on part d'un état initial E0 et qui a un nombre fini
d'états possibles. À chaque coup, on passe d'un état à un autre avec une
certaine probabilité fixe ; par exemple, à partir de E1 on pourrait rester
en E1 avec probabilité 1/2, aller en E5 avec probabilité 1/3, ou revenir
en E0 avec probabilité 1/6. Certains états sont des états finaux, par
exemple F1 qui fait gagner le joueur 1, F2 qui fait gagner le joueur 2
et F3 qui fait gagner le joueur 3.
Je sais tracer le graphe des probabilités, et je sais aussi en faire une
− déterminer avec quelle probabilité ce sera le joueur n qui va gagner ;
− déterminer en combien de coups en moyenne il gagnera.
J'ai cherché (rapidement) des cours sur la toile, mais je ne suis pas
encore arrivé à quelque chose de concluant. Quelqu'un pourrait me donner
des pistes ?
Cordialement,

Ca relève de la théorie des marches aléatoires. Ce n'est pas simple et
ça ne s'improvise pas. Je n'y connais rien, donc je ne peux pas aider.

ChatGPT propose ces ouvrages comme référence, mais je n'ai aucune idée
de sa fiabilité pour proposer des références :

1. "Random Walks and Electric Networks" – Peter G. Doyle et J. Laurie
Snell (1984)

Description : Cet ouvrage classique relie la théorie des marches
aléatoires à la théorie des réseaux électriques. Il offre une
introduction intuitive aux marches aléatoires et présente des techniques
comme l'utilisation de résistances électriques pour comprendre les
propriétés des marches.
Lien : Livre gratuit en ligne

2. "Random Walks on Graphs: A Survey" – László Lovász (1993)

Description : Bien que cet ouvrage soit un article plutôt qu'un
livre, il est un excellent point de départ pour les marches aléatoires
sur des graphes. Il aborde de nombreux concepts liés aux processus
stochastiques et aux applications informatiques des marches aléatoires.
Lien : Disponible en ligne avec une recherche simple.

3. "Random Walks on Infinite Graphs and Groups" – Wolfgang Woess (2000)

Description : Ce livre est une référence pour les marches
aléatoires sur des graphes infinis et des groupes. Il est idéal pour une
étude plus approfondie des marches aléatoires dans des contextes plus
avancés, incluant les groupes de Lie et la géométrie hyperbolique.
Public cible : Lecteurs ayant une certaine familiarité avec les
graphes et les groupes en mathématiques.

4. "Probability and Random Processes" – Geoffrey Grimmett et David
Stirzaker (2001)

Description : Ce livre est un texte de référence pour les
probabilités et les processus aléatoires. Il contient un chapitre dédié
aux marches aléatoires et couvre des bases importantes, tout en
proposant une introduction aux processus stochastiques.
Public cible : Étudiants de niveau avancé en mathématiques ou
ingénierie.

5. "Random Walks in Biology" – Howard C. Berg (1993)

Description : Ce livre aborde la théorie des marches aléatoires
dans le contexte de la biologie, en particulier la diffusion des
molécules et le mouvement des organismes. Il est idéal pour les lecteurs
intéressés par les applications biologiques.
Public cible : Chercheurs ou étudiants en biologie et physique.

6. "Spitzer's Principles of Random Walk" – Frank Spitzer (1976)

Description : Cet ouvrage est l'une des références classiques pour
la théorie des marches aléatoires. Il aborde la théorie en profondeur,
avec un focus sur les marches aléatoires en dimension infinie.
Public cible : Mathématiciens et physiciens intéressés par les
aspects théoriques avancés des marches aléatoires.

[Olivier Miakinen]

Bonjour efji,

Post by efji
Ca relève de la théorie des marches aléatoires.

Merci pour le mot-clé de recherche.

J'ai trouvé ça :
https://fr.wikipedia.org/wiki/Marche_al%C3%A9atoire#Marche_al%C3%A9atoire_sur_un_graphe
«
Dans l'algorithme de Wilson, on utilisera un type de marche aléatoire qui
s'appelle la "Marche aléatoire à boucles effacées" (Random erased loops walk) où
comme son nom l'indique, on retirera les cycles du chemin obtenu à la fin de la
marche.
»

... et en effet mon idée était de retirer des états l'un après l'autre en
remplaçant les transitions du type Ea -(p)-> Eb -(q)-> Ec par Ea -(pq)-> Ec
pour supprimer Eb.

Post by efji
[...]
ChatGPT propose ces ouvrages comme référence, mais je n'ai aucune idée

À vrai dire je n'ai pas tellement le courage de lire des docs en anglais,
et aussi j'espérais plutôt trouver des ressources en ligne. Mais merci
quoi qu'il en soit d'avoir fait cette recherche, je n'avais pas précisé
mon niveau de flemme. ;-)

[robby]

Post by efji
Ca relève de la théorie des marches aléatoires.

des chaînes de Markov, surtout !

[robby]

[ bon, ce provider de news perd mes messages aussi :-( ]

Post by Olivier Miakinen
Je sais tracer le graphe des probabilités, et je sais aussi en faire une
− déterminer avec quelle probabilité ce sera le joueur n qui va gagner ;

c'est pas donné par M^infinity * initialState ? ( qu'on calcule via les
valeurs propres )

Post by Olivier Miakinen
− déterminer en combien de coups en moyenne il gagnera.

[Olivier Miakinen]

Post by robby
[ bon, ce provider de news perd mes messages aussi :-( ]

:-(

Post by robby

Post by Olivier Miakinen
Je sais tracer le graphe des probabilités, et je sais aussi en faire une
− déterminer avec quelle probabilité ce sera le joueur n qui va gagner ;

c'est pas donné par M^infinity * initialState ? ( qu'on calcule via les
valeurs propres )

Ah, c'est une bonne idée, je vais essayer aussi. Je suis curieux de voir
si ça me donnera le même résultat que l'algorithme de suppression des
états intermédiaires.

Post by robby

Post by Olivier Miakinen
− déterminer en combien de coups en moyenne il gagnera.

Bon, ça c'est un autre problème, mais pour le moment je vais me concentrer
sur le premier.