Problème ECG1 maths appliquées : deux jetons, deux cases et une chaîne de Markov

↩ Chapitre : Graphes et chaînes de Markov · Matrices (ECG1-ECG2)

Introduction

Deux jetons sont posés dans deux cases. À chaque étape, on tire au hasard une lettre parmi a, b, c : la lettre a fait changer de case le jeton A, la lettre b le jeton B, et la lettre c ne change rien. Où sont les jetons au bout de n étapes ?

Ce problème de première année est une introduction aux chaînes de Markov : on traduit l’évolution des lois par une relation matricielle V_{n+1}=QV_n, on calcule des puissances de matrices, puis on utilise la linéarité de l’espérance. Une simulation Python vient confirmer les résultats.

Le sujet

Problème d’après un concours blanc d’ECE1, adapté au programme ECG 2021. Durée indicative : 2 h 30. Programme : probabilités, formule des probabilités totales, calcul matriciel, espérance, Python.

Option : maths appliquées (le problème est aussi accessible en maths approfondies). Niveau : ★★. Faisable : au second semestre, après les variables aléatoires discrètes ; les parties II et III dès que le calcul matriciel et les variables finies sont vus.

Énoncé et corrigé

On dispose de deux jetons A et B, que l’on peut placer dans deux cases C_0 et C_1, et d’un dispositif qui tire au hasard, de manière équiprobable, l’une des lettres a, b ou c. Au départ, les deux jetons sont dans C_0. On procède à une suite de tirages indépendants. Après chaque tirage :

  • si la lettre a est tirée, on change le jeton A de case ;
  • si la lettre b est tirée, on change le jeton B de case ;
  • si la lettre c est tirée, on ne change rien.

On pose X_0=Y_0=0 et, pour n\geqslant1 : X_n=0 si, à l’issue de la n-ième opération, le jeton A est dans C_0, et X_n=1 s’il est dans C_1. On définit de même Y_n pour le jeton B.

Partie I – Le mouvement du jeton A

1 ▷ (a) Soit n\geqslant1. Quelle est la probabilité qu’à l’issue de la n-ième opération, le jeton A n’ait jamais quitté C_0 ?

Indication

Le jeton A ne bouge que si la lettre a est tirée.

Corrigé

Notons L_k l’événement « la lettre a est tirée au k-ième tirage », de probabilité \frac13. Le jeton A n’a jamais quitté C_0 après n opérations si et seulement si la lettre a n’a été tirée à aucun des n premiers tirages. Par indépendance, cette probabilité vaut \left(\dfrac23\right)^n.

(b) Quelle est la probabilité que le jeton A reste indéfiniment dans C_0 ?

Indication

Écrire l’événement comme l’intersection d’une suite décroissante d’événements et utiliser le théorème de la limite monotone.

Corrigé

Notons R_n l’événement « A n’a pas quitté C_0 à l’issue de la n-ième opération ». La suite (R_n) est décroissante et l’événement « A reste indéfiniment dans C_0 » est \displaystyle\bigcap_{n\geqslant1}R_n.

Par le théorème de la limite monotone, sa probabilité vaut \displaystyle\lim_{n\to+\infty}\left(\frac23\right)^n=0.

2 ▷ Pour k\geqslant2, on note D_k l’événement « à l’issue de la k-ième opération, le jeton A revient pour la première fois dans C_0 ». Montrer que P(D_k)=\dfrac{k-1}9\left(\dfrac23\right)^{k-2}, puis vérifier que \displaystyle\sum_{k=2}^{+\infty}P(D_k)=1. On admettra que, pour |x|<1, \displaystyle\sum_{m=1}^{+\infty}mx^{m-1}=\frac1{(1-x)^2}.

Indication

D_k est réalisé si et seulement si, parmi les k premiers tirages, la lettre a sort exactement deux fois, la seconde fois au tirage k. Choisir la position j du premier a.

Corrigé

Le jeton A part de C_0. Il revient pour la première fois dans C_0 à l’opération k si et seulement si la lettre a a été tirée exactement deux fois parmi les k premiers tirages, dont une fois au tirage k (le premier a le fait passer dans C_1, le second le ramène).

Pour j\in[\![1,k-1]\!], l’événement « le premier a est au tirage j, le second au tirage k » a pour probabilité \left(\frac13\right)^2\left(\frac23\right)^{k-2} par indépendance. Ces k-1 événements sont incompatibles, donc P(D_k)=\dfrac{k-1}9\left(\dfrac23\right)^{k-2}.

En posant m=k-1 : \displaystyle\sum_{k=2}^{+\infty}P(D_k)=\frac19\sum_{m=1}^{+\infty}m\left(\frac23\right)^{m-1}=\frac19\cdot\frac1{(1/3)^2}=1. Le jeton A revient donc presque sûrement dans C_0.

3 ▷ On considère les matrices de \mathcal M_2(\mathbb R) : M=\begin{pmatrix}2&1\\1&2\end{pmatrix}, P=\begin{pmatrix}1&1\\-1&1\end{pmatrix}, D=\begin{pmatrix}1&0\\0&3\end{pmatrix}. (a) Calculer MP et PD. Justifier que P est inversible et donner P^{-1}.

Indication

Pour une matrice 2\times2 \begin{pmatrix}\alpha&\beta\\\gamma&\delta\end{pmatrix} avec \alpha\delta-\beta\gamma\neq0, l’inverse est \dfrac1{\alpha\delta-\beta\gamma}\begin{pmatrix}\delta&-\beta\\-\gamma&\alpha\end{pmatrix}.

Corrigé

MP=\begin{pmatrix}2-1&2+1\\1-2&1+2\end{pmatrix}=\begin{pmatrix}1&3\\-1&3\end{pmatrix} et PD=\begin{pmatrix}1&3\\-1&3\end{pmatrix} : MP=PD.

\det P=1\cdot1-1\cdot(-1)=2\neq0, donc P est inversible et P^{-1}=\dfrac12\begin{pmatrix}1&-1\\1&1\end{pmatrix}.

(b) En déduire par récurrence que M^n=PD^nP^{-1} pour tout n\in\mathbb N, puis que M^n=\dfrac12\begin{pmatrix}3^n+1&3^n-1\\3^n-1&3^n+1\end{pmatrix}.

Indication

De MP=PD, on tire M=PDP^{-1}. Pour l’hérédité, M^{n+1}=M^n\,M=PD^nP^{-1}PDP^{-1}.

Corrigé

De MP=PD et de l’inversibilité de P, on tire M=PDP^{-1}. Pour n=0 : M^0=I_2=PP^{-1}=PD^0P^{-1}. Si M^n=PD^nP^{-1}, alors M^{n+1}=M^nM=PD^nP^{-1}PDP^{-1}=PD^{n+1}P^{-1}.

Avec D^n=\begin{pmatrix}1&0\\0&3^n\end{pmatrix} : PD^n=\begin{pmatrix}1&3^n\\-1&3^n\end{pmatrix}, puis M^n=\dfrac12\begin{pmatrix}1&3^n\\-1&3^n\end{pmatrix}\begin{pmatrix}1&-1\\1&1\end{pmatrix}=\dfrac12\begin{pmatrix}3^n+1&3^n-1\\3^n-1&3^n+1\end{pmatrix}.

4 ▷ (a) Donner la loi de X_1.

Indication

Après un tirage, A est dans C_1 si et seulement si la lettre a est sortie.

Corrigé

P(X_1=1)=P(\text{« }a\text{ au premier tirage »})=\dfrac13 et P(X_1=0)=\dfrac23.

(b) Pour n\in\mathbb N, on pose V_n=\begin{pmatrix}P(X_n=0)\\P(X_n=1)\end{pmatrix}. Déterminer une matrice Q telle que V_{n+1}=QV_n pour tout n\in\mathbb N.

Indication

Formule des probabilités totales avec le système complet \big([X_n=0],[X_n=1]\big). Quelle est la probabilité que A change de case à l’opération n+1 ?

Corrigé

À l’opération n+1, le jeton A change de case avec la probabilité \frac13 (lettre a) et reste en place avec la probabilité \frac23, indépendamment des tirages précédents. Donc P_{[X_n=0]}(X_{n+1}=0)=\frac23, P_{[X_n=1]}(X_{n+1}=0)=\frac13, etc.

Par la formule des probabilités totales (avec la convention P(X_n=j)\,P_{[X_n=j]}(\cdot)=0 si P(X_n=j)=0) : P(X_{n+1}=0)=\frac23P(X_n=0)+\frac13P(X_n=1) et P(X_{n+1}=1)=\frac13P(X_n=0)+\frac23P(X_n=1).

Donc V_{n+1}=QV_n avec Q=\dfrac13\begin{pmatrix}2&1\\1&2\end{pmatrix}=\dfrac13M.

(c) En déduire la loi de X_n pour n\in\mathbb N. Que se passe-t-il quand n\to+\infty ?

Indication

Par récurrence, V_n=Q^nV_0 avec V_0=\begin{pmatrix}1\\0\end{pmatrix}, et Q^n=\dfrac1{3^n}M^n.

Corrigé

Par récurrence immédiate, V_n=Q^nV_0, avec V_0=\begin{pmatrix}1\\0\end{pmatrix} car X_0=0. Or Q^n=\dfrac1{3^n}M^n=\dfrac12\begin{pmatrix}1+3^{-n}&1-3^{-n}\\1-3^{-n}&1+3^{-n}\end{pmatrix}. V_n est la première colonne :

P(X_n=0)=\dfrac{1+3^{-n}}2 et P(X_n=1)=\dfrac{1-3^{-n}}2. Vérification : pour n=1, on retrouve \frac23 et \frac13.

Quand n\to+\infty, ces probabilités tendent vers \frac12 : à long terme, le jeton A est dans chaque case avec la même probabilité.

Partie II – Le mouvement du couple de jetons (A, B)

On définit, pour n\in\mathbb N, la variable W_n à valeurs dans \{0,1,2,3\} : W_n=0 si A et B sont dans C_0 ; W_n=1 si A est dans C_0 et B dans C_1 ; W_n=2 si A est dans C_1 et B dans C_0 ; W_n=3 si A et B sont dans C_1. Ainsi W_0=0.

1 ▷ Donner la loi de W_1.

Indication

Examiner l’effet de chacune des trois lettres sur la position (0,0).

Corrigé

Au départ, les deux jetons sont dans C_0. La lettre a conduit à W_1=2, la lettre b à W_1=1, la lettre c à W_1=0. Donc P(W_1=0)=P(W_1=1)=P(W_1=2)=\dfrac13 et P(W_1=3)=0.

2 ▷ Déterminer la matrice R\in\mathcal M_4(\mathbb R) telle que, pour tout n\in\mathbb N, \begin{pmatrix}P(W_{n+1}=0)\\P(W_{n+1}=1)\\P(W_{n+1}=2)\\P(W_{n+1}=3)\end{pmatrix}=R\begin{pmatrix}P(W_n=0)\\P(W_n=1)\\P(W_n=2)\\P(W_n=3)\end{pmatrix}.

Indication

Le coefficient (i,j) de R (lignes et colonnes numérotées de 0 à 3) est la probabilité de passer de l’état j à l’état i en une opération. Depuis chaque état, on peut aller dans exactement trois états.

Corrigé

Depuis chaque état, la lettre c laisse l’état inchangé, la lettre a change la case de A et la lettre b celle de B. Ainsi : de 0 on va en 0,1,2 ; de 1 en 1,0,3 ; de 2 en 2,3,0 ; de 3 en 3,2,1, chaque fois avec la probabilité \frac13. L’état inaccessible depuis j est 3-j (les deux jetons ne peuvent pas changer de case en même temps).

Par la formule des probabilités totales sur le système complet \big([W_n=j]\big)_{0\leqslant j\leqslant3} : R=\dfrac13\begin{pmatrix}1&1&1&0\\1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix}.

3 ▷ On pose U=\begin{pmatrix}1&1&1&1\\1&1&1&1\\1&1&1&1\\1&1&1&1\end{pmatrix} et V=\begin{pmatrix}0&0&0&1\\0&0&1&0\\0&1&0&0\\1&0&0&0\end{pmatrix}, de sorte que R=\frac13(U-V). (a) Calculer U^2, V^2, UV et VU.

Indication

Chaque coefficient de U^2 est une somme de quatre produits 1\times1. Multiplier par V permute les colonnes (à droite) ou les lignes (à gauche).

Corrigé

U^2=4U (chaque coefficient vaut 4). V^2=I_4 (V échange les coordonnées 1\leftrightarrow4 et 2\leftrightarrow3, et le fait deux fois revient à l’identité). UV=VU=U (permuter les lignes ou les colonnes de U ne la change pas).

(b) Montrer que, pour tout n\geqslant1, (U-V)^n=\dfrac{3^n-(-1)^n}4\,U+(-1)^nV^n.

Indication

Récurrence sur n, en développant \left(a_nU+(-1)^nV^n\right)(U-V) avec la question (a). Noter que V^nU=U.

Corrigé

Notons a_n=\dfrac{3^n-(-1)^n}4. Pour n=1 : a_1=1 et a_1U-V=U-V.

Si la formule est vraie au rang n : (U-V)^{n+1}=\left(a_nU+(-1)^nV^n\right)(U-V)=a_n(U^2-UV)+(-1)^n(V^nU-V^{n+1}). Or U^2-UV=4U-U=3U et V^nU=U (car VU=U). Donc (U-V)^{n+1}=\big(3a_n+(-1)^n\big)U+(-1)^{n+1}V^{n+1}.

Et 3a_n+(-1)^n=\dfrac{3^{n+1}-3(-1)^n+4(-1)^n}4=\dfrac{3^{n+1}-(-1)^{n+1}}4=a_{n+1} : la formule est vraie au rang n+1.

4 ▷ Pour n\geqslant1, calculer R^n et donner la loi de W_n. On distinguera les cas n pair et n impair.

Indication

R^n=3^{-n}(U-V)^n et V^n vaut I_4 ou V selon la parité de n. La loi de W_n est la première colonne de R^n, puisque W_0=0.

Corrigé

R^n=\dfrac1{3^n}\left(a_nU+(-1)^nV^n\right). Comme en I.4, le vecteur des P(W_n=i) est R^n appliqué au vecteur (1,0,0,0), c’est-à-dire la première colonne de R^n. Celle de U est (1,1,1,1), celle de I_4 est (1,0,0,0), celle de V est (0,0,0,1).

Si n est pair : a_n=\frac{3^n-1}4 et V^n=I_4, donc P(W_n=0)=\dfrac{3^n+3}{4\cdot3^n} et P(W_n=1)=P(W_n=2)=P(W_n=3)=\dfrac{3^n-1}{4\cdot3^n}.

Si n est impair : a_n=\frac{3^n+1}4 et (-1)^nV^n=-V, donc P(W_n=0)=P(W_n=1)=P(W_n=2)=\dfrac{3^n+1}{4\cdot3^n} et P(W_n=3)=\dfrac{3^n-3}{4\cdot3^n}.

Contrôles : la somme vaut 1 dans les deux cas ; pour n=1, on retrouve la loi de W_1 ; et P(W_n=0)+P(W_n=1)=\frac{1+3^{-n}}2=P(X_n=0), comme en I.4(c).

5 ▷ Les variables X_1 et Y_1 sont-elles indépendantes ? Et X_n et Y_n pour n pair ?

Indication

Comparer P(W_n=3)=P([X_n=1]\cap[Y_n=1]) et P(X_n=1)P(Y_n=1). Par symétrie, Y_n a la même loi que X_n.

Corrigé

Par symétrie des rôles de a et b, Y_n a la même loi que X_n : P(Y_n=1)=\frac{1-3^{-n}}2.

Pour n=1 : P([X_1=1]\cap[Y_1=1])=P(W_1=3)=0, alors que P(X_1=1)P(Y_1=1)=\frac19. Les variables ne sont pas indépendantes (un seul jeton bouge à chaque étape).

Pour n pair : P(W_n=3)=\dfrac{3^n-1}{4\cdot3^n} et P(X_n=1)P(Y_n=1)=\dfrac{(3^n-1)^2}{4\cdot9^n}. Leur rapport vaut \dfrac{3^n}{3^n-1}\neq1 : pas d’indépendance non plus. Mais ce rapport tend vers 1 : les positions des deux jetons deviennent « presque indépendantes » à long terme.

Partie III – Un temps de séjour

Chaque opération dure une minute. Pour n\geqslant1, on note T_n le nombre de minutes, parmi les n premières, à l’issue desquelles le jeton A se trouve dans C_1.

1 ▷ Exprimer T_n à l’aide des variables X_1,\dots,X_n et calculer E(T_n). Déterminer la limite de \dfrac{E(T_n)}n.

Indication

X_k vaut 1 exactement quand A est dans C_1 à la minute k. Utiliser la linéarité de l’espérance (sans chercher la loi de T_n) et une somme géométrique.

Corrigé

Comme X_k\in\{0,1\} vaut 1 si et seulement si A est dans C_1 à l’issue de la minute k, on a T_n=\displaystyle\sum_{k=1}^{n}X_k.

Par linéarité, E(T_n)=\displaystyle\sum_{k=1}^{n}E(X_k)=\sum_{k=1}^{n}P(X_k=1)=\sum_{k=1}^{n}\frac{1-3^{-k}}2=\frac n2-\frac12\cdot\frac13\cdot\frac{1-3^{-n}}{1-1/3}, soit E(T_n)=\dfrac n2-\dfrac{1-3^{-n}}4.

Donc \dfrac{E(T_n)}n\to\dfrac12 : en moyenne, le jeton A passe la moitié du temps dans chaque case.

2 ▷ (Python) Compléter la fonction suivante, qui simule n opérations et renvoie la liste [W_1,\dots,W_n]. Les états sont codés par W=2X+Y.

import numpy.random as rd

def simule(n):
    x, y = 0, 0
    L = []
    for k in range(n):
        lettre = rd.randint(3)      # 0 pour a, 1 pour b, 2 pour c
        if lettre == 0:
            x = 1 - x
        elif lettre == 1:
            ...
        L.append(...)
    return L
Écrire ensuite un programme qui estime P(W_{10}=3) et comparer avec la valeur exacte.

Indication

rd.randint(3) renvoie un entier uniforme parmi 0,1,2. Vérifier le codage : (X,Y)=(0,1) donne 1, (1,0) donne 2.

Corrigé

Les lignes manquantes sont y = 1 - y et L.append(2*x + y). Pour l’estimation :

N = 10000
c = 0
for i in range(N):
    if simule(10)[-1] == 3:
        c = c + 1
print(c / N, (3**10 - 1) / (4 * 3**10))

La valeur exacte (pour n=10 pair) est \dfrac{3^{10}-1}{4\cdot3^{10}}\approx0{,}24999 : la fréquence observée en est très proche.


Pour aller plus loin

Besoin d’aide sur ce chapitre, ou un concours à viser ?

Un blocage sur une notion, une méthode de rédaction à acquérir, un devoir surveillé — ou l’ambition d’intégrer une grande école : Pr. Elakili, agrégé de mathématiques depuis 1991, plus de 25 ans d’enseignement en classes préparatoires, propose des cours particuliers, en présentiel à Casablanca, ou à distance, partout au Maroc et en France.

🎯 Prépas commerciales : réussir les écrits BCE et Ecricome et intégrer les meilleures écoles de commerce (HEC, ESSEC, ESCP…).

Publications similaires