Considérons $n$ personnes en cercle, avec au début une personne possédant une pièce (non truquée). À tour de rôle, la personne qui a la pièce la lance au hasard (indépendamment de ce qui s'est passé avant). Si le résultat est pile, la pièce est donnée à la personne immédiatement à gauche; si le résultat est face, la pièce est donnée à la personne immédiatement à droite.
Fait: la dernière personne à recevoir la pièce suit la loi uniforme. Le nombre de fois que la pièce est lancée en tout est le cover time: c'est le temps qu'il a fallu pour que la pièce visite tout le monde.
Formellement, on considère une marche aléatoire simple $(X_k)_{k\geq 1}$ sur $\mathbb{Z}/n\mathbb{Z}$ issue de $X_1=0$. Le cover time, ou temps de recouvrement, est $\tau= \inf \{k \geq 1 : \{X_1,\ldots,X_k\}=\mathbb{Z}/n\mathbb{Z}$.
Ici il s'agit d'intéresser à l'espérance du cover time.
Dans l'exemple ci-dessus, il se calcule en écrivant $$\tau=\tau_n=\sum_{k=1}^{n-1}(\tau_{k+1}-\tau_k)+1$$ où $\tau_k$ est le premier temps tel que $|\{X_1,\ldots,X_{\tau_k}\}|=k$. Par un argument de ruine du joueur on obtient $\mathbb{E}[\tau_{k+1}-\tau_k]=k$, et donc $\mathbb{E}[\tau]$ est d'ordre $n^2$.
On se pose la question d'estimer l'espérance du cover time pour des chaînes de Markov plus générales (une des motivations sont algorithmiques).
Soit $(X_t)_{t \geq 1}$ une chaîne de Markov irréductible sur un espace d'état fini $S$. Pour $x \in S$ on note $T_x=\inf \{t \geq 0: X_{t+1}=x\}$ le premier temps d'atteinte de $x$, et $\tau$ est le premier temps tel que $ \{X_1, \ldots,X_{\tau+1}\}=S$ (cover time). On note $$t_{cov}=\max_{x \in S} \mathbb{E}_x[\tau].$$
L'idée est de comparer $t_{cov}$ avec $$t_{hit}=\max_{x \neq y \in S} \mathbb{E}_x[T_y].$$ On a clairement $t_{hit} \leq t_{cov}$. Le résultat suivant donne une inégalité dans l'autre sens:
Théorème (Matthews method) On a $$t_{cov} \leq t_{hit} \sum_{k=1}^{|S|-1} \frac{1}{k} \leq t_{hit}(1+\ln |S|)$$
Idée de la preuve. L'idée de la preuve est d'introduire une nouvel aléa indépendant en numérotant les sommets pa une permutation uniforme $(\Sigma(1),\ldots,\Sigma(n))$ où $n=|S|$. En effet, en notant $\tau_k$ le premier temps où $\Sigma(1), \ldots, \Sigma(k)$ ont été visités comme précédemment on a $$\mathbb{E}_x[\tau]=\sum_{k=1}^{n-1}\mathbb{E}_x[\tau_{k+1}-\tau_k]+\mathbb{E}_x[\tau_1].$$
D'une part $\mathbb{E}_x[\tau_1] \leq 0 \mathbb{P}(\Sigma(1)=x)+t_{hit} \mathbb{P}(\Sigma(1) \neq x) \leq t_{hit}$
D'autre part, pour majorer $\mathbb{E}_x[\tau_{k+1}-\tau_k]$, on écrit $$\mathbb{E}_x[\tau_{k+1}-\tau_k]= \mathbb{E}_x \left[ \mathbb{E}_{X_{\tau_k}}[\tau_{\Sigma(k+1)}] 1_{\Sigma(k+1) \not \in \{X_1, \ldots, X_{\tau_k}\}} \right] \leq t_{hit} \mathbb{P}(\Sigma(k+1) \not \in \{X_1, \ldots, X_{\tau_k}\})=t_{hit} \mathbb{P}(X_{\tau_{k+1}}=\Sigma(k+1)).$$ Pour calculer cette dernière quantité, l'idée est de conditionner par rapport à $(X_t)_{t \geq 0}$ et à un ensemble $S'$ de cardinal $k+1$ en remarquant que $$\mathbb{P}(X_{\tau_{k+1}}= \Sigma(k+1) \mid (X_t)_{t \geq 0}, \{\Sigma(1), \ldots, \Sigma(k+1)\}=S')= \frac{1}{k+1}.$$ En effet, sachant $ (X_t)_{t \geq 0}, \{\Sigma(1), \ldots, \Sigma(k+1)\}=S'$, $X_{\tau_{k+1}}$ est déterminé (c'est le dernier élément visité de $S'$, et $\Sigma(k+1)$ suit la loi uniforme dans $S'$. Le point clé est que ce résultat ne dépend ni de $(X_t)_{t \geq 0}$ ni de $S'$, ce qui permet de conclure. $\blacksquare$
Le "désavantage" du théorème précédent est qu'il nécessite de connaître $t_{hit}$, voir par exemple chapitre 10 dans Markov chains and mixing times (il y a au moins deux directions : via les distributions stationnaires ou dans le cadre des chaînes réversibles avec la théorie des réseaux électriques).
On va présenter maintenant une borne qui fait intervenir des quantités simples du graphe. On considère une marche aléatoires simple sur un graphe connexe non orienté $G=(V,E)$.
Théorème On a $t_{cov} \leq 2 (|V)-1)|E|$
Idée de preuve. On part de $x \in V$. Prenons un arbre couvrant quelconque de $G$, enraciné en $x$. On en fait le "tour" pour un ordre arbitrairement choisi $x=x_0 \to x_1 \to \cdots \to x_\ell =x$. Chaque arête est parcourue deux fois, de sort que $\ell=2|V|-2$. Par récurrence, on note $W_1$ le premier temps où $x_1$ est visité et $W_{k+1}$ le premier temps $>w_k$ pour lequel $X$ passe par $x_{k+1}$. On a clairement $\tau \leq w_\ell$ de sorte que $$\mathbb{E}_x[\tau] \leq \mathbb{E}_x[w_1]+ \sum_{k=1}^{\ell-1} \mathbb{E}_x[w_{k+1}-w_k]= \mathbb{E}_x[w_1]+ \sum_{k=1}^{\ell-1} \mathbb{E}_{x_k}[T_{x_{k+1}}] = \sum_{(x,y) \text{ arête de l'arbre}} (\mathbb{E}_x[T_y]+\mathbb{E}_y[T_x]).$$ Mais la quantité $\mathbb{E}_x[T_y]+\mathbb{E}_y[T_x]$ est connnue sous le nom de "commute time entre $x$ et $y$" et il n'est pas trop difficile de montrer que c'est au plus $2 |E|$, et le résultat s'ensuit.