Constante de Kemeny

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

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

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.

Références

• (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).