Subdesplazamiento de tipo finito

Tipo de espacio de desplazamiento estudiado en la teoría ergódica

En matemáticas , los subdesplazamientos de tipo finito se utilizan para modelar sistemas dinámicos y, en particular, son objeto de estudio en dinámica simbólica y teoría ergódica . También describen el conjunto de todas las secuencias posibles ejecutadas por una máquina de estados finitos . Los espacios de desplazamiento más estudiados son los subdesplazamientos de tipo finito.

Ejemplos motivadores

Un desplazamiento (unilateral) de tipo finito es el conjunto de todas las secuencias, infinitas en un solo extremo, que pueden estar formadas por las letras , como . Un desplazamiento (bilateral) de tipo finito es similar, pero consta de secuencias que son infinitas en ambos extremos. ${\displaystyle A,B,C}$ ${\displaystyle AAA\cdots ,ABAB\cdots ,\dots }$

Un subdesplazamiento puede definirse mediante un grafo dirigido sobre estas letras, como el grafo . Consiste en secuencias cuyas transiciones entre letras consecutivas son solo las permitidas por el grafo. Para este ejemplo, el subdesplazamiento consta solo de tres secuencias unilaterales: . De manera similar, el subdesplazamiento bilateral descrito por este grafo consta solo de tres secuencias bilaterales. ${\displaystyle A\to B\to C\to A}$ ${\displaystyle ABCABC\cdots ,BCABCA\cdots ,CABCAB\cdots }$

Otros grafos dirigidos sobre las mismas letras producen otros subdesplazamientos. Por ejemplo, si se añade otra flecha al grafo se produce un subdesplazamiento que, en lugar de contener tres secuencias, contiene una cantidad infinita e incontable de secuencias. ${\displaystyle A\to C}$

Medidas de Markov y no Markov

La parte oculta de un modelo de Markov oculto, cuyos estados observables no son markovianos.

Dada una matriz de transición de Markov y una distribución invariante en los estados, podemos imponer una medida de probabilidad en el conjunto de subdesplazamientos. Por ejemplo, considere la cadena de Markov dada a la izquierda en los estados , con distribución invariante . Si "olvidamos" la distinción entre , proyectamos este espacio de subdesplazamientos en en otro espacio de subdesplazamientos en , y esta proyección también proyecta la medida de probabilidad hacia abajo a una medida de probabilidad en los subdesplazamientos en . ${\displaystyle A,B_{1},B_{2}}$ ${\displaystyle \pi =(2/7,4/7,1/7)}$ ${\displaystyle B_{1},B_{2}}$ ${\displaystyle A,B_{1},B_{2}}$ ${\displaystyle A,B}$ ${\displaystyle A,B}$

Lo curioso es que la medida de probabilidad de los subdesplazamientos en no se crea mediante una cadena de Markov en , ni siquiera de órdenes múltiples. Intuitivamente, esto se debe a que si uno observa una secuencia larga de , entonces estaría cada vez más seguro de que , lo que significa que la parte observable del sistema puede verse afectada por algo infinitamente en el pasado. ^{[1] [2]} ${\displaystyle A,B}$ ${\displaystyle A,B}$ ${\displaystyle B^{n}}$ ${\displaystyle Pr(A|B^{n})\to {\frac {2}{3}}}$

Por el contrario, existe un espacio de subdesplazamientos en 6 símbolos, proyectados a subdesplazamientos en 2 símbolos, de modo que cualquier medida de Markov en el subdesplazamiento más pequeño tiene una medida de preimagen que no es Markov de ningún orden (Ejemplo 2.6 ^[2] ).

Definición

Sea V un conjunto finito de n símbolos (alfabeto). Sea X el conjunto de todas ${\displaystyle V^{\mathbb {Z} }}$ las sucesiones bi-infinitas de elementos de V junto con el operador de desplazamiento T. Dotamos a V de la topología discreta y a X de la topología de producto . Un flujo simbólico o subdesplazamiento es un subconjunto T -invariante cerrado Y de X ^[3] y el lenguaje asociado L _Y es el conjunto de subsecuencias finitas de Y . ^[4]

Ahora sea A una matriz de adyacencia n × n con entradas en {0, 1}. Usando estos elementos construimos un grafo dirigido G = ( V , E ) con V el conjunto de vértices y E el conjunto de aristas que contienen la arista dirigida x → y en E si y solo si A _{x , y} = 1 . Sea Y el conjunto de todas las infinitas secuencias admisibles de aristas, donde por admisible se entiende que la secuencia es un paseo del grafo, y la secuencia puede ser infinita unilateral o bilateral. Sea T el operador de desplazamiento a la izquierda en tales secuencias; juega el papel del operador de evolución temporal del sistema dinámico. Un subdesplazamiento de tipo finito se define entonces como un par ( Y , T ) obtenido de esta manera. Si la secuencia se extiende al infinito en una sola dirección, se denomina subdesplazamiento unilateral de tipo finito, y si es bilateral , se denomina subdesplazamiento bilateral de tipo finito.

Formalmente, se pueden definir las secuencias de aristas como

${\displaystyle \Sigma _{A}^{+}=\left\{(x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {N} \right\}.}$

Este es el espacio de todas las secuencias de símbolos tales que el símbolo p puede ser seguido por el símbolo q sólo si la entrada ( p , q ) -ésima de la matriz A es 1. El espacio de todas las secuencias bi-infinitas se define análogamente:

${\displaystyle \Sigma _{A}=\left\{(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {Z} \right\}.}$

El operador de desplazamiento T asigna una secuencia en el desplazamiento de uno o dos lados a otro desplazando todos los símbolos hacia la izquierda, es decir

${\displaystyle \displaystyle (T(x))_{j}=x_{j+1}.}$

Es claro que este mapa sólo es invertible en el caso del desplazamiento bilateral.

Un subdesplazamiento de tipo finito se llama transitivo si G es fuertemente conexo : existe una sucesión de aristas desde un vértice cualquiera a otro vértice cualquiera. Son precisamente los subdesplazamientos transitivos de tipo finito los que corresponden a sistemas dinámicos con órbitas densas.

Un caso especial importante es el desplazamiento n completo : tiene un gráfico con una arista que conecta cada vértice con cada otro vértice; es decir, todas las entradas de la matriz de adyacencia son 1. El desplazamiento n completo corresponde al esquema de Bernoulli sin la medida .

Terminología

Por convención, se entiende que el término desplazamiento se refiere al desplazamiento n completo . Un subdesplazamiento es entonces cualquier subespacio del desplazamiento completo que sea invariante respecto del desplazamiento (es decir, un subespacio que sea invariante bajo la acción del operador de desplazamiento), no vacío y cerrado para la topología del producto definida a continuación. Algunos subdesplazamientos se pueden caracterizar por una matriz de transición, como se indicó anteriormente; dichos subdesplazamientos se denominan entonces subdesplazamientos de tipo finito. A menudo, los subdesplazamientos de tipo finito se denominan simplemente desplazamientos de tipo finito . Los subdesplazamientos de tipo finito también se denominan a veces desplazamientos de Markov topológicos .

Ejemplos

Muchos sistemas dinámicos caóticos son isomorfos a subdesplazamientos de tipo finito; los ejemplos incluyen sistemas con conexiones homoclínicas transversales , difeomorfismos de variedades cerradas con una entropía métrica positiva , el sistema Prouhet–Thue–Morse , el sistema Chacon (este es el primer sistema que se muestra débilmente mixto pero no fuertemente mixto ), sistemas Sturmianos y sistemas Toeplitz. ^[5]

Generalizaciones

Un sistema sófico es una imagen de un subdesplazamiento de tipo finito donde diferentes aristas del grafo de transición pueden ser mapeadas al mismo símbolo. Por ejemplo, si uno solo observa la salida de una cadena oculta de Markov, entonces la salida parece ser un sistema sófico. ^[1] Puede ser considerado como el conjunto de etiquetados de caminos a través de un autómata : un subdesplazamiento de tipo finito corresponde entonces a un autómata que es determinista . ^[6] Tales sistemas corresponden a lenguajes regulares .

Los sistemas libres de contexto se definen de forma análoga y se generan mediante gramáticas de estructura de frases .

Un sistema de renovación se define como el conjunto de todas las concatenaciones infinitas de una colección finita fija de palabras finitas.

Los subdesplazamientos de tipo finito son idénticos a los modelos de Potts unidimensionales libres (no interactuantes) ( generalizaciones de n letras de los modelos de Ising ), con ciertas configuraciones vecinas más próximas excluidas. Los modelos de Ising interactuantes se definen como subdesplazamientos junto con una función continua del espacio de configuración ^{[ cuando se define como? ]} (continua con respecto a la topología del producto, definida a continuación); la función de partición y el hamiltoniano se pueden expresar explícitamente en términos de esta función. ^{[ aclaración necesaria ]}

Los subdesplazamientos pueden cuantificarse de una determinada manera, lo que conduce a la idea de los autómatas finitos cuánticos .

Topología

Un subdesplazamiento tiene una topología natural, derivada de la topología del producto en ⁠ ⁠ ${\displaystyle V^{\mathbb {Z} },}$ donde

${\displaystyle V^{\mathbb {Z} }=\prod _{n\in \mathbb {Z} }V=\{x=(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{k}\in V\;\forall k\in \mathbb {Z} \}}$

y a V se le da la topología discreta . Una base para la topología de ⁠ ⁠ ${\displaystyle V^{\mathbb {Z} },}$ que induce la topología del subdesplazamiento, es la familia de conjuntos de cilindros

${\displaystyle C_{t}[a_{0},\ldots ,a_{s}]=\{x\in V^{\mathbb {Z} }:x_{t}=a_{0},\ldots ,x_{t+s}=a_{s}\}}$

Los conjuntos cilíndricos son conjuntos clopen en ⁠ ⁠ ${\displaystyle V^{\mathbb {Z} }.}$ Todo conjunto abierto en ⁠ ⁠ ${\displaystyle V^{\mathbb {Z} }}$ es una unión contable de conjuntos cilíndricos. Todo conjunto abierto en el subdesplazamiento es la intersección de un conjunto abierto de ⁠ ⁠ ${\displaystyle V^{\mathbb {Z} }}$ con el subdesplazamiento. Con respecto a esta topología, el desplazamiento T es un homeomorfismo ; es decir, con respecto a esta topología, es continuo con inverso continuo.

El espacio ⁠ ⁠ ${\displaystyle V^{\mathbb {Z} }}$ es homeomorfo a un conjunto de Cantor .

Métrico

Se pueden definir distintas métricas en un espacio de desplazamiento. Se puede definir una métrica en un espacio de desplazamiento considerando que dos puntos están "cerca" si tienen muchos símbolos iniciales en común; esta es la métrica p -ádica . De hecho, tanto los espacios de desplazamiento unilaterales como bilaterales son espacios métricos compactos .

Medida

Un subdesplazamiento de tipo finito puede estar dotado de cualquiera de varias medidas diferentes , lo que conduce a un sistema dinámico que preserva la medida . Un objeto de estudio común es la medida de Markov , que es una extensión de una cadena de Markov a la topología del desplazamiento.

Una cadena de Markov es un par ( P , π) que consiste en la matriz de transición , una matriz n × n P = ( p _ij ) para la cual todos los p _ij ≥ 0 y

${\displaystyle \sum _{j=1}^{n}p_{ij}=1}$

para todos los i . El vector de probabilidad estacionario π = ( π _i ) tiene todos los π _i ≥ 0 , y tiene ${\textstyle \sum \pi _{i}=1}$

${\displaystyle \sum _{i=1}^{n}\pi _{i}p_{ij}=\pi _{j}.}$

Se dice que una cadena de Markov, como se definió anteriormente, es compatible con el cambio de tipo finito si p _ij = 0 siempre que A _ij = 0. La medida de Markov de un conjunto de cilindros puede definirse entonces por

${\displaystyle \mu (C_{t}[a_{0},\ldots ,a_{s}])=\pi _{a_{0}}p_{a_{0},a_{1}}\cdots p_{a_{s-1},a_{s}}}$

La entropía de Kolmogorov-Sinai con relación a la medida de Markov es

${\displaystyle s_{\mu }=-\sum _{i=1}^{n}\pi _{i}\sum _{j=1}^{n}p_{ij}\log p_{ij}}$

Función zeta

La función zeta de Artin-Mazur se define como la serie de potencia formal

${\displaystyle \zeta (z)=\exp \left(\sum _{n=1}^{\infty }{\Bigl |}{\textrm {Fix}}(T^{n}){\Bigr |}{\frac {z^{n}}{n}}\right),}$

donde Fix( T ⁿ ) es el conjunto de puntos fijos del desplazamiento n -fold. ^[7] Tiene una fórmula de producto

${\displaystyle \zeta (z)=\prod _{\gamma }\left(1-z^{|\gamma |}\right)^{-1}\ }$

donde γ recorre las órbitas cerradas. ^[7] Para subdesplazamientos de tipo finito, la función zeta es una función racional de z : ^[8]

${\displaystyle \zeta (z)=(\det(I-zA))^{-1}\ .}$

Véase también

• Operador de transferencia
• Gráfico de De Bruijn
• Autómatas finitos cuánticos
• Axioma A

Notas

1. Medidas sofísticas: caracterizaciones de cadenas ocultas de Markov mediante álgebra lineal, lenguajes formales y dinámica simbólica - Karl Petersen, Matemáticas 210, primavera de 2006, Universidad de Carolina del Norte en Chapel Hill
2. Boyle, Mike; Petersen, Karl (13 de enero de 2010), Procesos ocultos de Markov en el contexto de la dinámica simbólica , arXiv : 0907.1858
3. Xie (1996) pág. 21
4. Xie (1996) pág. 22
5. Matthew Nicol y Karl Petersen, (2009) "Teoría ergódica: ejemplos básicos y construcciones", Enciclopedia de complejidad y ciencia de sistemas , Springer https://doi.org/10.1007/978-0-387-30440-3_177
6. Pytheas Fogg (2002) pág. 205
7. Brin y Stuck (2002) pág. 60
8. Brin y Stuck (2002) pág. 61

Referencias

• Brin, Michael; Stuck, Garrett (2002). Introducción a los sistemas dinámicos (2.ª ed.). Cambridge University Press . ISBN 0-521-80841-3.
• David Damanik, Subdesplazamientos estrictamente ergódicos y operadores asociados , (2005)
• Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Lecture Notes in Mathematics. Vol. 1794. Berlín: Springer-Verlag . ISBN. 3-540-44141-7.Zbl 1014.11015  .
• Natasha Jonoska , Subdesplazamientos de tipo finito, sistemas sóficos y gráficos , (2000).
• Michael S. Keane, Ergodic theory and subshifts of finite type (Teoría ergódica y subdesplazamientos de tipo finito ), (1991), que aparece como capítulo 2 en Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces (Teoría ergódica, dinámica simbólica y espacios hiperbólicos ), Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991). ISBN 0-19-853390-X (Proporciona una breve introducción expositiva, con ejercicios y referencias extensas). 
• Lind, Douglas; Marcus, Brian (1995). Introducción a la dinámica simbólica y la codificación. Cambridge University Press . ISBN 0-521-55124-2.Zbl 1106.37301  .
• Teschl, Gerald (2012). Ecuaciones diferenciales ordinarias y sistemas dinámicos. Providence : American Mathematical Society . ISBN 978-0-8218-8328-0.
• Xie, Huimin (1996). Complejidad gramatical y sistemas dinámicos unidimensionales . Directions in Chaos. Vol. 6. World Scientific. ISBN 9810223986.

Lectura adicional

• Williams, Susan G., ed. (2004). Dinámica simbólica y sus aplicaciones: American Mathematical Society, curso breve, 4 y 5 de enero de 2002, San Diego, California . Actas de simposios sobre matemáticas aplicadas: notas de clase del curso breve de la AMS. Vol. 60. American Mathematical Society . ISBN 0-8218-3157-7.Zbl 1052.37003  .