Parties avec matchs nuls
Bonjour
Je sèche sur le problème suivant;
A et B se confrontent dans un jeu, la probabilité que A gagne une partie est a, que B gagne une manche est b et qu'ils fassent manche nulle est n. Est déclaré gagnant celui qui gagne 2 manches consécutives pour la première fois.
Calculer la probabilité que A gagne la partie?
Je sèche sur le problème suivant;
A et B se confrontent dans un jeu, la probabilité que A gagne une partie est a, que B gagne une manche est b et qu'ils fassent manche nulle est n. Est déclaré gagnant celui qui gagne 2 manches consécutives pour la première fois.
Calculer la probabilité que A gagne la partie?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Dans a mondes, A gagne la première partie, puis dans a de ces a mondes A gagne la deuxième partie et remporte le bigmatch, alors que dans (1-a) des a mondes, A perd la deuxième partie et c'est un retour au départ, ie dans p de ces derniers mondes A gagne le bigmatch. Dans 1-a mondes, A ne gagne pas la première partie, puis dans p de ces (1-a) mondes, A remporte le bigmatch.
La proportion (qui est p) des mondes où A gagne vérifie donc $p=(1-a)p + a(1-a)p +a^2$
Je te laisse de débrouiller avec ça (j'ai (charte) hésité à te mettre l'équation). Tu as tout un tas d'hypothèses à préciser (et à faire surtout :-D )
Mais je trouve bizarre que cette probabilité ne dépend pas explicitement du fait qu'il peut y avoir des manches nulles, c'est comme c- cette éventualité n'existe pas. Est-ce normal?
En fait, il n'y a retour au départ que lorsqu'il y a une partie nulle. Sinon, a ou b possède un avantage puisqu'il vient de gagner une partie.
Soit $\alpha_k$ la probabilité que personne ne gagne en $k$ manches et que $A$ remporte la dernière manche.
Soit $\beta_k$ la probabilité que personne ne gagne en $k$ manches et que $B$ remporte la dernière manche.
Soit $\gamma_k$ la probabilité que personne ne gagne en $k$ manches et que la dernière manche soit nulle.
Alors : $\alpha _{k}=a(\beta _{k-1}+\gamma _{k-1}),\beta _{k}=b(\alpha _{k-1}+\gamma _{k-1}),\gamma _{k}=c(\alpha _{k-1}+\beta _{k-1}+\gamma _{k-1})$.
La probabilité que $A$ gagne la partie en $k$ manches exactement est : $a\alpha _{k-1}$.
La probabilité que $B$ gagne la partie en $k$ manches exactement est : $b\beta _{k-1}$.
La probabilité que $A$ gagne la partie est : $ \displaystyle p_{A}=\underset{k=2}{\overset{+\infty }{\sum }}a\alpha _{k-1}$.
La probabilité que $B$ gagne la partie est : $ \displaystyle p_{B}=\underset{k=2}{\overset{+\infty }{\sum }}b\beta _{k-1}$.
Peut-être est-ce aussi faux que cette étrange histoire de mondes (parallèles ?) qui nous a été contée par christophe c, mais si c'est juste il reste à finaliser.
Bonne nuit.
F. Ch.
Là, dodo.
F. Ch.
[small]Ne forçons point notre talent,
Nous ne ferions rien avec grâce[/small]
Il vaut mieux considérer une petite chaîne de Markov à 5 états: on a alors le système $p_0=(1-(a+b))p_0+ap_1+bp_{-1}$, $p_1=bp_{-1}+a+(1-(a+b))p_0$, $p_{-1}=ap_1+(1-(a+b))p_0$, où $p_0$ est la probabilité que $A$ gagne, $p_1$ la probabilité de gagner sachant qu'il a engrangé une première victoire, $p_{-1}$ la probabilité de gagner sachant qu'il a essuyé une première défaite.
J'aimerais savoir si c'est correct : avec les chaînes de Markov, trouve-t-on les mêmes résultats pour les probabilités de mon précédent message, et pour cette espérance ?
Bonne journée.
F. Ch.
La première coordonnée de $R$ est la probabilité de gain de $A$, la première coordonnée de $T$ est le temps moyen du jeu.
Pour Feller, j'ai l'édition de 1968, sans doute est-ce le cas d'alea, alors ce serait sympa d'indiquer le chapitre et le paragraphe. Merci.
Moi j'ai calculé l'espérance en supposant qu'elle existe. C'est cette existence qui me semble le point délicat, il y a sans doute dans la théorie des chaînes de Markov des théorèmes qui la prouvent mais je ne les connais pas. Je pense pouvoir le faire avec une norme matricielle, et de même pour la variance (et tous les autres moments). . Et dès que j'en aurai le temps je calculerai aussi cette variance, à moins que "Sage" ne l'ait fait avant.
Maintenant mazza, le questionneur initial, pourrait nous dire ce qu'il pense de nos diverses réponses.
Bonne soirée.
F. Ch.
Celle de Chaurien est plus dans l'esprit du programme. Mais j'avoue qu'en écrivant sous forme matricielle $X_k=M X_{k-1}$ où $X_k=[\alpha_k,\beta_k,\gamma_k]^t$ je ne suis pas arrivé à trouver l'expression trouvée par lui. Les calculs des valeurs propres et/ou de $M^n$ me semblent très pénibles. Est-ce le cas? Je ne sais comment as-tu trouvé l'expression de $p$? Peux-tu me l'indiquer?
@Chaurien: en réalité, l'existence de l'espérance est bien plus facile que tout ce que tu as fait, puisqu'on a $P(T>2n)\le (1-a^2-b^2)^n$
Sauf erreur, le vecteur de la fonction génératrice des temps d'atteinte vérifie $\phi(x)=xA\phi(x)+B\begin{pmatrix} 1\\1\end{pmatrix}$, d'où
$\phi(x)=(1-Ax)^{-1}B\begin{pmatrix} 1\\1\end{pmatrix}$ où $A$ et $B$ sont les matrices qui apparaissent dans mon message précédent. Là encore, c'est la première coordonnée qui t'intéresse. Comme tu le sais, on en déduit les moments.
Je mettrai Sage sur le coup à l'occasion si personne ne l'a fait avant.
Du programme ? Quel programme ? Il serait bon que les questionneurs précisent ce point. Pour ne parler que des interventions sérieuses, la solution d'aléa convient pour les secteurs d'enseignement où l'on étudie les chaînes de Markov, sans doute à l'Université en M1 ? Comme j'ai dit je ne suis pas familier de cette théorie, alors j'ai trouvé une solution qui s'en passe, et qui convient pour Math. Spé, MP, PC ou PSI. Je présume que c'est ton cas.
J'ai été bien content de trouver les trois relations de récurrence linéaire qui me semblent la clé du problème, mais j'ai été moi aussi bien déçu par la matrice $M$ dont les valeurs propres ne sont pas évidentes, même à localiser. Il y en a une, et une seule, réelle entre $c$ et $1$, mais je ne suis pas certain que les deux autres soient réelles dans tous les cas ni même qu'elles soient distinctes. Elles sont de modules strictement inférieurs à 1. Moi je n'ai pas l'esprit aussi délié que certains camarades de ce forum aussi cela m'a pris pas mal de temps.
Pour trouver malgré tout les probabilités demandées, j'ai passé outre et j'ai posé : $ \displaystyle \alpha =\underset{k=1}{\overset{+\infty }{\sum }}\alpha _{k},\beta =\underset{k=1}{\overset{+\infty }{\sum }}\beta _{k},\gamma =\underset{k=1}{\overset{+\infty }{\sum }}\gamma _{k}$, et les trois relations de récurrence linéaire m'ont fourni trois équations linéaires aux inconnues $\alpha, \beta, \gamma $, que j'ai résolues avec les formules de Cramer. Pour l'espérance de durée de la partie j'ai utilisé l'antirépartition. Avec de la persévérance, on peut même trouver la variance, je n'ai pas encore eu le temps.
J'espère que cela répond à tes questions, au moins en partie. Tiens-nous au courant et n'hésite pas à questionner à nouveau si besoin est. .
Bon courage.
F. Ch.
Avec ses notations, il est clair que la série $(\sum a\alpha _{k-1})$ converge puisque les événements "A gagne la partie en $k$ manches exactement" sont incompatibles deux à deux.
C'est la même chose pour $(\sum b\beta _{k-1})$ et donc aussi pour $(\sum \gamma _{k-1})$ puisque $a\gamma _{k-1}=\alpha_k-a\beta _{k-1}$.
L'existence de l'espérance de $X$ en est une conséquence puisque $P(X>k)=\alpha _k+\beta _k+\gamma _k$ est le terme général d'une série convergente.
Ce que je trouve remarquable dans cet exercice c'est que les résultats, probabilité que A (ou gagne la partie, espérance de la durée $X$, ne dépendent pas de la valeur de $c$, probabilité qu'une manche soit nulle.
Est-ce qu'on pouvait le prévoir sans faire les calculs ?
Ou alors je n'ai pas compris ce que tu veux dire.
En fait j'avais remarqué que la somme des probabilités que A et B gagnent la partie est égale à 1 et cela ne dépend pas de la valeur de c.
De même, si a=b la probabilité que A gagne la partie est égale à 1/2 indépendemment de la valeur de c.
Mais dans le cas général cela dépend de c.
je parle des programmes en vigueur en maths spé (MP, PSI ou PC). Les chaine de Markov n en font partie explicitement.
Le fait que la somme des proba de gain de A et B soit 1 ce que signifie que pas de nul et l'un des deux finit par gagner et le resultat, d'apres le prof, du lemme de Borel-Cantelli.
Je n'ai pas bien compris $\phi(x)=xA\phi(x)+B\begin{pmatrix} 1\\1\end{pmatrix}$, ce doit être en rapport avec la théorie des chaînes de Markov, mais bon, tant pis.
@ jandri
Très heureux de notre accord, et de voir que je ne suis pas le seul à ne pas maîtriser les chaînes de Markov. Dommage pour nous, faudra qu'on s'y mette.
...........................................................................................................................
jandri utilise l'antirépartition $P(X>k)$ pour calculer l’espérance, c'est ainsi que j'ai procédé. Cette antirépartition a aussi une relation avec la variance. On a le théorème suivant, peu souvent évoqué :
« Une variable aléatoire $X$ ayant ses valeurs dans $\mathbb{N}$ admet un moment d'ordre 2 si et seulement si la série de terme général $nP(X>n)$ est convergente, et alors : $\displaystyle E(\frac{X(X-1)}{2})=\overset{+\infty }{\underset{n=1}{\sum }}nP(X>n)$ .»
On peut calculer ainsi la variance dans le cas présent, j'ai commencé, c'est faisable mais trop long pour ma patience. À moins que Sage ne s'en charge, ou bien qu'un théorème markovien ne nous donne rapidement la réponse...
mazza est-il satisfait de nos réponses ?
Bonne journée de froidure. Le réchauffement climatique est de sortie.
F. Ch.
C'est sympa mais ne te force pas, c'est à nous d'apprendre les chaînes de Markov, et tu dois avoir bien d'autres choses à faire. Par contre, tu pourrais rédiger un traité de ce sujet, je l'achèterais volontiers.
Bon dimanche.
F. Ch.
Bonne soirée.
F. Ch.
Je reviens sur ce problème qui comporte pour moi encore quelques zones d'ombre. Je souhaite l'aborder à la suite de mes messages précédents, sans recours à la théorie des chaînes de Markov, non par mépris pour cette belle théorie, mais parce que je souhaite demeurer dans le cadre Math-Spé, les lecteurs de ce forum comprendront pourquoi ;-).
Je reprends les notations de mes messages précédnts. Nous avons vu que $X_k=MX_{k-1}$, où : $X_k=\begin{pmatrix} \alpha_k \\ \beta_k \\ \gamma_k \end{pmatrix}$ et $M=\begin{pmatrix} 0 & a & a \\ b & 0 & b \\ c & c & c \end{pmatrix}$.
Avec : $a>0,b>0, c> 0, a+b+c=1$, et : $ \alpha_0=0, \beta_0=0, \gamma_0=1$.
Le polynôme caractéristique de $M$ est sauf erreur : $\Phi(x)=x^{3}-cx^{2}-(ab+bc+ca)x-abc$
Hélas, comme dit mazza, les valeurs propres sont récalcitrantes. Il y en a une dans $]\frac{c}{3},1[$ et les deux autres, si elles sont réelles, sont dans $]-1,0[$. Mais voilà, sont-elles réelles ? Assurément si $c< \frac{1}{3} $, mais sinon ? Mystère... Et sont-elles distinctes ? Je ne sais pas non plus.
Si l'on ne demande que la probabilité de gain de chacun des joueurs, on peut se passer de ces valeurs propres. Mon calcul de somme de série répond à la question, la convergence de ces séries étant assurée par le bel argument probabiliste de jandri. Ces calculs de sommes se font par résolution d'un système d'équations linéaires avec les formules de Cramer, laborieusement.
Reste la question de la durée du jeu. Ce sera pour un prochain message, celui-ci étant assez long.
Bonne soirée.
F. Ch.
14/04/2016
Grosse déception hier nuit, je croyais avoir trouvé un argument pour localiser les valeurs propres de la matrice $M$ mais c'était une erreur.
Venons-en à la durée de la partie. Il faut d'abord observer que celle-ci s'arrête quasi-certainement. La probabilité que la partie ne s'arrête pas au bout de $k$ manches est : $\alpha _{k}+ \beta _{k}+\gamma _{k}$, qui tend vers $0$ quand $k\rightarrow +\infty $. Ceci donne la preuve attendue.
On peut alors, avec aléa, désigner par $T$ la durée de la partie, et l'on a l'antirépartition : $P(T>k)=\alpha _{k}+\beta _{k}+\gamma _{k}$. Cette série converge, l'espérance existe donc, et c'est la somme de cette série. C'est ainsi que j'avais trouvé la valeur $E(T)=\frac{(a+1)(b+1)}{a^{2}(b+1)+b^{2}(a+1)}$ donnée dans un de mes messages ci-dessus, il y a deux mois, et confirmée par aléa.
La majoration donnée par aléa : $P(T>2k)\le (1-a^2-b^2)^k$ implique en fait l'existence de moments de tous ordres, mais je ne trouve pas cette majoration si "facile". Mon idée pour la prouver consiste à partir de : $X_{k+2}=M^{2}X_{k}$. C'est un calcul laborieux (encore !).
En fait, on utilise ici la norme matricielle subordonnée à la norme définie, pour $X=\begin{pmatrix} x \\ y \\ z \end{pmatrix}$$\in \mathbb{R}^3$ (resp. $ \mathbb{C}^3$), par : $\left\| X\right\| _{1}=\left| x\right| +\left| y\right| +\left| z\right| $. Cette norme matricielle subordonnée est le maximum des sommes des valeurs absolues (resp des modules) des coefficients par colonnes. C'est pourquoi il faut passer à la matrice $M^2$ car malheureusement la norme de la matrice $M$ est $a+b+c=1$, ce qui ne permet rien. Et la norme de $M^2$ est justement $1-a^2-b^2$, chic !
Et ceci règle la question de la localisation des valeurs propres de la matrice $M$, qui sont donc de valeurs absolues (resp. modules) $<1$.
Mais j'avoue que je serais curieux de savoir si le polynôme caractéristique a forcément ses trois racines réelles, s'il peut avoir une racine double réelle, ou non, et à quelles condition. Et calculer la variance, peut-être avec la formule que j'ai signalée plus haut : $\displaystyle E(\frac{X(X-1)}{2})=\overset{+\infty }{\underset{n=1}{\sum }}nP(X>n)$. Les usagers des logiciels de calcul formel pourraient peut-être répondre à ces questions.
Bonne journée.
F. Ch.
15/04/2016
$-(a-b)^2c^2(c^2+4(a+b)c+12ab)-4(ab)^2(c^2+3c(a+b)+ab)$ qui est toujours strictement négatif.
Il y a donc toujours trois valeurs propres réelles distinctes.
correction: j'avais inversé le signe!
F. Ch.
Le polynôme caractéristique est : $\Phi(x)=x^{3}-cx^{2}-(ab+bc+ca)x-abc$.
J'ai fait l'étude classique de fonction pour cette fonction $\Phi$. C'est ce qui m'a fait affirmer qu'il y a une seule racine positive, qui est dans $]\frac{c}{3},1[$.
Soit $\delta$ la racine négative de la dérivée $\Phi ^{\prime }$, qui est dans $]-1,0[$.
La fonction $\Phi$ est strictement croissante sur $[-1, \delta]$ et strictement décroissante sur $[ \delta,0]$.
On constate que $\Phi(0)<0$ et $\Phi(-1)<0$. Il faut donc trouver une valeur de la variable $x \in ]-1,0[$ qui rende $\Phi(x)$ positif. J'y avais pensé mais j'avais eu la flemme, et l'intervention de jandri n'a redonné courage.
On a : $\Phi (-a)=a^{2}(b-a)$, $\Phi (-b)=b^{2}(a-b)$, donc si $a\neq b$ c'est gagné. Si $a=b$ alors $-a$ est racine, et il n'est pas difficile de terminer.
C'est dur les math mais c'est sympa.
Au fait : quelqu'un connaîtrait-il un logiciel permettant d'éditer de jolis tableaux de variation ?
Bon appétit.
F. Ch.
La racine positive est même supérieure à $c$ puisque $\Phi(c)<0$.
D'ailleurs pour montrer que $\Phi$ possède trois racines réelles distinctes on utilise seulement le fait que $a,b,c$ sont strictement positifs.
Je me suis lancé à la main dans le calcul de $V(X)$.
Avec les notations de Chaurien je pose $A(x)=\displaystyle\sum_{k=1}^{+\infty } \alpha _{k}x^k$ et de même $B(x)$ et $C(x)$.
Les relations de récurrence linéaire donnent le système: $A(x)=ax(B(x)+C(x)+1)$, $B(x)=bx(A(x)+C(x)+1)$, $C(x)=cx(A(x)+B(x)+C(x)+1)$.
On en déduit $\dfrac{C(x)}{cx}=\dfrac1{\dfrac1{ax+1}+\dfrac1{bx+1}-cx-1}$ que je note $g(x)$.
Ensuite $\displaystyle E\left(\frac{X(X-1)}{2}\right)=\sum_{n>0}nP(X>n)=\sum_{n>0}\frac nc \gamma_{n+1}=g'(1)=\dfrac{a(b+1)^2+b(a+1)^2+c(a+1)^2(b+1)^2}{(1-c-ab-ac-bc-abc)^2}$.
On en déduit $V(X)=\dfrac{c(a+1)^2(b+1)^2+a(1-a)(b+1)^2+b(1-b)(a+1)^2}{(a^2(b+1)+b^2(a+1))^2}$.
Je n'ai pas trouvé d'expression plus simple.
$\{T>2k\}\subset\cap_{i=1}^k\{ (X_{2i-1},X_{2i})\not\in\{(A,A);(B,B)\}\}$.
où $X_i$ désigne le gagnant du $i$-ème lancer.
ZUT alors ! Dans le message que j'ai effacé, je disais justement que la racine positive $\lambda_1$ est $ >c$, au motif que $\Phi(c)<0$. Et puis je ne sais pourquoi, je me suis emmêlé les pinceaux et j'ai cru que ce n'était pas correct.
J'en tirais la conséquence suivante. Si les deux autres racines sont $\lambda_2$ et $\lambda_3$ alors : $abc=\left| \lambda _{1}\lambda _{2}\lambda _{3}\right| =\lambda _{1}\left| \lambda _{2}\lambda _{3}\right| >c\left| \lambda _{2}\lambda _{3}\right| $, et par suite : $\left| \lambda _{2}\lambda _{3}\right| <ab<1$. J'en déduisais que si $\lambda_2$ et $\lambda_3$ ne sont pas réelles, elles sont complexes conjuguées, et donc de module $<1$.
Je le mentionne pour mémoire puisque nous savons désormais que nos trois valeurs propres sont réelles, et dans $]-1,1[$. Le rayon spectral de la matrice$M$ est donc $\rho \in ]0,1[$, et ceci suffit à prouver que la variable aléatoire $T$ admet des moments de tous ordres, sans utiliser la norme matricielle que j'ai évoquée précédemment.
Et bravo à jandri pour son calcul de la variance. Si je pose ce problème en colle, je n'irai sans doute pas jusque là.
Bonne soirée.
F. Ch.
C'est un peu bizarre que certains d'entre vous se réjouissent de ne pas avoir utilisé la "théorie des chaînes de Markov" alors que pour justifier la phrase suivante... il faut utiliser la propriété de Markov (faible) :
Ce n'est pas un résultat hyper dur non plus, mais il faut pouvoir manipuler des suites infinies de v.a. On peut aussi admettre cette équation comme modélisation après tout, je pense que c'est la démarche que vous avez faite.
La théorie des chaînes de Markov commence à devenir vraiment profonde avec :
* la propriété de Markov forte
* les théorèmes de convergence