Chaîne stochastique à mémoire de longueur variable

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

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

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[1]. 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 »[2] et « modèles générés par des arbres de contexte »[6].

• Chaîne de Markov