« Constante de Kemeny » : différence entre les versions

Navigation interactive dans l’historique

Contenu supprimé Contenu ajouté

Intégrés

Dernière version du 1 février 2024 à 12:33

En probabilités, la constante de Kemeny d'une chaîne de Markov ergodique est l'espérance du temps d'atteinte d'un état choisi aléatoirement selon la probabilité stationnaire de cette chaîne. Ce qu'il y a de remarquable à propos de cette espérance est qu'elle ne dépend pas de l'état initial de la chaîne — d'où le nom de constante de Kemeny : il s'agit d'une quantité qui ne dépend que de la chaîne étudiée.

Définition formelle[modifier | modifier le code]

La définition suivante est conforme à la formulation originelle, mais comme détaillé plus bas il est possible d'adopter une autre convention. Soit $\textstyle T_{j}^{+}$ le temps d'atteinte de l'état $j$ , défini ici par $\textstyle T_{j}^{+}=\min\{t\geq 1\mid X_{t}=j\}$ , où $\textstyle X_{t}$ est l'état de la chaîne au temps $t$ . On note $\textstyle \mathbb {E} _{i}[T_{j}^{+}]$ l'espérance de cette variable aléatoire sachant que $\textstyle X_{0}=i$ , i.e. le temps moyen qu'il faut pour atteindre l'état $j$ en partant de l'état $i$ (qu'on prend égal au temps de retour en $i$ lorsque $i = j$ . La constante de Kemeny est donnée par

K=\sum _{j}\mathbb {E} _{i}\left[T_{j}^{+}\right]\pi _{j}

,

où ${\boldsymbol {\pi }}$ est la probabilité stationnaire de la chaîne. Comme expliqué plus haut, cette quantité ne dépend pas de $i$ .

Remarque : Il aurait également été possible d'adopter la définition suivante :

K'=\sum _{j}\mathbb {E} _{i}\left[T_{j}\right]\pi _{j}

,

où $T_{j}=\min \left\{t\geq 0\mid X_{t}=j\right\}$ . On a alors $K=K'+1$ . En effet, le seul terme différant dans les deux sommes précédentes est le terme pour $j = i$ . Dans avec la première définition, ce terme est égal au produit du temps de retour à l'état $i$ ( $1/\pi _{i}$ ) par la probabilité stationnaire de se trouver dans cet état ( $\pi _{i}$ ), soit 1; tandis qu'avec la deuxième il est égal à 0. La deuxième définition présente l'avantage de permettre d'exprimer la constante comme $K'=\mathrm {Tr} (\mathbf {Z} )$ , où $\mathbf {Z} =(I-P+\Pi )^{-1}-\Pi$ , où $P$ est la matrice de transition et $\Pi$ la matrice dont les lignes sont ${\boldsymbol {\pi }}$ .^{[réf. nécessaire]}

Anecdote historique[modifier | modifier le code]

Ce résultat est contre intuitif, si bien que lorsqu'il a été énoncé par John Kemeny en 1960, un prix a été promis à quiconque pourrait en donner une explication intuitive^[1].

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kemeny's constant » (voir la liste des auteurs).

↑ (en) John Kemeny et J. Laurie Snell, Finite Markov Chains, Princeton, NJ, D. Van Nostrand, 1960 (DOI 10.1007/s10915-010-9382-1) (Corollary 4.3.6)

Portail des probabilités et de la statistique

[kemeny-1] (en) John Kemeny et J. Laurie Snell, Finite Markov Chains, Princeton, NJ, D. Van Nostrand, 1960 (DOI 10.1007/s10915-010-9382-1) (Corollary 4.3.6)

[1]

@@ Ligne 1 : / Ligne 1 : @@
-En [[probabilités]], la '''constante de Kemeny''' d'une [[chaîne de Markov]] ergodique est l'[[espérance mathématique |espérance]] du temps d'atteinte d'un état choisi de façon aléatoire selon la [[Probabilité stationnaire d'une chaîne de Markov | probabilité stationnaire]] de la chaîne (c'est-à-dire avec une probabilité égale à la fraction du temps passé dans cet état). Ce qu'il y a de remarquable à propos de cette quantité est qu'elle ne dépend pas de l'état dont on part pour atteindre l'état choisi aléatoirement -- d'où le nom de ''constante'' de Kemeny. Il s'agit donc d'une quantité propre à la chaîne étudiée.
+En [[probabilités]], la '''constante de Kemeny''' d'une [[chaîne de Markov]] ergodique est l'[[espérance mathématique |espérance]] du temps d'atteinte d'un état choisi aléatoirement selon la [[Probabilité stationnaire d'une chaîne de Markov | probabilité stationnaire]] de cette chaîne. Ce qu'il y a de remarquable à propos de cette espérance est qu'elle ne dépend pas de l'état initial de la chaîne — d'où le nom de ''constante'' de Kemeny : il s'agit d'une quantité qui ne dépend que de la chaîne étudiée.
 == Définition formelle ==
-La définition suivante est conforme à la formulation originelle, mais comme nous le verrons il est possible d'adopter une autre convention. Soit <math>T^+_j</math> le temps d'atteinte de l'état <math>j</math>, défini ici par <math>T^+_j = \min \left\{ t \geq 1 \mid X_t = j \right\}</math>, où <math>X_t</math> est l'état de la chaîne au temps <math>t</math>. On note <math>\mathbb{E}_i \left[ T^+_j\right]</math> l'espérance de cette variable aléatoire sachant que <math>X_0 = i</math>, i.e. le temps moyen qu'il faut pour atteindre l'état <math>j</math> en partant de l'état <math>i</math> si <math>i \neq j</math>, et le temps de retour à l'état <math>i</math> si <math>i = j</math>. Alors la constante de Kemeny est donnée par
+La définition suivante est conforme à la formulation originelle, mais comme détaillé plus bas il est possible d'adopter une autre convention. Soit <math>\textstyle T^+_j</math> le temps d'atteinte de l'état {{mvar|j}}, défini ici par <math>\textstyle T^+_j = \min \{t \geq 1 \mid X_t = j\}</math>, où <math>\textstyle X_t</math> est l'état de la chaîne au temps {{mvar|t}}. On note <math>\textstyle \mathbb{E}_i [ T^+_j ]</math> l'espérance de cette variable aléatoire sachant que <math>\textstyle X_0 = i</math>, i.e. le temps moyen qu'il faut pour atteindre l'état {{mvar|j}} en partant de l'état {{mvar|i}} (qu'on prend égal au temps de retour en {{mvar|i}} lorsque {{math|''i'' {{=}} ''j''}}. La constante de Kemeny est donnée par
-:<math>\forall{i}, K = \sum_j \mathbb{E}_{i} \left[ T^+_j \right] \pi_j</math>,
+:<math>K = \sum_j \mathbb{E}_{i} \left[ T^+_j \right] \pi_j</math>,
-où <math>\boldsymbol \pi</math> est la probabilité stationnaire de la chaîne.
+où <math>\boldsymbol \pi</math> est la probabilité stationnaire de la chaîne. Comme expliqué plus haut, cette quantité ne dépend pas de {{mvar|i}}.
 '''Remarque :''' Il aurait également été possible d'adopter la définition suivante :
-:<math>\forall i, K' = \sum_j \mathbb{E}_{i} \left[ T_j \right] \pi_j</math>,
+:<math>K' = \sum_j \mathbb{E}_{i} \left[ T_j \right] \pi_j</math>,
-où <math>T_j = \min \left\{ t \geq 0 \mid X_t = j \right\}</math>. On a alors <math>K = K' + 1</math>. En effet, le seul terme différant dans les deux sommes précédentes est le terme pour <math>j = i</math>. Dans le premier cas, ce terme est égal au produit du temps de retour à l'état <math>i</math> (<math>1 / \pi_i</math>) par la probabilité stationnaire de se trouver dans cet état (<math>\pi_i</math>), soit 1, tandis que dans le deuxième cas il est égal à 0. Notons que le deuxième cas présente l'avantage de permettre d'exprimer la constante comme <math>K' = \mathrm{Tr}(\mathbf{Z})</math>, où <math>\mathbf{Z} = (I - P + \Pi)^{-1} - \Pi</math> (<math>P</math> étant la matrice de transition et <math>\Pi</math> la matrice dont les lignes sont <math>\boldsymbol \pi</math>).{{Référence nécessaire}}
+où <math>T_j = \min \left\{ t \geq 0 \mid X_t = j \right\}</math>. On a alors <math>K = K' + 1</math>. En effet, le seul terme différant dans les deux sommes précédentes est le terme pour {{math|''j'' {{=}} ''i''}}. Dans avec la première définition, ce terme est égal au produit du temps de retour à l'état {{math|i}} (<math>1 / \pi_i</math>) par la probabilité stationnaire de se trouver dans cet état (<math>\pi_i</math>), soit 1; tandis qu'avec la deuxième il est égal à 0. La deuxième définition présente l'avantage de permettre d'exprimer la constante comme <math>K' = \mathrm{Tr}(\mathbf{Z})</math>, où <math>\mathbf{Z} = (I - P + \Pi)^{-1} - \Pi</math>, où <math>P</math> est la matrice de transition et <math>\Pi</math> la matrice dont les lignes sont <math>\boldsymbol \pi</math>.{{Référence nécessaire}}
 == Anecdote historique ==