Connectez-vous pour consulter le corrigé.
Dans cet énoncé \(r\) est un entier naturel, \(r \geqslant 2\) et \(\left[\!\left[1, r\right]\!\right]\) désigne l’ensemble des entiers naturels \(k\) tels que \(1 \leqslant k \leqslant r\).
On s’intéresse dans ce problème aux chaînes de Markov homogènes à espace d’états fini \(\left[\!\left[1, r\right]\!\right]\) réversibles.
Ce type de chaîne intervient dans les marches aléatoires sur les sommets d’un graphe non orienté, les processus de naissance et mort, la méthode de Métropolis par exemple.
Le problème comporte trois parties. Les parties 2 et 3 sont indépendantes. Seules les questions 1 et 2 de la partie 1 sont utiles pour la partie 2.
Un aide-mémoire Python se trouve à la fin de
l’énoncé.
Pour les scripts et fonctions Python, on
supposera que les instructions suivantes ont été exécutées:
import numpy as np, numpy.random as rd
On considère, dans la suite du problème, une chaîne de Markov \(\left(X_n\right)_{n \in \mathbb{N}}\), sur un espace probabilisé \((\Omega, \mathcal{A}, \mathbb{P})\), vérifiant les propriétés suivantes :
Pour tout \(n \geqslant 0, X_n(\Omega)=\left[\!\left[1, r\right]\!\right]\).
Pour tout \(i \in \left[\!\left[1, r\right]\!\right]\), il existe \(n \in \mathbb{N}\) tel que \(\mathbb{P}(X_n=i) \neq 0\). On note \(S_i\) l’ensemble des entiers positifs \(n\) tels que \(\mathbb{P}(X_n=i) \neq 0\).
Pour tout \((i, j) \in \left[\!\left[1, r\right]\!\right]^2\), la fonction \(n \mapsto \mathbb{P}_{[X_n=i]}(X_{n+1}=j)\) est constante sur son ensemble de définition \(S_i\) et on note \(p_{i, j}\) cette constante.
La matrice \(P=\left(p_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) s’appelle la matrice de transition de la chaîne.
On rappelle que l’on a pour tout \(i \in \left[\!\left[1, r\right]\!\right]\), \(\displaystyle \sum_{j=1}^r p_{i, j}=1\).
On note \(\mathcal{S} \mathcal{T}_r\) l’ensemble des matrices \(M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) à coefficients positifs telles que pour tout \(i \in \left[\!\left[1, r\right]\!\right]\), \(\displaystyle \sum_{j=1}^r m_{i, j}=1\). Donc \(P \in \mathcal{S} \mathcal{T}_r\).
On considère \(\mu=\left(\mu_1 \ldots \mu_r\right)\) une matrice ligne appartenant à \(\mathcal{M}_{1, r}(\mathbb{R})\) dont les coefficients sont strictement positifs et tels que \(\displaystyle \sum_{k=1}^r \mu_k=1\).
On dit que la matrice \(M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) est \(\mu\)-réversible si \(M\) appartient à \(\mathcal{S} \mathcal{T}_r\) et vérifie : \[\forall(i, j) \in \left[\!\left[1, r\right]\!\right]^2, \ \mu_i m_{i, j}=\mu_j m_{j, i}\]
Dans cette partie \(M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) appartient à \(\mathcal{S T }_ { r }\).
Montrer que si \(M\) est \(\mu\)-réversible et si \(m_{i, j} \neq 0\) pour un couple \((i, j) \in \left[\!\left[1, r\right]\!\right]^2\) alors \(m_{j, i} \neq 0\).
On suppose dans cette question que \(M\) est symétrique. Déterminer \(\mu\) telle que \(M\) est \(\mu\)-réversible.
On note \(\Delta\) la matrice diagonale d’ordre \(r\) dont les éléments diagonaux sont \(\mu_1, \ldots, \mu_r\). Montrer que \(M\) est \(\mu\)-réversible si et seulement si \(\Delta M= {}^t\!M \Delta\).
Montrer que si \(M\) est \(\mu\)-réversible alors \(\mu M=\mu\).
Un premier exemple – On suppose que \(r=3\) et que \(\displaystyle P=\frac{1}{3} \begin{pmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1 \end{pmatrix}\) est la matrice de transition d’une chaîne de Markov.
Représenter le graphe probabiliste associé à cette matrice de transition.
Déterminer \(\mu\) telle que \(P\) soit \(\mu\)-réversible.
Un deuxième exemple – Soit \(G\) un graphe à \(r\) sommets \(1, \dots, r\), non orienté, connexe, simple (deux sommets ne peuvent être reliés que par une seule arête). On considère l’expérience aléatoire qui consiste à se déplacer d’un sommet à l’autre de la manière suivante :
on choisit un sommet au hasard ce qui définit la valeur de \(X_0\);
si on se trouve au sommet \(k\) après \(n\) déplacements, on a alors \(X_n=k\), on se déplace vers un sommet adjacent au sommet \(k\), ce qui définit \(X_{n+1}\). Tous les sommets en question peuvent être choisis de manière équiprobable.
On admet que l’on définit ainsi une chaîne de Markov et on note encore \(P=\left(p_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) sa matrice de transition.
Écrire une fonction Python
Trajectoire(L,n) qui étant donnée la liste des listes
d’adjacence L du graphe \(G\) et un entier \(n\), simule \(n\) déplacements sur le graphe et renvoie
la liste des sommets visités.
On notera que les sommets reliés au sommet i par une
arête se trouvent dans la liste L[i-1].
On note \(A=\left(a_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) la matrice d’adjacence de \(G, d_i\) le degré du sommet \(i\).
Montrer que pour tout \((i, j) \in \left[\!\left[1, r\right]\!\right]^2, \ \displaystyle p_{i, j}=\frac{a_{i, j}}{d_i}\).
En déduire \(\mu\) pour laquelle \(P\) est \(\mu\)-réversible.
On note, pour tout \(n \in \mathbb{N}^*, \ m_{i, j}^{(n)}\) les coefficients de la matrice \(M^n\).
S’il existe \(\sigma \in \mathbb{N}^*\) tel que, pour tout \((i, j) \in \left[\!\left[1, r\right]\!\right]^2, \ m_{i, j}^{(\sigma)}>0\), on dit que \(M\) est une matrice ergodique.
On définit aussi pour tout \(n \in \mathbb{N}^*\) et \(\left(i_0, \ldots, i_n\right) \in \left[\!\left[1, r\right]\!\right]^{n+1}\) : \[\theta_M(i_0, \ldots, i_n)=m_{i_0, i_1} \times \ldots \times m_{i_{n-1}, i_n}=\prod_{k=1}^n m_{i_{k-1}, i_k}\]
En particulier, pour tout \((i, j) \in \left[\!\left[1, r\right]\!\right]^2, \ \theta_M(i, j)=m_{i, j}\).
Montrer que pour tous \((n, s) \in\left(\mathbb{N}^*\right)^2, \ i_0, \ldots, i_n\) et \(j_0, \ldots, j_s\) éléments de \(\left[\!\left[1, r\right]\!\right]\) tels que \(i_n=j_0\) : \[\theta_M(i_0, \ldots, i_n) \, \theta_M(j_0, \ldots, j_s)=\theta_M(i_0, \ldots, i_n, j_1, \ldots, j_s)\]
On dit que \(M\) vérifie la propriété \((K)\) si, pour tout \(n \in \mathbb{N}^*\) et \(i_0, \ldots, i_n\) éléments de \(\left[\!\left[1, r\right]\!\right]\) : \[\theta_M(i_0, i_1, \ldots, i_n, i_0)=\theta_M(i_0, i_n, \ldots, i_1, i_0) \tag{$K$}\]
On admet qu’il suffit de vérifier \((K)\) lorsque les \(i_k\) sont deux à deux distincts et \(n \geqslant 2\).
On établit dans la fin de cette partie que, si \(M\) est ergodique, il existe \(\mu\) telle que \(M\) est \(\mu\)-réversible si seulement si \(M\) vérifie la propriété \((K)\).
Si \(r=3\), montrer que \(M\) vérifie \(( K )\) si et seulement si \(m_{1,2} m_{2,3} m_{3,1}=m_{1,3} m_{3,2} m_{2,1}\). Montrer que la matrice \(P\) de la question 3 vérifie \((K)\).
On suppose dans cette question que \(M\) est \(\mu\)-réversible.
Montrer que pour tout \(n \in \mathbb{N}^*\) et \(i_0, \ldots, i_n\) éléments de \(\left[\!\left[1, r\right]\!\right]\) :
\[\left(\prod_{k=1}^n \mu_{i_{k-1}}\right) \theta_M(i_0, \ldots, i_n)=\left(\prod_{k=1}^n \mu_{i_k}\right) \theta_M(i_n, \ldots, i_0)\]
En déduire que \(M\) vérifie \((K)\).
Soit \((i, j) \in \left[\!\left[1, r\right]\!\right]^2\). Montrer par récurrence sur \(s \in \mathbb{N}^*\) que \(m_{i, j}^{(s)}>0\) si et seulement si il existe \(\left(i_0, i_1, \ldots, i_s\right)\) appartenant à \(\left[\!\left[1, r\right]\!\right]^{s+1}\) tels que \(i_0=i, i_s=j\) et \(\theta_M(i_0, \ldots, i_s)>0\).
On suppose que la matrice \(M\) vérifie \((K)\) et est ergodique avec pour tout \((i, j) \in \left[\!\left[1, r\right]\!\right]^2\), \(m_{i, j}^{(\sigma)}>0\), où \(\sigma\) est un entier naturel non nul.
On veut montrer qu’alors \(M\) est \(\mu\)-réversible pour \(\mu\) à définir.
Montrer que, pour tout \(i \in \left[\!\left[1, r\right]\!\right]\), il existe \(( i_0, i_1, \ldots, i_\sigma )\) appartenant à \(\left[\!\left[1, r\right]\!\right]^{\sigma+1}\) tels que \(i_0=i, i_\sigma=1\) et \(\theta_M(i_0, \ldots, i_\sigma)>0\).
Montrer que si \(m_{1, i}>0\), alors \(\theta_M(i_\sigma, \ldots, i_0)>0\) et \(m_{i, 1}>0\).
Pour tout \(i \in \left[\!\left[1, r\right]\!\right]\), on pose alors \(\displaystyle \nu_i=\frac{\theta_M(i_\sigma, \ldots, i_0)}{\theta_M(i_0, \ldots, i_\sigma)}\) où \(i_0, \ldots, i_\sigma\) sont définis comme dans la question a).
Établir que pour tout \((i, j) \in \left[\!\left[1, r\right]\!\right]^2, \ \nu_i m_{i, j}=\nu_j m_{j, i}\), puis en interprétant matriciellement les égalités précédentes que, pour tout \(\left(i, j\right) \in \left[\!\left[1, r\right]\!\right], \ \nu_i m_{i, j}^{(\sigma)}=\nu_j m_{j, i}^{(\sigma)}\).
Montrer qu’il existe \(i \in \left[\!\left[1, r\right]\!\right]\) tel que \(m_{1, i}>0\). En déduire que pour tout \(j \in \left[\!\left[1, r\right]\!\right]\), \(\nu_j>0\).
Définir alors \(\mu\) telle que \(M\) soit \(\mu\)-réversible.
On conserve les notations de la partie 1. On rappelle que seules les questions 1 et 2 de la partie 1 sont utiles dans cette partie.
On considère que la matrice de transition \(P\) de la chaîne de Markov \(\left(X_n\right)_{n \in \mathbb{N}}\) est \(\mu\)-réversible.
On note \(Q\) la transposée de \(P\) et \(q_{i, j}\) ses coefficients.
On rappelle que \(\Delta\) désigne la matrice diagonale appartenant à \(\mathcal{M}_r(\mathbb{R})\) dont les éléments diagonaux sont \(\mu_1, \ldots, \mu_r\).
Déterminer une matrice diagonale \(D\) inversible telle que \(D^2=\Delta\).
En utilisant la question 1.c), en déduire que \(D^{-1} Q D\) est diagonalisable.
En conclure que \(Q\) est diagonalisable.
On admet que si \(M\) est une matrice carrée appartenant à \(\mathcal{M}_r(\mathbb{R})\) et \(Z\) une matrice ligne appartenant à \(\mathcal{M}_{1, r}(\mathbb{R})\) alors \({ }^t(Z M)= {}^t\!M \,{}^t\!\, Z\).
Montrer que \(Q \, {}^t\!\, \mu= {}^t\!\, \mu\). Que peut-on en déduire pour \(\operatorname{Sp}(Q)\) ?
Soit \(\lambda\) une valeur propre de \(Q\) et \(Y=\begin{pmatrix} y_1 \\ \vdots \\ y_r \end{pmatrix}\) un vecteur propre associé.
Montrer que \(\displaystyle \sum_{i=1}^r\left(\sum_{j=1}^r q_{i, j}\left|y_j\right|\right)=\sum_{j=1}^r\left|y_j\right|\).
En déduire que \(\displaystyle |\lambda|\left(\sum_{i=1}^r\left|y_i\right|\right) \leqslant \sum_{i=1}^r\left|y_i\right|\).
En conclure que \(\operatorname{Sp}(Q) \subset[-1,1]\).
On suppose dans cette question que tous les coefficients de \(P\), donc de \(Q\), sont strictement positifs. Dans cette question on détermine \(E_1(Q)\) où \(E_1(Q)\) désigne le sous-espace propre de \(Q\) associé à la valeur propre 1.
Soit un vecteur propre \(Y=\begin{pmatrix} y_1 \\ \vdots \\ y_r \end{pmatrix}\) de \(Q\) pour la valeur propre 1 dont l’un au moins des coefficients, noté \(y_k\), est strictement positif. On suppose qu’il existe \(\ell\) tel que \(y_{\ell}<0\). Montrer que \(\displaystyle y_k<\sum_{j=1}^r q_{k, j}\left|y_j\right|\), puis que \(\displaystyle \sum_{i=1}^r\left|y_i\right|<\sum_{i=1}^r\left|y_i\right|\). Conclusion?
En déduire que tous les vecteurs propres de \(Q\) pour la valeur propre 1 ont des composantes qui sont toutes, soit positives, soit négatives. Que peut-on dire d’un élément de \(E_1(Q)\) dont la somme des composantes est nulle?
Soit \(Y\) un vecteur propre de \(Q\) pour la valeur propre 1. Montrer que \(\displaystyle Y=\left(\sum_{i=1}^r y_i\right) {}^t\!\, \mu\). En conclure que \(E_1(Q)=\operatorname{Vect}\left( {}^t\!\, \mu\right)\).
Soit \(Y= \begin{pmatrix} y_1 \\ \vdots \\ y_r \end{pmatrix}\) tel que \(Q Y=-Y\). Montrer que \(\displaystyle \sum_{i=1}^r y_i=0\). En raisonnant par l’absurde, montrer que \(-1\) n’est pas une valeur propre de \(Q\).
Dans la suite de cette partie on suppose que \(P\) est ergodique et que, pour tout \((i, j)\) appartenant à \(\left[\!\left[1, r\right]\!\right]^2\), \(p_{i, j}^{(u)}>0\), où \(u\) est un entier naturel non nul.
En appliquant la question précédente à la matrice de transition \(P^u\) qui est aussi \(\mu\) réversible, on a : \[\operatorname{Sp}(Q^u) \subset\left]-1,1\right] \quad \text{et} \quad E_1(Q^u)=\operatorname{Vect}(\, {}^t\!\, \mu)\]
Montrer que \(E_1(Q)=\operatorname{Vect}( \, {}^t\!\, \mu)\).
En distinguant les cas, \(u\) pair et \(u\) impair, montrer par l’absurde que \(-1\) n’est pas une valeur propre de \(Q\).
On note \(\lambda_1, \ldots, \lambda_r\) les coefficients d’une matrice diagonale semblable à \(Q\), avec \(\lambda_1=1\), pour tout \(i \in\{2, \ldots, r\}, \ -1<\lambda_i<1\) et \(\left( \, {}^t\!\, \mu, Y_2, \ldots, Y_r\right)\) une base associée de vecteurs propres.
On note aussi pour \(n \in \mathbb{N}\), \(L_n\) la matrice élément de \(\mathcal{M}_{1, r}(\mathbb{R}):\left(\mathbb{P}\left(X_n=1\right) \cdots \mathbb{P}\left(X_n=r\right)\right)\).
Établir que pour tout \(n \in \mathbb{N}, \ L_{n+1}=L_n P\) puis que \(L_n=L_0 P^n\).
Montrer qu’il existe \(\left(\alpha_1, \ldots, \alpha_r\right) \in \mathbb{R}^r\) tel que, pour tout \(n \in \mathbb{N}\) : \[L_n=\alpha_1 \mu+\sum_{k=2}^r \alpha_k \lambda_k^n \left( {}^t\!\, Y_k \right)\]
En déduire que pour tout \(j \in \left[\!\left[1, r\right]\!\right]\), \(\displaystyle \lim _{n \rightarrow+\infty} \mathbb{P}(X_n=j)=\alpha_1 \mu_j\).
Montrer que \(\alpha_1=1\). En conclure que \(\left(X_n\right)_{n \in \mathbb{N}}\) converge en loi vers une variable aléatoire \(X\) à valeurs dans \(\left[\!\left[1, r\right]\!\right]\) telle que, \(\forall j \in \left[\!\left[1, r\right]\!\right], \ \mathbb{P}(X=j)=\mu_j\).
On conserve les notations de la partie 1. On rappelle que cette partie est indépendante de la précédente.
Soit \(\alpha \in \left] 0,1 \right]\). On définit deux opérations élémentaires sur les matrices \(M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) appartenant à \(\mathcal{ST}_r\) comme suit :
On modifie la ligne \(k\) de \(M\), où \(k \in \left[\!\left[1, r\right]\!\right]\), en remplaçant pour tout \(j \neq k\), \(m_{k, j}\) par \(m_{k, j}^{\prime}=\alpha \, m_{k, j}\) et \(m_{k, k}\) par \(m_{k, k}^{\prime}=1-\alpha+\alpha \, m_{k, k}\).
On modifie la colonne \(k\) de \(M\), où \(k \in \left[\!\left[1, r\right]\!\right]\), et sa diagonale en remplaçant pour tout \(i \neq k, m_{i, k}\) par \(m_{i, k}^{\prime}=\alpha \, m_{i, k}\) et \(m_{i, i}\) par \(m_{i, i}^{\prime}=m_{i, i}+ \left(1-\alpha \right) m_{i, k}\).
Par exemple si \(M=\begin{pmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{2}{3} \rule[0pt]{0pt}{15pt}\\ \frac{1}{6} & \frac{2}{3} & \frac{1}{6} \rule[0pt]{0pt}{15pt} \end{pmatrix}\), \(k=1\) et \(\alpha=\frac{1}{2}\), la première opération donne :
\[M^{\prime}=\begin{pmatrix} \frac{4}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{3} & 0 & \frac{2}{3} \rule[0pt]{0pt}{15pt}\\ \frac{1}{6} & \frac{2}{3} & \frac{1}{6} \rule[0pt]{0pt}{15pt} \end{pmatrix}\] et la deuxième donne : \[M^{\prime}= \begin{pmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{6} & \frac{1}{6} & \frac{2}{3} \rule[0pt]{0pt}{15pt}\\ \frac{1}{12} & \frac{2}{3} & \frac{1}{4} \rule[0pt]{0pt}{15pt} \end{pmatrix}\]
Dans les deux cas on obtient ainsi à partir de \(M \in \mathcal{S} \mathcal{T}_r, \ M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\), une matrice que l’on notera dans la suite \(M^{\prime}=(m_{i, j}^{\prime})_{1 \leqslant i, j \leqslant r}\) qui appartient à \(\mathcal{S \mathcal { T } }_ { r }\).
On remarquera que l’on ne modifie ainsi tout au plus, pour ce qui est des éléments non diagonaux de \(M\), que ceux de la ligne \(k\), pour la première opération, et ceux de la colonne \(k\) pour la deuxième.
Écrire une fonction Python
opLigne(M,k,alph) qui réalise l’opération élémentaire sur
la \(k\)-ième ligne de \(M\) représentée par la matrice
numpy M et \(\alpha\) représenté par
alph.
On définit de même une fonction Python opCol(M,k,alph)
qui réalise l’opération élémentaire sur la \(k\)-ième colonne et la diagonale de \(M\) (cette fonction n’est pas
demandée).
Soit \(M \in S \mathcal{T}_r, M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\).
Montrer que \(M\) vérifie la propriété \((K)\) si et seulement si \(M^{\prime}\) aussi.
Montrer que pour tout \((i, j) \in \left[\!\left[1, r\right]\!\right]^2\), si \(m_{i, j}>0\) alors \(m_{i, j}^{\prime}>0\).
Établir que si \(M\) est ergodique \(M^{\prime}\) l’est aussi.
Soit \(I\) un sous-ensemble non vide de \(\left[\!\left[1, r\right]\!\right]\) et \(M \in \mathcal{S} \mathcal{T}_r, M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\).
On définit le graphe non orienté \(G_M(I)\) dont l’ensemble des sommets est \(I\) et tel que \(\{i, j\}\) est une arête si \(i \neq j, m_{i, j} \neq 0\) et \(m_{j, i}=m_{i, j}\).
Donc si \(I\) est réduit à un seul élément le graphe ne comporte pas d’arête.
Par exemple si \(M=\begin{pmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{2}{3} \rule[0pt]{0pt}{15pt}\\ \frac{1}{6} & \frac{2}{3} & \frac{1}{6} \rule[0pt]{0pt}{15pt} \end{pmatrix}\), avec \(I=\{1,2,3\}\) les arêtes sont \(\{1,2\}\) et \(\{2,3\}\), et avec \(I=\{1,3\}\) il n’y a aucune arête.
On suppose que \(I\) est tel que \(G_M(I)\) est connexe et qu’il existe \(\ell \in I\) et \(k \notin I\) tels que \(m_{\ell, k}\) et \(m_{k, \ell}\) sont non nuls.
Si \(m_{\ell, k} \leqslant m_{k, \ell,}\) on pose \(\displaystyle \alpha=\frac{m_{\ell, k}}{m_{k, \ell}}\) et on fait l’opération élémentaire sur la ligne \(k\) avec ce coefficient, sinon on pose \(\displaystyle \alpha=\frac{m_{k, \ell}}{m_{\ell, k}}\) et on fait l’opération élémentaire sur la colonne \(k\) avec ce coefficient.
On note encore \(M^{\prime}\) la matrice obtenue. Montrer que \(\{k, \ell\}\) est une arête de \(G_{M'}(I \cup\{k\})\) et que ce graphe est connexe.
On suppose que \(M \in \mathcal{S} \mathcal{T}_r, \ M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) est ergodique dans la suite de cette partie.
On suppose dans cette question que \(M\) vérifie \((K)\).
En utilisant le résultat de la question 8, établir que si \(I\) est un sous-ensemble non vide de \(\left[\!\left[1, r\right]\!\right]\), différent de \(\left[\!\left[1, r\right]\!\right]\), il existe \(\ell \in I\) et \(k \notin I\) tels que \(m_{\ell, k}\) et \(m_{k, \ell}\) sont non nuls.
On pose \(I=\{1\}\). Le graphe \(G_M(I)\) est alors connexe. En déduire un algorithme, composé de \(r-1\) opérations élémentaires à partir de \(M\) et \(I=\{1\}\), qui la transforme en une matrice \(M^*\) ergodique, vérifiant \((K)\) et telle que \(G_{M^*}(\left[\!\left[1, r\right]\!\right])\) est connexe. En déduire que \(M^*\) est symétrique.
Réciproquement, on suppose qu’à partir de \(M \in S \mathcal{T}_r\), une suite d’opérations élémentaires la transforme en une matrice symétrique \(M^*\). Montrer que \(M\) vérifie la propriété \((K)\).
On veut implémenter l’algorithme de la question 19.b) en
Python.
Écrire une fonction Python
NonNuI (M, I, J) qui, étant donnés une matrice \(M= (m_{i, j})_{1 \leqslant i, j \leqslant
r}\) représentée par la matrice numpy M
et deux ensembles non vides d’indices \(I\) et \(J\), représentés par les listes
I et J, renvoie un couple \((i, j)\) tel que \(i \in I\), \(j
\in J\) et \(m_{i, j} \neq 0\),
c’est à dire M[i-1,j-1] est non nul, s’il existe un tel
couple et le couple \((0,0)\)
sinon.
Compléter la fonction suivante pour qu’elle réalise
l’implémentation de l’algorithme de la question 19.b) et renvoie
True si \(M\) ergodique
vérifie \((K)\) et False
sinon.
def estRev(M):
r=np.shape (M) [0]
I=[1]; J=[k for k in range (2,r+1)]
while len(I)< ... :
ell, k=NonNul(M,I,J)
if (ell==0) or M[k-1][ell-1]*M[ell-1][k-1]==0:
return ...
else:
if M[ell-1][k-1]<=M[k-1][ell-1]:
OpLigne(M,k,M[ell-1][k-1]/M[k-1][ell-1])
else:
OpCol(M,k,M[k-1][ell-1]/M[ell-1][k-1])
I. append (...)
J.remove (...)
return (np.transpose(M)===M).all()
# Teste l'égalité de deux matrices numpyToutes les fonctions et instructions présentées ne sont pas utiles et il est possible d’utiliser d’autres fonctions ou instructions absentes de cet aide-mémoire.
Listes
[] | Créer une liste vide |
|---|---|
[a]*n ou n*[a] | Créer une liste avec $n$ fois l'élément a |
L.append(a) | Ajoute l'élément a à la fin de la liste L |
L1 + L2 | Concatène les deux listes L1 et L2 |
len(L) | Renvoie le nombre d'éléments de la liste L |
L.count(a) | Renvoie le nombre d'occurences de a dans la liste L |
L.remove(a) | Enlève la première occurence de la valeur a de la liste L |
a in L | Vaut True si a se trouve au moins une fois dans L et False sinon |
Module mathématique numpy
import numpy as np
np.array(L) | Transforme la liste L en vecteur ou matrice numpy |
|---|---|
np.transpose(M) | Renvoie la transposée de $M$ |
np.shape(M) | Renvoie dans un couple le format de la matrice $M$ |
Sous module random de numpy
pour la simulation probabiliste
import numpy.random as rd
rd.randint(a,b,[r,s]) | Simule une réalisation d'une matrice $(r, s)$ dont les coefficients |
|---|---|
| sont des variables aléatoires indépendantes qui suivent la loi | |
| uniforme discrète $\mathcal{U}([a, b-1])$ |
Si le paramètre [r,s] est remplacé par r,
cette fonction renvoie la réalisation d’un vecteur de longueur
r correspondant à la loi en question, et si ce paramètre
est omis, elles renvoient un seul coefficient suivant les mêmes
contraintes.
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
Cette année, l'ESSEC et HEC proposent aux candidats de l'option maths appliquées un très joli sujet mais... il faut avoir le coeur bien accroché !
Beaucoup de notations à assimiler et un grand nombre de questions difficiles à justifier en étant rigoureux.
Bon courage !