Cadenas estocásticas con memoria de longitud variable

Consideremos un sistema formado por una lámpara, un observador y una puerta entre ambos. La lámpara tiene dos estados posibles : encendida (1) o apagada (0). Cuando la lámpara está encendida, el observador puede ver la luz a través de la puerta, dependiendo del estado en que se encuentre esta en ese momento: abierta (1) o cerrada (0). Estos estados son independientes del estado inicial de la lámpara.

Dejar${\displaystyle (X_{n})_{n\geq 0}}$una cadena de Markov que representa el estado de la lámpara, con valores en${\displaystyle A={0,1}}$y dejar${\displaystyle p}$Sea una matriz de transición de probabilidad . Además, sea${\displaystyle (\xi _{n})_{n\geq 0}}$sea ​​una secuencia de variables aleatorias independientes que represente los estados de la puerta, tomando también valores en${\displaystyle A}$, independientemente de la cadena${\displaystyle (X_{n})_{n\geq 0}}$y tal que

${\displaystyle \mathbb {P} (\xi _{n}=1)=1-\varepsilon }$

dónde${\displaystyle 0<\epsilon <1}$Definir una nueva secuencia${\displaystyle (Z_{n})_{n\geq 0}}$de tal manera que

${\ Displaystyle Z_ {n} = X_ {n} \ xi _ {n}}$por cada${\displaystyle (Z_{n})_{n\geq 0}.}$

Para determinar el último instante en que el observador pudo ver la lámpara encendida, es decir, para identificar el instante más corto.${\displaystyle k}$, con${\displaystyle k<n}$en el cual${\displaystyle Z_{k}=1}$.

Mediante un árbol de contexto es posible representar los estados pasados ​​de la secuencia, mostrando cuáles son relevantes para identificar el siguiente estado.

La cadena estocástica${\displaystyle (Z_{n})_{n\in \mathbb {Z} }}$es, entonces, una cadena con memoria de longitud variable, que toma valores en${\displaystyle A}$y compatible con el árbol de contexto probabilístico${\displaystyle (\tau ,p)}$, dónde

${\displaystyle \tau =\{1,10,100,\cdots \}\cup \{0^{\infty }\}.}$

En el artículo Un sistema universal de compresión de datos , ^{[ 1 ]} Rissanen introdujo un algoritmo consistente para estimar el árbol de contexto probabilístico que genera los datos. La función de este algoritmo se puede resumir en dos pasos:

1. Dado el ejemplo producido por una cadena con memoria de longitud variable, comenzamos con el árbol máximo cuyas ramas son todos los candidatos a contextos para el ejemplo;
2. Las ramas de este árbol se cortan hasta obtener el árbol más pequeño que se adapte bien a los datos. La decisión de acortar o no el contexto se toma mediante una función de ganancia determinada, como la razón de la verosimilitud logarítmica.

Ser${\displaystyle X_{0},\ldots ,X_{n-1}}$una muestra de un árbol probabilístico finito${\displaystyle (\tau ,p)}$. Para cualquier secuencia${\displaystyle x_{-j}^{-1}}$con${\displaystyle j\leq n}$, es posible denotar por${\displaystyle N_{n}(x_{-j}^{-1})}$el número de ocurrencias de la secuencia en la muestra, es decir,

${\displaystyle N_{n}(x_{-j}^{-1})=\sum _{t=0}^{nj}\mathbf {1} \left\{X_{t}^{t+j-1}=x_{-j}^{-1}\right\}}$

Rissanen construyó primero un candidato a máximo de contexto, dado por${\displaystyle X_{nK(n)}^{n-1}}$, dónde${\displaystyle K(n)=C\log {n}}$y${\displaystyle C}$es una constante positiva arbitraria. La razón intuitiva para la elección de${\displaystyle C\log {n}}$proviene de la imposibilidad de estimar las probabilidades de secuencias con longitudes mayores que${\displaystyle \log {n}}$basado en una muestra de tamaño${\displaystyle n}$.

A partir de ahí, Rissanen reduce el candidato máximo mediante el corte sucesivo de las ramas según una secuencia de pruebas basadas en la razón de verosimilitud estadística. En una definición más formal, si bANnxk1b0 define el estimador de probabilidad de la probabilidad de transición${\displaystyle p}$por

${\displaystyle {\hat {p}}_{n}(a\mid x_{-k}^{-1})={\frac {N_{n}(x_{-k}^{-1}a)}{\sum _{b\in A}N_{n}(x_{-k}^{-1}b)}}}$

dónde${\displaystyle x_{-j}^{-1}a=(x_{-j},\ldots ,x_{-1},a)}$. Si${\displaystyle \sum _{b\in A}N_{n}(x_{-k}^{-1}b)\,=\,0}$, definir${\displaystyle {\hat {p}}_{n}(a\mid x_{-k}^{-1})\,=\,1/|A|}$.

A${\displaystyle i\geq 1}$, definir

${\displaystyle \Lambda _{n}(x_{-i}^{-1})\,=\,2\,\sum _{y\in A}\sum _{a\in A}N_{n}(yx_{-i}^{-1}a)\log \left[{\frac {{\hat {p}}_{n}(a\mid x_{-i}^{-1}y)}{{\hat {p}}_{n}(a\mid x_{-i}^{-1})}}\right]\,}$

dónde${\displaystyle yx_{-i}^{-1}=(y,x_{-i},\ldots ,x_{-1})}$y

${\displaystyle {\hat {p}}_{n}(a\mid x_{-i}^{-1}y)={\frac {N_{n}(yx_{-i}^{-1}a)}{\sum _{b\in A}N_{n}(yx_{-i}^{-1}b)}}.}$

Tenga en cuenta que${\displaystyle \Lambda _{n}(x_{-i}^{-1})}$es la razón de la log-verosimilitud para probar la consistencia de la muestra con el árbol de contexto probabilístico${\displaystyle (\tau ,p)}$frente a la alternativa que es consistente con${\displaystyle (\tau ',p')}$, dónde${\displaystyle \tau }$y${\displaystyle \tau '}$Se diferencian únicamente por un conjunto de nudos hermanos.

La longitud del contexto estimado actual se define por

${\displaystyle {\hat {\ell }}_{n}(X_{0}^{n-1})=\max \left\{i=1,\ldots ,K(n):\Lambda _{n}(X_{ni}^{n-1})\,>\,C\log n\right\}\,}$

dónde${\displaystyle C}$es cualquier constante positiva. Finalmente, según Rissanen, ^{[ 1 ]} se obtiene el siguiente resultado. Dado${\displaystyle X_{0},\ldots ,X_{n-1}}$de un árbol de contexto probabilístico finito${\displaystyle (\tau ,p)}$, entonces

${\displaystyle P\left({\hat {\ell }}_{n}(X_{0}^{n-1})\neq \ell (X_{0}^{n-1})\right)\longrightarrow 0,}$

cuando${\displaystyle n\rightarrow \infty }$.

El estimador del árbol de contexto mediante BIC con una constante de penalización${\displaystyle c>0}$se define como

${\displaystyle {\hat {\tau }}_{\mathrm {BIC} }={\underset {\tau \in {\mathcal {T}}_{n}}{\arg \max }}\{\log L_{\tau }(X_{1}^{n})-c\,{\textrm {d}}f(\tau )\log n\}}$

El criterio del maximizador más pequeño ^{[ 3 ]} se calcula seleccionando el árbol más pequeño τ de un conjunto de árboles campeones C tal que

${\displaystyle \lim _{n\to \infty }{\frac {\log L_{\tau }(X_{1}^{n})-\log L_{\hat {\tau }}(X_{1}^{n})}{n}}=0}$