Comment deviner le prochain mot d’une phrase ? Combien de fois faut-il mélanger un jeu de cartes pour qu’il soit vraiment aléatoire ? Et comment Google, notre compagnon de recherche quotidien, arrive-t-il à nous présenter la page exacte que nous cherchons, au milieu de milliards d’autres ? Croyez-le ou non, la réponse à toutes ces questions, et bien d’autres, réside dans une querelle mathématique étrange qui a éclaté en Russie il y a plus d’un siècle. C’est de là que sont nées les chaînes de Markov, un concept fondamental qui a façonné notre monde numérique.
Les racines d’une révolution : Quand la probabilité s’est mêlée de libre arbitre
En 1905, la Russie est en pleine effervescence sociale. Les groupes socialistes se soulèvent contre le Tsar, réclamant des réformes politiques. Cette division s’insinue partout, même chez les mathématiciens ! D’un côté, Pavel Nekrasov, un homme pieux et puissant, surnommé le « Tsar de la probabilité ». Il soutenait que les mathématiques pouvaient prouver le libre arbitre et la volonté divine.
De l’autre, son féroce adversaire, Andrey Markov, un athée sans patience pour le manque de rigueur. Pour lui, les maths n’avaient rien à voir avec la religion. Il critiquait ouvertement Nekrasov, rangeant ses travaux parmi les « abus des mathématiques ».
Le cœur de leur désaccord portait sur un principe établi depuis 200 ans : la loi des grands nombres. En gros, si vous lancez une pièce de monnaie un grand nombre de fois, la proportion de « face » et de « pile » se rapprochera de 50/50. Ce principe, prouvé par Bernoulli, ne s’appliquait qu’aux événements *indépendants*, où un événement n’influence pas le suivant.
Nekrasov pensait que si une série d’événements suivait cette loi, alors ces événements devaient être indépendants, et donc, le fruit du libre arbitre. On observait par exemple les statistiques sociales – mariages, taux de natalité, criminalité – qui semblaient converger vers une moyenne stable. Pour Nekrasov, cela prouvait que les décisions humaines derrière ces chiffres étaient des actes de libre arbitre.
Markov, lui, trouvait cette idée absurde. Il s’est donné pour mission de prouver que la loi des grands nombres pouvait aussi s’appliquer à des événements *dépendants*. Pour cela, il s’est tourné vers un domaine où la dépendance est évidente : le texte. La prochaine lettre que vous écrivez dépend fortement de la précédente, n’est-ce pas ?
Il a analysé les 20 000 premières lettres du poème « Eugène Onéguine » de Pouchkine. Il a montré que la probabilité d’une voyelle suivant une autre voyelle n’était pas la même que si les lettres étaient indépendantes. Les lettres étaient bel et bien dépendantes.
Markov a ensuite construit une sorte de « machine à prédire ». En modélisant les transitions entre voyelles et consonnes avec des probabilités, il a simulé une chaîne de lettres. Au début, les proportions de voyelles et consonnes variaient, mais, surprise, elles convergeaient vers les proportions initialement comptées dans le poème !
Il venait de prouver qu’un système d’événements dépendants pouvait suivre la loi des grands nombres. Le libre arbitre de Nekrasov n’était plus nécessaire pour faire des probabilités. La chaîne de Markov était née, ouvrant la voie à la modélisation de presque tout dans le monde réel, où les choses dépendent les unes des autres.
De la simulation atomique à la méthode de Monte Carlo : Les chaînes de Markov au cœur de la guerre froide
Curieusement, Markov lui-même ne s’intéressait guère aux applications pratiques de sa découverte. Il se disait préoccupé « uniquement par des questions d’analyse pure ». Pourtant, quelques décennies plus tard, sa théorie allait jouer un rôle central dans un projet des plus concrets : la conception de la bombe atomique.
Après la Seconde Guerre mondiale, Stanislaw Ulam, un mathématicien clé du projet Manhattan, s’efforce de comprendre le comportement des neutrons dans une bombe nucléaire. La quantité d’uranium-235 nécessaire pour une réaction en chaîne était une question cruciale. C’était un problème d’une complexité ahurissante : des trillions de neutrons interagissant avec leur environnement, des milliards de milliards de résultats possibles !
En 1946, Ulam, gravement malade, passe son temps à jouer au Solitaire pour se rétablir. Une question le hante : quelles sont les chances de gagner une partie de Solitaire avec un jeu parfaitement mélangé ? Résoudre cela analytiquement était impossible. Une illumination le frappe : et si, au lieu de calculs exacts, on jouait des centaines de parties pour obtenir une approximation statistique ?
De retour au travail, il propose cette idée à John von Neumann. Ce dernier saisit immédiatement la puissance de l’approche, mais souligne une différence cruciale : les jeux de Solitaire sont indépendants, mais le comportement des neutrons ne l’est pas. Un neutron se comporte en fonction de sa position, de sa vitesse, et de ce qu’il a déjà fait. Il faut modéliser une chaîne d’événements où chaque étape influence la suivante.
Il fallait une chaîne de Markov. Ils en ont créé une version simplifiée : un neutron peut se disperser, être absorbé, ou provoquer une fission en libérant d’autres neutrons. Les probabilités de transition dépendaient de multiples facteurs. Cette chaîne était ensuite exécutée sur le premier ordinateur électronique, l’ENIAC, simulant des centaines de fois le comportement des neutrons. On mesurait le « facteur de multiplication k » pour déterminer si la réaction s’éteignait, se maintenait, ou devenait explosive.
Cette nouvelle approche statistique, qui permettait d’approximer des équations différentielles insolubles, avait besoin d’un nom. L’oncle d’Ulam était un joueur invétéré, et le caractère aléatoire et les enjeux énormes de ces simulations ont rappelé à Ulam le Casino de Monte Carlo à Monaco. La méthode Monte Carlo était née, et elle allait changer le cours de l’histoire.
PageRank de Google : Un surfeur aléatoire pour dompter le web
Dans les années 90, l’internet explose, et avec lui, un nouveau problème : comment trouver quoi que ce soit dans cette mer d’informations grandissante ? Yahoo, créé par Jerry Yang et David Filo, tente d’y répondre. Mais leur technologie de recherche, basée sur la fréquence des mots-clés, était facile à manipuler. Il suffisait de répéter des mots-clés des centaines de fois, cachés en blanc sur fond blanc, pour tromper le système. Il manquait une notion de *qualité* des résultats.
Sergey Brin et Larry Page, deux étudiants de Stanford, planchent sur cette question. Ils ont une idée simple mais géniale, inspirée des bibliothèques : un livre souvent emprunté (avec beaucoup de tampons sur sa fiche) est probablement un bon livre. Sur le web, un lien vers une page peut être vu comme un « tampon », un endossement. Et plus une page reçoit de « votes » (de liens), plus elle est importante.
Ils ont modélisé le web comme une chaîne de Markov. Chaque page web est un état, et chaque lien est une transition d’un état à un autre. Imaginez un « surfeur aléatoire » se promenant sur ce web : il clique sur un lien avec une certaine probabilité, ou bien, 15 % du temps, il « saute » aléatoirement vers une autre page (le « damping factor »), histoire de ne jamais rester bloqué dans une boucle et d’explorer tout le réseau.
En suivant ce surfeur imaginaire sur des milliers d’étapes, Brin et Page ont pu déterminer le « temps » qu’il passait en moyenne sur chaque page. Plus une page était visitée par ce surfeur aléatoire, plus elle était considérée comme importante et de qualité. Et la beauté de cette approche, c’est qu’elle ne se laissait pas berner par de nombreux liens de mauvaise qualité.
C’est ainsi qu’ils ont construit un moteur de recherche bien supérieur, qu’ils ont appelé PageRank (en référence à Larry Page, mais aussi au « rang » des pages). En 1998, ils ont lancé leur nouvelle entreprise, initialement nommée BackRub (pour les backlinks), puis rebaptisée Google, un clin d’œil au nombre « googol » (10 puissance 100), pour signifier leur ambition d’indexer toutes les pages du web. Le reste, comme on dit, appartient à l’histoire.
Les Chaînes de Markov et l’IA : Des mots prédits aux grands modèles de langage
L’idée originale de Markov de prédire le texte a été reprise et étendue par Claude Shannon, le père de la théorie de l’information, dès les années 1940. Au lieu de se limiter aux voyelles et consonnes, Shannon a commencé à considérer des lettres individuelles, puis des mots entiers. Il a découvert que plus on prenait en compte de mots précédents, meilleures étaient les prédictions du mot suivant.
C’est exactement ce que font nos claviers de smartphone et les fonctionnalités d’auto-complétion de Gmail : prédire ce que vous allez taper ensuite. Ces algorithmes sont intrinsèquement basés sur les chaînes de Markov et leurs évolutions.
Aujourd’hui, les grands modèles linguistiques (LLM) qui alimentent l’IA moderne opèrent sur le même principe fondamental : prédire la prochaine « token » (qui peut être une lettre, un mot, ou même une partie de mot) dans une séquence. Cependant, ils ne traitent pas tous les tokens de la même manière. Contrairement aux simples chaînes de Markov, ils utilisent des mécanismes plus sophistiqués comme l’attention, qui leur permet de comprendre le contexte et de pondérer l’importance des mots précédents. Par exemple, dans la phrase « la structure de la cellule », le modèle peut « prêter attention » à des mots comme « sang » ou « mitochondrie » dans le contexte précédent pour savoir qu’il s’agit d’une cellule biologique, et non d’une cellule de prison.
Cependant, l’utilisation massive de ces modèles soulève de nouvelles interrogations. Si le texte généré par l’IA est ensuite utilisé comme donnée d’entraînement pour les futures IA, on risque une « dégénérescence » du contenu, qui pourrait devenir répétitif et sans originalité. De plus, les chaînes de Markov classiques peinent à modéliser des systèmes avec des boucles de rétroaction positives, comme le réchauffement climatique, où les effets s’amplifient mutuellement.
Le pouvoir de l’oubli : La propriété « sans mémoire » des chaînes de Markov
Ce qui est fascinant, c’est que toutes ces applications, des poèmes russes aux bombes atomiques et aux algorithmes de recherche, reposent sur un principe étonnant : la propriété « sans mémoire » des chaînes de Markov. Cela signifie que pour prédire le prochain état d’un système, il n’est pas nécessaire de connaître toute son histoire. Seul l’état *actuel* compte.
Que ce soit la prochaine lettre d’un texte, la trajectoire d’un neutron ou la page web sur laquelle vous allez « cliquer » ensuite, le passé lointain n’a pas d’influence directe. Cette capacité à ignorer presque tout le passé permet de simplifier énormément l’analyse de systèmes complexes et de faire des prédictions significatives. C’est un peu comme si le système « oubliait » son historique, pour ne se concentrer que sur le présent.
Cette élégance mathématique, née d’une querelle d’ego et de principes, nous a dotés d’un outil d’une puissance inouïe. Comme l’a si bien dit un article : « Résoudre un problème, c’est souvent concevoir une chaîne de Markov appropriée. »
D’ailleurs, pour revenir à notre question de départ : combien de mélanges faut-il pour un jeu de cartes ? Pour un jeu de 52 cartes et un mélange de type *riffle shuffle* (celui où l’on divise le jeu en deux et qu’on les entrelace), il faut… sept mélanges pour que chaque arrangement soit à peu près également probable, et donc, vraiment aléatoire. Pour d’autres méthodes de mélange, on parle de milliers de fois ! C’est une autre application directe de la modélisation en chaîne de Markov. Comprendre le *pourquoi* est bien plus intéressant que de simplement connaître la réponse.
Questions Fréquemment Posées
Qu’est-ce qu’une chaîne de Markov ?
Une chaîne de Markov est un modèle mathématique qui décrit une séquence d’événements possibles, où la probabilité de chaque événement futur ne dépend que de l’état actuel et non de la séquence d’événements précédents. Cette caractéristique est appelée la propriété « sans mémoire ».
Quelles sont les applications concrètes des chaînes de Markov ?
Les chaînes de Markov ont de très nombreuses applications. Elles sont utilisées dans l’algorithme PageRank de Google pour classer les pages web, dans la méthode Monte Carlo pour simuler des systèmes physiques complexes (comme le comportement des neutrons dans une bombe nucléaire), dans les systèmes de prédiction de texte (comme l’auto-complétion de votre smartphone), et elles sont les fondations de nombreux grands modèles linguistiques (LLM) en intelligence artificielle.
Les chaînes de Markov sont-elles encore pertinentes face aux IA modernes ?
Absolument ! Bien que les modèles d’IA modernes comme les LLM intègrent des mécanismes plus sophistiqués (comme l’attention) pour gérer des dépendances plus complexes et des contextes plus larges, le concept fondamental des chaînes de Markov reste une base théorique essentielle. Elles fournissent les briques élémentaires pour comprendre comment ces systèmes « prédisent » la prochaine étape dans une séquence de données.
