Constante de Kemeny
# 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 de façon aléatoire selon la 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.

## 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 $T_{j}^{+}$ le temps d'atteinte de l'état $j$, défini ici par $T_{j}^{+}=\min \left\{t\geq 1\mid X_{t}=j\right\}$, où $X_{t}$ est l'état de la chaîne au temps $t$. On note $\mathbb {E} _{i}\left[T_{j}^{+}\right]$ l'espérance de cette variable aléatoire sachant que $X_{0}=i$, i.e. le temps moyen qu'il faut pour atteindre l'état $j$ en partant de l'état $i$ si $i\neq j$, et le temps de retour à l'état $i$ si $i=j$. Alors la constante de Kemeny est donnée par

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

où ${\boldsymbol {\pi }}$ est la probabilité stationnaire de la chaîne.

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

    $\forall i,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 le premier cas, 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 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 $K'=\mathrm {Tr} (\mathbf {Z} )$, où $\mathbf {Z} =(I-P+\Pi )^{-1}-\Pi$ ($P$ étant la matrice de transition et $\Pi$ la matrice dont les lignes sont ${\boldsymbol {\pi }}$).

## 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.

