Corrigé ESSEC-HEC 2025 Maths appliquées ECG — Partie 1 — Réversibilité et exemples (Q1.a à Q4.c) : Matrice stochastique µ-réversible : état stable µM = µ, critère ΔM = ᵗMΔ, exemple à trois états et marche aléatoire sur un graphe (µ proportionnelle aux degrés)

Sujet officiel du concours ESSEC-HEC, session 2025, épreuve Maths appliquées ECG. Corrigé rédigé par Ibrahim Alame.

Énoncé

Notations. $r ⩾ 2$ ; $(X_{n})_{n \in N}$ est une chaîne de Markov homogène sur $[[1, r]]$ , de matrice de transition $P = (p_{i, j})$ où $p_{i, j} = P_{[X_{n} = i]} (X_{n + 1} = j)$ dès que $P (X_{n} = i) \neq = 0$ . $S T_{r}$ désigne l'ensemble des matrices carrées d'ordre $r$ à coefficients positifs dont chaque ligne a pour somme $1$ ; ainsi $P \in S T_{r}$ .

$μ = (μ_{1} \dots μ_{r})$ est une matrice ligne à coefficients strictement positifs de somme $1$ . Une matrice $M = (m_{i, j}) \in S T_{r}$ est dite $μ$ -réversible lorsque $μ_{i} m_{i, j} = μ_{j} m_{j, i}$ pour tout $(i, j) \in [[1, r]]^{2}$ . Dans toute la partie, $M \in S T_{r}$ ; $Δ$ est la matrice diagonale de coefficients diagonaux $μ_{1}, \dots, μ_{r}$ .

Q1.a. Si $M$ est $μ$ -réversible et $m_{i, j} \neq = 0$ , montrer que $m_{j, i} \neq = 0$ .
Q1.b. Si $M$ est symétrique, trouver $μ$ telle que $M$ soit $μ$ -réversible.
Q1.c. Montrer que $M$ est $μ$ -réversible si et seulement si $Δ M =^{t} M Δ$ .
Q2. Montrer que si $M$ est $μ$ -réversible, alors $μ M = μ$ .
Q3. Ici $r = 3$ et $P = \frac{1}{3} 110202021$ . (a) Tracer le graphe probabiliste. (b) Trouver $μ$ telle que $P$ soit $μ$ -réversible.
Q4. $G$ est un graphe non orienté, simple, connexe, de sommets $1, \dots, r$ . On choisit $X_{0}$ au hasard parmi les sommets, puis, de $X_{n} = k$ , on va en un voisin de $k$ choisi de façon équiprobable : c'est $X_{n + 1}$ . On note $A = (a_{i, j})$ la matrice d'adjacence et $d_{i}$ le degré du sommet $i$ .
(a) Écrire Trajectoire(L,n) qui, à partir des listes d'adjacence L (les voisins de $i$ sont dans L[i-1]), simule $n$ déplacements et renvoie la liste des sommets visités.
(b) Montrer que $p_{i, j} = a_{i, j} / d_{i}$ .
(c) En déduire $μ$ telle que $P$ soit $μ$ -réversible.

Corrigé

Q1.a. Supposons $M$ $μ$ -réversible et $m_{i, j} \neq = 0$ . Comme $M \in S T_{r}$ , $m_{i, j} ⩾ 0$ , donc $m_{i, j} > 0$ ; et $μ_{i} > 0$ . Ainsi

$μ_{j} m_{j, i} = μ_{i} m_{i, j} > 0.$

Un produit nul ne pouvant être strictement positif, $m_{j, i} \neq = 0$ (et même $m_{j, i} > 0$ ).

Q1.b. Prenons la loi uniforme $μ = (\frac{1}{r} \dots \frac{1}{r})$ : ses coefficients sont strictement positifs et de somme $r \times \frac{1}{r} = 1$ . Pour tout $(i, j)$ , la symétrie $m_{i, j} = m_{j, i}$ donne

$μ_{i} m_{i, j} = \frac{m _{i, j}}{r} = \frac{m _{j, i}}{r} = μ_{j} m_{j, i},$

et $M \in S T_{r}$ par hypothèse de la partie : $M$ est $μ$ -réversible.

Q1.c. Calculons les deux produits coefficient par coefficient. Comme $Δ$ est diagonale, multiplier à gauche par $Δ$ multiplie la ligne $i$ par $μ_{i}$ , et multiplier à droite par $Δ$ multiplie la colonne $j$ par $μ_{j}$ :

$(Δ M)_{i, j} = k = 1 \sum r Δ_{i, k} m_{k, j} = μ_{i} m_{i, j},$

$(^{t} M Δ)_{i, j} = k = 1 \sum r (^{t} M)_{i, k} Δ_{k, j} = (^{t} M)_{i, j} μ_{j} = μ_{j} m_{j, i} .$

Deux matrices sont égales si et seulement si tous leurs coefficients le sont, donc

$Δ M =^{t} M Δ ⟺ \forall (i, j) \in [[1, r]]^{2}, μ_{i} m_{i, j} = μ_{j} m_{j, i} .$

Comme $M \in S T_{r}$ dans toute la partie, le membre de droite est exactement la $μ$ -réversibilité : $M est μ -r e ˊ versible ⟺ Δ M =^{t} M Δ$ . Autrement dit, la matrice $Δ M$ est symétrique, puisque $^{t} (Δ M) =^{t} M^{t} Δ =^{t} M Δ$ .

Q2. Soit $j \in [[1, r]]$ . Le coefficient $j$ de la matrice ligne $μ M$ vaut, en utilisant la réversibilité puis le fait que la ligne $j$ de $M$ a pour somme $1$ ,

$(μ M)_{j} = i = 1 \sum r μ_{i} m_{i, j} = i = 1 \sum r μ_{j} m_{j, i} = μ_{j} i = 1 \sum r m_{j, i} = μ_{j} .$

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →