La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.
Aucun document n'est autorisé. L'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée.
Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.

Dans cet énoncé

est un entier naturel,

désigne l'ensemble des entiers naturels

tels que

.
On s'intéresse dans ce problème aux chaînes de Markov homogènes à espace d'états fini

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

, sur un espace probabilisé

, vérifiant les propriétés suivantes :
(H1) Pour tout

.
(H2) Pour tout

, il existe

tel que

. On note

l'ensemble des entiers positifs

tels que

.
(H3) Pour tout

, la fonction

est constante sur son ensemble de définition

et on note

cette constante.
La matrice

s'appelle la matrice de transition de la chaine.
On rappelle que l'on a pour tout

.
On note

l'ensemble des matrices

à coefficients positifs telles que pour tout

. Donc

Partie 1 - Matrice stochastique réversible, exemples et caractérisation de Kolmogorov

On considère

une matrice ligne appartenant à

dont les coefficients sont strictement positifs et tels que

.
On dit que la matrice

est

-réversible si

appartient à

et vérifie :

Dans cette partie

appartient à

a) Montrer que si est -réversible et si pour un couple alors .
b) On suppose dans cette question que est symétrique. Déterminer telle que est -réversible.
c) On note la matrice diagonale d'ordre dont les éléments diagonaux sont . Montrer que est -réversible si et seulement si .
Montrer que si est -réversible alors .
Un premier exemple - On suppose que et que est la matrice de transition d'une chaîne de Markov.
a) Représenter le graphe probabiliste associé à cette matrice de transition.
b) Déterminer telle que soit -réversible.
Un deuxième exemple - Soit un graphe à sommets , 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 suìvante :

on choisit un sommet au hasard ce qui définit la valeur de ;
si on se trouve au sommet après déplacements, on a alors , on se déplace vers un sommet adjacent au sommet , ce qui définit . 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 sa matrice de transition .
a) Écrire une fonction Python Trajectoire( ) qui étant donnée la liste des listes d'adjacence L du graphe et un entier , simule 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 la matrice d'adjacence de le degré du sommet .
b) Montrer que pour tout .
c) En déduire pour laquelle est -réversible.
On note, pour tout les coefficients de la matrice .

S'il existe

tel que, pour tout

, on dit que

est une matrice ergodique.
On définit aussi pour tout

En particulier, pour tout

.
5. Montrer que pour tous

éléments de

tels que

On dit que vérifie la propriété si, pour tout et éléments de :

On admet qu'il suffit de vérifier (

) lorsque les

sont deux à deux distincts et

.
On établit dans la fin de cette partie que, si

est ergodique, il existe

telle que

est

-réversible si seulement si

vérifie la propriété

.
6. Si

, montrer que

vérifie

si et senlement si

Montrer que la matrice

de la question 3 vérifie

.
7. On suppose dans cette question que

est

-réversible.
a) Montrer que pour tout

éléments de

b) En déduire que

vérifie (

).
8. Soit

. Montrer par récurrence sur

que

si et seulement si il existe

appartenant à

tels que

.
9. On suppose que la matrice

vérifie (

) et est ergodique avec pour tout

, où

est un entier naturel non nul.
On veut montrer qu'alors

est

-réversible pour

à définir.
a) Montrer que, pour tout

, il existe (

) appartenant à

tels que

.
Montrer que si

, alors

Pour tout , on pose alors où sont définis comme dans la question a).
b) Établir que pour tout , puis en interprétant matriciellement les égalités précédentes que, pour tout .
c) Montrer qu'il existe tel que . En déduire que pour tout , .
d) Définir alors telle que soit -réversible.

Partie 2 - Matrice de transition réversible ergodique, convergence

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

de la chaîne de Markov

est

-réversible.
On note

la transposée de

ses coefficients.
10. On rappelle que △ désigne la matrice diagonale appartenant à

dont les éléments diagonaux sont

.
a) Déterminer une matrice diagonale

inversible telle que

.
b) En utilisant la question 1.c), en déduire que

est diagonalisable.
c) En conclure que

est diagonalisable.

On admet que si est une matrice carrée appartenant à et une matrice ligne appartenant à alors .

Montrer que . Que peut-on en déduire pour ?
Soit une valeur propre de et un vecteur propre associé.
a) Montrer que .
b) En déduire que .
c) En conclure que .
On suppose dans cette question que tous les coefficients de , donc de , sont strictement positifs. Dans cette question on détermine où désigne le sous-espace propre de associé à la valeur propre 1.
a) Soit un vecteur propre de pour la valeur propre 1 dont l'un au moins des coefficients, noté , est strictement positif.
On suppose qu'il existe tel que . Montrer que , puis que . Conclusion ?
b) En déduire que tous les vecteurs propres de 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 dont la somme des composantes est nulle?
c) Soit un vecteur propre de pour la valeur propre 1 . Montrer que . En conclure que .
d) Soit tel que . Montrer que . En raisonnant par l'absurde, montrer que -1 n'est pas une valeur propre de .

Dans la suite de cette partie on suppose que est ergodique avec pour tout , où est un entier naturel non nul .
En appliquant la question précédente à la matrice de transition qui est aussi réversible, on a :

a) Montrer que .
b) En distinguant les cas, pair et impair, montrer par l'absurde que -1 n'est pas une valeur propre de .
On note les coefficients d'une matrice diagonale semblable à , avec , pour tout et une base associée de vecteurs propres.
On note aussi pour la matrice élément de .
a) Établir que pour tout puis que .
b) Montrer qu'il existe tel que, pour tout :

c) En déduire que pour tout

.
d) Montrer que

. En conclure que

converge en loi vers une variable aléatoire

à valeurs dans

telle que,

Partie 3 - Un algorithme pour la réversibilité

On conserve les notations de la partie 1. On rappelle que cette partie est indépendante de la précédente.
Soit

. On définit deux opérations élémentaires sur les matrices

appartenant à

comme suit :

On modifie la ligne de , où , en remplaçant pour tout par et .
On modifie la colonne de , où , et sa diagonale en remplaçant pour tout par et par .
Par exemple si et , la première opération donne

è

Dans les deux cas on obtient ainsi à partir de

, une matrice que l'on notera dans la suite

qui appartient à

.
On remarquera que l'on ne modifie ainsi tout au plus, pour ce qui est des éléments non diagonaux de

, que ceux de la ligne

, pour la première opération, et ceux de la colonne

pour la deuxième.
16. Ecrire une fonction Python opLigne (

) qui réalise l'opération élémentaire sur la

-ième ligne de

représentée par la matrice numpy M et

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

-ième colonne et la diagonale de

(cette fonction n'est pas demandée).
17. Soit

.
a) Montrer que

vérifie la propriété

si et seulement si

aussi.
b) Montrer que pour tout

, si

alors

.
c) Établir que si

est ergodique

l'est aussi.

Soit un sous-ensemble non vide de et .

On définit le graphe non orienté

dont l'ensemble des sommets est

et tel que

est une arête si

.
Donc si

est réduit à un seul élément le graphe ne comporte pas d'arête.
Par exemple si

, avec

les arêtes sont

, et avec

il n'y a aucune arète.
18. On suppose que

est tel que

est connexe et qu'il existe

tels que

sont non nuls.
Si

, on pose

et on fait l'opération élémentaire sur la ligne

avec ce coefficient, sinon on pose

et on fait l'opération élémentaire sur la colonne

avec ce coefficient.
On note encore

la matrice obtenue. Montrer que

est une arête de

et que ce graphe est connexe.

On suppose que est ergodique dans la suite de cette partie.

On suppose dans cette question que vérifie ( ).
a) En utilisant le résultat de la question 8, établir que si est un sous-ensemble non vide de , différent de , il existe et tels que et sont non nuls.
b) On pose . Le graphe est alors connexe. En déduire un algorithme, composé de opérations élémentaires à partir de et , qui la transforme en une matrice ergodique, vérifiant et telle que est connexe.
En déduire que est symétrique.
Réciproquement, on suppose qu'à partir de , une suite d'opérations élémentaires la transforme en une matrice symétrique . Montrer que vérifie la propriété .
On veut implémenter l'algorithme de la question 19.b) en Python.
a) Écrire une fonction Python qui, étant donnés une matrice représentée par la matrice numpy M et deux ensembles non vides d'indices et , représentés par les listes I et J, renvoie un couple tel que , et , c'est à dire M [i-1] [j-1] est non nul, s'il existe un tel couple et le couple sinon.
b) 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 ergodique vérifie ( ) et False sinon.

def estRev(M):
    r=np.shape(M)[O]
    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 numpy

Aide-MÉmoire PYTHON

Toutes 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

Créer une liste avec

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

np. shape (M) Renvole dans un couple le format de la matrice

Sous module random de numpy pour la simulation probabiliste
import numpy.random as rd
rd.randint (

) Simule une réalisation d'une matrice (

) dont les coefficients sont des variables aléatoires indépendantes qui suivent la loi uniforme discrète

Si le paramètre [

] est remplacé par

, cette fonction renvoie la réalisation d'un vecteur de longueur

correspondant à la loi en question, et si ce paramètre est omis, elles renvoient un seul coefficient suivant les mêmes contraintes.

FIN DE L'ÉNONCÉ

Contenu du sujet

Source LaTeX du sujet • Code source complet

Aperçu du contenu :

\documentclass[10pt]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[version=4]{mhchem}
\usepackage{stmaryrd}
\usepackage{bbold}

\title{Conception : ESSEC - HEC Paris }

\author{MATH...

23701 caractères • Texte complet disponible ci-dessus

Pas de description pour le moment

Commentaires• BCE Maths appliquees HEC/ESSEC ECG 2025

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...