{ "cells": [ { "cell_type": "markdown", "id": "10f8802e", "metadata": {}, "source": [ "$$\n", "\\def\\CC{\\bf C}\n", "\\def\\QQ{\\bf Q}\n", "\\def\\RR{\\bf R}\n", "\\def\\ZZ{\\bf Z}\n", "\\def\\NN{\\bf N}\n", "$$\n", "# La bibliothèque de Tsetlin\n", "\n", "
\n", "\n", "## Introduction\n", "\n", "Il est connu depuis quelques dizaines années que la théorie des\n", "représentations des groupes peut faciliter l'étude de systèmes dont\n", "l'évolution est aléatoire (chaînes de Markov), en les décomposant en\n", "systèmes plus simples. Plus récemment on a réalisé qu'en généralisant un\n", "peu le cadre (en remplaçant l'axiome d'inversibilité des groupes par\n", "d'autres axiomes) on pouvait expliquer le comportement particulièrement\n", "simple d'autres chaînes de Markov.\n", "\n", "Dans ce texte, nous étudions une chaîne de Markov simple, la\n", "bibliothèque de Tsetlin, afin d'illustrer ce propos. C'est l'occasion de\n", "connecter entre eux quelques points clés du programme de l'agrégation:\n", "combinatoire, algèbre linéaire, représentations, chaînes de Markov,\n", "exploration informatique, sans demander de bagage théorique lourd.\n", "\n", "## La bibliothèque de Tsetlin\n", "\n", "Considérons un rayon d'une bibliothèque contenant $n$ livres tous\n", "distincts. Lorsque l'on emprunte un livre pour le consulter, le\n", "règlement intérieur stipule que l'on doit le redéposer tout à la droite\n", "du rayon. C'est ce que l'on fait naturellement avec sa pile de chemises\n", "dans le placard: après usage et nettoyage d'une chemise, on la range en\n", "haut de la pile.\n", "\n", "Ce mode d'organisation a l'intérêt d'être d'auto-adaptatif:\n", "\n", "- Les livres les plus souvent utilisés s'accumulent en bout de rayon,\n", " et sont donc très rapidement retrouvés.\n", "- Si l'usage évolue dans le temps, le système s'adapte.\n", "\n", "De fait, ce type de stratégie est utilisé non seulement dans la vie\n", "courante, mais aussi dans des systèmes informatiques. Les questions\n", "naturelles qui se posent sont:\n", "\n", "- L'*état stationnaire*: Vers quel(s) état(s) converge le système?\n", " Cela afin, entre autres, d'évaluer le temps moyen d'accès à un\n", " livre.\n", "- La *vitesse de convergence*: à quelle vitesse le système s'adapte à\n", " un changement d'environnement.\n", "\n", "Formalisons cela un peu. La bibliothèque de Tsetlin est la chaîne de\n", "Markov discrète (temps discret, espace d'état discret) décrite par:\n", "\n", "- Un ensemble $\\Omega_n$ d'états donné par les permutations des $n$\n", " livres.\n", "- Un ensemble d'opérations $\\tau_i: \\Omega_n\\mapsto\n", " \\Omega_n$. Appliquer $\\tau_i$ à une permutation $\\sigma$ consiste à\n", " déplacer la valeur $i$ à la fin de la permutation.\n", "- Des paramètres $x_i\\geq 0$, avec $\\sum_i x_i=1$, donnant à chaque\n", " itération la probabilité d'appliquer l'opération $\\tau_i$.\n", "\n", "## Graphe et matrice de transition\n", "\n", "On peut représenter l'ensemble $\\Omega_n$ muni des opérations $\\tau_i$\n", "par un digraphe (essentiellement un automate); voici ce que l'on obtient\n", "pour $n=3$ :\n", "\n", "\n", "\n", "### Exercice: étude du graphe/automate de transition\n", "\n", "