38
2 Marches aléatoires
on coupe le paquet en deux et on fusionne les deux sous-paquets en intercalant
leurs cartes. La convergence abrupte dans les battages de cartes fait partie plus
généralement du thème de la convergence à l’équilibre des chaînes de Markov,
très étudié par Persi Diaconis et ses collaborateurs, et brillamment présenté
dans les livres de David Aldous et James Fill [AF01] et de David Levin, Yuval
Peres, et Elizabeth Wilmer [LPW09].
Le collectionneur de coupons intervient également dans l’analyse de la
marche aléatoire sur l’hypercube (section 9.1) qui constitue un exemple remarquable de marche aléatoire sur un graphe régulier. Il est également possible
de définir des marches aléatoires sur des graphes orientés ou non plus généraux, en considérant, pour chaque sommet, une loi sur ses voisins. Ces marches
constituent des chaînes de Markov. Réciproquement, toute chaîne de Markov
d’espace d’états au plus dénombrable peut être vue comme une marche aléatoire sur son graphe squelette. L’algorithme PageRank de Google est basé sur
une marche aléatoire sur le graphe orienté des pages web. Un autre exemple
classique est celui de la marche aléatoire sur le graphe de Cayley d’un groupe
finiment engendré. On peut enfin définir une marche aléatoire sur un groupe
en utilisant des «incréments» i.i.d.
2 Marches aléatoires
on coupe le paquet en deux et on fusionne les deux sous-paquets en intercalant
leurs cartes. La convergence abrupte dans les battages de cartes fait partie plus
généralement du thème de la convergence à l’équilibre des chaînes de Markov,
très étudié par Persi Diaconis et ses collaborateurs, et brillamment présenté
dans les livres de David Aldous et James Fill [AF01] et de David Levin, Yuval
Peres, et Elizabeth Wilmer [LPW09].
Le collectionneur de coupons intervient également dans l’analyse de la
marche aléatoire sur l’hypercube (section 9.1) qui constitue un exemple remarquable de marche aléatoire sur un graphe régulier. Il est également possible
de définir des marches aléatoires sur des graphes orientés ou non plus généraux, en considérant, pour chaque sommet, une loi sur ses voisins. Ces marches
constituent des chaînes de Markov. Réciproquement, toute chaîne de Markov
d’espace d’états au plus dénombrable peut être vue comme une marche aléatoire sur son graphe squelette. L’algorithme PageRank de Google est basé sur
une marche aléatoire sur le graphe orienté des pages web. Un autre exemple
classique est celui de la marche aléatoire sur le graphe de Cayley d’un groupe
finiment engendré. On peut enfin définir une marche aléatoire sur un groupe
en utilisant des «incréments» i.i.d.