Chaîne stochastique à mémoire de longueur variable

Une chaîne stochastique à mémoire de longueur variable fait partie d'une famille de chaînes stochastiques d'ordre fini dans un alphabet fini. L'idée est que, pour chaque passé, seul un suffixe fini du passé, appelé le contexte, est nécessaire pour être capable de prévoir le prochain symbole. Ces modèles ont été introduits dans la théorie de l'information par Jorma Rissanen, en 1983, comme un outil universel pour la compression des données. Récemment, ces chaînes ont été utilisées pour modéliser des données dans différents domaines tels que la biologie, la linguistique et la musique.

Définition

Une chaîne stochastique à mémoire de longueur variable est une chaîne stochastique $(X_{n})_{n\in Z}$, prenant des valeurs de l'alphabet fini $A$ et représentée par un arbre probabiliste de contextes $(\tau ,p)$ , tel que:

1. $\tau$ est l'ensemble de tous les contextes. Un contexte $X_{n-l},\ldots ,X_{n-1}$, étant $l$ la taille du contexte, est une portion finite du passé $X_{-\infty },\ldots ,X_{n-1}$ qui est nécessaire pour prédire le prochain symbole $X_{n}$;
2. $p$ est une famille de probabilités de transition associée à chaque contexte.

Histoire

La classe de chaînes stochastiques à mémoire de longueur variable a été introduite en 1983 par Jorma Rissanen, dans l'article A universal system for data compression system. Cette classe de chaînes stochastiques a été popularisée dans la communauté des probabilités et statistiques par P. Bühlmann et Abraham J. Wyner, en 1999, dans l'article longueur Variable Length Markov Chains. Bühlmann et Wyner ont alors appelé cet objet mathématique de « chaînes de Markov à longueur variable ». Ces chaînes sont également connues sous le nom de « modèles de Markov d'ordre variable », « arbres probabilistes de suffixes » et « modèles générés par des arbres de contexte ».

Notions liées

• Chaîne de Markov