Le cours

Résumé en cinq points

Une chaîne de Markov se code par sa matrice de transition, et la loi à l'étape $n$ se calcule par $V_n = V_0 M^n$ avec le produit matriciel.
L'état stable s'obtient soit par itération, soit comme vecteur propre de la transposée de $M$ pour la valeur propre $1$ , après normalisation.
Sur un graphe complet, on observe numériquement la convergence de la suite des lois vers l'état stable, indépendamment de la loi initiale.
Comparer deux estimateurs se fait par simulation de nombreux échantillons, puis comparaison des histogrammes, des moyennes et des écarts-types.
L'intervalle de confiance asymptotique pour une proportion est centré sur la fréquence observée. Il est plus court que celui issu de Bienaymé-Tchebychev, mais sa garantie n'est qu'asymptotique.

Pourquoi ce chapitre

C'est le dernier chapitre d'informatique de la prépa.

On y manipule des matrices avec numpy, ce qui remobilise l'algèbre linéaire du troisième semestre.
On y simule des lois, ce qui remobilise les probabilités de première année.
On y trace des histogrammes, ce qui remobilise les statistiques.

Deux thèmes sont au programme :

les chaînes de Markov, avec le calcul des puissances de la matrice de transition, la mise en évidence d'un état stable et l'observation de la convergence ;
l'estimation, avec la comparaison de plusieurs estimateurs d'un même paramètre et la construction d'un intervalle de confiance asymptotique pour une loi de Bernoulli.

Ce chapitre remobilise l'algèbre linéaire, les probabilités et les statistiques.

Les exemples suggérés par le programme sont :

la popularité d'une page Web ;
la mobilité sociale ;
le bonus-malus en assurance.

Fin de l'aperçu gratuit

Encore 10 parties de cours et 8 corrigés.

Essayer 7 jours gratuitement Sans engagement · cours, exercices et fiches complets

Méthodes et exercices

Exercices classiques corrigés

Les exercices se suivent : garde leur ordre. Difficulté et durée indicatives.

Tous 9 Application 3 Classiques 5 Approfondissement 1

Exercice 1. Chaîne à deux états ★

Application du cours · 10 min · Niveau khôlle · État stable

Un abonné change d'opérateur d'un mois sur l'autre.

Il quitte $A$ avec probabilité $0{,}2$ et quitte $B$ avec probabilité $0{,}3$ .

Écrire $M$ , calculer l'état stable à la main, puis le vérifier en Python.

Voir l'indice

Technique résolution de $V M = V$ avec une somme égale à $1$ .

Voir le corrigé offert

$M$ a pour lignes $(0{,}8, 0{,}2)$ et $(0{,}3, 0{,}7)$ .
$V = (x, y)$ vérifie $x = 0{,}8x + 0{,}3y$ , soit $0{,}2x = 0{,}3y$ .
Avec $x + y = 1$ , on obtient $x = 0{,}6$ et $y = 0{,}4$ .
En Python, np.array([0.6, 0.4]) @ M redonne $(0{,}6, 0{,}4)$ . Tous les coefficients sont strictement positifs, donc la chaîne converge vers cet état pour toute loi initiale.

piège : Écrire $M V$ au lieu de $V M$ , ce qui revient à la convention des colonnes et donne un faux état stable.

Exercice 2. Vitesse de convergence ★★

Classiques de khôlle et concours · 20 min · Niveau khôlle · Convergence des chaînes

Pour la matrice de l'exercice 1, montrer que $V_n - V$ est multiplié par $0{,}5$ à chaque étape.

Écrire un programme qui confirme ce facteur.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 3. Fréquences sur une trajectoire ★

Application du cours · 15 min · Niveau khôlle · Simulation de trajectoires

Simuler $10\,000$ étapes de la chaîne de l'exercice 1 partant de $A$ .

Calculer la fréquence de passage en $A$ et la comparer à $0{,}6$ .

Tracer la fréquence cumulée en fonction du temps.

Voir le début du corrigé

On utilise la fonction trajectoire de la fiche, et chemin est la liste obtenue. …

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 4. Bonus-malus ★★

Classiques de khôlle et concours · 30 min · Niveau écrit Ecricome · État stable

Un assureur a trois niveaux, $0$ (bonus), $1$ (base) et $2$ (malus).

Chaque année, un assuré n'a aucun sinistre avec probabilité $0{,}9$ et descend alors d'un niveau, en restant en $0$ s'il y est déjà.

Sinon il monte d'un niveau, en restant en $2$ s'il y est déjà.

Les cotisations valent $0{,}8$ , $1$ et $1{,}25$ fois le tarif de base.

Déterminer la répartition de long terme et la cotisation moyenne.

Voir le début du corrigé

$M$ a pour lignes $(0{,}9, 0{,}1, 0)$ , $(0{,}9, 0, 0{,}1)$ et $(0, 0{,}9, 0{,}1)$ .

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 5. Une chaîne qui ne converge pas ★★★

Approfondissement · 25 min · Type oral · Convergence des chaînes

On prend $M$ de lignes $(0, 1)$ et $(1, 0)$ et $V_0 = (1, 0).$ Afficher $V_n$ pour $n$ de $0$ à $5$ .

Calculer les valeurs propres de $M$ .

Expliquer pourquoi l'état stable existe sans être limite.

Voir le début du corrigé

$V_n$ vaut $(1, 0)$ si $n$ est pair et $(0, 1)$ si $n$ est impair. …

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 6. Trois estimateurs du paramètre d'une loi uniforme ★★

Classiques de khôlle et concours · 45 min · Niveau écrit BCE, ESSEC ou HEC · Estimation ponctuelle

Soient $X_1, \ldots, X_n$ indépendantes de loi uniforme sur $[0, \theta]$ .

On pose $T_1 = 2 \bar{X}$ , $T_2 = \max X_k$ et $T_3 = \frac{n + 1}{n}\, T_2.$ Calculer biais et risques, les comparer pour $n = 30$ , et vérifier par simulation.

Voir le début du corrigé

$E(T_1) = \theta$ et $V(T_1) = 4 \times \theta^2/(12n) = \theta^2/(3n)$ , donc $r(T_1) = \theta^2/(3n)$ .

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 7. Deux intervalles pour une proportion ★★

Classiques de khôlle et concours · 30 min · Niveau écrit BCE, EDHEC ou emlyon · Intervalles de confiance

On observe la fréquence $F_n$ de succès sur $n$ épreuves de Bernoulli indépendantes.

Établir un intervalle de confiance de niveau au moins $1 - \alpha$ par Bienaymé-Tchebychev.

Comparer sa demi-largeur à celle de l'intervalle asymptotique majoré.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 8. Couverture effective pour une petite proportion ★★

Classiques de khôlle et concours · 25 min · Niveau écrit BCE, ESSEC ou HEC · Intervalles de confiance

Estimer par simulation le taux de couverture de l'intervalle asymptotique non majoré, pour $n = 30$ et $p$ variant de $0{,}02$ à $0{,}5$ .

Tracer ce taux en fonction de $p$ et commenter.

Voir le début du corrigé

On pose ps = np.linspace(0.02, 0.5, 25).

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 9. Taille d'un sondage ★

Application du cours · 15 min · Niveau khôlle · Intervalles de confiance

Quelle taille d'échantillon garantit une demi-largeur au plus $0{,}02$ au niveau $95$ pour cent, selon chacune des deux méthodes ?

Écrire une fonction Python qui renvoie cette taille.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Fiche de cours rédigée à partir du programme officiel de la voie EC, enseignement annuel d'informatique et algorithmique de seconde année, partie II « Programme du quatrième semestre », paragraphes « Chaînes de Markov » et « Estimation ponctuelle ou par intervalle de confiance ». Elle illustre en Python les deux derniers chapitres de probabilités. Le programme précise que ce thème est l'occasion de revoir la simulation des lois discrètes et la représentation de données par un graphe fini, vues en première année.

Chaînes de Markov et estimation en Python

Le cours et les corrigés complets

Résumé en cinq points

Exercices classiques corrigés

Exercice 1. Chaîne à deux états ★

Exercice 2. Vitesse de convergence ★★

Exercice 3. Fréquences sur une trajectoire ★

Exercice 4. Bonus-malus ★★

Exercice 5. Une chaîne qui ne converge pas ★★★

Exercice 6. Trois estimateurs du paramètre d'une loi uniforme ★★

Exercice 7. Deux intervalles pour une proportion ★★

Exercice 8. Couverture effective pour une petite proportion ★★

Exercice 9. Taille d'un sondage ★