↩ 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
,
,
: la lettre
fait changer de case le jeton
, la lettre
le jeton
, et la lettre
ne change rien. Où sont les jetons au bout de
é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
, 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
et
, que l’on peut placer dans deux cases
et
, et d’un dispositif qui tire au hasard, de manière équiprobable, l’une des lettres
,
ou
. Au départ, les deux jetons sont dans
. On procède à une suite de tirages indépendants. Après chaque tirage :
- si la lettre
est tirée, on change le jeton
de case ; - si la lettre
est tirée, on change le jeton
de case ; - si la lettre
est tirée, on ne change rien.
On pose
et, pour
:
si, à l’issue de la
-ième opération, le jeton
est dans
, et
s’il est dans
. On définit de même
pour le jeton
.
Partie I – Le mouvement du jeton A
1 ▷ (a) Soit
. Quelle est la probabilité qu’à l’issue de la
-ième opération, le jeton
n’ait jamais quitté
?
Indication
Le jeton
ne bouge que si la lettre
est tirée.
Corrigé
Notons
l’événement « la lettre
est tirée au
-ième tirage », de probabilité
. Le jeton
n’a jamais quitté
après
opérations si et seulement si la lettre
n’a été tirée à aucun des
premiers tirages. Par indépendance, cette probabilité vaut
.
(b) Quelle est la probabilité que le jeton
reste indéfiniment dans
?
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
l’événement «
n’a pas quitté
à l’issue de la
-ième opération ». La suite
est décroissante et l’événement «
reste indéfiniment dans
» est
.
Par le théorème de la limite monotone, sa probabilité vaut
.
2 ▷ Pour
, on note
l’événement « à l’issue de la
-ième opération, le jeton
revient pour la première fois dans
». Montrer que
, puis vérifier que
. On admettra que, pour
,
.
Indication
est réalisé si et seulement si, parmi les
premiers tirages, la lettre
sort exactement deux fois, la seconde fois au tirage
. Choisir la position
du premier
.
Corrigé
Le jeton
part de
. Il revient pour la première fois dans
à l’opération
si et seulement si la lettre
a été tirée exactement deux fois parmi les
premiers tirages, dont une fois au tirage
(le premier
le fait passer dans
, le second le ramène).
Pour
, l’événement « le premier
est au tirage
, le second au tirage
» a pour probabilité
par indépendance. Ces
événements sont incompatibles, donc
.
En posant
:
. Le jeton
revient donc presque sûrement dans
.
3 ▷ On considère les matrices de
:
,
,
. (a) Calculer
et
. Justifier que
est inversible et donner
.
Indication
Pour une matrice
avec
, l’inverse est
.
Corrigé
et
:
.
, donc
est inversible et
.
(b) En déduire par récurrence que
pour tout
, puis que
.
Indication
De
, on tire
. Pour l’hérédité,
.
Corrigé
De
et de l’inversibilité de
, on tire
. Pour
:
. Si
, alors
.
Avec
:
, puis
.
4 ▷ (a) Donner la loi de
.
Indication
Après un tirage,
est dans
si et seulement si la lettre
est sortie.
Corrigé
et
.
(b) Pour
, on pose
. Déterminer une matrice
telle que
pour tout
.
Indication
Formule des probabilités totales avec le système complet
. Quelle est la probabilité que
change de case à l’opération
?
Corrigé
À l’opération
, le jeton
change de case avec la probabilité
(lettre
) et reste en place avec la probabilité
, indépendamment des tirages précédents. Donc
,
, etc.
Par la formule des probabilités totales (avec la convention
si
) :
et
.
Donc
avec
.
(c) En déduire la loi de
pour
. Que se passe-t-il quand
?
Indication
Par récurrence,
avec
, et
.
Corrigé
Par récurrence immédiate,
, avec
car
. Or
.
est la première colonne :
et
. Vérification : pour
, on retrouve
et
.
Quand
, ces probabilités tendent vers
: à long terme, le jeton
est dans chaque case avec la même probabilité.
Partie II – Le mouvement du couple de jetons (A, B)
On définit, pour
, la variable
à valeurs dans
:
si
et
sont dans
;
si
est dans
et
dans
;
si
est dans
et
dans
;
si
et
sont dans
. Ainsi
.
1 ▷ Donner la loi de
.
Indication
Examiner l’effet de chacune des trois lettres sur la position
.
Corrigé
Au départ, les deux jetons sont dans
. La lettre
conduit à
, la lettre
à
, la lettre
à
. Donc
et
.
2 ▷ Déterminer la matrice
telle que, pour tout
,
.
Indication
Le coefficient
de
(lignes et colonnes numérotées de
à
) est la probabilité de passer de l’état
à l’état
en une opération. Depuis chaque état, on peut aller dans exactement trois états.
Corrigé
Depuis chaque état, la lettre
laisse l’état inchangé, la lettre
change la case de
et la lettre
celle de
. Ainsi : de
on va en
; de
en
; de
en
; de
en
, chaque fois avec la probabilité
. L’état inaccessible depuis
est
(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
:
.
3 ▷ On pose
et
, de sorte que
. (a) Calculer
,
,
et
.
Indication
Chaque coefficient de
est une somme de quatre produits
. Multiplier par
permute les colonnes (à droite) ou les lignes (à gauche).
Corrigé
(chaque coefficient vaut
).
(
échange les coordonnées
et
, et le fait deux fois revient à l’identité).
(permuter les lignes ou les colonnes de
ne la change pas).
(b) Montrer que, pour tout
,
.
Indication
Récurrence sur
, en développant
avec la question (a). Noter que
.
Corrigé
Notons
. Pour
:
et
.
Si la formule est vraie au rang
:
. Or
et
(car
). Donc
.
Et
: la formule est vraie au rang
.
4 ▷ Pour
, calculer
et donner la loi de
. On distinguera les cas
pair et
impair.
Indication
et
vaut
ou
selon la parité de
. La loi de
est la première colonne de
, puisque
.
Corrigé
. Comme en I.4, le vecteur des
est
appliqué au vecteur
, c’est-à-dire la première colonne de
. Celle de
est
, celle de
est
, celle de
est
.
Si
est pair :
et
, donc
et
.
Si
est impair :
et
, donc
et
.
Contrôles : la somme vaut
dans les deux cas ; pour
, on retrouve la loi de
; et
, comme en I.4(c).
5 ▷ Les variables
et
sont-elles indépendantes ? Et
et
pour
pair ?
Indication
Comparer
et
. Par symétrie,
a la même loi que
.
Corrigé
Par symétrie des rôles de
et
,
a la même loi que
:
.
Pour
:
, alors que
. Les variables ne sont pas indépendantes (un seul jeton bouge à chaque étape).
Pour
pair :
et
. Leur rapport vaut
: pas d’indépendance non plus. Mais ce rapport tend vers
: 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
, on note
le nombre de minutes, parmi les
premières, à l’issue desquelles le jeton
se trouve dans
.
1 ▷ Exprimer
à l’aide des variables
et calculer
. Déterminer la limite de
.
Indication
vaut
exactement quand
est dans
à la minute
. Utiliser la linéarité de l’espérance (sans chercher la loi de
) et une somme géométrique.
Corrigé
Comme
vaut
si et seulement si
est dans
à l’issue de la minute
, on a
.
Par linéarité,
, soit
.
Donc
: en moyenne, le jeton
passe la moitié du temps dans chaque case.
2 ▷ (Python) Compléter la fonction suivante, qui simule
opérations et renvoie la liste
. Les états sont codés par
.
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 Indication
rd.randint(3) renvoie un entier uniforme parmi
. Vérifier le codage :
donne
,
donne
.
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
pair) est
: 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…).
